Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.pragmaticengineer.com

Post reply on HN
Print view View original

341–350 of 547 posts

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

#341

Post by Swizec »

dmoy wrote: post #336
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.…

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 candidates approach this, how they think about redundancy, how they deal with additional constraints or extra scenarios thrown at them tells a lot about how they approach things. The question is not about software (explicitly) on purpose so that it gets people out of the coding mindset.

With more software-focused systems you always get candidates who starts writing code and designing objects and classes and stuff. No, I want you to design a system. Stop writing code.

The reason this question is unburnable is that there's no right answer. You're being asked to show how you work through an abstract problem and design a solution. You aren't being asked for an answer.

So far everyone who did well on that question has turned out to be a great engineer. Whether they were fresh out of college (and learned a lot fast) or they were already experienced.

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

#342

Post by woeirua »

ojr wrote: post #236
whack wrote: post #228

I'm increasingly convinced that Algorithms-and-Data-Structure interviews are essentially being used as a proxy for: - General IQ. Can this person understand and apply complex ideas - Grit. Is this person hard-working enough to learn things that take time and effort It's the software equivalent of the NFL scouting combine. The goal is not to create a test that is similar to the day-to-day job. But rather, create a tes…

- Retention. If this person spent hours on leetcode, they’ll be less likely to leave the job knowing the effort it takes to get through the gate

Meanwhile, engineer retention statistics at FAANG companies prove otherwise...

[1] https://www.businessinsider.com/average-employee-tenure-rete...

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

#343

Post by ladberg »

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 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 had to re-figure it out on the fly, which took most of the interview (I even similarly mention "in any real situation I would just look this up", but that didn't help). At the end, I had a bunch of pseudo-C++-code that should do it correctly.

I thought I was done, then the interviewer said she would go go copy my code and compile it after the interview to see if I was right, which blew my mind. It was never mentioned previously that the code would actually be compiled and run, and with no syntax highlighting or ability to compile and test the code myself there is zero chance it was ever going to work.

I never heard back, so I'm assuming my code failed and they left it at that. Anyway, I'm much happier now that I think I would have been at Google.

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

#345

Post by derefr »

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

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

#347

Post by pb7 »

oblio wrote: post #330
syndacks wrote: post #284

Earlier quoted context omitted.

>Is any of that even controversial enough to require citation? I'm sorry, excuse me? Are you saying that non-minority, non-women don't suffer anxiety? Your parent comment certainly seems to suggest that. Which, at a minimum, is flat out wrong. Educate yourself[0]. And then zoom out and ask yourself why it's not only permissible, but often lauded, to so flippantly say what you just said. [0] - https://www.apa.org/abou…

You just "All Lives Matter"ed his "Black Lives Matter" argument. And I'm not writing this as praise for your comment...

Stop dehumanizing an entire group of people. All humans feel anxiety and that's a fact. Excluding one group of people that is equally likely to experience it because it's currently in vogue is still discriminatory.

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

#348

Post by mindcrime »

arethuza wrote: post #293
unclewalter wrote: post #181

Earlier quoted context omitted.

> What is an IC? Believe op is using it as "individual contributor"

Isn't there just a bit of condescension in that title? It always sounds to me like something invented by a manager to be dismissive of someone who doesn't manage anyone.

I never got the vibe that "IC" was intended to be dismissive, or intended to be a pejorative or anything. I think it's more of an HR thing, because the distinction between IC vs Manager usually affects compensation and blah, etc. Whether or not that should be the case is a separate question.

I always assumed the term just leaked out of the HR world and into the general parlance.

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

#349

Post by NotSammyHagar »

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

That was a terrible interview experience. Of course anyone would look it up. I used to work at google and interviewed people as part of my job as a regular software engineer. I occasionally heard about these kinds of stories. Google didn't give much feedback to individual interviewers, no one told them if they were terrible or great questions or whatever. I also saw better interviews.

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

#350

Post by derefr »

dmoy wrote: post #336
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.…

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…

I think they may also ask them because they want to see how you do at the specific task of taking a problem you remember the pseudocode algorithm for, and actually turning that into working code in a real programming language. You know, the "schlep" part of programming.

I feel like they don't realize that this is the goal they're calibrating these questions toward, though. If they did, they wouldn't require the "from memory" component—instead, they'd break the question into two parts:

1. tell me what algorithm you would use to solve this problem; or, failing that, tell me what criteria you'd use to select the best algorithm for solving this problem out of a set of candidate algorithms.

2. Here's a journal paper, explaining a particular data structure + set of algorithms that can† be used to solve the problem we're talking about. All the algorithms in the journal paper are in that sort of declarative, math-proof-phrased pseudo-pseudo-code form. Now take this journal paper and turn it into an implementation in your language of choice. Explain your thinking as you go.

† The paper chosen is not the one corresponding to the algorithm the candidate chose; nor is it the one corresponding to the algorithm that's "right" to pick for solving the problem. It is, in fact, randomly-chosen from the pool of sub-optimal solutions to the problem, filtered for the ones that get rarely used in practice and so have no easy non-journal-paper presentations of a reference impl laying about on the web to study. Alternately—if the interviewer has enough time to explain a second problem—it could even be a paper randomly-chosen from the pool of all algorithms papers!

Benefits:

• Both task 1 and task 2 are things "senior" engineers do every day in the real world.

• There's no component of memorization; the step "between" step 1 and step 2, where you'd look up the journal paper corresponding to the algorithm you thought of, is dropped.

• You can't really "burn" either task.

Post reply on HN