| I went up to level 3 and then work/life took over. Here's my approach to the problems: (1) Python. Used a set() for the dictionary. Got ~200 points. I was planning to go back and implement this in Go to see the difference in performance but never got around to do it. (2) Python. I wrote a single-threaded miner which could do around 300K hashes/s. My miner calculated 1M hashes (~3s), then fetched origin, then continued until it got a hit. I stopped after the first Gitcoin. (3) Node. My solution was very simple and pretty much like the OP's. I kept a map between IP and count and always let through IPs with count <= 4. If the count was > 4, then I let them through with 0.3 probability to keep the backends working. (4) I spend most of my time on this problem, largely trying to keep the memory within the constraints. I started with Node and created a simple inverted index of all words to their positions. Since we needed substring search I had to loop through the keys of the index which was too slow. My next attempt was to index all substrings but that used too much memory. My third, and best, Node attempt was using a prefix tree to index all suffixes, effectively building a suffix tree. This was quite fast, got ~2200 on local tests but was still over the memory limits. I then gave up on Node and moved to Python. I used Flask for the server and built two solutions. A simple inverted index and a prefix tree (using datrie) with all suffixes. To keep the memory footprint low, I stored file/line locations as bit-shifted longs. Amazingly, the simple index and the prefix tree performed the same (!), so I submitted the inverted index solution and got a passing score. Thanks for a great week Stripe. I learned tons! Looking forward to the next one. |