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

#211

Post by jihadjihad » Wed, Jul 15, 2020, 1:48 PM UTC

mumblemumble wrote: post #197

eru wrote: post #64

A few years ago I spend lots of time and effort at Goldman Sachs solving a performance problem in a major part of their internal cloud infrastructure. The programme in question was running into performance problems, and a few smart people had already banged their head against a wall solving them. After lots of experiments and different approaches, my solution was to remove most of the advanced data structures that we…

Eric Lippert did a nice blog post on this sort of thing a few months ago: https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.

I think one of the main takeaways of his post is that anything is survivable when n is small, and that the overhead required to spool up more robust data structures just isn't worth it for small n.

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

#212

Post by ricksharp » Wed, Jul 15, 2020, 1:48 PM UTC

ricksharp wrote: post #193

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…

This sounds like an inspection of whether the person has had a class in basic algorithms rather than if they have ever coded anything in real life. In school I played with sorting algorithms, in business if I ever found a developer manually writing a sorting algorithm, I would consider them inept (unless there were very specific reasons to do so). If someone didn’t know how to sort a list using the built in or standa…

In fact now that I think about it, it might be a good test to see if they are passionate enough to be a great problem solver:

When was the last time you wrote a sorting algorithm?

Acceptable answers:

- You mean sorting a list? - In school - Why would I write a sorting algorithm? - Never - (Glazing eyes and other body language that indicates frustration)

Red Flags:

- Anything that indicates they think writing a sorting algorithm is a perfectly logical thing to do during the course of software development.

(Note: The problem is sorting may seem like a well-understood problem, but it’s actually not. Only a person who studied the algorithms in school as an assignment would feel comfortable with that code.)

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

#213

Post by agentultra » Wed, Jul 15, 2020, 1:48 PM UTC

I think they're useful to know. I don't mind algorithms and data structure questions in interviews. I use them a fair bit even in some of my most benign, enterprise JSON-schlepping tasks.

Indexes come up a bit. I've seen many junior engineers struggle when performance problems crop up over time. If they don't have a familiarity with data structures and algorithms their "fixes" never seem to work and they get frustrated. I enjoy taking the time to show them how indexes can speed up search and when they don't give you much benefit. At small companies getting off the ground I think it's less important to hire people for their algorithms/data-structures knowledge.

At companies where the teams are working on high-performance or large scale problems it's quite essential. Being able to shave down build times, as in the article, is a big deal. Knowing how to scale a large problem is a big deal when the quality of the service depends on it.

There are also some problems that require it. I'm building a key-value data store as one of my side projects and it definitely requires knowledge of data structures and algorithms. You can't even implement one efficiently without such knowledge!

So I guess it depends on how much your team actually works with these concepts. If your hiring process is keeping the bar high but all you do is schlep JSON from one bucket to another you're missing out on a lot of good candidates for no good reason. If you're building networking products or databases then yeah, keep the bar high.

But within reason. I agree with the OP -- the need for exotic structures and algorithms is so rare that it's not a terribly good indicator of anything to use them in an interview unless you're looking for researchers.

update: spelling.

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

#214

Post by Taek » Wed, Jul 15, 2020, 1:49 PM UTC

tchaffee wrote: post #78

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 already don't want the job because of the interview process. Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal. You should be doing everything you can to put the candidate on their own turf and letting them shine. I have a lot of advice about interviews but one of the best I've heard over the years: whatever impres…

Talking about code that someone has already written is missing the element of productivity. Since we pay you by the week and only get so many hours a week out of you, we need some way before we hire you to understand what type of output we can expect.

The best way I know would be to work with someone for a week or two on a real problem, but that's way too expensive to trial a junior role.

At least for us, the system is more optimized around avoiding false positives than ensuring we don't pass over someone good.

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

#215

Post by sushshshsh » Wed, Jul 15, 2020, 1:49 PM UTC

tchaffee wrote: post #78

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 already don't want the job because of the interview process. Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal. You should be doing everything you can to put the candidate on their own turf and letting them shine. I have a lot of advice about interviews but one of the best I've heard over the years: whatever impres…

Good thing you don't want it because I'll happily take it.

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

#216

Post by sushshshsh » Wed, Jul 15, 2020, 1:51 PM UTC

Taek wrote: post #214

tchaffee wrote: post #78

Earlier quoted context omitted.

I already don't want the job because of the interview process. Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal. You should be doing everything you can to put the candidate on their own turf and letting them shine. I have a lot of advice about interviews but one of the best I've heard over the years: whatever impres…

Talking about code that someone has already written is missing the element of productivity. Since we pay you by the week and only get so many hours a week out of you, we need some way before we hire you to understand what type of output we can expect. The best way I know would be to work with someone for a week or two on a real problem, but that's way too expensive to trial a junior role. At least for us, the system…

Your current system is better. I'm happy to take 15 minutes of my life to prepare for your interview instead of 1 week.

Since the denial rate in our industry is so high, you can see which one is more preferable.

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

#217

Post by eru » Wed, Jul 15, 2020, 1:51 PM UTC

mumblemumble wrote: post #197

eru wrote: post #64

A few years ago I spend lots of time and effort at Goldman Sachs solving a performance problem in a major part of their internal cloud infrastructure. The programme in question was running into performance problems, and a few smart people had already banged their head against a wall solving them. After lots of experiments and different approaches, my solution was to remove most of the advanced data structures that we…

Eric Lippert did a nice blog post on this sort of thing a few months ago: https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.

> The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.

I'd say _some_ algorithms and data structures with great theoretical characteristics tend that way. Just as many other work great in practice as well. You have to measure and benchmark.

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

#218

Post by collyw » Wed, Jul 15, 2020, 1:52 PM UTC

bananaface wrote: post #86

I don't like algorithms as an interview structure but I do think they have one property that people way underestimate. Algorithms test your ability to manipulate a complex problem in your head without being able to break it down. Most coding problems can be broken apart and the individual components tackled one by one. But that has two problems. One, it doesn't stress-test the programmer. Two, the most beneficial cha…

The problem I have with algorithms is I can get good at them if I practice them all the time - basically like I did at university 20 years ago. I have barely used them in real jobs since, so while I write far better (more readable maintainable, performant) code now, I am far worse at answering this stuff in an interview.

Also a number of times I haven't got an answer in an interview only for something to pop into my head ten minutes out of the door (or a far more elegant solution came to me). You might as well toss a coin and save me the hassle.

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

#219

Post by spaetzleesser » Wed, Jul 15, 2020, 1:52 PM UTC

jihadjihad wrote: post #211

mumblemumble wrote: post #197

Earlier quoted context omitted.

Eric Lippert did a nice blog post on this sort of thing a few months ago: https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.

I think one of the main takeaways of his post is that anything is survivable when n is small, and that the overhead required to spool up more robust data structures just isn't worth it for small n .

I often find that the actual number that could be called “Small” in this sense is often quite large. Computers are very fast these days.

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

#220

Post by tsimionescu » Wed, Jul 15, 2020, 1:53 PM UTC

ricksharp wrote: post #193

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…

This sounds like an inspection of whether the person has had a class in basic algorithms rather than if they have ever coded anything in real life. In school I played with sorting algorithms, in business if I ever found a developer manually writing a sorting algorithm, I would consider them inept (unless there were very specific reasons to do so). If someone didn’t know how to sort a list using the built in or standa…

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 problem and in real life you should use a library. But you will not find a library for each problem you encounter, and sorting is a very simple problem to solve compared to anything you'll find in real life.