working on parquet to json conversion recently.I used graph and dept-first search to create the schema operations.
Data structures and algorithms I actually used while working at tech companies
161–170 of 547 posts
Re: Data structures and algorithms I actually used while working at tech companies
#162Earlier quoted context omitted.
Writing speed isn't the bottleneck hopefully :)
It's not a matter of writing speed, it's familiarity. I've been programming for 30 years and I don't think I've ever written code down on paper. Why ask an interview candidate to do something they've never done before and will never do again? You might as well ask them to type their code using only one hand.
As a heavy smoker, I'd be quite good in an interview where I was forced to type with one hand.
Re: Data structures and algorithms I actually used while working at tech companies
#163Earlier 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…
> 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.
Agreed. The best jobs I've taken had interviews like this, or paid assignments.
Re: Data structures and algorithms I actually used while working at tech companies
#164Earlier quoted context omitted.
Of course, recursion vs iteration is mostly an implementation detail. Here's a recursive version (expressed in Python) that works better than your loop: def fib(n): if n = (I say it works better, because it has the same asymptotic runtime, but fails better: When numbers get large, your C version will run into undefined behaviour that can cause arbitrary problems. The Python version will just crash with a well-defined…
In practice iteration will be faster, even in Python (because there's less overhead). But yes, I should have written "naive recursive solution". There are many ways to fix it. It just wasn't what the question was about.
In Python, yes.
If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.)
But, agreed with everything else you wrote!
Re: Data structures and algorithms I actually used while working at tech companies
#165Earlier quoted context omitted.
In my experience it's pretty necessary to do this. Probably depends on your local job market, but there are a shocking number of candidates that just don't know how to code. The explanation I've heard is that good devs generally get hired after only a handful of interviews, whereas really bad devs are going to do a lot more interviews on average before they get hired, so you get a pretty skewed sampling even if there…
I don't know what your hiring experience with this is, but there is an entire market around "coding interviews" where people will learn how to pass these. I found algorithmic interviews completely useless to assess junior engineers because of how many just learn just to pass interviews, but then have very little experience with real problems.
If you want an example of this, check out r/cscareerquestions. The standard advice is not to practice any practical coding with projects, but to "grind leetcode" to get past interview filters.
Re: Data structures and algorithms I actually used while working at tech companies
#166Earlier quoted context omitted.
Of course, recursion vs iteration is mostly an implementation detail. Here's a recursive version (expressed in Python) that works better than your loop: def fib(n): if n = (I say it works better, because it has the same asymptotic runtime, but fails better: When numbers get large, your C version will run into undefined behaviour that can cause arbitrary problems. The Python version will just crash with a well-defined…
True, but then the "worker" fib() method should be called fib_calculate() and should be wrapped by fib() which then returns a single integer.
Agreed. I only left that out for brevity.
Re: Data structures and algorithms I actually used while working at tech companies
#167I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never used outside programming competitions. The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far you…
standard 'text justification' dp problem ?
Eric's mit video on this : https://www.youtube.com/watch?v=ENyox7kNKeY
Re: Data structures and algorithms I actually used while working at tech companies
#168A 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…
This was the focus of my advanced algorithms course at Georgia Tech in my senior year. We had basically a full semester on random algorithms, and I remember walking out each day feeling like the fancy algorithms I'd memorized the previous year were a bit less glamorous. The number of algorithms that removed multiple complicated stateful steps with 'and we randomly select an element from the array' was mindblowing. As…
Yes! Randomised algorithms are my favourite.
You can sometimes put all the randomness in one part of the algorithm, even. Like shuffling before a naive quicksort.
In practice that's often even easier to understand (and debug!) than algorithms that keep making random choices as they run.
Shuffling and sorting are two humble but powerful building blocks of many algorithms. Both distributed and sequential.
In the example of what I did at Goldman, the core of the problem was essentially a souped up multi-dimensional bin packing problem. The big insight was that the typical distribution of our input data, random assignments had a high enough chance of being good, so we didn't need to keep track of everything in k-d-trees.
(k-d-trees are also awesome. And I even implemented randomized k-d-treaps at first, before I hit on an even simpler solution.)
Re: Data structures and algorithms I actually used while working at tech companies
#169Would love to hear a take on this from a game programmer. They might be a bit more specialized these days, but I'm sure in the late 90's, earl 2000's if you were working on a game, or game engine (and their tools) you used numerous algorithms.
Re: Data structures and algorithms I actually used while working at tech companies
#170Earlier quoted context omitted.
This sounds like a reasonable approach and that is why software interviews remain broken. I'm sure it works for your organization, not saying you are bad at hiring or anything but it still smacks of the kind of hoop-jumping that turned me off so much from the process last time I was interviewing. This included on-the-spot coding exercises, massive take-home projects that required many hours of undifferentiated grunt…
Many people would consider a 30 question take home project massive. You discuss your second experience as if it is some novel Utopian experience but when I read it sounds like an experience that was well suited to your strengths but wouldn't be suited to mine.
It definitely favored verbal skills, I am assuming that was a feature not a bug in the hiring process. The questions were not a project but a conversation in the context of my experience With a specific tech stack such as... “How do you keep a server from getting hacked”, “how do you handle conflicting dependencies”, “how do you know your code is ready to deploy to production”