Hacker News Reader

Comment by SamReidHughes | Hacker News Reader

> Here's my gripe with this interview process. It encourages engineers to spend months and years into learning and remembering optimal solutions to textbook problems.

Wrong. Questions aren't designed to be memorized. It shouldn't take months, or years, to prepare for this stuff if you already have a CS background unless you're really slow.

View on HN

> Wrong. Questions aren't designed to be memorized.

Do you know that 'detect a cycle in a linked list' question? I can't imagine many people being able to answer that without having seen the question previously.

I figured that problem out on my own the first time I heard of it. It wasn't Floyd's algorithm, there are many solutions.

One data point, but I was asked that as a Microsoft interview question when I was a freshman. I figured it out on on the fly pretty quickly. I'm no genius.

Recent surprise: exponentiation by squaring. Not by name, but by being the correct answer to the question. (This is in the list of 500, by the way.)

It's trivial to explain:

    x^n = x(x^2)^((n-1)/2), if n is odd
        = (x^2)^(n/2)     , if n is even

Knowing that (or having figured that out yourself if an interview was your first exposure to this problem), it's even more trivial to implement, making it a math quiz far more than a programming exercise. (Though I later turned it into a programming exercise entirely to exploit an arbitrary eye bleedecution bug in the human brain: https://gist.github.com/LnxPrgr3/7154873d3eb8b1e5960851628c7...)

Maybe that's what they intended. It's certainly legit if the job will have you actually doing, rather than applying, math. Except that it concludes you can math if you're smart enough to pretend to derive the answer you memorized after encountering it before. You might accidentally hire a bunch of crypto nerds.

For what it's worth I learned that explicitly in a data structures & algorithms class. I've seen it come up in a bunch of other introductory material, so it seems like a relatively standard part of "the curriculum." I think somebody might have a chance of coming up with this shortcut on their own, if, for example, they wanted to compute the Nth Fibonacci number efficiently (using matrix exponentiation -- the bignum arithmetic makes it O(n^2) if you just do n multiplications) or if they wanted to compute a polynomial more efficiently by memoizing the values x^(2^n), or if you kidnapped them and threatened to kill their family if they couldn't figure out how to compute x^n using O(log_2(n)) multiplications...

The difficult thing about that shortcut isn't that you couldn't come up with it, it's that you wouldn't think to try coming up with it unless you are in a particularly painful situation.

I don't view this exponentiation speedup stuff as math-specific, it's something you can come across when efficiently updating string checksums under random access modifications and concatenations, or when solving some graph problem where you exponentiate an adjacency matrix.

I'm glad your algorithm class covered this. Mine did not. It surely covered some other obscure material that you don't know. You are missing the point. If we had a standard CS curriculum, you can fault people for missing out on stuff they should know. I think part of the problem is people is that CS is too big of a discipline at this point. A systems person couldn't pass a graphics person's interview, etc.

But I wouldn't require somebody to know of faster exponentiation in an interview. It's still too obscure.

Who do you want to work with? A person who can regurgitate CS trivia or a person who has interest and track record in solving interesting problems?

Like I said, it's not regurgitation. There's a reason companies try to keep their questions secret.

It's all a variation of the 500 questions listed. Nobody memorizes code line by line. But there are enough hires at Google and FB who memorized algorithms and solutions and got in.

Do you want to work with people who memorize solutions or do you want people who are innovative, genuine problem solvers who've solved interesting problems?

It's hard to imagine an innovative problem solver being unable to tackle Google's interview questions. You gave the example of optimizing an SQL query. That's a data structures problem itself.

Google apparently has an NDA for the interview questions they ask, so they're trying to avoid quizzing people on stuff that they've memorized. I know any place I worked at always tried to ask "fresh" questions to people. There's just no point if they already know the answer.

I had a phone interview with Google a few years ago. I was asked to implement a Soduko solver. I didn't manage it during the interview, but half an hour later a solution came to me when walking down the road. Should I have been a hire or a no hire?

I'm someone who cycles over my thoughts for long periods of time. Interviews really don't capture this at all, but it's one of my strongest intellectual assets.

What is your point? They've got limited time and don't want to waste candidates' time. There is some variance in the process, which they try to minimize by asking lots of questions.

Point is that it is a very poor way of assessing someone.

>> It's hard to imagine an innovative problem solver being unable to tackle Google's interview questions. You gave the example of optimizing an SQL query. That's a data structures problem itself.

Dude, is your definition of problem solving limited only to Algos and datastructs?

Because I can imagine sql optimization in the following ways: 1. Compiler modification to use different instructions 2. Hinting branch predictors 3. Modifying the database environment to use different operations under the hood 4. Use a different hardware 5. Use a different language 6. Allocate different memory configs 7. Use SSD

Do you even realize that CS is not algos and datastructs only?

The big optimization would be avoiding full table scans or full table joins. That would be at the query level.

>> The big optimization would be avoiding full table scans or full table joins. That would be at the query level.

An insight that can only come from experience and to someone who is actually interested in this.

I want to work with people like you, not with the person who can solve some stupid dynamic programming puzzle but can't do any real interesting stuff in the real world.

Well, I meant that the biggest optimization you can do is algorithmic in nature.

Reply on news.ycombinator.com