Data structures and algorithms I actually used while working at tech companies • Hacker News Board

Re: Data structures and algorithms I actually used while working at tech companies

#471

Post by tsimionescu » Thu, Jul 16, 2020, 6:04 AM UTC

ivanhoe wrote: post #246

tsimionescu wrote: post #220

Earlier quoted context omitted.

If you're given a blank slate and asked to sort a list without using a library without any gotchas, complexity requirements, space requirements, expectations that the code is completely free of small bugs etc.; and you can't do that after some thinking even to a basic degree, then you're just not a good programmer. As a programmer, your task is to find algorithms to solve problems. Sure, sorting numbers is a solved p…

I agree, but how is applying pre-learned algorithms significantly better than using pre-build libraries? Both is about using an existing solution, instead of coming up with it on your own. The real approach would be to ask candidates to solve a problem that doesn't easily fit into any popular category, so that they have to come up with an original approach - but that is first hard to come up with, and 2nd it would re…

Yes, that's a good point, and in our interviews we do try to take a slightly less well-known problem, at least one that doesn't have a dozen well-known named algorithms.

Still, even using a pre-learned algorithm demonstrates some level of confort with algorithms in general, and can be used as a stepping stone during the interview to shift the problem slightly to see how they adapt the algorithm.

For example, if a candidate is clearly taking their time and essentially working out the algorithm themselves, and succeeding, that demonstrates the skill and we can move to other problems. If the candidate just breezes through and finishes in 2 minutes, then we can change the problem ad-hoc to try to get them off the beaten track a bit (say, if they wrote quicksort, maybe ask about making it stable, or sorting even numbers differently from odd numbers, off the top of my head).

Re: Data structures and algorithms I actually used while working at tech companies

#472

Post by tsimionescu » Thu, Jul 16, 2020, 6:10 AM UTC

ricksharp wrote: post #464

tsimionescu wrote: post #220

Earlier quoted context omitted.

If you're given a blank slate and asked to sort a list without using a library without any gotchas, complexity requirements, space requirements, expectations that the code is completely free of small bugs etc.; and you can't do that after some thinking even to a basic degree, then you're just not a good programmer. As a programmer, your task is to find algorithms to solve problems. Sure, sorting numbers is a solved p…

My point was that if testing for a skillset, using something that favors those who have toyed with a specific algorithm is the same as asking trivia questions. Trivia does not provide evidence of skill, it demonstrates prior knowledge. It would be better to introduce a unique situation that would place everyone at the same starting point.

If the expectation of the interviewer is to see if they know quicksort, then I fully agree with you. If the sorting problem is simply used as a (rather uninspired, granted) stepping stone to checking that the candidate has basic algorithm-finding skills, then I think it can serve this purpose (though less well-known but still relatively simple problems would be better). I gave an example in another thread as well, but in principle I would change the problem up a bit if the candidate is obviously producing a well-known algorithm; whereas, if the candidate is working out the solution themselves, I would be happy with that and move to other topics.

Even so, knowing very widely talked about programming trivia is still a signal for interest in the art. I'm not sure that sorting algorithms are a good example of what I'm thinking, but I always award extra mental points to candidates who seem knowledgeable about the field (e.g. they know the general consensus on manual memory management vs garbage collection). Still, I wouldn't consider these sorts of things dealbreakers by any stretch of the imagination.

Re: Data structures and algorithms I actually used while working at tech companies

#473

Post by gregoryl » Thu, Jul 16, 2020, 6:22 AM UTC

Swizec wrote: post #436

hackinthebochs wrote: post #406

Earlier quoted context omitted.

This is a terrible question. Problem solving ability doesn't exist in a vacuum. Our experiences give us resources to draw from to combine in new ways that allow us to solve novel problems. Asking a software engineer to solve a problem in a dissimilar domain is badly missing the point of screening software engineers. Sure, you may say that everyone who does well turns out to be a great engineer. I'm sure Google says t…

I disagree. The goal of this question is to see how you utilize domain experts as a resource, add your software expertise, and design a comprehensive solution. It is specifically not a question about what you already know. In the interview I play the domain expert. This is exactly what your job will look like: collaborate with domain experts, use your software skills, solve real world problems. I don’t need an engine…

Have you considered asking questions that involve queues.

Re: Data structures and algorithms I actually used while working at tech companies

#474

Post by pjmlp » Thu, Jul 16, 2020, 6:27 AM UTC

jkingsbery wrote: post #327

Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anything related to convex hulls since my algorithms class as a sophomore in college (several years earlier), I couldn't remember all the details. At some point, I said, I know where in CLRS ( https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press... ) this is.…

Exactly my experience twice over phone interviews with them, after the second one I actually got some kind of survey question, my answer was not to ever bother me again with stupid emails how great my CV looks like, that I would be the right person that they are looking for and then waste a couple of hours of my life with such exercises.

And for what? Anyone that works with Android only has to wonder where do those algorithm magicians land at Google.

Re: Data structures and algorithms I actually used while working at tech companies

#475

Post by abtinf » Thu, Jul 16, 2020, 6:32 AM UTC

spankalee wrote: post #415

jkingsbery wrote: post #327

Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anything related to convex hulls since my algorithms class as a sophomore in college (several years earlier), I couldn't remember all the details. At some point, I said, I know where in CLRS ( https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press... ) this is.…

