4 rounds of on-site technical interview, first three are just questions with solution patterns on leetcode, 2 medium and 1 easy. What I want to highlight and share here is the 4th round, which breaks my confidence.
Question:
You’re giving two strings source and target , write a function to determine if we could convert source to target .
Limits :
Both source and target are consisted with lower letters, which is a-z .
All available letters in converting are a-z , which means you can not convert one letter to 1 or # or others.
Converting rules:
In one convert operation, you can replace one value with another value , which means if there’re three letters with same value, you need to replace them together. For example, I have "abca" , now I can replace "a" to "d" , then it become "dbcd" . "dbca" is impossible !
You can do convert operation as many as you want.
How I feel:
I don’t know if I described clearly about the question, I’ve struggled about 20 minutes with the interviewer to clearify the question by talking (Now I realized that just asking the interviewer to paste the question is more efficient!). Then all I have was only 20 minutes (Because bath break, self introduction and environment setting cost 5 mins) to figure out the solution. It’s really hard to me, I’m thinking if there is a pattern to handle this but finally with interviewer’s hint (almost equals telling me the answer), I found it’s a un-pattern question and all it’s testing is how I think, not coding.
I would say that I performed well in all other sessions, but get bad feed back from this session, and finally rejected by the hiring committee.
I’m still in practicing, but I know the next time I meet questions like this, I can still not figure out the solution, but maybe I could perform better on communication and problem solving pattern(figure out all cases and write them down then try to solve one by one) to get the luck to earn a neutral feedback.
Solutions:
Check corner cases, like null.
Check the length.
Check violations like "#" .
Check if there exists mapping of one to multiple, like "aba" → "cde" where "a" maps to "c" and "e" . If so, return false.
Check if all letters are used in target , if not then return true. Because we could use the un-used letter to convert each value one by one without affecting others.
Below are some examples:
Question: "ab" → "cd"
Answer: true
Solution: convert "a" to "c" then "b" to "d" , "ab" → "cb" → "cd"
Question: "aba" → "cde"
Answer: false
Solution: the first "a" and last "a" are always same, it’s impossible to make them one is "c" and the other is "e"
Question: "ab" → "ba"
Answer: true
Solution: convert "a" to "d" , then "b" to "a" , then "d" to "b" , "ab" → "db" → "da" → "ba"