Microsoft Interview Question
Country: India
One way is to find this out in O(k)..
lets say A is one byte element and BC are two bytes i.e. B 1st byte and C is 2nd byte
1. Now start with i=0 i.e. first element
1a if element is b/w 0-127 it has to be A, increment i by one
1b if element is b/w 128-255 it has to be B, now increment i by 2 as next element has to be C , so i = i+2
repeat 1a and 1b until i>=k..
In this case you would miss out on finding out if kth element was the first or second byte of 2 byte. Run the algorithm with the following array for k=4 and k=5, where k starts from 0. In both cases it will come out of the loop after k=4 and the solution will show B.
[1,1,1,1,200,1]
Incrementing by 2 is not an option.
A better solution would be:
1. If element is between 128 and 255,
1a. Check if previous value was B, current is C, else current is B
2. If element is between 0 and 127,
2a. Check if previous value was B, current is C, else current is A
@tallitester
We will terminate the loop if i>=k.
if i=k we know what it is.
if i>k, it means element at k was C.
Say one byte number is represented as A and two byte number is represented as B1B2
now take number(k) byte number
x = number(k)
Case 1:
if x < 128 then x is either A or B2.
Now take number(k-1) byte number
y = number(k-1)
if y > 128 then x is B2 otherwise A
Case 2:
x > 128 then it is B1
Wrong solution.
Case 2 is wrong when x>128 it can be B1 or B2
E.g. we have a (120)(129)(129) i.e. AB1B2 lets say k =2 i.e. B2
if ( k==0 )
check if array[k]>127
must be the 1st byte of 2 byte char.
else if array[k]<128
it must be the 1 byte char.
if ( k!=0 )
check if (array[k] range 0-127 )
either it is the 1 byte array, or the 2nd byte of two byte character
check if ( array[k-1] lie in range 0-127)
1 byte character as 1st byte of 2 byte cant contain value less then 128
else if ( array[k-1] lie in range 128-255 )
then that k-1 is either the 1st byte of 2 byte or 2nd byte of 2byte, and
we cannot decide exactly about the one at index k, so we will keep on
moving left until when we can find uniquely about a particular indexed char,
and will move back upto k to find the value.
A similar argument will be used for solving if the value at index k is more than 127.
Define 3 types of character:
- upi March 13, 2012A - 1st byte of 1-bytes character;
B - 1st byte of 2-bytes character;
C - 2nd byte of 2-bytes character.
Define 2 characters value types:
type (1) is character [0-127];
type (2) is character [128-255].
if k == 0 we have clear solution.
In case of k>0 we can consider two character str[k-1] and str[k].
Take a look at all variants of their types:
(1) (1) - result in str[k] has type A
(1) (2) - result in str[k] has type B
(2) (1) - ambiguous
(2) (2) - ambiguous
So, in case of type of str[k-1] is (2) we should make further investigation for str[k-1] (recursion).
When we find out type of str[k-1] we consider few variants:
A (1) - result in str[k] has type A;
A (2) - result in str[k] has type B;
B (1) - result in str[k] has type C;
B (2) - result in str[k] has type C;
C (1) - result in str[k] has type A;
C (2) - result in str[k] has type B.
Well, all we have to do is go from k-th position down to first character of type (1), then return back.
Complexity in worst case O(k).