Ask HN: Is asking obscure algorithms any test of programming ability?
A friend of mine is being interviewed for Big 4. In the first round of screening, (s)he was asked about a linear time algorithm to find all the maximum element in a sliding window in an array.
Now this is a simple problem for anyone who has taken any DS or Algo Undergraduate level class since it involves the important concept of the priority queue. However, it is my understanding that to do this in a linear time is neither trivial nor straightforward and unless that person is really gifted. (Its something called Monotone Priority Queue which is not present in any standard Algorithm textbook) So my question to the general populace is: Are knowing obscure algorithms like this any test of a person's programming ability ?
42 comments
[ 0.29 ms ] story [ 60.9 ms ] threadThere are rumors that unless you are spot on perfect in Big 4 interviews, they wont advance you.
It's about understanding the computer science fundamentals in order to keep your code from burning up 1000's of cores due to asymptotically-poor characteristics.
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
Problem with Big 4 is that these problems are on such scale that you cannot possibly expect anyone knowing how to solve them. In the same sense your experience is irrelevant because these companies have internal tooling and frameworks that are mostly specific to problem domain.
Algorithms questions test two things: 1. How you think under pressure. (culture fit) 2. Dedication, because you need to waste weeks on preparations (corporate slave).
Or it could be a mistake, and it was just bad luck that your friend got an interviewer who doesn't know how to interview, and asked a question that about a subject that they're intimately familiar with, but is too hard compared to what is asked by other interviewers.
I am a Phd student in Computer Graphics and so it is a reasonable expectation that I should know more about linear algebra than my peers. But if you extrapolate it to ask extremely hard research level problem it kills the purpose.
No, it is not. Knowing what a priority queue is is a reasonable expectation; knowing the monotone variant is not.
Unfortunately, far too many empathy-deaf programers get to interview candidates. They think that maintaining the company's reputation for having a hard interview process will work in their favor - no "undesirable" candidate get through under MY watch! - unaware of the long-term ill effects such stupid questions have on their profession.
"Hire programers smarter than you" seem to be interpreted as "ask more obscure things than what you were asked". :(
If someone thinks that is a good way to judge hires they are wrong.
"Given an array, and a sliding window within that array, how would you go about finding the max" is a legitimate question with plausible real-world application. 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.
- They started asking algos and datastructs in the 00s because not too many people had the resources to study it. This served as a proxy for intelligence and was vaguely related as compared to other IQ tests or puzzles
- In this decade, more and more CS graduates and bootcampers started studying the same algo and datastruct problems
- Unable to reject anyone (because everyone could solve those problems), they started increasing the difficulty of the problems and started fretting over stupid things like variable names, arcane data structures and solutions, culture fit, ability to handle pressure etc.
- Today, it has devolved into a nerd show off event where the entire goal of interview has become diluted.
The goal of the interview was to open a requisition, find a smart candidate to do the job, close the requisition.
Nowadays, they'll open a req/have a pipeline of candidate, grill them over unnecessary questions and keep interviewing candidates until they get bored/really need to close this req.
The whole point of the interview process is so lost. As a person who is employed in one of these companies, I hate to see what it has become. We regularly reject candidates who are clearly more passionate than their interviewers, have better experience and bring something new to the table.
But because these mediocre interviewers (my peers) interview candidates on some arcane crap (that they obviously can't solve in 30 mins) these smart guys get rejected and I'm relegated to working with these retards.
It is one thing to ask coding questions to filter out the complete losers. It is completely another thing to hire only people who can solve these stupid questions.
Sad!
Instead, the "nerd show off event" exists for one reason "see how much you want to work at that company". Since the realities of software development means the bulk of the engineers will probably be working on some small part of an unglamourous project, yet the "big 4" still want a monopoly on the best and the brightest, the interview process exists as a very targeted test to find people willing to jump through hoops. At this point the broad strokes of what is required is a solved problem, you just need to spend several weeks/months studying up on errata. The thinking is, any candidate willing to do that will be willing to spend several years working on CRUD interfaces for adsense or refactoring old php.
In other words, they want people who'll work for them without complaining. Submissive people. People who won't think out of the box.
Would you say that Apple or Microsoft are any different?
I believe it's the opposite. We all went to college and got the same freakin CS degree. We don't know anything about building products when we graduate. Building a product from the ground up without the help of a designer and PM is a tough exercise. Most engineers would fail. Guess what, that's what we do all day in the real world. 10 years later I still get algorithm questions as if my job is %100 about algorithm. That's %5 of my Master's program by the way.
What an interviewer focusing on specifics can pick up on is near term familiarity with a topic. But someone who can deliver value is also able to propel knowledge into novel areas, and can explain and debug the solution they came up with. They aren't there to be a student passing an exam.
Familiarity tests are often "weeder" filters that clear out candidates with no knowledge of the domain problem. This is a mixed blessing as it can find senior people if you drill deep enough with the right problems, but it can also make the overall skillset and wisdom of the team brittle if they are overfit.
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.
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.
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
Like really I don't know what to expect. I wonder what % of programmers can actually solve the problem without studying the solution (I'm sure there are many out there but I would guess most are from a mathematical field/background).
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.
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!).
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.
But the more obscure stuff doesn't demonstrate much, really, except that they know obscure stuff or are good at researching to find solutions. A more effective question might be: develop or use an algorithm (no constraint on performance like here) to solve problem X. Then follow it up with discussions on how their solution performs and see if it can be improved, and how well they handle being directed to a better--more efficient--solution if they didn't pick an optimal one already.
Of course, even that has problems (with the second part having an implicit bit of "culture fit" to it, and depending on the interviewer being a good critiquer and not merely a nitpicker). And it still only reveals the ability to program-in-the-small. So would only be useful for certain roles, or perhaps more widely for entry level employees.