ghj

Violates expectations of privacy. Anyone can reconstruct your watch history.

I've actually gotten this question in a google interview before: https://leetcode.com/problems/peeking-iterator/

Yet another graph theory theorem falling to automated reasoning!

I wonder why progress has been so slow though. After the promising result decades ago where the Four Color Theorem was proven by a computer, I expected to see a lot more computer assisted proofs.

> They ultimately streamlined the search for a clique of size 128 so that instead of checking 2^39,000 configurations, their SAT solver only had to search about 1 billion (2^30)

Why is human insight needed for finding symmetries to make problems computationally tractable? Why can't this part be automated too? This must've been worked on for decades already, so is there a fundamental reason why computers can't do it?

EDIT: Also found some more technical links by one of the co-authors: http://www.cs.cmu.edu/~mheule/talks/ijcar2020.pdf http://www.cs.cmu.edu/~mheule/Keller/

At that point you might as well make it useful and search all cctv for the face of some suspect. And of course with zoom and enhance features too.

(memes aside, I am sure this tech already exists given how popular the idea is in tv shows and movies)

Those time estimates look way too optimistic.

Or I am just the type that would mess up an equation and spend the next 3 hours trying to figure out why something is rendered upside down or worse, with just subtly incorrect lighting and colors.

Anything math-y that doesn't fail loudly requires a different type of debugging skill that the typical programmer doesn't have.

If you think about it, it's insane how much infrastructure we take for granted (xxx kilowatt of electricity, xxx mbps of internet, all for dirt cheap).

Maybe in a near future everyone would need xxx petaflops of compute just as you would any other utility. At least anyone who wants their personal AI secretaries to "learn" and "think" effectively.

Historically these utility/infrastructure projects needs to be built by the government since it's a chicken and egg problem. "Internet" companies can only exist after the internet is built. "AI" companies can only exist after gpt3 levels of compute is made available to the everyday person.

(There might be a physics argument to why the economy of scale of compute can't go down that much even with nation-level of investments. Usually it ends up with needing to build a dyson swarm. I really hope they are wrong because I don't think I will live to see it)

There are plenty of competitive programming sites where you can grind rating just like you would for MMR rating in video games.

For example CodeForces, AtCoder, TopCoder, and even LeetCode have rated contests

I was tricked into writing a VM while doing Advent of Code last year and it really deepened my understanding of programming (e.g., on how to implement simple coroutines).

Advent of Code is supposed to be 25 daily programming puzzles leading up to christmas. I went in thinking they were going to be algo/datastructure tasks but half of them were actually about implementing and using a VM for a made up assembly language! The difficulty ramp was gradual enough that I did it with no background in compilers and it was lots of fun.

If you want to experience it, in last year's version https://adventofcode.com/2019 you write the VM in Days 2, 5, 7, 9 then apply it to solving problems in Days 11, 13, 15, 17, 19, 21, 23, 25.

I ended up loving the VM puzzles and ended up doing the AoC author's other challenges which have a similar theme: https://challenge.synacor.com/

Different race happen to be correlated with different cultural values.

One particular cultural value is caring a whole lot about education and prestigious degrees (see the test prep industry in most of asia).

I have no problem with people who value education getting an edge in admissions. So even in a race-blind world, I am okay with outcomes not matching population statistics. Because in a world where you're solely judged based on your values that's exactly what you'd see.

But what's happening is that two different people can both adopt this same "education" value and have different outcome because of their race. The opportunities are not equal, not for blacks, not for asians.

Online lectures might be able to scale, but communication platforms and social networks cannot.

I would say more than half of what you learn is from your peers. People who by design were already filtered to be at a high baseline of competence and are forced to go through the same curriculum in the same timeframe as you.

No professor or expert can explain a concept better than someone similar to yourself who recently figured it out. There's also an immense amount of camaraderie built from helping each other grow. All of this is lost when you're just one of millions watching a video where most of the public discussion is dumb.

A little artificial exclusivity isn't a bad thing.

Even more hijacking, I remember thinking medical applications were going to be the killer apps for VR. I was blown away by these demos almost half a decade ago https://youtu.be/MWGBRsV9omw?t=251

Did they ever make it into real life practice?

I highly doubt js engines would compile a string down to a linked list. But you're right they might compile it to a circular buffer or deque which can have O(1) prepends.

Quick googling shows that this optimization might exist but only for firefox and only if you use "unshift": https://lannonbr.com/blog/2020-01-27-shift-optimizations https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-opti...

But it's very unlikely that the jit can optimize `str = ch + str;`

They failed at writing a correct O(n) left pad in their benchmark:

https://github.com/left-pad/left-pad/blob/master/perf/O(n).j...

They are repeatedly appending a single character to the front of a string. This is actually O(n^2) so of course they are winning against it.

This is so hilariously overengineered: not failing when passed the wrong types, arbitrarily caching padding of len < 10, etc

The most egregious is the bad big O analysis for a pointless binary search. The loop does indeed run O(log(n)) times but `ch += ch` still takes O(ch.length) which is growing exponentially. It ends up being a complicated way of still taking O(n) time while creating a lot of intermediate strings.

It isn't any faster than just creating the padding with a loop or `new Array(len).fill(ch).join('')` or `ch.repeat(len)`

I don't care how big the underwater part is though. I am just using the case rate as a proxy for when states seem to hit their peak (yes, extremely handwavy).

