5 ms·
I don't know about the average but at Google I probably write a new call to std::set::find twice an hour, and it's important to know that std::set is a red-blac
by stuckagain 10y ago
I don't know about the average but at Google I probably write a new call to std::set::find twice an hour, and it's important to know that std::set is a red-black tree, and how std::set::find is implemented and how much that costs and so forth. Fluency with data structures and algorithms is not some kind of brain candy. It's absolutely necessary to get the job done.
- alistproducer2 10y agoone does not need to know how to write an algorithm on a white board to understand it. Seems like it would better to ask what a red-black tree is, what's it's time complexity, and what would be a good situation to use one. In fact, I would argue that one could know how to write one and have no idea of the practical use of it.
- stcredzero 10y agoIt pretty much has no practical use, that a different data structure couldn't do more efficiently.
- poikniok 10y agoWhat in the world are you talking about, RB trees are incredibly useful.
- stcredzero 10y agoThere's a well known analysis that shows they're asymptotically equivalent to B-trees. You can tune a B-tree to better exploit cache locality. Other kinds of ordered binary trees are far less complicated to code and have similar performance characteristics.
- metaphorm 10y agoI understand the perfomance characteristics of red/black trees very well. I couldn't implement one in 30 minutes on a whiteboard.
- devy 10y agoAfter preparing and studying the interview questions on data structure, algorithms etc. with the help of guide books like https://books.google.com/books/about/Cracking_the_Coding_Interview.html?id=anhAXwAACAAJ https://books.google.com/books/about/Cracking_the_Coding_Int... You definitely can!
- joshuamorton 10y agoNeither could I, but that was also well beyond the scope of my Google interviews.
- deleted 10y ago[deleted]
- valuearb 10y agoI've been a developer for 30 years, helped start a half dozen companies. Since college I've never written a single tree traversing algorithm, and would need to Google red-black tree to know what it is. There is a whole world of development that is OS specific, UI specific, shipping commercial applications. Shipping quickly is always a higher priority than performance, because adequate performance is usually trivial to implement with hash tables/arrays/linked lists.
- yomly 10y agoI'm not entirely sure adequate performance is good enough when you work at the scale of Google...
- maverick_iceman 10y ago>because adequate performance is usually trivial to implement with hash tables/arrays/linked lists Are you sure about that? What if your code has to work for billion plus people correctly 99.999% time who are on all different kind of connections?
- 10y ago
- kisstheblade 10y agoYes but jeesus here we are discussing an algorithm that I first heard about in literally my first CS course on algorithms in my first year at the university, some 20 years ago. And I had to manipulate red black threes on the blackboard. Haven't seen them since in my 20 years of work in the industry. I you need to write so performance critical code that the choice of tree structures matters then this interview question sure as hell isn't going to find out if you are cut out for it.
- DesiLurker 10y agoI've interviewed many candidates for one of the big 4 & sat on the decision loops too. 'Attribute substitution'[1] one thing that does stands out in these interviews. essentially interviewers substitute answering the larger question of judging the candidate's suitability for the job at hand with a simpler but easier to judge (& defend!) problem of solve this particular coding problem that I have 'normalized' over many candidates. Also, deep domain knowledge is often hard to judge. 1. https://en.wikipedia.org/wiki/Attribute_substitution https://en.wikipedia.org/wiki/Attribute_substitution
- koyote 10y agoMaybe I am missing something but if you're using set::find so often, why not an unordered_set?