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

131–140 of 547 posts

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

#131

Post by eru »

vishbar wrote: post #97
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…

Due to the physical architecture of CPUs/etc., data structures that have "worse" asymptotic performance are often quite a bit faster than those with "better" performance. For example, iterating through a small array to find an item and test for existence is often quite a bit faster than using a hash set for the same operation.

In the same vein, pre-processing your data via sorting on some carefully chosen keys can sometimes alleviate the need for purpose built data structures.

And because of caches, sorting can sometimes beat hashtables.

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

#132

Post by dolmen »

WalterBright wrote: post #109
karolist wrote: post #94

Earlier quoted context omitted.

The actual quote was something like "aerodynamics are for people who can't build engines" which proves your point a bit better.

It's actually a bit ironic, because I consider Ferrari to build elegant cars while my old V8 Dodge is a triumph of brute force and ignorance. They're both great cars at opposite ends of the spectrum :-) A variation on the sentiment I heard in a movie: "turbochargers are for wussies, real cars have cubic inches!"

Elegant doesn't always go with optimized aerodynamics.

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

#133

Post by exdsq »

eru wrote: post #124
Smaug123 wrote: post #113

Earlier quoted context omitted.

I, for one, prefer recursion to explicit iteration in most cases. Anyway, if you were going to write the answer in Haskell, it's a three-liner and it's recursive.

Why do you need so many lines? fib = 1 : zipWith (+) (0 : fib) fib

Because the three liner is easier to read

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

#134

Post by [deleted] »

charlus wrote: post #130
varbhat wrote: post #114

Which are the best books to learn Data Structures and Algorithms ? (Or which books did you use/recommend to learn Data Structures and Algorithms?)

Cormen - Introduction to Algorithms (CLRS) is probably the most recommended. Depending on where you are starting from, MIT opencourseware lectures might be helpful too.

[deleted]

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

#135

Post by dolmen »

perlgeek wrote: post #42

There's a huge distinction between "used" and "implemented myself". I've used quite a lot of features from RDBMs, as well as topological sorting, LRU for caches, Unicode normalization, graph traversal, bloom filters, hash maps and so on. I'm not payed to implement algorithms or data structures, but to solve problems. So for anything non-trivial I tend to use ready-made libraries. I only implement stuff myself when it…

You still have to understand how things are implemented by others (even at a high level view: ex: what is a RDBMS index) to be aware of their advantages and drawbacks to make the best use of algorithms available to achieve your goals (ex: performance of the solution, ease of evolution of the solution).

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

#137

Post by nostrebored »

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…

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 I work on more and more distributed systems I keep seeing opportunities for simplifications with randomness (with obvious drawbacks on occasion).

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

#138

Post by eru »

pintxo wrote: post #76
eru wrote: post #60

Earlier quoted context omitted.

Be careful, 'persistent' is used with different meanings in different contexts. See eg https://en.wikipedia.org/wiki/Persistent_data_structure and immediately notice the warning 'Not to be confused with persistent storage.'

Thanks, I usually refer to them as immutable, haven't actually come across the term persistent for these, but seems sensible.

Persistent data structures don't have to be immutable. (The Wikipedia article explains.)

But immutable data structures are always trivially persistent.

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

#139

Post by psds2 »

lootsauce wrote: post #63
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…

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…

Many people would consider a 30 question take home project massive. You discuss your second experience as if it is some novel Utopian experience but when I read it sounds like an experience that was well suited to your strengths but wouldn't be suited to mine.
Post reply on HN