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

231–240 of 547 posts

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

#231

Post by sufyanadam »

tchaffee wrote: post #78
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…

I already don't want the job because of the interview process. Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal. You should be doing everything you can to put the candidate on their own turf and letting them shine. I have a lot of advice about interviews but one of the best I've heard over the years: whatever impres…

You nailed it. This is the fairest proposal with the best outcome for all sides. Thank you for posting.

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

#232

Post by kerneltime »

stan_rogers wrote: post #28
simonhamp wrote: post #19

Earlier quoted context omitted.

Most wood workers likely won’t know or care how to build their tools from scratch

In the sense of going from rocks to iron to steel to finished tool, no, but otherwise, yes. Making specialised saws, scrapers, chisels, spokeshaves, planes and so forth are part of the luthier's, cabinetmaker's, and shipwright's existence. And that's just the tools, leaving workholding aside. Add in jigs and fixtures and there's a whole lot more. Not everything you need to do the job can be had off the shelf.

+1

I have been tracking luthiers and it is fascinating how detailed and varied each builder is.. the likelihood that the instrument will sound good is well correlated to how much time the luthier puts into refining his process. I don’t understand the rational for not wanting to learn DS/Algos this is just one part of it, there is also the whole business/customer side of writing code. There is a difference between never getting a demanding customer who understands the difference between a good instrument and something glued together and not wanting to know how to do something more than glueing it together is appalling. As a coder if you want to learn DS/Algos and you do not find a job the values that maybe there is more to learn so that find a job that values it. It will be competitive and you can fail but it is not wasted.

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

#233

Post by [deleted] »

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.

[deleted]

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

#234

Post by cordite »

I wrote a typed visitor pattern for validating and rewriting objects with an audit log, it became necessary for an integration where an error response would need to return a modified input if the original could not be processed but he modified one could be resubmitted successfully.

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

#235

Post by Taek »

WJW wrote: post #153
ForHackernews wrote: post #92

Earlier quoted context omitted.

Fibonacci has a closed-form solution! Forget writing loops, you can write one damn equation. Runs in constant time.

The closed form solution is technically O(phi^N), so still exponential. It comes mostly from exponentiation not being constant time, see https://stackoverflow.com/questions/360748/computational-com... . It'll only be constant time if your values fit into a hardware register and you can leverage the exponentiation instructions of your CPU. There is a O(log(N)) solution involving matrix exponentiation though, if you re…

Technically, Fib(n) at unbounded sizes is at least linear to compute. This is because the output of Fib(n) has O(n) bits in it. So even if the computation is free, it's still O(n) just to print the result.

That's not the type of thing I would ever expect a candidate to know in an interview, just something fun I've run across.

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

#236

Post by ojr »

whack wrote: post #228

I'm increasingly convinced that Algorithms-and-Data-Structure interviews are essentially being used as a proxy for: - General IQ. Can this person understand and apply complex ideas - Grit. Is this person hard-working enough to learn things that take time and effort It's the software equivalent of the NFL scouting combine. The goal is not to create a test that is similar to the day-to-day job. But rather, create a tes…

- Retention. If this person spent hours on leetcode, they’ll be less likely to leave the job knowing the effort it takes to get through the gate

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

#237

Post by kamaal »

eru wrote: 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…

Algorithms are all about eliminating waste effort. Not using programs invented by others to manipulate data structures. Those just happen to be solutions to some problem patterns.

A person good at algorithms is some one who can make things happen with least effort possible. Not some one who can invert trees, even more so when there is not need to invert a tree.

You can see how good some one is at algorithm stuff to see how much drudgery exists in the way they do work themselves.

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

#238

Post by nathanyz »

mumblemumble wrote: post #197
eru wrote: 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…

Eric Lippert did a nice blog post on this sort of thing a few months ago: https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.

Exactly this. While the underlying theory is excellent on many of these theoretical algorithms, they typically don't perform as expected when taking into account the infinite complexities of the real-world.

But being able to understand the core value of the algorithm enables you to adapt or modify slightly in order to get it to work as needed in the real world.

In general just knowing that there are specialized algorithms for certain classes of problems is 80% of the expertise you gain over years of experience. Knowing that things like Bloom filters exist when you hit a problem that could be solved by this class of algorithm gets you much further than expertly memorizing any specific implementation of the algorithm. There are a variety of them depending on the actual use case you are looking to solve for.

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

#239

Post by rimliu »

elcomet wrote: post #154
rimliu wrote: post #69

Earlier quoted context omitted.

If you use recurssion for Fibbonacci, you do not understand neither recurrsion nor Fibbonacci.

That's a bold claim. You can very much solve Fibonacci with recursion efficiently. It's just not in the naive way. (You can look up "accumulator")

There are lots of thing you can, but you should not.

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

#240

Post by midev »

whack wrote: post #228

I'm increasingly convinced that Algorithms-and-Data-Structure interviews are essentially being used as a proxy for: - General IQ. Can this person understand and apply complex ideas - Grit. Is this person hard-working enough to learn things that take time and effort It's the software equivalent of the NFL scouting combine. The goal is not to create a test that is similar to the day-to-day job. But rather, create a tes…

Algorithms and Data Structures don't measure either of those things. General IQ is not measured by very specific technical problems. Nor is learning something specific an indication of "grit".

It's a proxy for interviewers to jerk their ego.

Post reply on HN