## 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).