4 ms·
Well, I probably used it last time 10 years ago and still remember it. All you need to remember is that you sort points by angle from a fixed point on the conv
by devit 6y ago
Well, I probably used it last time 10 years ago and still remember it.
All you need to remember is that you sort points by angle from a fixed point on the convex hull, and you can easily work out the rest of the algorithm as well as the proof of correctness.
Not knowing it is a relevant signal that you did not seriously attempt to compete in computer science competitions during high school and college and did not otherwise have a burning desire to learn algorithms and data structures nor a specific interest in computational geometry. Whether it's in Google's interest to select for that of course is debatable.
- duskwuff 6y ago> Whether it's in Google's interest to select for that of course is debatable. I'd argue it does not. Computational geometry is a niche. It's not even a niche that's particularly relevant to most of Google's development operations. In modern software development, knowing the detail of specific algorithms off the top of your head and being able to implement them unaided is, at best, a parlor trick. I doubt very much that it even correlates to one's effectiveness as a developer. Even for development tasks which involve algorithmic work -- which many don't! -- knowing that various algorithms exist, and what they're used for, is much more valuable than having memorized the details of how those algorithms are implemented.
- devit 6y agoThe idea is that you might need to invent a new algorithm where a technique from an existing algorithm is used in a modified way or in a new setting, and then knowing the actual technique can be essential to find an inspiration. E.g. if you know that convex hulls can be computed by sorting by angle and sweeping, then you might come up with the idea of sorting by angle and sweeping in problems that are unrelated to convex hulls (e.g. determining what is visible from a given point in an environment with obstacles). In general, if you know a lot of those techniques and heuristics, you will be much more effective at problem solving in domains where these techniques apply. It is relatively rare for this to be a big factor in routine software development, so that's probably something one should filter for only if interviewing for roles where you might need to design novel algorithms (which Google probably has more than the average company).
- ashconnor 6y agoYour entire premise is based upon the fact that this wouldn't be discoverable for anyone that didn't already know the algorithm.
- jkingsbery 6y agoYeah, I remembered the sort by angle part and the broad strokes after that, but there were some details I forgot so I missed some corner cases.