Data Structure Visualizations (2011) | Hacker News Reader

Data Structure Visualizations (2011)

cs.usfca.edu

384 pointsprabhupant33 comments

I was a bit annoyed that the visualizations require you to enter a number, then press a button, which triggers the input field to clear and disables input until the current animation is done. So if you wanna see a quick progression of building a linked list, you have to click, type, press button, repeat. It'd be neat if they queued up comma separated inputs so you could actually watch an entire sequence unfold.

maybe it's time to mark bubble-sort with a latin-cross (deprecated) too[1][2]

[1] https://users.cs.duke.edu/~ola/bubble/bubble.html

[2] also bubble sort is shapeist and efficiency-shaming :)

QuickSort with Hungarian (Küküllőmenti legényes) folk dance: https://www.youtube.com/watch?v=ywWBy6J5gz8

This is amazing

You know, in some cultures I'd assume a computer scientist paid a bunch of folk dancers, slapped numbers on them, and and taught them this pattern to have a laugh with other computer scientists.

But knowing Hungarians, I bet all these folk dancers have math/physics/compsci degrees and had to draw straws to decide whose interpretation of quicksort to choose.

I picture them all during break time playing with their rubik cubes

2013: https://news.ycombinator.com/item?id=6928904

2015: https://news.ycombinator.com/item?id=10183811

2017: https://news.ycombinator.com/item?id=14064865 https://news.ycombinator.com/item?id=15480517

Interesting site! Always cool to see these things visualised.

It reminds me of the visualisation of different sorting algorithm (with sound): https://youtu.be/kPRA0W1kECg

Some very nice ones in here: AVL and Red/Black trees, especially the rotation step. I also liked it when the code shows up on the upper left and you can see it stepping through line-by-line, such as the Fibonacci example.

The radix tree didn't seem to work for me.

Query regarding Preparing for interviews: Is it expected from me to know implementations for all of them with all the posdible operations?

In some way yes, especially when looking at comparing their time/memory complexities and weighing tradeoffs.

A good starter would be to go through the classic: Cracking The Coding Interview book as a form of guide.

Also there are a few sites out there that offer practical contextual problems to solve in preparation.

Interview questions vary and how stringent they will be with it would also vary.

All of them? No. The basic ones? Yes. You should know how to implement a stack, queue, linked list, doubly-linked list, heap, and binary tree. You should also know how to represent a tree in binary form. You should know how to balance a binary tree. You should know the time and space complexity of common operations on those structures. Do they expect you to build a skip-list from scratch on a whiteboard? Probably not, and they shouldn't. If you're very familiar with the basics, then implementing more advanced structures is a matter of doing some basic Googling.

> You should know how to implement a stack, queue, linked list, doubly-linked list, heap, and binary tree.

Not once in the last 20 years have I had to use one of those that wasn't already implemented for me. Nor, I suspect, have most people. It's like requiring a delivery driver to know the internals of engines - completely unnecessary to getting the day to day work done.

It's still useful to understand data structures and algorithms on a conceptual level. Even if all you ever do is use premade ones it's going to be nontrivial to pick the correct ones in some cases if you never thought about the costs/benefits they come with.

And I wouldn't call it premature optimization either, just picking sane defaults.

Also...and that's just a personal opinion, I think it's good practice to show an interest beyond black box use when you work with stuff. Poking around in standard libraries can be great fun :D

yes, for a driver is also useful to know how an engine works.

would you put it in an interview for uber or to get a driving license? no

plus you forget that stuff really quickly if you don't use it. I can barely remember half of those from Uni.

But if you were tasked with designing a vehicle, it would behoove you to know how the engine worked, rather than only using it as a black box.

That depends - it's entirely possible to design and build vehicles using black box engines. What you might mean is "designing an optimal vechicle"? But for most people, they're basically working on simple CRUD stuff which doesn't need to be supra-optimal etc.

(I could make all my internal code supra-optimal, write all my own data structure code, handcraft some assembly, etc. but it would be beyond pointless since 99% of the time it takes to do stuff is in the database server.)

