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

531–540 of 547 posts

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

#531

Post by ashconnor »

cmrdporcupine wrote: post #301
tchaffee wrote: post #115

This article is an excellent example of why most companies should never ask about algorithms in an interview. The author has worked for elite companies and yet even there he rarely had to reach something advanced. I've worked on some cool and really hard stuff in my career including cryptography and a popular Facebook app where my team used a graphdb, etc, etc, etc. And I would fail at most of today's interviews. For…

Thank you. I've been poking around the job market again after 10 years not searching, and it's disheartening. I have 20 years software development experience, I work at Google, I'm no spring chicken. I'm not the best engineer in the world, I'm sure, but I am a good programmer. I think I'd be an asset in many jobs. But I just turned down proceeding with interviews at a certain payment processing company because in par…

You would think working at a top tier tech company like you are, would allow you to bypass this requirement.

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

#532

Post by tome »

Smaug123 wrote: post #527
eru wrote: post #521

Earlier quoted context omitted.

Oh, that version takes exponential time to compute. The one-liner I gave computes up to the n-th Fibonacci number in linear time.

Not in Haskell, it doesn't. Haskell stores everything for you, right?

No, it doesn't.

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

#533

Post by tom_mellior »

eru wrote: post #518
tom_mellior wrote: post #224

Earlier quoted context omitted.

> If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.

I just tried it out, I didn't manage to get GHC to compile the equivalent of the code I've given into something that runs in constant memory. (I did the calculations modulo some number, to keep the numbers themselves bounded.) GHC is sometimes able to do some of those transformations. > The recursive Python version above didn't use tail calls. Just to be more pedantic: it did use tail calls, but the recursive calls w…

> Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.

I was talking about this code:

    def fib(n):
      if n =
Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.

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

#534

Post by musicale »

jkingsbery wrote: post #327

Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anything related to convex hulls since my algorithms class as a sophomore in college (several years earlier), I couldn't remember all the details. At some point, I said, I know where in CLRS ( https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press... ) this is.…

> with him frustrated that I couldn't remember the details of an algorithm I last had seen 6 years earlier and couldn't recite in 60 minutes what took our professor 180 minutes of lectures to cover, and me frustrated that would have taken me 30 seconds to look up.

Sounds like a very effective way to filter out people who haven't taken algorithms courses recently and/or don't spend hours every week on algorithm puzzle contests or solving algorithm puzzles for "fun." They could probably save a lot of time by asking your graduation year and looking at your hackerrank score.

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

#535

Post by musicale »

dmoy wrote: post #370
derefr wrote: post #350

Earlier quoted context omitted.

I think they may also ask them because they want to see how you do at the specific task of taking a problem you remember the pseudocode algorithm for, and actually turning that into working code in a real programming language . You know, the "schlep" part of programming. I feel like they don't realize that this is the goal they're calibrating these questions toward, though. If they did, they wouldn't require the "fro…

Yup if you are willing to explain the algorithm to the candidate and not dock them any "points" (or whatever) for having to explain the algorithm, then this works fine. I have no qualms about having a discussion about an algorithm that's tricky, and seeing how the candidate works through it. That's not what I see in practice though. Not remembering the whole algorithm at best ends up wasting half of the interview (co…

> That's not what I see in practice though. Not remembering the whole algorithm at best ends up wasting half of the interview (code the remainder in 20 minutes??), and at worst gets explicit language from the interviewer like "TC couldn't figure out and I had to explain the algorithm to them explicitly, WEAK/BORDERLINE on algorithms".

It is kind of hilarious to get an algorithm problem which took eminent computer scientists years to solve the first time. "Why yes, I am Donald Knuth/Edsger Dijkstra/et al. – only smarter, luckier, and much faster!"

As you note, the initial question is basically "how well do you recall the solution to this problem?"

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

#536

Post by musicale »

> The Algorithm Design Manual and Algorithms: Fourth Edition are both books I picked up back in the day to refresh some of the my university algorithm class studies. I gave up midway, and found them pretty dry, and not applicable to my day-to-day work.

These are both good books that I actually like! They aren't quite as massive or comprehensive as CLRS but are easier to read as a textbook. I also like Steven Skiena's course videos. But I agree completely that they are unlikely to be something you'll use day-to-day unless you work as an algorithms specialist.

> Grokking Algorithms by Aditya Bhargava... I am convinced that you don't need to know more about algorithms than this book covers.

This is a nice and compact book, and I think he's right for most jobs that involve writing software. Won't be enough to get you past the idiotic algorithm puzzle interviews though. ;-(

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

#537

Post by cmrdporcupine »

ashconnor wrote: post #531
cmrdporcupine wrote: post #301

Earlier quoted context omitted.

Thank you. I've been poking around the job market again after 10 years not searching, and it's disheartening. I have 20 years software development experience, I work at Google, I'm no spring chicken. I'm not the best engineer in the world, I'm sure, but I am a good programmer. I think I'd be an asset in many jobs. But I just turned down proceeding with interviews at a certain payment processing company because in par…

You would think working at a top tier tech company like you are, would allow you to bypass this requirement.

When everyone else has gone through the pain of such an interview process, they are emotionally and ego-wise invested in believing in its efficacy. They have to apply it consistently, and they mostly have to believe it proves something about the intelligence of the successful applicant.

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

#538

Post by thecat08021 »

I'm surprised that you didn't recommend Knuth as the best reference for algorithms.

Technical interviewing for long term employees based on exam essay like questions is rarely productive. My first objective is determining the applicant's honesty on their prior experience. It is amazing that the vast majority of applicants will out right lie on their resumes and to your face when questioned.

Past success in solving/implementing difficult projects is the best indicator of future success.

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

#539

Post by eru »

maxov wrote: post #530
eru wrote: post #522

Earlier quoted context omitted.

Chazelle also came up with the ingenious soft heaps. I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality. I have to admit, I only managed to work through some of the chapters in the books I recommended. And for example, the main reason I know of Chazelle's book it's because it is available for free…

> I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality. Fair enough! I still think it's a good recommendation, I was also adding on some thoughts on things that might be easier to digest :-) > Chazelle also came up with the ingenious soft heaps. Yes, soft heaps are very cool! > I have an algorithmic…

The min-pop is not supposed to return anything, yes. We are only interested in the final contents of the heap. So no sorting required. You can eg give the results of the whole operation as a bitmap over the inserts, so you need to return a linear number of bits.

Min-pops and inserts will in generally be interleaved. The prototypical example has blocks of 2 inserts and 1 pop repeated n times. (All other interleaving patterns can be reduced to this one in linear time.)

QuickSelect doesn't work for this.

QuickSelect or Median-of-Medians approaches work if you only have a small constant number of interleaved blocks (of any arbitrary internal length). Like eg all the inserts first then all the min-pops is equivalent to finding the k smallest elements.

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

#540

Post by eru »

tom_mellior wrote: post #533
eru wrote: post #518

Earlier quoted context omitted.

I just tried it out, I didn't manage to get GHC to compile the equivalent of the code I've given into something that runs in constant memory. (I did the calculations modulo some number, to keep the numbers themselves bounded.) GHC is sometimes able to do some of those transformations. > The recursive Python version above didn't use tail calls. Just to be more pedantic: it did use tail calls, but the recursive calls w…

> Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls. I was talking about this code: def fib(n): if n = Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.

The last call (to a function or operator) is in the tail position. In this case, it is tuple packing.

Why wouldn't the tuple packing be in tail position in the Python code?

Post reply on HN