Hacker News Reader

Comment by avl999 | Hacker News Reader

I would also add heaps/priority queues to this list. They don't come up as often as HashTables/LinkedLists but come up often enough.

If you wanna be thorough (esp if you are applying at companies known for harder interviews) I would add practicing backtracking problems where you are doing a full exhaustive search of the problem space as well (often O(k^n) or O(n!) complexity). Yes these are often mostly just DFS + Recursion but they have subtlety to them that requires practice for most people. They tend to be tricky to get right in an interview setting without practice as due to the really bad time complexity of most problems of this type they almost never come up in production for most people so they're not even on the radar of most engineers.

View on HN

There's a specific reason I didn't mention priority queues in the post. In most cases, anything you can do with a heap you can do with a binary tree instead! A binary tree has O(log(n)) insert and deletion which is the same as a traditional heap. The only advantage a traditional heap has is you can construct a heap in O(n) time whereas a binary tree takes O(nlog(n)) time.

Of course there are even more niche data structures like a Fibonacci heap which have O(1) insertion, but you will have to get extremely unlucky to get asked about a Fibonacci heap in an interview.

One more thing: a heap can be easily packed contiguously in memory, while the tree nodes are typically dynamically allocated.

This helps with allocation pressure, which is often the "hidden" cost people don't pay enough attention to, especially in garbage-collected languages where the allocation might appear to be almost "free" (often a simple bump allocator), but the deallocation price is paid at later indeterminate time (when the GC runs).

But heap gives you O(1) max/min and Binary tree gives you O(log(n)) of max/min. Am I wrong?

In C++ (for example) getting the minimum and maximum is an O(1) operation [1][2]. I guess this is probably enabled through some extra bookkeeping and many other languages may do the same.

[1]: https://en.cppreference.com/w/cpp/container/set/begin

[2]: https://en.cppreference.com/w/cpp/container/set/rbegin

Wouldn't that mean you have to implement the binary tree as part of your solution?

Seems way easier/time efficient to just use the built-in heap/priority queue of the language standard lib

C++ has built in binary trees with fast iteration. The C++ binary tree is my favourite standard library data structure of any language I've used, it isn't the fastest out there but it has so many useful things you can do with it. You can use it as a heap, you can use it as a dictionary, you can use it to sort things, you can insert items at the same time you iterate through it and if they are after where you are in the tree then you will find them in your iteration etc. It does so many things right that others don't do, I'm sure the others data structures are slightly faster but the C++ binary tree is so powerful and still fast enough for basically every problem.

Oh interesting, I'll have to try that, didn't know there was a built-in one

A priority queue is the easy answer to virtually any “top k” problem so is still worth mentioning.

That's reasonable, makes a lot of sense.

Reply on news.ycombinator.com