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

#361

Post by chrisseaton » Wed, Jul 15, 2020, 6:23 PM UTC

CydeWeys wrote: post #198

This article is hurting its credibility right from the get-go by un-critically reproducing yet again this tired saw from Max Howell: > Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off. First, it's not remotely true that 90% of Google engineers use Homebrew, seeing as how almost all development is done on Linux (Max Howell is unjustifiab…

I think people forget how incredibly high the Google hiring bar is. Tons of people have written extremely successful software, but I think you really need to be at the very top of your field to even be considering going to Google. You can be absolutely excellent... and still not be good enough for Google, and it's fine to admit that.

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

#362

Post by 000000000000010 » Wed, Jul 15, 2020, 6:26 PM UTC

derefr wrote: post #354

linza wrote: post #351

Earlier quoted context omitted.

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 work with novel algorithms all day (I'm writing a decompiler.) The more I learn, the more I have confidence in the fact that I have absolutely no hope of inventing an algorithm that doesn't already exist; and that I shouldn't waste my time trying , when instead I could be spending that time digging through the nigh-infinite vault of potential solutions to my problem known as "the output of CS academia." Software en…

I think the point is that no one is being asked to derive a novel algorithm. It’s taken for granted that a person with enough experience will have an understanding of broad categories of algorithms and should be able to reason about the small changes to those algorithms that would be necessary for practical application.

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

#363

Post by chubot » Wed, Jul 15, 2020, 6:28 PM UTC

giomasce wrote: post #4

I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never used outside programming competitions. The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far you…

Here's a thread on the same article that ended up being largely about dynamic programming :)

https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actu...

I still say it is a bad interview question, but there were lots of interesting examples I learned about.

- GCC splitting IA-64 instructions

- Trellis quantization in lossy video encoding

- Knuth-Plass line breaking algorithm (mentioned here too)

- Some algorithms I knew about, but which can be considered dynamic programming (I'm not sure how interesting this is): A* search, Dijikstra's shortest path, Myers common subsequence algorithm, transitive closure algorithm

I would say the GCC one is most interesting because there's a link to the actual code and comments by the developer.

https://github.com/gcc-mirror/gcc/blob/master/gcc/config/ia6...

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

#364

Post by sterlind » Wed, Jul 15, 2020, 6:30 PM UTC

ladberg wrote: post #343

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…

Yeah, Google's interviews are whack. I've been rejected twice -- I think because of flubbing an algorithm question -- and after that I designed a new algorithm for my work that's getting published in OSDI this year, I think.

Their loss.

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

#365

Post by pkaye » Wed, Jul 15, 2020, 6:36 PM UTC

the_mitsuhiko wrote: post #50

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…

> I like having candidates write out these problems on paper because it shows that they know how to think about code. Is this really a useful exercise? Why not present them with an actual problem that is relevant to your field and see how they approach it?

A lot of candidates can't reason past the simple stuff so rarely do I have go beyond a simple coding problem. The FAANGs and unicorns maybe get lots of candidates so they can be very choosy.

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

#366

Post by jlokier » Wed, Jul 15, 2020, 6:38 PM UTC

justicezyx wrote: post #358

Swizec wrote: post #341

Earlier quoted context omitted.

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…

IMHO, this is not particular better than an algorithm question. Why not just summarizes the traits of the technical skills you expect from the candidate, lay it out, and come up appropriate questions for each interview? General software engineering interview does not work. But there can be more specific measures to improve the experience.

> Why not just summarizes the traits of the technical skills you expect from the candidate, lay it out, and come up appropriate questions for each interview?

That won't work; it's aimed at a different kind of skill.

The skill the GP is looking for is ability to solve a problem you have never seen before, for a problem that bears little resemblance to anything you've done before, by transferring your existing general problem solving skills. It's a test of your ability to solve new things, which is a capability the company finds useful.

This is a very useful skill, and you can learn to do it better, but it's not a "technical" skill as we usually mean it. However it is one of the things which might be associated with "great engineer".

Listing technical skills and testing them will not tell you if the candidate has developed the above capability.

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

#367

Post by giomasce » Wed, Jul 15, 2020, 6:38 PM UTC

chubot wrote: post #363

giomasce wrote: post #4

I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never used outside programming competitions. The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far you…

Here's a thread on the same article that ended up being largely about dynamic programming :) https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actu... I still say it is a bad interview question, but there were lots of interesting examples I learned about. - GCC splitting IA-64 instructions - Trellis quantization in lossy video encoding - Knuth-Plass line breaking algorithm (mentioned here too) - Some algorithms…

I tried to read the comment, but don't quite understand: what is the problem GCC is trying to solve there?

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

#368

Post by Teknoman117 » Wed, Jul 15, 2020, 6:42 PM UTC

Can anyone recommend a good resource for learning about Dynamic Programming? Not from a FAANG interview perspective, it's something that I didn't really wrap my brain around in the algorithms courses in University. Five years into my career I still haven't ever had to use it. It's something I feel mildly guilty about.

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

#369

Post by dekhn » Wed, Jul 15, 2020, 6:44 PM UTC

chrisseaton wrote: post #359

dekhn wrote: post #304

Earlier quoted context omitted.

Most Googler SWEs have Mac laptops, not linux or windows laptops. But only a fraction of them use brew to install additional software. I'd love to interview the creator of homebrew. There are so many dependency and reliabiltiy questions that it's clear brew doesn't handle well (same criticism of CPAN, and pip to some degree) in terms of performance or correctness that you could just talk for an hour about graph probl…

How does Google develop software? Someone told me they did all their development in the cloud and you aren't allowed to check out software locally? Does that mean they just use their macs as thin terminals? But what's running in the cloud for development then? Linux X desktops, or do you edit in a browser, or do you develop entirely in a console over SSH? Nobody seems to talk about the developer experience at Google…

It depends.

Many googlers work on the centralized google3 source tree where the source lives in the cloud and your workstation is mostly a frontend for editing a FUSE view (citc): https://cacm.acm.org/magazines/2016/7/204032-why-google-stor... among other documentation gives some details on the process.

Typically that work will be done on a workstation at your desktop. But if you want to work remotely, and you can't access citc from your laptop. So, you'd ssh into your workstation, or use Chrome Remote Desktop (personally, I ssh from a ChromeOS laptop to a glinux workstation with tmux). Others use CRD for a full remote desktop. At that point the dev experience is mostly what like other people experience, except that the source and build and test environments are in the cloud, rather than on your local machine.

That just describes one common case- devs and researchers writing stuff that runs on Google's internal resource management system, borg. There are many other teams, who have their own standards and approaches, which don't use the technology I described abvove. I'm sure there are plenty of devs at Google who actually build directly on their laptop, and commit code to open source repos without ever touching citc, or google3.

For me at least, the dev experience at Google feels like every other dev job I've had: ssh to a LINUX machine, write code, compile it, run tests, send it for review, submit. A lot of people who are C++ server developers and python client developers could drop into the Google environment and quickly be productive.

A lot of this is documented in external talks but it takes a ton of work to assemble all of it.

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

#370

Post by dmoy » Wed, Jul 15, 2020, 6:47 PM UTC

derefr wrote: post #350

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…

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 "fro…

Yup if you are willing to explain the algorithm to the candidate and not dock them any "points" (or whatever) for having to explain the algorithm, then this works fine. I have no qualms about having a discussion about an algorithm that's tricky, and seeing how the candidate works through it.

That's not what I see in practice though. Not remembering the whole algorithm at best ends up wasting half of the interview (code the remainder in 20 minutes??), and at worst gets explicit language from the interviewer like "TC couldn't figure out and I had to explain the algorithm to them explicitly, WEAK/BORDERLINE on algorithms".

I should also say, I dislike doing any engineer interviews that are purely talk-about-algorithm without any code, because I've interviewed a disturbingly large number of candidates who cannot write about 10 lines of mostly-bug-free code with a single state variable and like one loop, in 30+ minutes.