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

491–500 of 547 posts

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

#491

Post by munchbunny »

michaelg7x wrote: post #487
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…

We often see the "don't roll your own crypto", and of course, in a production setting that's obligatory advice. I think that it's a valuable exercise for anyone to implement some of the algorithms and protocols, just to understand the complexity within. I did that for a minimal TLS1.2 implementation, just because, and it was a valuable exercise. Do you see any value in changing the slant you put on "don't try this at…

I think there has always been an implied exception for doing things for their pedagogical value. In the case of my previous comment, I think it’s pretty clear that I’m talking about production code.

As far as rolling your own crypto goes, I think the advice should be “only try it at home and don’t ever use it in production even for yourself”.

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

#492

Post by eternalban »

Swizec wrote: post #436
hackinthebochs wrote: post #406

Earlier quoted context omitted.

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

Properly testing for a "solution engineer" (which is what you appear to be testing for) would pose a question that is a legitimate "software" problem and "domain experts" would be in areas such as say "electronic payments". Candidate would be expected to demonstrate ability to devise proposals for a 'functional solution to a business requirement' using available domain experts.

The key phrase is yours: "real world problems". Your hypothetical misses that by a generous mile.

And I apologize about this but we're discussing actual issues with software recruitment:

One major problem noted by senior engineers subject to these interviews is the competence level of the interviewer. I had this one guy, a "principal engineer", ask me about "Optimistic locks" as his initial query into my knowledge of concurrent systems. It took a lot of self-restraint to not blurt out "You mean optimistic locking?"

It is amazing to me that we somehow managed to hire very good software workers in the 90s without any of these shenanigans. One thing that does stand out from my memory of the 90s: we had senior colleagues (with literal white hair) in senior engineering positions. Go figure.

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

#493

Post by fatnoah »

redblacktree wrote: post #313
fatnoah wrote: post #275

Earlier quoted context omitted.

>I agree. I really dislike being asked to produce code of any complexity in an interview setting, although I do think it's important to see a candidate's code to understand how they solve problems for more senior roles. I've never been a big fan of giving code interviews, however when I have to give them, I'm far more interested in the candidate's thought process around how they understand the problem and what needs…

I agree, and I think this is where the value in these kinds of interview techniques lie. As the interviewee though, I have to say that the high-pressure situation makes me feel very... exposed(?) when I have to elucidate my thought process in real time. I will say that one of the best "interviews" I've had included a portion where I worked with one of their engineers on a design problem they were actually having. It…

>I agree. I really dislike being asked to produce code of any complexity in an interview setting, although I do think it's important to see a candidate's code to understand how they solve problems for more senior roles.

I've been around the block a few times and I LOVE system design interviews, both as an interviewer and interviewee. They are much more collaborative and "fun" for me. The good news is that I've been managing for several years at this point, so those types of interviews are far more prevalent than coding.

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

#494

Post by 000000000000010 »

mcguire wrote: post #379
000000000000010 wrote: post #362

Earlier quoted context omitted.

I think the point is that no one is being asked to derive a novel algorithm. It’s taken for granted that a person with enough experience will have an understanding of broad categories of algorithms and should be able to reason about the small changes to those algorithms that would be necessary for practical application.

Can you offhand write C++ code for a 2-3 Finger Tree, including the changes necessary to make it efficient in a strict language?

I don’t think the point is being able to use a specific language or to know a specific algorithm, unless the role requires it. If the goal is to test a person’s knowledge and understanding, then the actual implementation is probably less important than their ability to explain and reason about the problem. OTOH, if the goal is to find out whether the person is highly skilled in a specific language and has a lot of experience with an algorithmic domain, then what you’re asking isn’t unreasonable.

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

#495

Post by sharken »

Thanks for this insightful look into software engineering in tech companies, as a more DevOps person this is very useful to know about, i.e. there are just too many things outside of programming that are interesting so developing full time is not an option.

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

#496

Post by [deleted] »

jkingsbery wrote: post #486
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…

> Design a system that ensures that doesn't happen Well, if we live in a world with magic, I would just use the magic material to make a machine that removes the water magically.

[deleted]

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

#497

Post by wutbrodo »

mianos wrote: post #438
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…

My experience at Google was that the secret sauce wasn't that it was full of geniuses. It's that everyone was _reliably_ competent and very smart. It's hard to overstate how valuable that certainty is, and how impressive it is to manage that at scale. It enables an entirely new world of employer-employee relationships, including their famous transparency and policies that could (and would) be abused by people too dumb to understand coordination problems. The cost of this is of course going to be plenty of false negatives. (Bear in mind they were a fifth of their current size when I was there, so I don't know how much this applies anymore)

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

#498

Post by wutbrodo »

abtinf wrote: post #475
spankalee wrote: post #415

Earlier quoted context omitted.

I work at Google and have performed plenty of interviews over the years. We're specifically trained not to do this. We have "feedback feedback" in our interview systems specifically for this type of situation.

And yet... I've read countless anecdotes about this kind of behavior, over multiple decades.

Your surprise comes from the fact that you're modeling an institution as a single person when it in reality consists of a hundred thousand people. It's obviously less mental effort to reason about large entities this way, but it's obviously much less accurate.

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

#499

Post by 908B64B197 »

helen___keller wrote: post #398
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…

Seems reminiscent of the tales of early 2000s Google interviews, of the "estimate how many golf balls fit in an airplane" variety. I'm not convinced this offers a useful selection criteria other than boosting your unconscious bias on who "seems smart", but on the other hand I'm also not convinced it's any worse than the standard modern Leetcode interview.

I don't think they were looking for the right answer; I think the goal of that type of questions is to see how does the candidate approaches it. It's especially valuable with college hires.

Some candidates will simply freeze if they don't know the answer. Some will try to estimate the dimensions and come up with an estimate. I think Google wanted to try to anticipate what a person would do when stuck by asking these types of questions.

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

#500

Post by 908B64B197 »

RogerL wrote: post #490
Swizec wrote: post #411

Earlier quoted context omitted.

Funnily that old style of question is far closer to my day-to-day as an engineer than a leetcode algorithms question. Most of my job involves figuring out solutions to fuzzy problems based on unknown constraints, undiscovered requirements, and often unclear end-goals. "How would you fill this airplane with golf balls?" is a fantastic question. If the candidate doesn't reply with "Why? What are you really trying to ac…

Why? Isn't the better question "how would you solve "? I hire people to track objects via computer vision. I ask them "hey, here's a system I want, what approaches would you take", and explain that this is a 3 year research project, of course they will be giving simplistic and wrong answers and there is knowledge asymmetry here, but I'll inform you as you go as to what works and not. "Optical flow". Okay, why? What's…

I think your approach is pretty optimal, but at larger companies the candidates might be interviewing for the company as a whole and not for a specific team.
Post reply on HN