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

221–230 of 547 posts

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

#221

Post by eru »

Pmop wrote: post #175
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…

I've learned approaches like this when I took a Operations Research class. I found it all exciting. We've also learned techniques to better choose between meta-heuristics like CGRASP, or flat algos, or integer programming, and so on. Now I'm seeing if I can think of some cool pet project where I can apply this stuff.

Oh, I also applied lots of linear and integer programming.

The main benefit of something like integer programming is that you get a clear separation of the specification of your solution and the algorithm that computes it.

When even smart people naively attack any kind of optimization (or selection) problem, the resulting approach often mixes the business logic for specifying the optimum solution and the code for finding that optimum.

That makes any change in business requirements very hard to implement.

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

#222

Post by craftinator »

ricksharp wrote: post #212
ricksharp wrote: post #193

Earlier quoted context omitted.

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

Acceptable answer: it depends on what I'm sorting. Is it a primitive like char strings, numbers, or a more complex data type? Could it have null values and type mismatches, am I using a strongly typed language? Does it need to be cleaned first?

I think the ability to come up with relevant and important questions to ask about the task given is more crucial than whether they can solve it. You can look up answers to questions from hundreds of good sources, but you need to be able to generate the right questions that need to be answered first.

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

#224

Post by tom_mellior »

eru wrote: post #164
ajuc wrote: post #141

Earlier quoted context omitted.

In practice iteration will be faster, even in Python (because there's less overhead). But yes, I should have written "naive recursive solution". There are many ways to fix it. It just wasn't what the question was about.

In Python, yes. If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) But, agreed with everything else you wrote!

> If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration.

The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.

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

#225

Post by raphlinus »

tzs wrote: post #177
dominotw wrote: post #167

Earlier quoted context omitted.

standard 'text justification' dp problem ? Eric's mit video on this : https://www.youtube.com/watch?v=ENyox7kNKeY leetcode https://leetcode.com/problems/text-justification/

(Apologies to people on mobile for the following...) One of the things I miss about Usenet was that nearly everyone read it with a fixed with font so that if you choose your phrasing well so as to make your text come out naturally perfectly justified, it would come out that way for them too. English has so many synonyms and near-synonyms for every word, and so much flexibility in the ordering of words that you can wr…

I read at one point that the typesetters at the New Yorker would work with the copy editors to fix cases of bad justification (huge word space, awkward hyphen). It's rare to see that kind of care, but automatic algorithms are getting better.

On topic to the original post, I implemented Knuth-style line breaking in the Android text stack (working with Anish Athalye who was an intern at the time and did the first prototype). There were a bunch of nicely tuned implementations of advanced data structures and algorithms in there.

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

#226

Post by ivanhoe »

dominotw wrote: post #209
ajuc wrote: post #10

I've used Dijkstra algorithm for calculating distance in a graph once. It was a highlight of that month. Of course I had to look it up(despite learning it and implementing it at university). Who remembers this stuff exactly after years of glueing libraries together? And even if you remember - won't you check it anyway just to be sure? It's OK to ask people general questions (what's algorithmic complexity, what kind o…

you don't need to know algorithms with somone's name on it for an interview but there are few exceptions, 1. Dijkstra's 2. Kadane's 3. Bellman ford - negative edges

IMHO all you need to know is to recognize a certain category of problems and remember that there is an appropriate algorithm for it - and if can you recall the name even better, will save you some time googling, but it's not that important. After consulting the documentation and if you previously learned it in a school/course, you'll be able to implement it in pretty much the same time as someone who knows how to draw it on a whiteboard from the top of their head.

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

#227

Post by no_wizard »

Taek wrote: post #22
ajuc wrote: post #10

I've used Dijkstra algorithm for calculating distance in a graph once. It was a highlight of that month. Of course I had to look it up(despite learning it and implementing it at university). Who remembers this stuff exactly after years of glueing libraries together? And even if you remember - won't you check it anyway just to be sure? It's OK to ask people general questions (what's algorithmic complexity, what kind o…

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’ve been interviewing at a lot of places lately. I _never_ white board interviewed before this round of interviews I’ve done And at first I have to say that I hated it so much.

In a weird way though, I’ve at least grown to understand why it’s so popular, and I don’t think it’s just because FAANGS do it (though I think that’s how it came to prominence). It boils down to showing as an engineer your capable of being flexible and malleable your change and understanding. Some places definitely do this better than others, and I think it says a lot about company culture if they are Adversarial about it or not. In my experience rather unfortunately even good places to work can be adversarial about it.

The massive downside is and always will be it puts so much onerous on the candidate because you don’t really know what they are going to ask and freezing up or getting stumped is very frowned upon in these style interviews from what I experienced.

My tip to anyone though is just to practice, but I’ve yet to encounter places that don’t employ some technique to test algorithmic thinking and understanding of complex systems in some way.

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

#228

Post by whack »

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 test that isolates and evaluates a specific set of skills, which you think are important to the organization.

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

#229

Post by onion2k »

Taek wrote: post #22
ajuc wrote: post #10

I've used Dijkstra algorithm for calculating distance in a graph once. It was a highlight of that month. Of course I had to look it up(despite learning it and implementing it at university). Who remembers this stuff exactly after years of glueing libraries together? And even if you remember - won't you check it anyway just to be sure? It's OK to ask people general questions (what's algorithmic complexity, what kind o…

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

...because you like working through problems on paper, and your interview process is designed to find people like you.

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

#230

Post by maaaaattttt »

craftinator wrote: post #222
ricksharp wrote: post #212

Earlier quoted context omitted.

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

Acceptable answer: it depends on what I'm sorting. Is it a primitive like char strings, numbers, or a more complex data type? Could it have null values and type mismatches, am I using a strongly typed language? Does it need to be cleaned first? I think the ability to come up with relevant and important questions to ask about the task given is more crucial than whether they can solve it. You can look up answers to que…

> you need to be able to generate the right questions

Completely agree with this statement.

I would add that having the proper vocabulary is an important part of generating the right questions.

Post reply on HN