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

501–510 of 547 posts

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

#501

Post by jiveturkey »

nice thread. sorry for the noisy comment, but most threads similar to this end up with folks griping that the interviewer asked them to invert a binary tree or other such super basic stuff that -- no, you do not do every day or even ever at all, but -- is 101 level stuff that you better be able do in a few minutes from first principles. sticking with that theme, even AVL or red/black you better be able to describe it off the top of your head although asking to implement a working solution covering all edge cases in the span of an interview session is nonsense.

no, in this thread people are describing actually hard, complex algorithms and ridiculous interviews. so sad to see that these questions are still being asked today.

this is the best thread on this subject that i have ever seen on HN.

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

#502

Post by 908B64B197 »

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'll play devil's advocate and say I don't dislike coding interviews. Most of the time they are done completely wrong however.

They are extremely useful to filter out candidates that simply cannot program, and who won't be able to no matter how much mentoring time you 'invest' in them. I've heard about interviews for senior engineers that were totally derailed by a simple FizzBuzz. I like wordcount (the wc *nix command) as a warmup/screening question simply because either: The candidate comes up with an algorithm for it and test cases OR starts counting whitespace and derails the implementation with a cascade of if-else for every new test cases that breaks the previous implementation (I've seen if-else to check for the n cases I suggested...).

But honestly I feel there is so much cargo-culting for coding interview. Especially if you ask for compliable code of well known (as described by a textbook) algorithms you ultimately assess rote memorizations skills and not engineering.

Convex Hull doesn't sound so bad to be honest. If I was using this question I would expect someone to be able to come up with the gift wrapping algorithm with maybe a little bit of help. What, as an interviewer, would really want to see is if the candidate can come up with test cases and a way to test whether his solution is actually a convex hull and then try to break down the problem and come up with an algorithm. I sure wouldn't expect to be able to type what's on the board and for it to compile right away (it's a board, not an IDE!) but I expect the candidate to be able to walk me through the code and run it line by line through some test cases.

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

#503

Post by eveningcoffee »

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…

I think you are doing it right.

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

#504

Post by rowanG077 »

treebog wrote: post #463
bjourne wrote: post #401

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.

One thing I learned in getting my engineering degree is that it’s unethical to practice engineering in an area you don’t understand. No way would I ever try to apply my software engineering skills to a materials problem

I feel it's only unethetical if there are "real" stakes on the line. E.g. Where people can get hurt. I don't mind a mechanical engineer writing code for a company that makes the zillionth vapid webapp nor do I mind a software engineer designing a mechanical watch.

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

#505

Post by benibela »

ladberg wrote: post #343
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 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…

I had the opposite experience in a Google interview.

I just said, that can be solved with a topological sort, and then we moved on.

But I failed with another interviewer. He kept asking how to prevent hashing from producing collisions. The answer was universal hashing, but I had forgotten about that

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

#506

Post by dragonsngoblins »

Swizec wrote: post #456
dragonsngoblins wrote: post #448

Earlier quoted context omitted.

I suppose it depends on how you grade the answers. Like I have bad spatial awareness in terms of how big things like planes are. I genuinely don't really have an idea how long a commercial airliner is, or how big a ping pong ball is. I feel like I'd do ok if I could get reasonable approximate values for things like the size of the plane, the balls, the seats, etc. if I also have to supply those values myself the end…

Like I said, the point of this question isn’t to seek your domain expertise, the point is to see how you use other people’s domain expertise to create a [software] system.

The way you ask it sure. I'm just not sure that is how everyone asks it, though maybe it is. I've never been asked something quite like that before but some comments I've seen around seem to imply some people want a close to accurate answer.

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

#507

Post by GeneralMayhem »

tchaffee wrote: post #178
GeneralMayhem wrote: post #176

Earlier quoted context omitted.

>Lots of engineer types freeze when they have to make a presentation. I remember a meeting early in my career with literally three people in a conference room and I almost had a panic attack. That's definitely an unfortunate experience, but isn't giving presentations to explain your ideas - sometimes to people you don't really know - actually a significant part of the job? I'm an IC, and I present designs and project…

What is an IC? > isn't giving presentations to explain your ideas - sometimes to people you don't really know - actually a significant part of the job? For many engineering positions it is not. There are loads of shops where the developers, even senior developers, mostly just write code. I have hired many of them and put them to work successfully building stuff while I deal with the meetings. > If I were conducting a…

>What is an IC?

Individual Contributor, used to contrast with "Manager". Point being, my main job is to design systems and write code, but I still have to do some of the organizational stuff sometimes.

>There are loads of shops where the developers, even senior developers, mostly just write code.

Okay, so your experience is different from mine. I'm surprised that there are places where this is really not a meaningful job requirement, and I've never worked at one, but I believe you.

>it's something people can learn if they want to

Sure... but so is coding. Part of the point of an interview is to see what skills and traits you already have. If you're missing some, that can be balanced against the ones you do have - it's not a dealbreaker, but it is still a negative.

>Some people don't want to. There are roles for them too.

Again, not where I work. Engineering, even at relatively junior levels, includes collaboration and explaining your work. You can't just say you don't want to do that - or rather, you can, but you'll have no upward mobility and be managed out pretty quickly.

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

#508

Post by PlanetLotus »

908B64B197 wrote: post #502
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'll play devil's advocate and say I don't dislike coding interviews. Most of the time they are done completely wrong however. They are extremely useful to filter out candidates that simply cannot program, and who won't be able to no matter how much mentoring time you 'invest' in them. I've heard about interviews for senior engineers that were totally derailed by a simple FizzBuzz. I like wordcount (the wc *nix comma…

I don't dislike coding interviews either. But if I were asked about a Convex Hull, my response would have to be, "What is a convex hull?" otherwise I'd have to guess. I have a computer science degree, did I miss something? Is that common knowledge? Right now I have the power to look it up, but it's a little strange to me that I could be asked about that in an interview and my pass/fail would potentially depend on it (granted when I am the interviewer, my pass/fail rarely depends on the response to the coding questions).

So the next question is, will interviewers explain the problem if you're unfamiliar and not "fail" you if you can explain how you'd approach a solution?

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

#509

Post by 908B64B197 »

PlanetLotus wrote: post #508
908B64B197 wrote: post #502

Earlier quoted context omitted.

I'll play devil's advocate and say I don't dislike coding interviews. Most of the time they are done completely wrong however. They are extremely useful to filter out candidates that simply cannot program, and who won't be able to no matter how much mentoring time you 'invest' in them. I've heard about interviews for senior engineers that were totally derailed by a simple FizzBuzz. I like wordcount (the wc *nix comma…

I don't dislike coding interviews either. But if I were asked about a Convex Hull, my response would have to be, "What is a convex hull?" otherwise I'd have to guess. I have a computer science degree, did I miss something? Is that common knowledge? Right now I have the power to look it up, but it's a little strange to me that I could be asked about that in an interview and my pass/fail would potentially depend on it…

I would never fail someone for asking questions.

I liked the convex hull problem because it's easy to sketch in 2D and explain in case someone doesn't know what it is.

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

#510

Post by milesvp »

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…

Interesting you mention 80’s style image processing techniques. Please take care with these kinds of biases. Often older techniques are superior than ones that are merely fashionable today. I’ve also been around long enough to see pendulums go back and forth at least once in the AI realm, never mind tech in general.

Mind you, I’m not saying you’re wrong to discount people who fail to stay abreast in their field, just know that sometimes there is wisdom in ignoring popular trends, or revisiting old techniques that might benefit from a different landscape.

Post reply on HN