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

Post by ajuc » Wed, Jul 15, 2020, 12:14 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!

Post by pizza_worker » Wed, Jul 15, 2020, 12:18 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 Pmop » Wed, Jul 15, 2020, 12:30 PM UTC

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…

Post by tzs » Wed, Jul 15, 2020, 12:40 PM UTC

dominotw wrote: post #167

giomasce wrote: post #4

I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never used outside programming competitions. The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far you…

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/

  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 write like this
  in near real time.

  You get to the end of a line, find that you're
  just a little long or short, and you backtrack
  just a couple words or so most of the time and
  you can usually find a way that works. In this
  paragraph, for instance, I was one too long in
  the first line, but contracting "you are" down
  to "you're" fixed it. I was short in that last
  sentence, but inserting "down" fixed it.

  Perfect justification by inserting extra space
  is for amateurs.

  Now we've got all fancy and use variable width
  fonts and automatic wrapping and posting isn't
  quite as fun anymore.

  Give it a try. Use an editor with a fixed font
  to compose your next post and try to get it to
  come out perfectly justified without having to
  insert extra spaces. When you paste it into HN
  that will get lost, but the composing can be a
  fun little English puzzle.

Post by pps43 » Wed, Jul 15, 2020, 12:54 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…