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

431–440 of 547 posts

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

#431

Post by jiggawatts »

kelnos wrote: post #413
ladberg wrote: post #343

Earlier quoted context omitted.

I had a very similar experience interviewing for Google. I was asked to do a task that eventually boiled down to a topological sort, and I thought the question consisted of recognizing that the answer was a topological sort and moving on because it was over the phone. However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically…

The entire concept of asking someone to write code in Google Docs is just insane to me. No one would ever do that on a job, because it's remarkably awful and difficult, and the editor will fight against you every step of the way (auto-capitalization, just to name one thing). And yet somehow interviewers think that this will give them a good picture of how you'd do work on the job. Baffling.

They're doing it so that they can see your edits live, "prooving" that you're not cheating in some way.

But yes, this is asinine. Sharing your desktop through a video conferencing program and using the IDE of your choice would be far more realistic test, but Google likes to put hoops up to jump through that are smaller than your body.

Why can't you contort yourself like an octopus!? Fail!

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

#432

Post by jiggawatts »

munchbunny wrote: post #308

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…

I'm a very "generic" programmer that dabbles in an incredible variety of problems, from Windows GUIs to health monitor probes running on a BSD network appliance. You just summed up pretty much everything I've ever needed to know as well.

IMHO the #1 thing that most developers are missing is database query writing skills. There is a shocking amount of terribly inefficient SQL out there that is wasting everyone's time and money.

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

#433

Post by tonymet »

I like his point at the end, that the interviewing process is the most pragmatic one, not the best. It reminds me of boarding airplanes, where we've chosen pragmatic boarding strategies, but not the most efficient.

Remember people processes need to be the least bad, not the best. Most of the best are either unworkable or tyrannical.

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

#434

Post by WalterBright »

egman_ekki wrote: post #140
c17r wrote: post #104

Earlier quoted context omitted.

“You understand neither recursion nor Fibonacci” Or “You do not understand recursion nor Fibonacci”

Ain't nobody got time for that.

Ain't nobody got no time for that.

FTFY

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

#435

Post by duskwuff »

devit wrote: post #419
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.…

Well, I probably used it last time 10 years ago and still remember it. All you need to remember is that you sort points by angle from a fixed point on the convex hull, and you can easily work out the rest of the algorithm as well as the proof of correctness. Not knowing it is a relevant signal that you did not seriously attempt to compete in computer science competitions during high school and college and did not oth…

> Whether it's in Google's interest to select for that of course is debatable.

I'd argue it does not. Computational geometry is a niche. It's not even a niche that's particularly relevant to most of Google's development operations.

In modern software development, knowing the detail of specific algorithms off the top of your head and being able to implement them unaided is, at best, a parlor trick. I doubt very much that it even correlates to one's effectiveness as a developer. Even for development tasks which involve algorithmic work -- which many don't! -- knowing that various algorithms exist, and what they're used for, is much more valuable than having memorized the details of how those algorithms are implemented.

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

#436

Post by Swizec »

hackinthebochs wrote: post #406
Swizec wrote: post #341

Earlier quoted context omitted.

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…

This is a terrible question. Problem solving ability doesn't exist in a vacuum. Our experiences give us resources to draw from to combine in new ways that allow us to solve novel problems. Asking a software engineer to solve a problem in a dissimilar domain is badly missing the point of screening software engineers. Sure, you may say that everyone who does well turns out to be a great engineer. I'm sure Google says t…

I disagree. The goal of this question is to see how you utilize domain experts as a resource, add your software expertise, and design a comprehensive solution. It is specifically not a question about what you already know.

In the interview I play the domain expert.

This is exactly what your job will look like: collaborate with domain experts, use your software skills, solve real world problems.

I don’t need an engineer who can build a queue. I need an engineer who can use a queue.

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

#437

Post by urschrei »

jiggawatts wrote: post #429
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.…

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.

An entire industry – geospatial – and a variety of related industries depend on high-performance CH, Voronoi, and line simplification algorithms, among others. Not to mention their importance in medical imaging applications, tomography (so, in a sense, they directly contribute to healthcare improvements). This should be self-evident, but I can provide further direct evidence if need be; I’ve implemented QuickHull, Visvalingam-Whyatt etc from the papers, and the resulting libraries see enthusiastic use in a variety of sometimes surprising fields. They get lots of attention because the problem domain is well-understood and often resistant to low-hanging optimisation efforts (computational geometry algorithms tend to be difficult to optimise)

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

#438

Post by mianos »

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

I interviewed at Google quite a few years ago and had a similar experience but over multiple interviews. I had 5 interviews slowly getting harder and harder questions. By the fifth interview I got past the first question pretty fast so he moved onto a second harder one that my answer did not seem to impress. After all these interviews they just never called me back again. The whole process was senseless. It was as if they wanted to find the point at which I would fail so they could stop. I'll probably hate Google forever after that. I am sure they have great people but I am always very interested when I meet someone who works there so I can ask them about what they do and they always seemed kinda average good not amazing.

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

#439

Post by duskwuff »

pps43 wrote: post #188
paulryanrogers wrote: post #183

Earlier quoted context omitted.

Recursion is often less efficient but looks more elegant and simpler. It breaks the problem down to is essence. Then you can trade some complexity for more run-time efficiency.

> more elegant and simpler Beauty is in the eye of the beholder, but a loop is hard to beat as far as simplicity goes, and you don't depend on your compiler being clever enough to optimize tail recursion. If you need to traverse a tree then sure, but with Fibonacci you don't even need the stack to begin with. You only need to keep a previous number.

You don't even need a loop. Binet's formula gives a closed-form expression for the Fibonacci sequence. (And of course I don't remember that formula off the top of my head, but I know it exists, so I'd be 90% of the way to solving a problem which required it.)

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

#440

Post by johnofthesea »

Swizec wrote: post #402
JakeStone wrote: post #394

Earlier quoted context omitted.

Use to build a wall around the city? Have the people who maintained each individual building form a team that can keep an eye on sections in shifts? If we have enough magic material, build a double wall system for breaches? I'm done. Give me my paycheck.

> Use to build a wall around the city? That sounds expensive. Do we need to do that? Does it solve the problem better? Does it maybe create a worse solution? How would you find out? > Have the people who maintained each individual building form a team that can keep an eye on sections in shifts? How would you make this less time intensive? Can you use automation? > If we have enough magic material, build a double wall…

It would be probably cheeper - simply because the perimeter would be shorter than the sum of perimeters for most of buildings included in the city/district. That is what cities did since at least Neolithic til moment when cities become undefendable (because of cannons and airstrike).

But that is probably not the point. In order to build wall around the city, you need to have power or consensus in society to deliver this decision. And achieve that in reasonable time might be unreal for someone in charge of one building.

Post reply on HN