Hacker News Reader

Comment by freshfunk | Hacker News Reader

One more thing: This is why I always find it sort of useless during tech interviews to ask someone who's been out of school for a long time the difference between a thread and a process or the difference between sorting algorithms.

It's like people couldn't think of an original question that might actually be of some use to the actual job you'd be doing.

View on HN

> ask someone who's been out of school for a long time the difference between a thread and a process

Quite the contrary: if you're in the industry, the difference between a thread a process should be very hot in your page cache. Understanding why ``system("cd ..");'' won't work is pretty vital.

As for sorting algorithm, you should at least know the big-Oh for a good sorting algorithm. In many specialties of programming, understanding what "amortized" means (e.g., in the context of quicksort's performance) is also important.

Somebody out of school may naively think that quicksort is always good as it's O(log N) or (if they never took an OS class-- and OS classes are, unfortunately, optional in some universities) not fully understand why their code is burning up 100% of a single core in a 8-core machine and leaving the other 7 idle.

On the other hand, I can agree that asking questions which are only answered from memory (i.e., either you know the trick or you don't) that will only be in a recent graduates page cache (e.g., remembering all the rules of a red black tree, or a dynamic programming solution to a classic problem) but can -- and should -- be looked up, doesn't make sense (if I see you implementing a balanced tree in a project without at least cracking CLRS open and looking at existing implementations, I'll have a chat with you...)

But "amortized" is irrelevant in the context of quicksort, as it is not an amortized algorithm. You may hit an unlucky streak and get the worst case of O(n^2) behaviour on every call. An amortized algorithm on the other had would guarantee that while each individual operation on a data structure may hit the worst case, it will always (and not just in the average case) average out over many operations on the same data structure.

Doh, screw up on my part. You are completely right. An amortized algorithm would be something like a dynamic array (std::vector or ArrayList) in this case, which is doubled every time it hits capacity.

Err, as fhars poster pointed out quicksort is not an amortized algorithm, I should have used a better example. It is, however, a good example of an algorithm with a worst case running time of N^2.

On the contrary, it's irrelevant if you're not writing a sorting algorithm or your main role doesn't consist of writing any algorithms. Most web developers I know simply call sort() in whatever language they're using instead of reinventing the wheel. Even my work in Objective-C where I handle retaining and releasing memory, I still call sort() (and compare()) without caring about algorithm efficiency.

If you're calling a sorting algorithm, you should still know about the efficiency of that sorting algorithm takes so you can make a choice between sorting an array or indexing using a data structure (which data structure).

Web is just a UI to layer software that _does something_, algorithms are a way to get that something done. Have you ever needed to understand why e.g., a SQL JOIN is taking too long? That's an example where algorithms matter (in selecting the index type, knowing whether to use a join between two tables or to denormalize etc...)

Knowing how to do your own memory management and knowing Objective C is great and valuable, but if mobile/Mac desktop application development were to become less valuable and more commodity (right now, I don't think it will happen-- but I can't predict the market), will you be able to apply these skills to (say) working on more complex C and C++ software such as a web browser?

IMO, I think you're spending more time talking about edge cases than the norm. How many people are web developers vs those developing web browsers?

Understanding query cost has more to do with data structures than algorithms. Why does the optimizer seek vs scan? What column(s) do I need to index and how should it be structured? You really don't need to understand how things get sorted in a b-tree.

Knowing normal forms is also different from algorithms. Ergo, it would be more useful to ask "When would you denormalized your data?" instead of "What's the difference between Quicksort and Bubble Sort?"

Objective-C is really just one of many languages I know and use. It just happens to be the most recent. Oddly enough I did spend some time (many years ago) implementing my own browser for a job. We used Java and, again, I never really had to know the complexities of sorting algorithms.

Reply on news.ycombinator.com