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

Post by ivanhoe » Wed, Jul 15, 2020, 2:13 PM UTC

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…

Post by crimsonaluca20 » Wed, Jul 15, 2020, 2:18 PM UTC

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!

  fib :: int -> int
  fib 0 = 1
  fib 1 = 1
  fib n = fib (n - 1) + fib (n - 2)

  fib :: int -> int
  fib n = let _fib 0 a b = a
              _fib 1 a b = b
              _fib n a b = fib (n - 1) b (a + b) 
          in _fib n 0 1

Post by dhsysusbsjsi » Wed, Jul 15, 2020, 2:22 PM UTC

vishbar wrote: post #97

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.

Post by chrisparnin » Wed, Jul 15, 2020, 2:23 PM UTC

whack wrote: post #228

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

Post by [deleted] » Wed, Jul 15, 2020, 2:26 PM UTC

ojr wrote: post #236

whack wrote: post #228

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

- Retention. If this person spent hours on leetcode, they’ll be less likely to leave the job knowing the effort it takes to get through the gate