Hacker News Reader

Comment by kazinator | Hacker News Reader

> We do algorithms every day at 9am (9am!) on whiteboards in groups. It’s a pain in the ass, but they’re necessary for job interviews. What’s kind of amazing is that an algorithm that used to take me hours/days last year now takes me 15 minutes.

What does that mean, "do" algorithms, I wonder. Design algorithms based on requirements which describe the inputs and outputs? Implement existing algorithms from a description? Check the correctness of algorithms? Some of all of the above?

If it's the same algorithm as last year, why would it be amazing that it takes 15 minutes to do it (whatever that entails)? If you had to basically reinvent insertion sort the first time and now you can just regurgitate it from memory, of course it's faster.

View on HN

You are being pedantic. The author obviously meant "algorithms that you might be asked to do on a whiteboard during a tech interview at Google, FB, ect"

I honestly don't know what exactly that means. (Given your nickname, it must be obvious to you, of course).

Is it like, "write down the entire A-star search algorithm in pseudo-code from memory"?

I assumed she meant that they answer questions like "write a function that finds an arbitrary value in a sorted array" and are expected to use a binary search.

I would rather have a programmer look for a library function to do the task, and understand its specification and all its cases, for correct use.

Failing that, I'd expect them to research the solutions online (and offline if necessary). Find some suitably licensed code snippet or failing that, carefully implement it from a quality specification somewhere (an original paper, good textbook or whatever).

The last thing we want is programmers regurgitating from memory what they think are the correct algorithms.

The vanishingly small number of times I've implemented a binary search from scratch over the past several decades, I cribbed it from somewhere. I needed the algorithm not only to find the item but also correctly indicate where a not-found item would be inserted. I don't want to reinvent annoying little crap like that from scratch, only to get some detail wrong, just like whoever did it first, fifty years before me!

Here is a good exercise for an interview. Give someone an obtusely written, confusing specification for an API, together with a task to implement with that API: watch how they defend the code against the corner cases, and deal with the ambiguities. The task would be "make a best effort to solve the task, and write down any questions about the API which block the completion of the task."

Because that's what we deal with: we read docs, try to use things, hit issues, and then research (online, with vendors, source code, etc) to get unblocked.

I might have a part II to the question where some source code of the API is revealed, and the interviewee would have an opportunity to continue. (So they don't walk away with a sense of incompleteness.)

I live in a bubble in San Francisco and post on HN, so when talking to people I usually assume (perhaps incorrectly), that they are all software engineers between the ages of 18-25 currently in the job market, interviewing at all the same hip 5 companies, so I apologize :P .

In software engineer, when applying for jobs at tech companies, you are universally asked to program solutions to algorithms problems on a whiteboard that follow a very specific formula. If you ever interview for a software position, you will get these exact kinds of questions.

Such questions are usually things like:

"Given a N sorted lists of numbers, join the lists into a single sorted list efficiently"

"Implement a Stack which has push, pop, and minimum operations in O(1)"

"Traverse a Tree and print out each item in level by level order" ect

They are all very formulaic and similar. In the last 3 years I've done about 100 algorithms interviews, and 9 out of 10 times it is a question I've been asked before.

You can find other examples at Glassdoor, hacker rank, or project Euler.

http://www.glassdoor.com/Interview/Google-Interview-Question...

https://projecteuler.net/

Did you get hired?

I've received about a dozen job offers in the last 3 years. TBH, I don't even consider myself better than an average programmer. I've just practiced interview questions a lot.

I'd say this only holds for ~70%, although it's likely geographically skewed - I'm in Seattle, you're in SF.

I've interviewed (and been hired, and been successful) at many great companies where we didn't do specific algorithm implementations on a whiteboard during the loop.

I would certainly not throw out a promising candidate because they couldn't remember specifics on a certain algorithm.

You're not alone. I too, have no idea what it means. These things seem to teach a bunch of buzzwords and then maybe lecture about how cool Ruby is for a few days. It is sort of self-taught programmers turned ... not-self-taught.

I happen to really like A-star search. So I'll give this a shot just for fun.

  Let Q[(Node, Cost)] be a priority queue.
  Let G be a graph. (This makes up the search space.)
  Let V be the set of Nodes visited by the algorithm.
  Let S be the starting Node of G.
  Let F be the objective Node of G. (Node we are searching for)
  
  Let D(N1, N2) -> n be a function (computes the number of edges between N1 and N2.
  Let H(N) -> T be a function that computes an admissible heuristic cost for traversing N. (eg, taxicab distance)

  Let Search(G, Q, V, S, F) be a function that finds the lowest-cost path to F:
    Add (S, 0) to Q

    While there are items in Q:
      Pop (N, C) from Q

      If N is equal to F:
        Return the path from N to S. (Trivial parent traversal)
      
      Add N to V

      For each Nc in N's neighbours:
        Set Nc.Parent = N
        If Nc is not in V:
          Add (Nc, H(N) + D(N, Nc)) to Q
    
    Return an error, a path does not exist.

I have to admit this ended up taking longer than I thought it would. ~20 minutes. And I'm not sure if it's correct.

Reply on news.ycombinator.com