If you didn't understand how an engine worked, you could make drastic mistakes designing the car (and not even talking about making it optimal). Imagine designing a car, but having no idea if the engine is electric or combustion. How are you going to make the rest of the car fit the nuances of the engine?!

You don't need to write the libraries yourself, but you have to know what the library does, and know the internals, and the intended uses of the library. Otherwise, you end up writing your app with an ORM and don't even understand SQL or how a database works, and disaster surely follows.

I remember in 9th grade there was one kid who complained the entire year about how he would never use algebra. He asked his dad and his dad said he had never used algebra. He must have brought this up 30 times and each time the teacher tried to give practical answers like calculating how much fertilizer or deer feed (we lived in a farming community). He was unswayed. Comically, he gave answers where algebra would be helpful if he knew, but because his dad didn’t know it was difficult (simultaneous solution for cow auction of different types of cows).

Just because you think you haven’t used or didn’t use, doesn’t mean it’s not useful. First, maybe I didn’t use because I didn’t know how to use. Second, maybe there is more to the world than me and the probability of folks needing info is 95% and I’m in the 5% of the lucky/unlucky.

I try to learn things based on curiosity and intrinsic value that I try to estimate. The act of learning is valuable as a system and I’m frequently surprised by putting unlikely topics together.

> First, maybe I didn’t use because I didn’t know how to use.

Alas, I grew up having to code my own data structures and consequently got a thorough grounding in the theoretical and infernal details therein at University.

> Second, maybe there is more to the world than me

You seem to have taken my personal anecdata as some kind of global diktat. I assure you, it most certainly was nothing more than a personal anecdata.

That's funny, I've had to implement a queue, linked list (singly and doubly), heap and binary tree, and other custom data structures that use concepts from all of these in the past month. Depends on what you're working on. If you're writing an engine of some sort, you need to know these things, and often importing third party implementations is neither desired nor worth it. If you're writing business logic, then of course, import some third party lib and do things the quick way.

I know the basic ones. I was asked to do inorder traversal with some other requirements which I think I did. I was also asked to write correct code for finding connected components on a paper which I kinda didn’t do so well. I think having a computer nearby would have helped me in the second problem but writing on paper seems to much for me.

in the past 10 years I never had to implement a linked list in any of my jobs. is this anormal?

same here, 10 years, no need to implement linked list

Like I said to the other guy, depends on what you're working on. If you're building a product for users, there's a chance you have never implemented this. If you're building a product for developers, those chances should be lower. For example, I doubt anyone writing business logic for an API thought "time to implement a linked list!" instead of just importing a built-in linked list or a third-party lib.

Someone writes those libraries. Not you, apparently.

yes, the issue is when you are asking these questions in interviews for jobs where you don't need them.

Are you sure about that?

I've seen people not realize they are implementing a linked list when they are working in a language like PHP or Python, have an array of objects, and those objects contain indexes or keys to other objects in the array.

Similarly, I've seen people not realize they have trees. For instance, suppose a program generates some kind of report. The report has multiple sections. Somewhere in there you might have a

  report = [section1, section2, ..., sectionN]

to represent the report. But section can have subsections, so that section1 could actually be

  section1 = [section1_1, section1_2, ...]

and so one with subsubsections and more.

That final 'report' variable references a tree, but a lot of people wouldn't notice because they didn't have to make a node structure with child and parent pointers and maintain those pointers manually.

A interviewer that asks you to implement a non-trivial data structure is a bad interviewer that should feel bad about himself. Unless you are going for a job on the BCL team or something.

However, you definitely should be familiar with all the basic and many of the intermediate data structures, their asymptotic behaviors (bonus points if you can say something about their cache friendliness), and where you might use them.

What's a BCL team?

Sorry, didn’t mean to be obscure. The .net standard library team. Any standard library team would qualify that’s just the first that came to mind.

Man, I'll always have a soft spot in my heart for these visualizations.

Extremely useful learning aids :)

I remember back in the day when they were Java applets :)

How well can it visualize arbitrary graphs of various types (trees, DAGs, undirected graphs, cyclic graphs, ...)?

Very cool! Always fun to watch all the different tree implimentations.

Reply on news.ycombinator.com