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

111–120 of 547 posts

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

#111

Post by Smaug123 »

dotancohen wrote: post #77
wadkar wrote: post #61

Earlier quoted context omitted.

By the way they discuss the implementation. First level is ensuring that base cases are covered (i.e. correct implementation of recursion) Second level is how they explain the simple recursion that’ll hit stack limits (i.e. without tail recursion) Third level is using accumulator/tail recursion. See how they can express these ideas and are they able to effectively communicate their intentions.

Serious request, as a developer who would probably code a naive Fibonacci that doesn't meet your standard: Could you provide a code sample that does meet your standard? This looks like an important learning opportunity for me. Thanks.

Instead of recursing twice, recurse once, by carrying around not fib(n-1) but the pair (fib(n-2), fib(n-1)).

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

#112

Post by fogetti »

paxys wrote: post #39
kristopolous wrote: post #32

Let's say someone can solve the algo problem, what's that show? Mostly that they prepared for an algorithms question. It may be a good filter for 3rd-wave do-as-you're told programmers who stay in their lanes, produce by the book expected code, and just consistently obediently build things. They wan better cogs for the corporate software machine. If people are asking me algo questions, the job probably isn't right fo…

This is like how every second kid in high school goes "I get bad grades because I'm too smart".

Or it's more like "I am paxys and I know what every second kid in high school thinks"

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

#113

Post by Smaug123 »

fanf2 wrote: post #41
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…

Why would anyone use recursion to calculate Fibonacci numbers other than as a microbenchmark for function call performance?

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.

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

#115

Post by tchaffee »

This article is an excellent example of why most companies should never ask about algorithms in an interview. The author has worked for elite companies and yet even there he rarely had to reach something advanced. I've worked on some cool and really hard stuff in my career including cryptography and a popular Facebook app where my team used a graphdb, etc, etc, etc. And I would fail at most of today's interviews. Fortunately I'm often the one doing the interviews so I rarely have to endure this nonsense. If you ask me algorithm questions on an interview and you're not the equivalent of Google or Facebook in their early years then I'll find a way to end the interview early and you just lost the opportunity to work with a talented dev. Get some training in interviewing. Do the research on best practice. Create the type of interview that gets people talking enough about past work that you learn what they are actually good at. It's not really that hard to figure out how to create an effective interviewing process for the types of problems your company is solving. It's surprising at just how many otherwise smart people fail at creating that.

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

#116

Post by rvz »

> When we built Skype of Xbox One, we worked on a barebones Xbox OS, that was missing key libraries. We were building one of the first full-fledged applications on the platform. We needed a navigation solution that we could hook up both to touch gestures and to voice commands.

That makes sense. I would expect one to implement data structures and algorithms in a new operating system / kernel without the presence of any libraries available, except for libc, so that they can be reused or abstracted elsewhere in the kernel, drivers etc.

> There were cases where we had to build our own encryption / decryption implementations, formally verifying and auditing them, in the absence of the framework supporting it, or audited libraries being available.

I would leave implementing cryptographic protocols to the professional cryptographers.

But overall, I agree with the author to ask about data structures and algorithms that are actually used in the company if I were interviewing a candidate. It gives an honest account of the engineering decisions and reasons made in the team as to how implementing this DS & A helped them solved their problem and to test if the candidate understands these concepts.

However, after asking the candidate to implement a DS or A, if the candidate questions the technical interviewer if they use it in the company / teams and the answer is no, then it seems rather than a dishonest ego trip on the interviewer's side to test the candidate if they know the secret konami code.

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

#117

Post by gridlockd »

99% of the time, the "right" data structure is either an array of records or a hash table, or a tree that you traverse depth-first.

However, you should be able to implement some of these more rarely used data structures, given a description. You shouldn't know how to do it ahead of time, however, because your job is to solve problems that aren't solved yet.

What you get with these interview questions is that some applicants prepare for how to solve some of these commonly posed problems specifically. So you have to implement a bug-free linked list, on a whiteboard, in ten minutes, to be competitive. It's doable if you are prepared, but that defeats the purpose.

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

#118

Post by heavenlyblue »

tchaffee wrote: post #115

This article is an excellent example of why most companies should never ask about algorithms in an interview. The author has worked for elite companies and yet even there he rarely had to reach something advanced. I've worked on some cool and really hard stuff in my career including cryptography and a popular Facebook app where my team used a graphdb, etc, etc, etc. And I would fail at most of today's interviews. For…

I had interviewers grill me about the time complexity of dictionary implementations in python while making assumptions about their behaviour from Java.

I was impressed by the fact that nobody ever tried to argue with them before.

Basically they were hiring for a Python position and I know that part of the test is the same for everyone. Yet they didn’t know about open addressing.

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

#119

Post by eru »

dotancohen wrote: post #88
eru wrote: post #59

Earlier quoted context omitted.

In eg Python you can just add a memoization decoration, and get a linear solution from the naive recursive one. That's pretty neat.

In almost any language, a hashtable check after the base case check could be used in a similar manner.

Yes. I just singled out Python, because the language is well-known, and adding the memoization is particularly straight-forward.
Post reply on HN