Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Hi,
The problem is to find whether the said operation can be done in the given steps, if it is to find the lowest number of steps needed it would be simple,
It would get harder in this case, say you rotated once and changed one character and you already got the destination (2 steps) and the given number of steps is 4, what you can now do is, change one character twice to make it 4 steps and the answer would be yes..
he specifically told to check only if its possible with the given number of steps or not.. he is not worried if it can be solved with lower number of steps :)
Agreed. First we need to find out in how many steps it can be done. If the number of steps in the input is less than that then it cannot be solved.
If greater then find the number of extra steps. If its even then we can solve the problem in the given number of steps (one step to change something and other to undo that). If odd then it cannot be solved.
The question looks very tough but becomes easy with the following observation.
- kr.neerav February 09, 2014First we rotate the source string (left or right) to get the maximum match with target. Then change the mismatch characters. If there are n characters in the string then the complexity will be:
1) n times we rotate the array and do n comparison for each rotation = O(n^2)
2) one scan of both source and target to change the mismatch = O(n)
But i guess the n^2 complexity is still very poor. Looking forward to a smarter algorithm for it.
Once we have the minimum number of steps it can be done then we can verify if it can be done in the given number of steps in input.