Data structures and algorithms I actually used while working at tech companies • Hacker News Board

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

#201

Post by eru » Wed, Jul 15, 2020, 1:38 PM UTC

ajuc wrote: post #171

eru wrote: post #164

Earlier quoted context omitted.

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!

I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC. And I instinctively distrust Sufficiently Smart Compilers ;)

Oh, your compiler doesn't have to be sufficiently smart. It merely has to avoid premature optimization: see this classic paper https://dspace.mit.edu/handle/1721.1/5753 by Guy Steele.

> I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC.

I guess that's the same overhead as in this imperative version:

    a, b = 0, 1
    for _ in range(n):
      a, b = b, a + b

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

#202

Post by mumblemumble » Wed, Jul 15, 2020, 1:38 PM UTC

Being able to use algorithms and data structures, which what this article mostly talks about, is rather a different thing from knowing how to implement them, which is what interviews go after.

That said, the only algorithm that I'm convinced that every single programmer needs to know by heart is state machines. Because using them can often save you a lot of code and complexity. And because you really have to know them well to recognize spots where they would be useful. And because using an off-the-shelf library to implement them is, for most use cases, more complicated, more time-consuming to implement, and less readable than a little light hard-coding.

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

#203

Post by dominotw » Wed, Jul 15, 2020, 1:38 PM UTC

> come up with simple ones on your own, like a greedy one.

Greedy alogrithms are simple to come up with in an interview, Yes. But they are often wrong and even if they are right there is no way to know that, unless you construct a mathematical proof.

I would highly advice not using greedy in an interview since coming up with a solid proof in 15 mins is not really possible in all but simple cases.

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

#204

Post by Taek » Wed, Jul 15, 2020, 1:39 PM UTC

dotancohen wrote: post #145

Smaug123 wrote: post #111

Earlier quoted context omitted.

Instead of recursing twice, recurse once, by carrying around not fib(n-1) but the pair (fib(n-2), fib(n-1)).

True, but then the "worker" fib() method should be called fib_calculate() and should be wrapped by fib() which then returns a single integer. I believe that breaks the spirit of the question.

Really it's about this type of discussion. Already with your 'but then' you are showing that you know your way around a program.

I'd still have you write the full thing out, but I'm guessing you'd do just fine.

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

#205

Post by eru » Wed, Jul 15, 2020, 1:39 PM UTC

ourlordcaffeine wrote: post #185

nostrebored wrote: post #137

Earlier quoted context omitted.

This was the focus of my advanced algorithms course at Georgia Tech in my senior year. We had basically a full semester on random algorithms, and I remember walking out each day feeling like the fancy algorithms I'd memorized the previous year were a bit less glamorous. The number of algorithms that removed multiple complicated stateful steps with 'and we randomly select an element from the array' was mindblowing. As…

Do you know any good books or resources to read up more on random algorithms?

See eg https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-n...

And https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor... describes one of my favourite algorithms.

https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf is also interesting.

You can find a lot of good material just via Google, actually.

If you read the likes of The Art of Computer Programming for breakfast, you might like 'The Discrepancy Method - Randomness and Complexity' available at https://www.cs.princeton.edu/~chazelle/pubs/book.pdf But it's not for the faint of heart.

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

#206

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

nipxx wrote: post #21

As sad as it is, I get 90% of my algorithm work done with sorted arrays and binary search. Rarely I need more fancy stuff.

I sometimes suspect that everything is really just a sorting problem.

For example, here is a shell script that takes an input file consisting of lines of the form

X Y

where X and Y are integers representing the X and Y coordinates of live cells in a Conway's Life grid, and outputs the next generation in the same format. It runs in O(n log n) where n is the number of live cells, and it is really just sorting.

  > alive.$$
  while read cells
  do
      echo $cells >> alive.$$
      set x $cells
      x=$2
      y=$3
      echo $x $((y-1))
      echo $x $((y+1))
      echo $((x-1)) $((y-1))
      echo $((x-1)) $y
      echo $((x-1)) $((y+1))
      echo $((x+1)) $((y-1))
      echo $((x+1)) $y
      echo $((x+1)) $((y+1))
  done | sort | uniq -c > neighbors.$$
  grep '^ *3'  has2.$$
  sort alive.$$ -o alive.$$
  comm -12 has2.$$ alive.$$
  rm has2.$$ neighbors.$$ alive.$$

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

#207

Post by TedDoesntTalk » Wed, Jul 15, 2020, 1:40 PM UTC

tchaffee wrote: post #90

wadkar wrote: post #61

Earlier quoted context omitted.

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.

In my decades of programming I've never had to seriously consider these issues. I have used recursion and have written some pretty deep stuff like cryptography and writing my own interpreter (for a business - not a school project). I've even implemented recursion in a language that didn't support it. I have read about tail recursion several times. I still barely remember what it is. But I know a few books to reach fo…

I’ve worked with some interviewers who are out to prove they are smarter than the candidate because they remember a bit of something that the candidate does not.

Only when the interviewer finds someone “smarter” than himself does he approve of hiring the candidate.

It is an ego game.

Perhaps this describes OP.

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

#208

Post by ausjke » Wed, Jul 15, 2020, 1:40 PM UTC

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…

It does not matter how us think, I believe these detail-oriented algorithm interviews are intentionally designed for younger coders who can still do them out of memory, though in practice they're not very meaningful and if you really need them sometime you can always dive-in and get what you need.

I'm doing leetcode now, as a senior engineer there is no way to get a decent job without being tested like a college fresh-out as far as programmer positions are concerned, no complains, I will do them, it is the market picks me, not the other way around.

To me even though this is painful, but at least it is "merit-based", what I dislike the most is that you got a job based on other factors instead of how able you are.

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

#209

Post by dominotw » Wed, Jul 15, 2020, 1:45 PM UTC

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…

you don't need to know algorithms with somone's name on it for an interview but there are few exceptions,

1. Dijkstra's 2. Kadane's 3. Bellman ford - negative edges

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

#210

Post by woadwarrior01 » Wed, Jul 15, 2020, 1:48 PM UTC

In this case, this was implementing the AES standard.

Sounds like a terrible case of NIH. Why (re)implement AES when you've got battle tested implementations from OpenSSL, NaCL and practically any OS provided crypto APIs?