Re:Leetcode Considered Harmful
by lowendstock on Tuesday June 28, 2022 @04:03PM
(#31912329)
For #1 a Discrete Interval Encoding Tree may be what you want.
On 1, you don’t really have to consolidate them just to check if the whole range is covered. You can just sort beginnings and ends together and then iterate over them with some tmp variable to check that you always have at least one beginning “open” (n log n).
On 2, to be fair, 10 TB of RAM is not that outlandish. That’s a fraction of what fits in a modern mainframe.
I’d love to have an excuse to get a machine like that.
Re:Leetcode Considered Harmful
by AstralStorm on Tuesday June 28, 2022 @04:14AM
(#31905392)
And the standard answer is that you won't get it. What then?
You can also expand the problem to be approximately internet sized.
That’s unimaginative. I’d go for “you can, but you’ll get 100 machines of 100GB each”.
A couple for example:
1. Given a set of number ranges (e.g. [1..3, 4..5, 9..20, 2..5]) consolidate them. Tying this to a real world scenario: we had a system that dealt with "time periods" and we needed to write a validator to ensure all future dates were covered by at least one configured "time period." One of the first steps to do this was basically the number-range consolidation.
2. Given a list of numbers output metrics like average, min, max, and mode. Now what if the list doesn't fit in memory and instead comes in as a stream (or from an iterator)? This one was inspired by an intern that got stuck when he needed to run calculations on data that didn't fit into memory. He was seriously about to request a host with 10+TB of memory before we stopped him.