I think it depends on the interviewer intentions. If the intention is to judge whether the candidate knows such and such algorithm (aka they have used or read about it) then it is obviously stupid. On the other hand it could be about how you approach the problem, how you start with a simplest possible solution and then engage in a thought process (along with conversation about what you are thinking) to improve the solution. In this case the final solution doesn't matter, what matters is your thought process.
Ask HN: Is asking obscure algorithms any test of programming ability?
21–30 of 43 posts
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#22I think these questions usually focus on the wrong part of the equation. Is knowledge of obscure algorithms a good indicator of programming ability? Maybe, maybe not. Is the interviewer expecting you to know the Monotone Priority Queue algorithm, or are they evaluating your ability to approach and solve a problem? That's the question that matters, and there's no information about that here. "Given an array, and a sli…
> The fact that there's an obscure algorithm to optimally solve this doesn't mean it's not a good test of someone's ability to think through an algorithmic problem - as long as you don't make it an algorithm memorization test.
From my read of the description, the OP implies that the candidate provided (or at least, if OP were the candidate s/he would have provided) a O(n log n) solution using PQs. The task was to specifically to make the algorithm O(n), which required an obscure data structure discovered in the late 90s. So I think this is more of an algorithm memorization test.
There are very few practical problems where an O(n log n) solution is completely unacceptable, and an O(n) is essential. And in those situations, many engineers can do the relevant literature study and come up the MPQ solution.
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#23The test isn't about whether you know the algorithm – quite the opposite. The test is about seeing how you approach a problem you haven't (possibly) solved before.
This is what everybody who employs a vanity interview question tells themselves. You can use this logic to justify any question, and the result is an entirely subjective interview process that occasionally and randomly admits candidates based on their knowledge of trivia.
Well put! "Vanity interview question" reminds me of "vanity business metrics" in not just name but also utility.
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#24A Monotone Priority Queue is neither sufficient nor needed to solve this problem (as it does not give a linear time solution). Instead the proper solution just needs a deque, see http://techieme.in/maximum-element-sliding-window/ . So yes as you can see knowing algorithms is important, as if you don't you will attempt to use an overly complicated data structure to come up with a suboptimal solution.
The solution using double ended queue is often referred to as monotonic queue, because queue content will be monotonic sequence.
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#25The test isn't about whether you know the algorithm – quite the opposite. The test is about seeing how you approach a problem you haven't (possibly) solved before.
How do you differentiate between:
1. Someone genuinely solving the question on the fly
2. Someone who memorized the answer, and is just pretending to solve it on the fly
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#26As you probably expected from your phrasing/question, no.
Ultimately there's often some frustration from both sides when hiring. Interviewers get a ton of under-qualified candidates and need a way to weed them out. A semi-technical conversation isn't always enough (lots of practically useless programmers can repeat dogma). Stumping someone _is_ a good way to assess their technical capabilities (you get a nice mix of analytical thinking and creativity to try to come up with a working solution even if it's not perfect).
I try to tie my technical questions to previous projects/areas of interest, with increasing difficulty/complexity, but sometimes this is difficult (particularly if the potential hire doesn't have any particular specialisations). If you start too low, the interviews go too long and you don't get a good feel for what the person can actually do. If you start too high, it comes across as demanding knowledge of obscure algorithms. I know that I've unintentionally asked questions that have come across this way, but in those cases you can't really expect a full and correct answer -- all you can expect is an appreciation of the components and some thought on how the person approaches problems.
That said, if you're being hired for your specific pre-existing knowledge, that's a different matter.
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#27I was recently asked to calculate the fibonacci sequence value in an O(log n) time complexity. I had no clue how to do it and explained that I can solve it in O(N) easily but don't even know how to approach the O(log n) method. I knew there must be some trick using factors but didn't even know how to start the problem. I looked it up later and one of the ways is using matrix multiplication (an implementation I still wouldn't be able to do without seeing pseudocode).
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#28Yes, absolutely! A person who knows the answer to that question is definitely a strong developer. It does not mean someone who does not know the answer isn't as strong, but my bet would be on the one who knows it.
If I was asked the question I would probably use a set and mark the indices of the maximum elements. I think that should be O(n) but there is probably methods that are much faster.
I also really don't agree that it is the "thought process" that matters. What that means is that you should speak what your mind is thinking while you solve the problem and the interviewer should rate you based on this speech. Meaning those who like to think quietly are unfairly penalized.
Like who would really want to talk to the examiner while solving tough linear algebra problems? Math doesn't work that way and neither does programming.
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#29This seems to be a rather easy, no ? All you need to do is to keep the top-2 elements in every window (okay I guess that part can be done with queue), and update it as you move it to the right. This is trivially linear time since you only look at elements once.
Nah this is cool.
What you need to watch out for is obscure badly worded nonsense. I once had a interview where I was asked to "design a protocol". The guys asking the question were so vague that it essentially turned into a game where I was constantly throwing predicates at them to find out what they meant. In the end it turned out they wanted me to use a predefined alphabet S without an end symbol, and lift it to one with an end symbol. Obviously, the cartesian product of S does the trick. All I got out of the interviewers though was some verbose non-sense about the grand design of computing. What a waste of time that was (and what a relief to not get that job!).
Re: Ask HN: Is asking obscure algorithms any test of programming ability?
#30It's a tough reality, but yes. Memorizing trivia is a useful skill to get past first-tier tech interviews at large firms.
As a developer, you have a few options. First, you can recognize this reality and simply spend the necessary time cramming useless algorithms for a few weeks before you go off interviewing.
Or you can declare all this stupidity as beneath you, go in to your Google interview cold, and get rejected based on trivia even though you're genuinely smart and good at what you do.
Or, you can spend your first several years building impressive artifacts and creating relationships that you can leverage when the time comes to bypass the entire Tech Interview/Resume Filter/HR step of the hiring process and skip straight to the part where you're having coffee with the guy with hiring authority.
I've personally landed every gig I've had in the last 15 years using that last trick. Which is a good thing, since despite having made a lot of software companies a lot of money, I can't recite so much as Bubble Sort on demand.