Live data from Hacker News

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

blog.pragmaticengineer.com

421–430 of 547 posts

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

#421
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…

A lot of algorithms and data structures are not cache aware and assume that all memory operations have the same cost.

It's sometime best to use the 'worst' approach that allows most data to be as close to the CPU as possible for the longest.

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

#422
post #351

Earlier quoted context omitted.

That may be true. But then why hire someone with just look-up skills before hiring someone who really tries, and enjoys the challenge? I'm interviewing engineers frequently and although I agree that the question asked by GP is maybe not the best it still gives the signal if someone is willing to power through a problem with minimal guidance and/or ambiguous constraints. Something I'm willing to find out at the peril…

> why hire someone with just look-up skills before hiring someone who really tries, and enjoys the challenge This attitude will keep you from hiring someone who will just "do the right thing," which is to look up stuff that can be looked up, and also persevere when an off-the-shelf solution won't be sufficient. Plenty of engineers will spend time trying to reinvent the wheel when it is totally unncesssary.

At some point we had a brilliant junior dev who had a task to add some logic to some ES plugins in Java. When the code review went up, it was all a single Java 8 stream statement. He went out of his way to convert everything to a stream because he enjoyed the challenge I guess. It was 3 pages of nested declarations and inscrutable.

He left eventually but person was hard to work with because you had to beat back this kind of shenanigans every step of the way.

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

#423
post #336

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.…

Yea I interview (and have sat on HC) at Google, and interviewers who ask these types of questions really frustrate me. If your question requires having previously memorized or being able to come up with some tricky algorithm on the fly in 45 minutes and code a solution using it , your question is probably bad. I get why they ask them - they're easy to ask, they're easy to score, and when your question inevitably gets…

What on earth is wrong with asking to see the interviewee's code? Skim over it looking for neatness, how they comment, what build procedure is there and quiz them about what you see: anything from language choice, to build reproducibility, from architecture to install. And of course quiz them on algos you see.

All of these 'tricky' exam style questions don't show a thing about the person sitting in the interview room.

I've hired based on a good discussion alone, without code... And got a great engineer.

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

#424

As an engineer who works on security software, here's what I've empirically used on the job: 1. Tree/graph traversal (certificate validation and a couple other random places) 2. Using, not implementing, hash tables 3. Generators/iterators/streams: minimizing the number of unnecessary list traversals or allocations made when you have to shovel data around 4. Circular buffers: specifically in low latency, high throughp…

Thumbs up on circular buffers. Those are totally underrated.

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

#425
post #177

Earlier quoted context omitted.

standard 'text justification' dp problem ? Eric's mit video on this : https://www.youtube.com/watch?v=ENyox7kNKeY leetcode https://leetcode.com/problems/text-justification/

(Apologies to people on mobile for the following...) One of the things I miss about Usenet was that nearly everyone read it with a fixed with font so that if you choose your phrasing well so as to make your text come out naturally perfectly justified, it would come out that way for them too. English has so many synonyms and near-synonyms for every word, and so much flexibility in the ordering of words that you can wr…

s /a fixed with font/fixed width fonts/ in the second line

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

#426

Earlier quoted context omitted.

Everything else in an interview is also completely different from 9-5 engineering.

Due to a lack of imagination and people who don't host interviews on a regular basis so they never put in the effort to get good at it. When I conduct a technical interview we are going to end up doing some stuff you do in your 9-5. And you probably won't even notice it. And if there is a budget available for it, I'm going to pay you to do a very small coding assignment. A few hours. Almost exactly your 9-5.

The fundamental difference is that a job is directly at stake based on your performance. For many people, this makes them more nervous than they would ever generally be during work. Due to the nature of interviews, I don't think there's really a way for it to be otherwise.

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

#427
post #363

Earlier quoted context omitted.

Here's a thread on the same article that ended up being largely about dynamic programming :) https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actu... I still say it is a bad interview question, but there were lots of interesting examples I learned about. - GCC splitting IA-64 instructions - Trellis quantization in lossy video encoding - Knuth-Plass line breaking algorithm (mentioned here too) - Some algorithms…

I tried to read the comment, but don't quite understand: what is the problem GCC is trying to solve there?

CPUs have some number of individual units that do different things. You'll have a few ALUs that can do stuff like adding, subtracting, xor, and, etc. You'll have some number of units that do floating point math. You'll have a shift unit to do bitshifts. In ye olden days, the CPU would only do one thing at a time, while the rest of the CPU sat idle.

x86-64 (and most other architectures) can use multiple units at the same time using what's called a superscalar architecture. There's a hardware unit that figures out what units are in use and what instruction just arrived, and can either send the instruction to ALU0 if it's unused, or ALU1 if ALU0 is in use, etc.

But this hardware unit that does scheduling is complex, it takes up space that could be used by other stuff. IA64 aka Itanium, not to be confused with x86-64, is a VLIW (very long instruction word) architecture. The underlying assumption is that the compiler knows in advance what operations it's already emitted, and what operations are coming next, and the compiler can be considerably more complex than the hardware scheduler does. So a VLIW instruction isn't just "add eax,ebx" like x86, it's more like "ALU0: add r12,r48; ALU1: add r93,r42; SHIFT: r60,12; MEM: load r17,r32". (Itanium had 128 registers) The compiler had to do a bunch of stuff that modern CPUs do in hardware. I think it even had to deconflict instructions; like the compiler had to know that an addition takes 3 clock cycles or whatever, so if you used ALU0 on cycle 123772 and then tried to use ALU0 again on 123774 something bad would happen, but don't quote me on that.

So at some point the compiler is going to have a DAG of operations that need to get run in a block, and it needs to bundle up those individual operations into bundles of (I think) 4. Sounds dynamic programmy to me. At least I think that's what's going on.

It turns out that most code is pretty branchy, which means many lines of code will have multiple entry points. This invalidates the assumption that the compiler knows what operation it just executed. So in practice, VLIW architectures aren't able to achieve their theoretical performance, and superscalar architectures are better.

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

#428
post #341
post #336

Earlier quoted context omitted.

Yea I interview (and have sat on HC) at Google, and interviewers who ask these types of questions really frustrate me. If your question requires having previously memorized or being able to come up with some tricky algorithm on the fly in 45 minutes and code a solution using it , your question is probably bad. I get why they ask them - they're easy to ask, they're easy to score, and when your question inevitably gets…

My favorite question to ask in software engineering interviews is one that I believe to be un-burnable. > It's 2140 AD, New York is under water up to X feet high. Buildings have been retrofitted with to withstand the water. You are in charge of keeping your building dry. If water gets in and damages the foundation, a few thousand people die or become homeless. > Design a system that ensures that doesn't happen. How c…

Call uber boat. Have people evacuate. Problem solved. Building gets collected by the garbage collector.

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

#429

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.…

One day I will understand why seemingly half of all CS papers seem to be concerned with convex hulls and Voronoi decomposition. What is so fascinating about these two topics as to warrant hundreds, if not thousands of papers? I've never heard of anyone using them anywhere ever for any purpose in industry, yet these topics are a focus of concentrated intellectual study as if they were the cure for cancer.

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

#430
post #403

Earlier quoted context omitted.

I'd let the material science engineer figure that one out too. No way in hell would I risk my ignorance of building maintenance be the cause of thousands of deaths.

The materials engineer can give you a great material. They can't design a system to monitor said material for defects.

S3 bucket had public access enabled... we asked a software engineer to do something that they're not the expert in.
Post reply on HN