On the KMP interview...
Was reading a thread on blind about someone asking it in an interview. How would it be seriously possible for one to come up with the backtracking table algorithm on the spot? That algorithm took several years to the KMP guys to develop and they even published a paper, how can one expect to reinvent it? Am I just way too dumb for this game?! If I was asked such question, I would implement either a simple solution based on rolling hash, making sure that I highlight the worst case scenario, or I would code the KMP algorithm leaving the backtrack table as a black box, explaining what it does with an intuitive example but *not* coming up with a solution. If I were an interviewer and I’d see a candidate coding the KMP backtracking table, I’d start hammering the shit out of him/her with mathematical questions on the state machine until he/she admits that he/she fucking memorized it and was cheating, or until I found out that he/she is the real deal and didn’t just memorize it from watching some YouTube video. Seriously, are you saying I’d be canned with this approach?
This happened to me too...there are 2 schools thought.. one..people want you to know shit.. it is like you can't solve this.. it is a very well known question.. what the hell.. other one is.. I want him to get close to a particular stage of solving this question.. second one is better because they will bounce ideas and try to get to the solution.. first kind of interviewers are pure bred a**h***s
Is the censored word archives?
Anchovi s?
What do you think about quicksort and merge sort? They took quite a bit of research to be invented. And there are many questions based off that.
I don’t know, you have a point but I see quicksort and merge sort as much easier algorithms. Once you have the idea, all it takes is basic recursion and not getting confused with indexes, which is something that can reasonably be expected from a swe. Calculating the backtracking table is instead a lot of logic that is incredibly difficult to come up with in 45min.
@OP I would place quick sort and merge sort in the same boat. Unless someone is a genius or has exceptional memory, in order to compete in the job market they would still have to review these before job interviews!
Even the rolling hash approach is kinda finicky tbh. Getting it right is hard
Yes, unfortunately the whole process sucks. I just started interviewing and this whole process is depressing! I recently got asked a question, where if I knew the "trick" it wouldn't take more than 5 mins to write up the code, it took me 40 mins and the interviewer said your implementation is very "slow". So I asked him how he would do it, he gave me the equation and but didn't even know how and why it worked! I later implemented it his way and it took the same amount of execution time for large and small data sets. If only companies would allow candidates to interview the employees!
If you can explain kmp clearly, then you definitely deserve a strong hire. If you do not know kmp, it does not mean a no hire.
You’re not expected to invent KMP in the interview. Just solve leetcode mediums and be really good + fast at it. Like 90%+ success rate and you should be able to solve them in <20 mins during practice.