## Microsoft Interview Question

Country: India

Comment hidden because of low score. Click to expand.
5
of 5 vote

Define 3 types of character:
A - 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).

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

@tallitester...waht if the input is sumthing like 120,2,245,129,245,126 and k=4(index 0 array)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

1. We can find number of 1 byte characters(nA) from 0 to K-1
2. Check if K is of Type A,if not and if K=0 element is B1 if K=N element is B2
3. If not, if((K - nA)%2 == 1) element is B2 else B1

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

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.