I had an interview with Google (onsite) and one of the questions was: redacted for me, its quite obv that the max number is the total number - the amount of clusters there are, since each marble cluster must have one marble remaining. What kind of proof was he expecting??? Anyways i stumbled on this and wasted time prior to coding the solution. I gave the optimal approch (union find + path compression) but didnt have enough time to finish coding it, but mentioned how i would do it. Obviously i failed due to the lack of time. What the heck is the solution for the proof?
By proof they probably just wanted an explanation and maybe running through examples?
I did that, still wasnāt satisfied
If you can't prove the correctness of a solution there's no point coding it.
Yes thatās what happened, I proved it for up to case k but based on another users reply I guess I needed to prove k+1...
In that case I believe your solution might have been incorrect. When an interviewer asks you a question, it's meant to nudge you in the right direction. If she was asking for proof it means she wanted you to take another look at your solution and hit that Aha! moment where you realized the flaw in your solution and corrected it.
Would be useful if you can give your explanation to us. Maybe draw the diagrams in a notebook and then post the picture along with your explanation. Folks can provide decent feedback based on that. (Assuming you are looking to improve rather than just vent today.)
I got the answer I needed above - use strong induction not just induction. Sad life
I did CS and donāt even know what are the differences between a strong induction and an induction. But hey... what matters if $$$.
Ya go figure, I did engineering so Iām even more lost than you are
I think he was just surprised that I came up with the solution so quickly and probably thought I had seen it before. Itās funny because I also mentioned bidirectional BFS on another interview question which too is the most optimal approach and the interviewer said they had never had someone suggest that. I was absolutely killing it (L4) but never practiced proofs, was completely thrown off guard. Not bashing the google interview process, the problems were really fun and I hadnāt seen them before. So props to them, came out learning a lot. Unlike Amazon... boring ass leetcode problems that you can find on the front page and they managed to throw three leetcode hard questions in one interview loop. So troll.
I was also asked for proof but for a different problem. If you canāt proof you might not have understood the problem well - this I think a new signal google started collecting.
You can always remove some element from the cluster without inducing a partition. There's a simple algorithm to find a valid candidate, but I wouldn't say it's obvious enough to handwave
Itās not? Iād say it is, there should always be a path to remove every possible node besides the root for a cluster. It just makes sense idk
@sookme This is equivalent to proving that there is a hamiltonian path through each connected component of the graph ("each stone can only be picked up once" is equivalent to saying each vertex can only be traversed once). You would have to prove that the graph made by the stones has a hamiltonian path. Why does it just make sense for every such graph to have a hamiltonian path?
Why union find + path compression? Why not just a simple dfs to find connected components? Total marbles remaining= number of connected components. Can be done in o(n+e). Is union find + path compression even more efficient?
More space efficient Actually more time efficient as well.. unless i think if you store if an element has been visited already or cache it somehow. I found the problem, itās on leetcode actually, 947
If you proposed union find where simple Dfs wouldāve sufficed, you failed.
Itās a graph problem
Yes I know I gave the optimal solution. But whatās the proof?
I canāt remember exactly but itās in one of the founder of Akamai technology lectures on mit open course.discrete mathematics on mit open course on YouTube