I work at Google and have performed plenty of interviews over the years. We're specifically trained not to do this. We have "feedback feedback" in our interview systems specifically for this type of situation.

And yet... I've read countless anecdotes about this kind of behavior, over multiple decades.

Re: Data structures and algorithms I actually used while working at tech companies

#476

Post by pjmlp » Thu, Jul 16, 2020, 6:36 AM UTC

jkingsbery wrote: post #443

derefr wrote: post #345

Earlier quoted context omitted.

For a company whose main claim-to-fame is indexing the web (rather than mirroring it in their databases), Google sure doesn't seem to understand that CS learning is done by mentally indexing textbooks (rather than mirroring them in your brain.)

If I had any wit, I would have responded to the convex hull question: "I would look this up on the Internet, assuming there is a search engine good enough to find the algorithm."

Lovely!

Re: Data structures and algorithms I actually used while working at tech companies

#477

Post by pjmlp » Thu, Jul 16, 2020, 6:38 AM UTC

spankalee wrote: post #415

jkingsbery wrote: post #327

Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anything related to convex hulls since my algorithms class as a sophomore in college (several years earlier), I couldn't remember all the details. At some point, I said, I know where in CLRS ( https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press... ) this is.…

I work at Google and have performed plenty of interviews over the years. We're specifically trained not to do this. We have "feedback feedback" in our interview systems specifically for this type of situation.

Given that I gave my feedback about 10 years ago and it keeps happening, something is not right.

Re: Data structures and algorithms I actually used while working at tech companies

#478

Post by qohen » Thu, Jul 16, 2020, 6:50 AM UTC

varbhat wrote: post #114

Which are the best books to learn Data Structures and Algorithms ? (Or which books did you use/recommend to learn Data Structures and Algorithms?)

Given that the publisher, Springer, is giving it away for free during the pandemic, you should grab the PDF of Steven Skiena's The Algorithm Design Manual[0] (direct PDF link[1]) -- it's a book that has often been mentioned favorably here on HN.

(And you can pick up another book of his, The Data Science Design Manual[2] (direct PDF link[3]), which is similar in its conversational style, but about a different aspect of CS)

[0] https://link.springer.com/book/10.1007/978-1-84800-070-4

[1] https://link.springer.com/content/pdf/10.1007%2F978-1-84800-...

[2] https://link.springer.com/book/10.1007/978-3-319-55444-0

[3] https://link.springer.com/content/pdf/10.1007%2F978-3-319-55...

Re: Data structures and algorithms I actually used while working at tech companies

#479

Post by pasabagi » Thu, Jul 16, 2020, 7:25 AM UTC

linza wrote: post #351

derefr wrote: post #345

Earlier quoted context omitted.

For a company whose main claim-to-fame is indexing the web (rather than mirroring it in their databases), Google sure doesn't seem to understand that CS learning is done by mentally indexing textbooks (rather than mirroring them in your brain.)

That may be true. But then why hire someone with just look-up skills before hiring someone who really tries, and enjoys the challenge? I'm interviewing engineers frequently and although I agree that the question asked by GP is maybe not the best it still gives the signal if someone is willing to power through a problem with minimal guidance and/or ambiguous constraints. Something I'm willing to find out at the peril…

I don't really see a hard distinction between meat memory and silicone memory, so I've never bothered to memorize stuff that I could simply lookup. To me, it seems almost ridiculously inefficient to carry around large amounts of indepth data in your brain, which is limited, costs constant energy to maintain, and isn't even particularly good when it comes to fidelity of recollection and searchability.

It's much more efficient to remember the general shape of problems, to remember where you can find further information (books, chapters, etc). Remembering that something is a well-studied problem, and where to find a solution, is straight-up more efficient than remembering that solution.

Dijkstra once remarked that trying to make a computer act like a human brain was far less interesting than seeing what the limits are of a computer as something that is unlike a human brain. It seems the reverse observation is also true - human brains, once freed from rote memorization and computation (that's literally what programming does to us), can tackle much larger, more interesting, and more complex problems.

Re: Data structures and algorithms I actually used while working at tech companies

#480

Post by ajuc » Thu, Jul 16, 2020, 7:58 AM UTC

pantaloony wrote: post #297

Taek wrote: post #22

Earlier quoted context omitted.

We always tell our candidates in advance what algorithms we'll be quizzing them on. And it's pretty much always: + fibbonacci + a sort + a linked list I like having candidates write out these problems on paper because it shows that they know how to think about code. Fibbonacci allows us to see that they have basic recursion understanding, and basic iterative loop understanding. Linked lists shows us that they underst…

Have you tried just having a conversation about pointers and recursion? Does that not work as well (or better)? Kudos for letting candidates know what’s going to happen, it’s just that when I see problems that are clearly just a stand in for “do you know X?” I always wonder why interviewers don’t cut to the chase and just ask directly. “Are you comfortable with recursion? Can you describe it? When does it tend to be…

Some people (myself included) can bullshit through such questions pretty well even when we don't know the answers. It's a skill, a combination of reading body language for clues, being confidently vague in the right places and turning attention away from dangerous questions with charisma.

You learn it quickly when teachers do oral exams at university :)

Code doesn't lie, so I understand why people like to check candidates that way instead of relying on talk alone. I would just prefer if it wasn't a hit-or-miss test on what algorithms you memorized.