is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
Take an array of 26(assume only small letters present in string). Now this array will store the index of the character in given string. Initially, initialize it with -1. Now traverse string from right to left and change the index value in array based on next promising character.
Consider given string "cbacdcbc". Maintain one variable say 'next_ch' and array 'foo[26]'. Initially,all elements of array is -1. start from right most character and initialize next_ch as 'c'. Now foo[c]==-1, so change it foo[c]=7.
Now the logic is check entry in foo array corresponding to current character. If it is -1 then directly update current index in array and change the value of next_ch as current character. But if value is not -1, then that character is already came in string so check with next_ch. If current character < next_ch. then update the value of foo[current character] to current index. Otherwise leave unchanged. Below is pseudo code for clarification:
So according to above logic, final array has only four entry without -1 because only 4 unique character in string.
- Yug October 26, 2015foo[a]=2; foo[b]=6; foo[c]=3; foo[d]=4;
So generate answer from given string based on above array
cbacdcbc --> **acd*b* --> acdb
time complexity: O(n), n-length of given string
space complexity: O(26)=O(1)