Ask HN: Is asking obscure algorithms any test of programming ability? | Hacker News Reader

Ask HN: Is asking obscure algorithms any test of programming ability?

43 pointsraj_m41 comments

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 ?

View on HN

Here's what happened to these companies:

- 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!

I think you've missed an important step in how these systems are used at these companies and how their funnels work. For a comapny like Google, their funnel is so tight by the time a candidate is onsight it's known that they're capable.

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.

You are right.

In other words, they want people who'll work for them without complaining. Submissive people. People who won't think out of the box.

That's a scary thought to me. One that's probably correct, but scary, especially at companies who claim to champion "outside the box" thinking. It's almost like a sort of "Do as I say, not as I do."

I think it's just the reality of how software is made. There's room of innovative thinking in small startups, or at the highly technical specialized teams in mega corpX, but at the end of the day the grunt work has to be done by someone and that's going to fall to the line member.

I think this is right on the money, particularly with respect to Google. They're going to lock you away for X years to work on some internal project that'll probably never see the light of day. I think all of the hullabaloo about company culture "fit" and the awe of working for the Big G factors into that. The work is probably boring and mundane and they hope to further lock you in by making sure that you only subscribe to their ideology. This is all conjecture for now, but I have an internship coming up with one of the Big 4 and while I am genuinely excited/interested to work there I wonder if it'll also confirm my suspicions.

Would you say that Apple or Microsoft are any different?

As someone who is looking to transition from a non-programming field into a paid position, how do I avoid these types of companies? Is there a good indicator of which companies use these types of screenings before applying? Or do I just have to cast a wide net and suffer through these types of interviews?

I 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 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.

> 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.

> Are knowing obscure algorithms like this any test of a person's programming ability ?

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". :(

It'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.

Normally, you would interview someone on problems that you want to solve. You would want to hire someone that will help with business challenges by providing specific programming expertise. Requiters do keywords search for a reason.

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).

A 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.

The OP referred to a "Monotone Priority Queue" which seems to be something different: https://en.wikipedia.org/wiki/Monotone_priority_queue.

The 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.

Ditto.

That's an interesting observation. So what you are saying is that if I make sufficient headway into the problem without providing the most efficient answer, it should be fine?

There are rumors that unless you are spot on perfect in Big 4 interviews, they wont advance you.

It depends on the aptitude for problem solving that the interviewer observes in the process.

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.

It all depends on the interviewer. Anyone claiming different is selling you bullshit. The purpose of the interview and how they are actually used in practice is all on the interviewer.

I mean, aren't those algorithms developed by CS professors/researchers/Ph.D's/mathematicians? As a junior developer I seriously doubt I'd even approach the problem the same way as the super smart person who developed that algorithm.

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.

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

Monotone Priority Queues were formulated after I took an algo class. I've encountered them because I had exceptional need to understand priority queues, but have never needed to implement, describe, or recognize them.

If someone thinks that is a good way to judge hires they are wrong.

I 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).

I wonder what the interviewer would have said if you'd written down Binet's formula :)

http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...

Maybe his response would have been "Thank you for memorizing obscure formulas. Unfortunately, we look for motivated employees who study relevant topics pertinent to work."

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).

No it's stupid. Like asking an iOS engineer a question involving a tree data structure. It is stupid and irrelevant because at the end of the day our job is to build products/features. If you think at a student level you will never learn anything past college. Companies think that by default everyone can write code and build product. So they focus on stupid obscure stuff.

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.

Will an iOS engineer never consider a binary search tree to store sorted data?

An iOS engineer would look at things like CoreData or Sqlite :) certainly not a binary search tree.

Yes, 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.

As 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.

Algorithms knowledge demonstrates competency in the small, but isn't good for demonstrating skill at programming in the large. The person passing such tests will be effective in developing programs, but not systems, and may not be effective in self-directed design of programs that exist within systems.

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.

This 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!).

No, with the sole exception of interviewing for a research position where new algorithm variants on the sliding window might be developed.

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.

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.

If you believe some reports, it doesn't matter what is covered in an interview; it's no better than a lottery regardless.

Also, any test that you ace has not completely characterized your actual skill level; all it tells you is that you're above the skill range measured by the test. You might be a little bit above, or far above, that upper bound. Maybe they've decided to have one really hard question that it's unlikely anyone will answer correctly, but if they get someone who can answer it then they know they've found someone really suited for the job.

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.

One may argue that a Phd student working in genomics must know the Monotone Queue variant because it MAY come up as a research implementation in his/her work. But this doesn't hold true for general software engineering folks.

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.

I recently did a test with a huge ( 200M MAU ) consumer company for a developer role ( back-end ), and the first test was extremely challenging. It wasn't algorithms per se, but maths. To solve this, you had to understand counting ( N choose K ) but to a level such that the way to solve these particular problems really only emerged in a paper a decade or so ago. So you had to go look up a paper, and implement. None of this was specified, I just had to figure it out. Another question also involved looking up a paper ( tho it probably could have been done another way as well ), and the easiest question was a relatively basic programming question. It was hard to see a rationale that linked the questions together, and linked the test to the role, but at least you could be sure that if people got through they were pretty clever and capable.

Reply on news.ycombinator.com