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

#441

Post by brown9-2 » Wed, Jul 15, 2020, 11:16 PM UTC

Swizec wrote: post #341

dmoy wrote: post #336

Earlier quoted context omitted.

Yea I interview (and have sat on HC) at Google, and interviewers who ask these types of questions really frustrate me. If your question requires having previously memorized or being able to come up with some tricky algorithm on the fly in 45 minutes and code a solution using it , your question is probably bad. I get why they ask them - they're easy to ask, they're easy to score, and when your question inevitably gets…

My favorite question to ask in software engineering interviews is one that I believe to be un-burnable. > It's 2140 AD, New York is under water up to X feet high. Buildings have been retrofitted with to withstand the water. You are in charge of keeping your building dry. If water gets in and damages the foundation, a few thousand people die or become homeless. > Design a system that ensures that doesn't happen. How c…

This is an awful question for hiring software engineers. It’d be like asking a building engineer what quicksort is.

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

#442

Post by dmoy » Wed, Jul 15, 2020, 11:28 PM UTC

cmroanirgo wrote: post #423

dmoy wrote: post #336

Earlier quoted context omitted.

Yea I interview (and have sat on HC) at Google, and interviewers who ask these types of questions really frustrate me. If your question requires having previously memorized or being able to come up with some tricky algorithm on the fly in 45 minutes and code a solution using it , your question is probably bad. I get why they ask them - they're easy to ask, they're easy to score, and when your question inevitably gets…

What on earth is wrong with asking to see the interviewee's code? Skim over it looking for neatness, how they comment, what build procedure is there and quiz them about what you see: anything from language choice, to build reproducibility, from architecture to install. And of course quiz them on algos you see. All of these 'tricky' exam style questions don't show a thing about the person sitting in the interview room…

You lose out on candidates who work at companies that don't let them show you their current code, and have a home life that occupies their time outside of work.

So, you can ask to see candidate's existing code if you work at a small enough shop and/or don't care about missing out on candidates who don't have shareable code. But if you are trying to hire at a larger scale, it does not work.

Many great hiring schemes work until a certain scale and then they fall apart. Some hiring schemes also severely tilt your candidate pool towards a certain subset of the population. I'm sure whiteboard style interviewing also has similar issues.

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

#443

Post by jkingsbery » Wed, Jul 15, 2020, 11:48 PM UTC

derefr wrote: post #345

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

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

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

#444

Post by jkingsbery » Wed, Jul 15, 2020, 11:55 PM UTC

devit wrote: post #419

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

Well, I probably used it last time 10 years ago and still remember it. All you need to remember is that you sort points by angle from a fixed point on the convex hull, and you can easily work out the rest of the algorithm as well as the proof of correctness. Not knowing it is a relevant signal that you did not seriously attempt to compete in computer science competitions during high school and college and did not oth…

Yeah, I remembered the sort by angle part and the broad strokes after that, but there were some details I forgot so I missed some corner cases.

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

#445

Post by abower » Thu, Jul 16, 2020, 12:22 AM UTC

TedDoesntTalk wrote: post #191

haggy wrote: post #150

Earlier quoted context omitted.

I agree with this 100%. I'd also like to add that because of this I adapted the traditional whiteboarding exercise at my current company to be about problem solving and design, and not about how many data structures you've memorized. When a candidate comes in, I give them a fake-yet-realistic product requirement (like count elements in a real-time stream from field sensors) and let them run with it however they see f…

I do something similar: I ask the candidate to take 30 minutes or so to design a system like an online library. What are the objects in the system, how do they relate, can you design a REST or graphQL API for CRUD operations. Then if it’s a front-end position we can move onto UI components for it; for back-end or full stack I focus on implement a couple of the CRUD operations. You really get to see how people think a…

Agree. Its far more valuable to see how a candidate approaches problems than some memorized recital show. I don't expect perfection, but if their reasoning is sound that becomes clear fairly quickly. I usually also include some imperfect questions purposely to see how they handle that. While we wish client projects were nice and clean with orderly data and tight requirements, the truth is that is rarely the case. It's useful to see how the candidate responds to those types of things. I had one gentleman argue with me about one of those questions claiming you would never see primary and foreign keys between tables not perectly match in the real world. Well when you are matching data from entirely disparate systems, you typically do. Anyway I digress.

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

#446

Post by ladberg » Thu, Jul 16, 2020, 12:26 AM UTC

kelnos wrote: post #413

ladberg wrote: post #343

Earlier quoted context omitted.

I had a very similar experience interviewing for Google. I was asked to do a task that eventually boiled down to a topological sort, and I thought the question consisted of recognizing that the answer was a topological sort and moving on because it was over the phone. However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically…

The entire concept of asking someone to write code in Google Docs is just insane to me. No one would ever do that on a job, because it's remarkably awful and difficult, and the editor will fight against you every step of the way (auto-capitalization, just to name one thing). And yet somehow interviewers think that this will give them a good picture of how you'd do work on the job. Baffling.

