They asked me how to build a QuadTree. There's a similar problem on LeetCode (the original post referenced it in a garbled, obfuscated way, probably to dodge the forum's keyword filter), but the interview version wasn't limited to just 0s and 1s — the description given was pretty high-level, and I had to implement the data structure from scratch by hand.
I'd solved this problem more than once, three years ago, but I've forgotten all of it, and none of the recent interview experience posts I read covered it either. Overall it's a formulaic question — if you don't know it, you just don't know it. My guess is you're not necessarily going to be able to write it out the first time you see it, unless the interviewer understands the problem deeply enough to give good hints, or unless you vaguely remember something similar and can ask the right clarifying question — like whether the side length is a power of two, which lets you determine top-down whether a region is a leaf node and whether it can be further subdivided.
The interviewer showed up 7 minutes late. With 20 minutes left I still had no clear approach — I kept trying to figure out how to build the leaf nodes first, then build the parent nodes on top of that while simplifying, which was clearly overcomplicating the problem. So I decided to end the interview early, and we just talked about the tech stack Uber uses.
Discussion
Loading comments…