> I made mention of a Paint Bucket and the interviewer asked me to implement it.
That is one interesting question. It can be solved trivially with BFS, but there is also some crazy way of doing it without using the stack (or a queue). I am sure the MS Paint uses what I call it the smart zamboni algorithm. You basically pretend you are a zamboni driver, and paint the screen avoiding obstacles but being careful not never paint yourself in a corner. It is complex but uses no stack space. I don't imagine there are any people that could implement it on the whiteboard. I was glad to see that he didn't do some impossible feat.
That is one interesting question. It can be solved trivially with BFS, but there is also some crazy way of doing it without using the stack (or a queue). I am sure the MS Paint uses what I call it the smart zamboni algorithm. You basically pretend you are a zamboni driver, and paint the screen avoiding obstacles but being careful not never paint yourself in a corner. It is complex but uses no stack space. I don't imagine there are any people that could implement it on the whiteboard. I was glad to see that he didn't do some impossible feat.