4 ms·

Finding the optimal longest palindrome substring algorithm surely is in the "you'll only get this if you've seen it before" territory. Implementing a binary se

Finding the optimal longest palindrome substring algorithm surely is in the "you'll only get this if you've seen it before" territory. Implementing a binary search algorithm is anything but trivial, you've got overflows, off-by-one errors, passing arguments by value, etc. Sure, the idea of finding the point in the array that starts decreasing with a binary search is simple, but the subtle ways you can write it wrong are practically infinite.

opportune 9y ago
That's true about the binary search. I didn't complete that one in time (although I did relay the algorithm structure). Although I think white boarding gets a lot of undeserved hate, one gripe I have is with its occasional focus on compilable code. Obviously you want to hire a developer that is actually capable of implementing solutions to problems, and one that can code in a timely manner. However, it really stings to get the algorithm right and know what the implementation concerns (overflow/OBOB) are, but simply not have enough time to get them written in a correct/compilable manner. I've failed a few online interviews where I knew the solution to a problem but simply didn't have the time to write it. For example, I got a question that required building a heap, but at some points you needed to remove items from the middle of the heap. This would require being able to call sift-down/sift-up on the underlying data structure. I didn't know how/if I could call sift-down/sift-up on the priority queue implementation of the language they made me use. So I essentially ran out of time because I couldn't look up an algorithm I knew how/why to use. I have to disagree about the palindrome question only because I got it in the last ~15 minutes of a 30 minute first round interview. With 10 minutes passed and 5 remaining, I still only had the naive solution on the board with less than five minutes to go. After a few more minutes of thinking I eventually realized that I had only been thinking of palindromes from outside-in. With about 1-2 minutes left I hurriedly explained to my interviewer that you should check each character and find the largest palindrome that character is the center (or half of a paired center) of, by expanding outwardly. He asked a few questions, then assured me that it was ok to not write it on the board and that he could tell I understood it. It really gave me a good impression of the company that their hiring practices were so rational, and I now work there. I really think anybody would have figured out the problem if they looked at it long enough, it's just that sometimes things like this take 4 minutes and sometimes they take 4 hours. It depends on the person but not strictly an "intelligence" way, I just think there's a lot of variance in how long it takes people, even pretty smart people, to solve sufficiently hard problems.
- SamReidHughes 9y ago
  That's a good solution but it's not the optimal solution. In the worst case that's still n^2. Nobody expects candidates to answer the linear time solution for that question.
- sushisource 9y ago
  Bit of a necropost, but - I agree with most of your points, the thing is, that palindrome question worked out because 1) You had a "realization", which still feels a little "there's a trick to it" to me, which can be a sign of a bad whiteboard Q, I think. Obviously, this is fungible. 2) More importantly, your interviewer didn't suck. They understood the process is what matters, and not the code on the whiteboard. That #2 is the reason I think whiteboard coding is bad. Most interviewers simply aren't trained well enough to evaluate based on process rather than results. That's why I advocate for only doing very simple ones, or not at all, simply because it's less dependent on how good the interviewer is.

opportune 9y ago

That's true about the binary search. I didn't complete that one in time (although I did relay the algorithm structure). Although I think white boarding gets a lot of undeserved hate, one gripe I have is with its occasional focus on compilable code. Obviously you want to hire a developer that is actually capable of implementing solutions to problems, and one that can code in a timely manner. However, it really stings to get the algorithm right and know what the implementation concerns (overflow/OBOB) are, but simply not have enough time to get them written in a correct/compilable manner. I've failed a few online interviews where I knew the solution to a problem but simply didn't have the time to write it. For example, I got a question that required building a heap, but at some points you needed to remove items from the middle of the heap. This would require being able to call sift-down/sift-up on the underlying data structure. I didn't know how/if I could call sift-down/sift-up on the priority queue implementation of the language they made me use. So I essentially ran out of time because I couldn't look up an algorithm I knew how/why to use. I have to disagree about the palindrome question only because I got it in the last ~15 minutes of a 30 minute first round interview. With 10 minutes passed and 5 remaining, I still only had the naive solution on the board with less than five minutes to go. After a few more minutes of thinking I eventually realized that I had only been thinking of palindromes from outside-in. With about 1-2 minutes left I hurriedly explained to my interviewer that you should check each character and find the largest palindrome that character is the center (or half of a paired center) of, by expanding outwardly. He asked a few questions, then assured me that it was ok to not write it on the board and that he could tell I understood it. It really gave me a good impression of the company that their hiring practices were so rational, and I now work there. I really think anybody would have figured out the problem if they looked at it long enough, it's just that sometimes things like this take 4 minutes and sometimes they take 4 hours. It depends on the person but not strictly an "intelligence" way, I just think there's a lot of variance in how long it takes people, even pretty smart people, to solve sufficiently hard problems.

SamReidHughes 9y ago
That's a good solution but it's not the optimal solution. In the worst case that's still n^2. Nobody expects candidates to answer the linear time solution for that question.
sushisource 9y ago
Bit of a necropost, but - I agree with most of your points, the thing is, that palindrome question worked out because 1) You had a "realization", which still feels a little "there's a trick to it" to me, which can be a sign of a bad whiteboard Q, I think. Obviously, this is fungible. 2) More importantly, your interviewer didn't suck. They understood the process is what matters, and not the code on the whiteboard. That #2 is the reason I think whiteboard coding is bad. Most interviewers simply aren't trained well enough to evaluate based on process rather than results. That's why I advocate for only doing very simple ones, or not at all, simply because it's less dependent on how good the interviewer is.