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

121–130 of 547 posts

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

#121

Post by eru »

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 :)

It depends on how you measure.

If you can do arbitrary precision arithmetic (including powers and square roots) in unit time, this one is fastest.

In practice, this algorithm is not the fastest, because handling arbitrary precision floating point numbers is a pain.

Have a look at the matrix exponentiation algorithm for Fibonacci numbers in http://pages.cs.wisc.edu/~mhock/SSL/fibcalc.pdf

You can implement the matrix exponentiation via repeated squaring recursively even in a language like Python that doesn't do tail call optimization, and it will still be fast: your recursion only goes to a logarithmic depth.

In any case, recursion vs iteration is an implementation detail. Especially if your language supports tail call optimization. Have a look at this example:

    f(0) := (0, 1)
    f(n) := let (a, b) = f(n-1) in (b, a + b)
f is recursive function over tuples of integers. And f is basically equivalent to the typically iterative algorithm for computing Fibonacci numbers.

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

#122

Post by parentheses »

algo questions come in many forms. it is a problem space that devs can focus on when preparing for interviews. it side-steps integration issues that occur in real world problems like "implement an HTTP server" or "implement a multi-host parallelization framework".

even though real world problems are better interview questions, they suffer from requiring more candidate/interviewer prep. they can also stall out due to integration/machine/etc issues

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

#123

Post by kristopolous »

akkawwakka wrote: post #38
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…

Whenever I interview engineers, my main priority, beyond grasping whether they understand the stack they’ll be working with, is gauging how well they can work in an organization of fellow engineers, designers, and product folks to deliver a product and support the larger engineering team. If they can pass that hurdle, you can almost be certain they know how and when crack open an algorithms textbook or use Google-fu…

I internally have something I call the "scramble score". If I hire someone to say, do some python backend and then a few weeks in I'm like "oh shit, actually this big deal we're doing needs us to get an iphone app together" and I can be like "hey, can you go from python backend to do an iphone app?" and a week or so later I'd have a basic app.

Those people do exist. Really, they think it's a thrilling joyride. Hard to find, but they're real. I look for those and run the team tight and small.

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

#124

Post by eru »

Smaug123 wrote: post #113
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?

I, for one, prefer recursion to explicit iteration in most cases. Anyway, if you were going to write the answer in Haskell, it's a three-liner and it's recursive.

Why do you need so many lines?

    fib = 1 : zipWith (+) (0 : fib) fib

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

#126

Post by blackrock »

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…

Are you hiring for first year beginners? Or is this also a test for your senior software engineers?

Your question topics are completely useless to normal software engineering work. And this proves how immature your company is, in understanding the nature of the work.

Perhaps you should consider asking them instead, what their technique is to ensure reliability, throughout, and redundancy in their code? Can they make their code self-heal itself? Or to make some minor decisions to restart itself, if optimal conditions are not met.

You know.. basic software engineering stuff.

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

#127

Post by eru »

ajuc wrote: post #100
dotancohen wrote: post #79

Earlier quoted context omitted.

> 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

Of course, recursion vs iteration is mostly an implementation detail. Here's a recursive version (expressed in Python) that works better than your loop:

    def fib(n):
      if n =
(I say it works better, because it has the same asymptotic runtime, but fails better: When numbers get large, your C version will run into undefined behaviour that can cause arbitrary problems. The Python version will just crash with a well-defined exception.

A better language than Python can run this recursive version for arbitrarily big numbers.)

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

#128

Post by theelous3 »

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…

Making people write code on paper is just ridiculous - way outside of testing and checking reality - and your reasoning of

>"because it shows that they know how to think about code"

means nothing at worst, and at best indicates you'll only be happy to work with people who are replicas of yourself.

Take home is the way to go, unless the position is some sort of public exhibitionist analogue developer position.

The least I think you can do is move from paper to machine, and inform them they should bring their own machine, or offer them use of one with many envs preconfigured.

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

#129

Post by eru »

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.

Well, I was using less horsepower.

The problem in the previous solution was that it took a while to keep the fancy datastructures updated. (It's a globally replicated distributed system..)

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

#130

Post by charlus »

varbhat wrote: post #114

Which are the best books to learn Data Structures and Algorithms ? (Or which books did you use/recommend to learn Data Structures and Algorithms?)

Cormen - Introduction to Algorithms (CLRS) is probably the most recommended.

Depending on where you are starting from, MIT opencourseware lectures might be helpful too.

Post reply on HN