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

71–80 of 547 posts

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

#71

Post by WalterBright »

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…

At Caltech, we'd call that "brute force and ignorance" which is often the best solution.

For example, Enzo Ferrari once said that the secret to better performance is more horsepower.

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

#72

Post by WalterBright »

rimliu wrote: post #69
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…

If you use recurssion for Fibbonacci, you do not understand neither recurrsion nor Fibbonacci.

"You, Sir, are employing a double negative." -- Mr. Spock

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

#74

Post by entha_saava »

suyash wrote: post #34

I've used Sort method several types both in Java and JavaScript but they way it's used it as a library function, I don't need to write my own sorting algorithm. Same for Data Structure commons ones I've used are found in Java Collections - ArrayList, LinkedList, HashMap, Set etc. For Deep Learning have used several algorithms that are best practices and common data structures like Tensors and Vectors. I realize the v…

The point is, they should not actually require candidates to recall these things from memory. But there is certainly value in the non-memorization part of this knowledge and the ability to solve this kind of problems distinguish people who can think from those naive jobsworths. If nothing, they are better than back-of-the-newspaper if-you-have-seen-the-answer-you-know-the-answer kind of trick questions.

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

#75

Post by deepGem »

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 think someone's ability to understand and explain recursion like am a child is very undervalued. It's not about testing whether you know the base case or the fact that you write less lines of code in recursion but the fact that there is a built-in stack for you to use without creating one.

What are the practical applications of recursion though ? Other than sorting and DFS ( well even DFS can be done iteratively with stacks ). I'll be curious to know.

I find testing for HashTable/HashMap knowledge to be far more practical than testing for LinkedLists simply because you can't escape HashTables in today's world.

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

#76

Post by pintxo »

eru wrote: post #60
pintxo wrote: post #3

It’s an interesting question why we focus so much on algorithms that are mostly not used on a day to day basis, but the topic of persistence that’s everywhere and which is often only partially understood is far from being this prominent. I remember a stint in research, about data analytic non the less, where rarely anyone had a good grasp of SQL or any other way to persist data for that matter. It really puzzles me t…

Be careful, 'persistent' is used with different meanings in different contexts. See eg https://en.wikipedia.org/wiki/Persistent_data_structure and immediately notice the warning 'Not to be confused with persistent storage.'

Thanks, I usually refer to them as immutable, haven't actually come across the term persistent for these, but seems sensible.

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

#77

Post by dotancohen »

wadkar wrote: post #61
deadgunslinger wrote: post #53

Earlier quoted context omitted.

How do you figure from a Fibonacci exercise that the candidate understands recursion? It's 5 lines of code to memorize.

By the way they discuss the implementation. First level is ensuring that base cases are covered (i.e. correct implementation of recursion) Second level is how they explain the simple recursion that’ll hit stack limits (i.e. without tail recursion) Third level is using accumulator/tail recursion. See how they can express these ideas and are they able to effectively communicate their intentions.

Serious request, as a developer who would probably code a naive Fibonacci that doesn't meet your standard: Could you provide a code sample that does meet your standard? This looks like an important learning opportunity for me. Thanks.

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

#78

Post by tchaffee »

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 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 impression you have of the candidate try to prove yourself wrong. Using that advice, I've found a lot of great programmers that other companies skip over. Some people who are great at coding are bad at interviews and bad at live problem solving with an audience. If you really feel the need for a test, a paid take home coding assignment will give you the best signal.

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

#79

Post by dotancohen »

bbarn wrote: post #54
fanf2 wrote: post #41

Earlier quoted context omitted.

Why would anyone use recursion to calculate Fibonacci numbers other than as a microbenchmark for function call performance?

It's a great showcase of how a flashy looking solution is the wrong approach. A good candidate will know it can be written in 2 lines recursively, but that the stack will explode with a fairly low term number, and that iterating with a for loop is more efficient.

> iterating with a for loop

I'm struggling to understand what you mean? This is a learning opportunity for me, if you wouldn't mind posting a code sample or elaborating further.

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

#80

Post by entha_saava »

p1necone wrote: post #68
entha_saava wrote: post #52

Earlier quoted context omitted.

To filter out naive people that don't have proper understanding of fundamentals and just having some framework plumbing knowledge, I guess. These are considered pretty basic stuff that every programmer should know..

In my experience it's pretty necessary to do this. Probably depends on your local job market, but there are a shocking number of candidates that just don't know how to code. The explanation I've heard is that good devs generally get hired after only a handful of interviews, whereas really bad devs are going to do a lot more interviews on average before they get hired, so you get a pretty skewed sampling even if there…

Yes, Joel Spolsky and IIRC Jeff Atwood have written somewhat extensively about it.

We are in a bubble, if we read programming blogs and think about programming in our free time, we are definitely not the kind that FizzBuzz exists to filter out. But from the perspective of companies, it makes sense if they really understood pointers or recursion or graph manipulation, because there are so many people lying on their resumes, not having sufficient analytical skills despite doing some resume driven cargo cult development etc.. And as an industry we don't really have an alternative to these algorithm interviews at scale, at the point we rely on non technical HR people to filter out resumes for us and they literally grep for framework/language experience.

Post reply on HN