Earlier quoted context omitted.
Btw, which three-liner do you mean?
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
Oh, that version takes exponential time to compute. The one-liner I gave computes up to the n-th Fibonacci number in linear time.
Data structures and algorithms I actually used while working at tech companies
521–530 of 547 posts
Re: Data structures and algorithms I actually used while working at tech companies
#522Earlier quoted context omitted.
See eg https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-n... And https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor... describes one of my favourite algorithms. https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf is also interesting. You can find a lot of good material just via Google, actually. If you read the likes of The Art of Computer Programming for breakfast, you might like 'The Di…
I'm surprised and delighted to see someone recommend The Discrepancy Method by Chazelle. I love this book, but even beyond it requiring a lot of mathematical prerequisites, I'm not sure of the use to most software engineers. I think only the chapters on sampling, geometric algorithms, minimum spanning trees, and maybe linear programming would be useful references on algorithm design for most software engineers. I sec…
Chazelle also came up with the ingenious soft heaps.
I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality.
I have to admit, I only managed to work through some of the chapters in the books I recommended. And for example, the main reason I know of Chazelle's book it's because it is available for free online and stumbled across it a while ago.
Btw, you seem knowledgeable. I have an algorithmic puzzle that has plagued me for some years now:
Starting with an empty heap, and a sequence of inserts and min-pops, can you compute what elements will be left in the heap at the end in linear (expected) time?
Obviously, you can't just run the instructions, that would take O(n log n) time.
I have an algorithm to verify a proposed solution in linear time. But I don't have anything solid for finding one in linear time. I have a hunch that soft-heaps might be useful. And there's probably an even simpler probabilistic approach.
Ideally, I'd like the solution in the comparison model, but if you have something that works on numbers only, that's also fine.
Re: Data structures and algorithms I actually used while working at tech companies
#523Earlier quoted context omitted.
Due to the physical architecture of CPUs/etc., data structures that have "worse" asymptotic performance are often quite a bit faster than those with "better" performance. For example, iterating through a small array to find an item and test for existence is often quite a bit faster than using a hash set for the same operation.
Which is why I just use the standard library.
Most languages have more than one data structure in their standard library.
Re: Data structures and algorithms I actually used while working at tech companies
#524A 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…
Nested loops go brrrrr
No loops in this program. It's all written in Erlang, so it's (tail) recursion all the way.
Re: Data structures and algorithms I actually used while working at tech companies
#525Earlier quoted context omitted.
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
Oh, that version takes exponential time to compute. The one-liner I gave computes up to the n-th Fibonacci number in linear time.
Your version is definitely more performant, but the three liner is just a bit nicer to read (especially for beginners) :)
Re: Data structures and algorithms I actually used while working at tech companies
#526Earlier quoted context omitted.
Oh, that version takes exponential time to compute. The one-liner I gave computes up to the n-th Fibonacci number in linear time.
Your version is definitely more performant, but the three liner is just a bit nicer to read (especially for beginners) :)
Yes. It depends on what you want to show. Your version shows how to define functions and some simple pattern matching.
Re: Data structures and algorithms I actually used while working at tech companies
#527Earlier quoted context omitted.
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
Oh, that version takes exponential time to compute. The one-liner I gave computes up to the n-th Fibonacci number in linear time.
Not in Haskell, it doesn't. Haskell stores everything for you, right?
Re: Data structures and algorithms I actually used while working at tech companies
#528Earlier quoted context omitted.
> Whether it's in Google's interest to select for that of course is debatable. I'd argue it does not. Computational geometry is a niche. It's not even a niche that's particularly relevant to most of Google's development operations. In modern software development, knowing the detail of specific algorithms off the top of your head and being able to implement them unaided is, at best, a parlor trick. I doubt very much t…
The idea is that you might need to invent a new algorithm where a technique from an existing algorithm is used in a modified way or in a new setting, and then knowing the actual technique can be essential to find an inspiration. E.g. if you know that convex hulls can be computed by sorting by angle and sweeping, then you might come up with the idea of sorting by angle and sweeping in problems that are unrelated to co…
Your entire premise is based upon the fact that this wouldn't be discoverable for anyone that didn't already know the algorithm.
Re: Data structures and algorithms I actually used while working at tech companies
#529Earlier quoted context omitted.
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.
That's funny because institutions can only be modeled as a statistical average of all of the humans who contribute to a given property of the institution.
Untrue (there's plenty of emergent behavior in large organizations), and ignoring that, irrelevant. An obvious trivial example is looking at the property of consistency in actions: an organization consisting of a hundred thousand people is going to be far less consistent in many sequences of actions than any given person would be.
Re: Data structures and algorithms I actually used while working at tech companies
#530Earlier quoted context omitted.
I'm surprised and delighted to see someone recommend The Discrepancy Method by Chazelle. I love this book, but even beyond it requiring a lot of mathematical prerequisites, I'm not sure of the use to most software engineers. I think only the chapters on sampling, geometric algorithms, minimum spanning trees, and maybe linear programming would be useful references on algorithm design for most software engineers. I sec…
Chazelle also came up with the ingenious soft heaps. I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality. I have to admit, I only managed to work through some of the chapters in the books I recommended. And for example, the main reason I know of Chazelle's book it's because it is available for free…
> I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality.
Fair enough! I still think it's a good recommendation, I was also adding on some thoughts on things that might be easier to digest :-)
> Chazelle also came up with the ingenious soft heaps.
Yes, soft heaps are very cool!
> I have an algorithmic puzzle..
Cool puzzle! Hmm, the solutions depend on exactly what you're asking.
The puzzle is substantially easier if the min-pop operation is not required to return anything. In this case, you are solving the much easier problem "return the top k elements of an array in unsorted order". You can insert into an unordered list and increment a counter every time min-pop is called. Then the last step can be done with a basic quickselect. See https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0908.pdf page 21, the "QuickSelect" algorithm. You need to do some small modifications to give you the "top k" elements rather than just the "kth" element. This gives expected linear time, and the note describes a deterministic algorithm that makes this worst-case linear time. You can implement deterministic quick select using soft heaps, or instead you could also do a radix sort and then slice out the popped elements.
If the min-pop operation is required to return the popped element, then I believe you run into the sorting linear bound that prevents a deterministic O(n) solution. (Surprisingly, this indicates the hardness of the problem is not really in the last step, it's in implementing constant-time insert and pop). I can't think of an immediate solution off the top of my head, but I don't think a soft-heap provides the right guarantees here. I also don't know of a probabilistic data structure that provides both insert and min-pop in expected amortized constant time, and it seems that this could be an area of research. There are some better, but not quite linear results outside the comparison-based model (https://cs.stackexchange.com/questions/6455/an-efficient-dat...)