As long at the confirmed cases is within some constant fraction of true number, it will be a decent proxy. This makes sense to me since some x% of the people who get infect will need hospitalization so they will get counted towards the statistics.

NYC is a good case study since it's one of the first place hit and is now more or less "done" with covid in the same sense used in this article (it had a peak and is now on the right tail).

NYC is at 2716 cases per 100k and 281 deaths per 100k: https://www.cdc.gov/covid-data-tracker/#cases

States with aggressive reopening policies like Florida/Louisana/Arizona etc had spikes recently but are also coming back down. They are sitting at around 2-3k cases per 100k (deaths will lag).

Even if the reason why those states "peaked" is because of herd immunity, it seems like it still requires at least 3k cases per 100k. That would translate to 300k cases for a population of 10 million but Sweden is only at 80k right now.

I highly doubt they have herd immunity.

> I think this example is well known but I can’t think what it is

Could be the basel problem though he probably used this trick many times in his prolific life:

https://en.wikipedia.org/wiki/Basel_problem#Euler's_approach

Make it easy to create /r/highqualitygifs style memes and it will probably market itself!

> Desktop Client is only 1/3 of the overall Dropbox traffic -- the rest 2/3 are split between Web and API

Interesting! I assume the desktop client is still dropbox's main product so that's surprising to hear. Is it because the desktop has everything cached and rarely has to download whereas web and mobile has to download a fresh copy each time they are viewed?

The theory of hashing never matched up well with how I've experienced it in the real world. For example almost all analysis of the hash table (for proving stuff about load factor, chain length, or probe clustering sizes, etc) starts off with a "uniform hashing" assumption. But that assumption have basically never held true given how languages define their default hashes.

I've never heard of the eytzinger layout but it seems like it's just a static binary tree on a array (children are at 2i and 2i+1), commonly used for heaps and segment trees.

Very readable blog post on how it helps with binary search: https://algorithmica.org/en/eytzinger

With follow up post on N-ary approaches: https://algorithmica.org/en/b-tree

Remember to url escape your words. For example if you want to search for a hash tag you need '%23' instead of '#'

e.g., https://thoughts.sushant-kumar.com/%23MeToo

The readme doesn't describe why it's faster. Looking at the code of the variant that is the fastest: https://github.com/scandum/binary_search/blob/master/binary-...

It seems like it's a quaternary search which seems like an arbitrary "magic number" of interior points. It's easy to understand what it does if you already know other variants like ternary search (cut search space into 3 to pick 2 interior points) or golden section search (same thing as ternary except in golden ratio). Here, quaternary search is just picking 3 interior points after dividing into 4 parts.

So the speed up is the same as how b-trees get their speedup: increase branching factor which costs more comparisons but reduces the depth. I might be wrong, but instead of quaternary it could also be 5-ary or 8-ary or any B-ary and any of these variants can also have the potential to perform better.

Just a tradeoff between: cost_of_divide * log_B(N) + cost_of_compare * (B - 1) * log_B(N)

EDIT: Thinking about it more, the divison doesn't seem like it should be the most expensive operation (especially relative to compares/branching). Anyone have any better ideas on why you would prefer more compares? Is it some pipelining thing?

I have seen HN comments saying madison seating refurbish using cheap non-genuine parts: https://news.ycombinator.com/item?id=22553667

What's the verdict?

That Foundations of Applied Mathematics series is such a gem! I skimmed it a bit and it covers a huge breadth of topics ranging from from numerical methods to traditional algorithms. All the while being practical about how you would actually apply it in the real world (for example it has code samples for using the networkx library instead of writing your own graph algorithms, and many more code snippets for using numpy/sympy/cvxpy/etc).

Thanks for linking it!

Python collections doesn't have basic data structures like red black trees (which are in java as java.util.TreeMap or c++ as std::map). You end up needing third party libraries like sortedcontainers.

Watching good people's work-in-progress and debugging process helped me a lot in getting better myself.

This is especially true in competitive programming where everyone is solving the same task!

Some competitive programming streamers:

William Lin: https://www.youtube.com/channel/UCKuDLsO0Wwef53qdHPjbU2Q

Errichto: https://www.youtube.com/c/Errichto

SecondThread: https://www.youtube.com/channel/UCXbCohpE9IoVQUD2Ifg1d1g

Alex Wice: https://www.youtube.com/channel/UCQmrwIwzEu8MxplJw9EUcAg

All youtube links because I do random old contests on leetcode/codeforces and usually at least one of the people above would have a screencast recorded (though unfortunately not always with commentary). Some of them also have twitch.

If you include Borg (Kubernetes' predecessor as an internal tool at Google), then the tech has been around since 2003:

https://blog.risingstack.com/the-history-of-kubernetes/

I am sure that's not what they meant though!

We tend to overestimate how often a document will be modified. For example wikipedia seems to keep "a history of every change ever made to the document" and they seem to be managing fine. If there are bad actors, what you need is better moderation. Having easy undo helps a lot in that case!

The empty loop in python was surprisingly slow (68,000,000 iterations per second).

What is it actually doing here? A 3ghz cpu has 3 billion cycles per second. So it's spending an average of 44 cycles to increment an integer and compare???

(also fun fact, python integers are 28 bytes, but it still doesn't really explain the slowness: `import sys; sys.getsizeof(123456)`)