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

91–100 of 547 posts

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

#91

Post by foota »

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…

It doesn't matter how well you can optimize if you don't measure in production and benchmark!

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

#92

Post by ForHackernews »

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.

Fibonacci has a closed-form solution! Forget writing loops, you can write one damn equation. Runs in constant time.

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

#93

Post by ForHackernews »

ajuc wrote: post #66
eru wrote: post #57

Earlier quoted context omitted.

Because it's the most straightforward implementation in many languages? (And you can also use recursion in the fastest implementations. You just wouldn't use the naive recursive solution.)

Fastest implementation is one non-recursive equation (which I had to look up) :) fib(n) = (((1 + sqrt(5)) / 2)^n - ((1 - sqrt(5)) / 2)^n) / sqrt(5) I even understood, once, how to arrive at the magic numbers :)

Derivation is here http://mathonline.wikidot.com/a-closed-form-of-the-fibonacci...

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

#94

Post by karolist »

WalterBright wrote: post #71
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.

The actual quote was something like "aerodynamics are for people who can't build engines" which proves your point a bit better.

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

#95

Post by kristopolous »

zodiac wrote: post #87
kristopolous wrote: post #32

Let's say someone can solve the algo problem, what's that show? Mostly that they prepared for an algorithms question. It may be a good filter for 3rd-wave do-as-you're told programmers who stay in their lanes, produce by the book expected code, and just consistently obediently build things. They wan better cogs for the corporate software machine. If people are asking me algo questions, the job probably isn't right fo…

What does this have to do with the bulk of the article (which is about algorithms the author used at his jobs, and only tangentially (IMO) about the use of algorithmic questions in interviews)?

It has to do with the rest of the comments in this thread at the time I posted it ... I was replying to that sentiment.

The vast majority of algorithms I use are for parallelizing complex workloads, failure detection, and scoring systems. I usually DIY after I find the OTS ones unsatisfactory.

I'm not "smarter", they're general solutions but all I seem to have in life are specific problems so specific solutions perform better.

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

#96

Post by enriquto »

ajuc wrote: post #66
eru wrote: post #57

Earlier quoted context omitted.

Because it's the most straightforward implementation in many languages? (And you can also use recursion in the fastest implementations. You just wouldn't use the naive recursive solution.)

Fastest implementation is one non-recursive equation (which I had to look up) :) fib(n) = (((1 + sqrt(5)) / 2)^n - ((1 - sqrt(5)) / 2)^n) / sqrt(5) I even understood, once, how to arrive at the magic numbers :)

While your formula is correct, it is not an actual implementation. How many digits of the square root do you need to compute exactly for being sure that the value of the power does not change?

Whether this is "fast" or not depends a lot on the concrete implementation of your arbitrary-precision real numbers.

As a nice thing, the second term (after the first minus sign) is smaller than 1, so you can omit it by rounding the result to the nearest integer; all the game happens in the first term.

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

#97

Post by vishbar »

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…

Due to the physical architecture of CPUs/etc., data structures that have "worse" asymptotic performance are often quite a bit faster than those with "better" performance. For example, iterating through a small array to find an item and test for existence is often quite a bit faster than using a hash set for the same operation.

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

#98

Post by tchaffee »

veselin wrote: post #43

For interviewing, I find it most useful if we ask a question that is an algorithmic problem to solve (but we don't tell them it is a graph problem and obviously it's not something as classic as Dijkstra). Then we observe if the candidate can formulate it as such, or can formulate it as anything useful (often there are several options, e.g. some find the problem to be dynamic programming). This gives much more informa…

False negatives is right. You're skipping over a lot of good engineers with this approach and you'd have to interview fewer people if you could avoid that. How many times even without the pressure of an interview have I been stuck on what seems like a hard problem and then I go for a walk and end up running home because the lightbulb goes off and I can't believe how "stupid" I was and how simple the problem was.

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

#99

Post by mFixman »

deadgunslinger wrote: post #53
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…

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

I think it's the O(log n) algorithm that uses matrix exponentiation to find out the n'th Fibonacci number.

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

#100

Post by ajuc »

dotancohen wrote: post #79
bbarn wrote: post #54

Earlier quoted context omitted.

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.

Something like this (might be subtly wrong, I wrote it in 2 minutes).

    int fib(int n) {
       if (n
vs recursive solution which is pretty but slow (and will fail when you run out of stack)

    int fib(int n) {
       if (i
Post reply on HN