Uber OA, the chain reaction balls problem
Uber OA, the chain reaction balls problem
Took the Uber HackerRank OA last night, 2 problems, 70 min, camera on. Posting the first one since I couldn't find a clean writeup of it before I sat down.
You get a bunch of balls on a 2D grid plus a distance d. Two balls are linked if they share a row or a column and the gap along that axis is at most d. When you pop one ball, everything linked to it goes too, and it chains, so whatever is linked to those also goes. Question is the minimum number of pops to clear the board. Up to 10^4 balls, coords go negative.
Once I realized it's just counting connected components it was fine. The part that ate my time was building edges without going O(n^2). I grouped balls by x, sorted each group by y, and only unioned neighbors that were within d. Then did the same thing grouped by y. Union find, count the roots.
Tested a case like three balls stacked in one column spaced exactly d apart plus one lonely ball off to the side, should be 2. First run gave me 4 because I wrote < instead of <= lol.
Second problem was a simulation thing, got most test cases but not all. Waiting to hear back on whether they move me to phone screen.