I had a google phone interview today, below are the questions that the interiewer asked me:
- Given a char array remove all occurances of 'a'.
Example:
Input: ['a', 'b', 'c', '\0']
Output: ['b', 'c', '\0']
Requirements: Linear time and Constant space complexity.
My Solution: Move all non 'a' characters as much front of the array as possible by keeping track of the index of the last 'a' char. Trim the array till last index.
Interviewer seemed to be impressed by the solution.
Follow Up:
Remove all occurances of 'a' and replace all occurances of 'b' with 'b','e','e'.
I asked if there would be enough space in the array to do this operation so he said yes.
I couldn't solve the problem but suggested that whenever there I see a 'b' I would move all the characters 2 spaces forward and add 'e', 'e' after. However, I also suggested that this approach is not scalable and couldn't come up with an actual working algorithm.
I think they were pretty simple problems but I messed up. Anyway, wishing you guys all the best.
Update 02/21/2019: I got selected for the onsite interview.