commercial.eddie
BAN USER- 6 Answers Use of advanced data structures on a Google interview
Hi,
- commercial.eddie December 08, 2012
My friend has recently interviewed with Google. During one of the on-site interviews he was given the following question:
On a Cartesian coordinate system we draw a Bar chart. You can assume that the height of each bar is a natural value. Give an algorithm finding the rectangle of maximum area, bound by the diagram and the x axis. With n being the number of bars, you should do significantly better than O(n^2).
My friend was unable to answer this question, and after we analyzed it at home the only way we could find for meeting the time complexity requirements, is to use a k-d tree\Interval tree data structure for keeping coordinates. These are not basic data structures; They're nearly never discussed during undergraduate studies, and the careercup book doesn't cover this type of questions. Is there a trivial solution we've been missing? Or is it that if I ever interview with Google I should expected to be asked on topics I don't have a chance to be prepared for? This is not what "Cracking the coding interview" is implying.
Please share your thoughts. 10x.| Flag | PURGE