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

#61

Post by wadkar » Wed, Jul 15, 2020, 9:10 AM UTC

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.

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.

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

#62

Post by kristopolous » Wed, Jul 15, 2020, 9:11 AM UTC

paxys wrote: post #39

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…

This is like how every second kid in high school goes "I get bad grades because I'm too smart".

Not at all. it's a different kind of job for a different kind of person.

Fabrice Bellard, Ted Nelson, Theo de Raadt, Patrick Volkerding, Richard Stallman, Larry Wall, these people aren't off working at stable ibm-like firms. It's a different kind of thing. Look at Nelson's fiery career crash when he worked at Autodesk. Look at Woz and Paul Allen walking away or Bushnell getting rid of Atari. This isn't the grab-and-dash modern unicorn stuff, these people saw it wasn't right for them. The company outgrew them.

They couldn't do the job. That's not where they fit.

Chefs make terrible bus boys and bus boys make terrible chefs.

That's the big important lesson: The Chef is incapable of being a bus boy.

It's not "too easy for her" and she's not "too smart for it". The chef can't consistently, reliably, and efficiently do the tasks. The hierarchy is illusory, it's all about fit.

Drucker explains this better than I ever could. He's a good read

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

#63

Post by lootsauce » Wed, Jul 15, 2020, 9:11 AM 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…

This sounds like a reasonable approach and that is why software interviews remain broken. I'm sure it works for your organization, not saying you are bad at hiring or anything but it still smacks of the kind of hoop-jumping that turned me off so much from the process last time I was interviewing. This included on-the-spot coding exercises, massive take-home projects that required many hours of undifferentiated grunt work, totally useless whiteboard sketching and pseudo-code sessions, obscure Google-like quiz questions.

The interview process for the job I have now was a massive breath of fresh air.

The application asked for code samples and a cv. It was a small company and the CEO, CTO and direct co-workers all drove the interview process. The process was entirely conversational. First an intro phone call with the CTO and then a questionnaire via email in which I answered about 30 questions on various topics that were all very practical daily software development type stuff. It was painless to respond to each with about a paragraph in detail. Then a call with a direct co-worker about the questionnaire and this was my opportunity to ask questions of him about the company. Before getting the interview they actually read my code samples and reviewed my Github account. In the interview there was a ton of discussion about the company, its culture and all the of the above discussions. Following this was compensation negotiation with the CEO.

Everything about the hiring process said to me yes this is the place, they get it!

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

#64

Post by eru » Wed, Jul 15, 2020, 9:14 AM UTC

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 were in the code.

In theory, they should have given us logarithmic runtime on some common operations, but the constant factors were too large. I proved (in the mathematical and the practical sense) that a brute force scheme combined with a careful randomization would dramatically improve real world performance with a fraction of the previous line count.

Despite me removing those interesting data structures, I still count it as a great application of my algorithms-and-data-structures knowledge: a big part of expertise is to be able to spot opportunities for simplification.

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

#65

Post by saos » Wed, Jul 15, 2020, 9:15 AM UTC

What a satisfying read.

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

#66

Post by ajuc » Wed, Jul 15, 2020, 9:18 AM UTC

eru wrote: post #57

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?

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

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

#67

Post by ajuc » Wed, Jul 15, 2020, 9:22 AM UTC

arethuza wrote: post #40

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…

"write out these problems on paper" I write on paper so infrequently that I actually find it pretty difficult to write more than a few words. I certainly wouldn't want to write something out longhand in an interview! Edit: It seems to me it would be rather unfair of me to ask people to write out their thoughts in Org Mode in VS Code just because that's how I happen to like writing notes :-)

Writing speed isn't the bottleneck hopefully :)

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

#68

Post by p1necone » Wed, Jul 15, 2020, 9:23 AM UTC

entha_saava wrote: post #52

the_mitsuhiko wrote: post #50

Earlier quoted context omitted.

> I like having candidates write out these problems on paper because it shows that they know how to think about code. Is this really a useful exercise? Why not present them with an actual problem that is relevant to your field and see how they approach it?

To filter out naive people that don't have proper understanding of fundamentals and just having some framework plumbing knowledge, I guess. These are considered pretty basic stuff that every programmer should know..

In my experience it's pretty necessary to do this. Probably depends on your local job market, but there are a shocking number of candidates that just don't know how to code.

The explanation I've heard is that good devs generally get hired after only a handful of interviews, whereas really bad devs are going to do a lot more interviews on average before they get hired, so you get a pretty skewed sampling even if there aren't that many really bad candidates around.

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

#69

Post by rimliu » Wed, Jul 15, 2020, 9:24 AM 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…

If you use recurssion for Fibbonacci, you do not understand neither recurrsion nor Fibbonacci.

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

#70

Post by WalterBright » Wed, Jul 15, 2020, 9:27 AM UTC

namdnay wrote: post #15

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…

Completely agree. The only thing that's important is knowing what to google for. i.e. being able to map from a real world problem to one or several algorithm/structure classes.

> The only thing that's important is knowing what to google for.

It's even more important to recognize when the solution found with google is subtly wrong.