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

141–150 of 547 posts

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

#141

Post by ajuc »

eru wrote: post #127
ajuc wrote: post #100

Earlier quoted context omitted.

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…

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.

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

#143

Post by zelly »

thaumasiotes wrote: post #46
james_s_tayler wrote: post #8

Earlier quoted context omitted.

Can you not study Ravens progressive matrices?

You can; validity drops severely for testees that are familiar with the problems. (The set of problems is not large.)

Sounds like leetcode questions

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

#144

Post by throwawayiionqz »

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

The "better" recursive solution computes fib(n) and fib(n-1) at the same time. Linear time recursion!

    def f(n):
        if n

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

#145

Post by dotancohen »

Smaug123 wrote: post #111
dotancohen wrote: post #77

Earlier quoted context omitted.

Serious request, as a developer who would probably code a naive Fibonacci that doesn't meet your standard: Could you provide a code sample that does meet your standard? This looks like an important learning opportunity for me. Thanks.

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.

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

#146

Post by dotancohen »

eru wrote: post #127
ajuc wrote: post #100

Earlier quoted context omitted.

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…

True, but then the "worker" fib() method should be called fib_calculate() and should be wrapped by fib() which then returns a single integer.

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

#147

Post by kristopolous »

zozbot234 wrote: post #37
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…

If so, they're pushing "conformity" and "being a good cog in the machine" well past the point of cargo cult programming. That's what this algorithm-based interviewing is all about: a textbook cargo cult. And people wonder why they aren't seeing quality.

I'm not so sure. Maintaining and building an empire are dramatically different.

Companies that could build and not maintain: Lotus, Digital Research, Palm, Netscape, MySpace, Digg, Blackberry, Ashton Tate, it's a different set of skills. Heck, you can even toss the French Jacobins in there

They all shot themselves in the foot, I know, that's the point. Not having their eye on the ball and instead looking over the horizon is what built the empire, but then the ball hit their nose

Some people can do both (gates, zuck, bezos), but once you're at the Apple/Microsoft stage, you need the second group.

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

#148

Post by dotancohen »

throwawayiionqz wrote: post #144
ajuc wrote: post #100

Earlier quoted context omitted.

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

The "better" recursive solution computes fib(n) and fib(n-1) at the same time. Linear time recursion! def f(n): if n

You have a bug for the case of fib(0).

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

#149

Post by WJW »

wadkar wrote: post #61
deadgunslinger wrote: post #53

Earlier quoted context omitted.

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.

There should be a fourth level where they use the closed form solution to get to the solution they want without any recursion or looping for reasonable values of N. Maybe even a fifth level using the O(log(N)) matrix exponentiation method.

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

#150

Post by haggy »

tchaffee wrote: post #78
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…

I already don't want the job because of the interview process. Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal. You should be doing everything you can to put the candidate on their own turf and letting them shine. I have a lot of advice about interviews but one of the best I've heard over the years: whatever impres…

I agree with this 100%.

I'd also like to add that because of this I adapted the traditional whiteboarding exercise at my current company to be about problem solving and design, and not about how many data structures you've memorized.

When a candidate comes in, I give them a fake-yet-realistic product requirement (like count elements in a real-time stream from field sensors) and let them run with it however they see fit. I put zero restrictions on the tech side of things in order to let the candidate shine (hopefully) in whatever tech they are most comfortable with.

I make sure to ask for feedback on the exercise and I've gotten all positive feedback from candidates.

Post reply on HN