sudhanshu22
internet
internet
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.
Hi all,
- sudhanshu22 June 09, 2008I am pretty new to this forum.
My solution to the above problem would be:
We already know that current pointer points to beginning of a character.
Our target is know where does the previous character begin. The previous character can begin at 1 byte left or 2 bytes left. We don't bother about other characters.
two/three/four previous bytes inspection
pattern 00 -- previous common character starts with immediate left
pattern 11 -- previous uncommon character starts with two bytes left
pattern 01 -- This is not an allowed pattern. Note that we will have found a character when we have moved 2 bytes to the left. here 1 means it is not a1 byte character and 0 means it is not a 2 byte character.
patttern 10 -- This is ambiguous and we need to explore furthur.
needs to look the third byte to the left and we derive 110
or 010 .
If it is 010,then it is (0)(1 0), i.e. the previous character is a 2 byte character, note that if we took
(0 1)(0), we would encounter a (0 1) pattern which is not an allowed pattern.
if it is 110, then it can be (..1) (1 0) or it can be
(1 1)(0).So we need to explore furthur one byte.
So we can have 1110 or 0110.
In case of 0110, we can have (..0)(1 1)(0) again because (0 1) is not an allowed pattern.
In case of 1110, we have ambiguity, so explore furthur.say we get 01110, so the pattern is (1 1)(1 0).( see that (1 1)(0) is not allowed because we will again have 0 1 , which is not an allowed pattern.
lesson: we get ambiguity for 11111...0 series, and once we get 01111...0, we stop.
So once we get a zero on left, we stop. Now for finding the answer, we can look at our lesson, we can count the no of 1's , if we get an even no of 1's,(like 0110), we can say that last character begins at the 1st byte from the current position.
if we get an odd no of 1's(like 01110), we cna say that last character begins at 2 bytes from the current character.
Hope the problem is solved.