Yep, it was a struggle even when I thought I was supposed to be writing pseudocode. I've had some really great interviews using coderpad and similar software (including the company I'm at now), and it's such a better representation of how the interviewee actually codes.

I don't get how my interviewer (an engineer), didn't see the problem with it. I know that Google wants to use their own products, but that can't possibly be the norm for other Google interviews.

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

#447

Post by maxov » Thu, Jul 16, 2020, 12:37 AM UTC

eru wrote: post #205

ourlordcaffeine wrote: post #185

Earlier quoted context omitted.

Do you know any good books or resources to read up more on random algorithms?

See eg https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-n... And https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor... describes one of my favourite algorithms. https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf is also interesting. You can find a lot of good material just via Google, actually. If you read the likes of The Art of Computer Programming for breakfast, you might like 'The Di…

I'm surprised and delighted to see someone recommend The Discrepancy Method by Chazelle. I love this book, but even beyond it requiring a lot of mathematical prerequisites, I'm not sure of the use to most software engineers. I think only the chapters on sampling, geometric algorithms, minimum spanning trees, and maybe linear programming would be useful references on algorithm design for most software engineers.

I second the recommendation of Probability and Computing by Mitzenmacher and Upfal. In addition to being much more mathematically self-contained, there is more focus on models and techniques that I imagine software engineers might actually use, e.g. hashing, load balancing.

In addition, Randomized Algorithms by Motwani and Raghavan is a fantastic book, and should be doable after completing Mitzenmacher and Upfal. It goes into further depth on techinques for designing randomized algorithms.

A bit orthogonal but still related to the idea of "what should a software engineer read for interesting algorithm ideas", I really like Approximation Algorithms by Shmoys and Williamson. There is some intersection with randomized algorithms there too.

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

#448

Post by dragonsngoblins » Thu, Jul 16, 2020, 12:56 AM UTC

Swizec wrote: post #411

helen___keller wrote: post #398

Earlier quoted context omitted.

Seems reminiscent of the tales of early 2000s Google interviews, of the "estimate how many golf balls fit in an airplane" variety. I'm not convinced this offers a useful selection criteria other than boosting your unconscious bias on who "seems smart", but on the other hand I'm also not convinced it's any worse than the standard modern Leetcode interview.

Funnily that old style of question is far closer to my day-to-day as an engineer than a leetcode algorithms question. Most of my job involves figuring out solutions to fuzzy problems based on unknown constraints, undiscovered requirements, and often unclear end-goals. "How would you fill this airplane with golf balls?" is a fantastic question. If the candidate doesn't reply with "Why? What are you really trying to ac…

I suppose it depends on how you grade the answers. Like I have bad spatial awareness in terms of how big things like planes are. I genuinely don't really have an idea how long a commercial airliner is, or how big a ping pong ball is. I feel like I'd do ok if I could get reasonable approximate values for things like the size of the plane, the balls, the seats, etc. if I also have to supply those values myself the end result is likely to be off

The end result being off is fine if I am being graded based on my thought process, but a disaster if I am being graded at having an idea of the size of airplanes before walking into the interview.

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

#449

Post by wainstead » Thu, Jul 16, 2020, 1:09 AM UTC

tjr wrote: post #397

ladberg wrote: post #343

Earlier quoted context omitted.

I had a very similar experience interviewing for Google. I was asked to do a task that eventually boiled down to a topological sort, and I thought the question consisted of recognizing that the answer was a topological sort and moving on because it was over the phone. However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically…

A passage from one of Jon Bentley's Programming Pearls : As soon as we settled on the problem to be solved, I ran to my nearest copy of Knuth's _Seminumerical Algorithms_ (having copies of Knuth's three volumes both at home and at work has been well worth the investment). Because I had studied the book carefully a decade earlier, I vaguely recalled that it contained several algorithms for problems like this. After sp…

"Never memorize what you can look up in books" is often attributed to Albert Einstein; the long version is "[I do not] carry such information in my mind since it is readily available in books. ...The value of a college education is not the learning of many facts but the training of the mind to think."

https://en.wikiquote.org/wiki/Albert_Einstein#1920s

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

#450

Post by [deleted] » Thu, Jul 16, 2020, 1:15 AM UTC

kelnos wrote: post #413

ladberg wrote: post #343

Earlier quoted context omitted.

I had a very similar experience interviewing for Google. I was asked to do a task that eventually boiled down to a topological sort, and I thought the question consisted of recognizing that the answer was a topological sort and moving on because it was over the phone. However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically…

The entire concept of asking someone to write code in Google Docs is just insane to me. No one would ever do that on a job, because it's remarkably awful and difficult, and the editor will fight against you every step of the way (auto-capitalization, just to name one thing). And yet somehow interviewers think that this will give them a good picture of how you'd do work on the job. Baffling.

[deleted]