Microsoft Interview Question for Developer Program Engineers

Country: -
Interview Type: Phone Interview

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

It's actually not that trivial. Did you overlook some details? If you can't use extra space and "aaa" takes up more space than "a3", you will overwrite the "b" in "b4". The trick is to determine how much space is needed first, treat that as the back of the array, and start placing letters there (work from the back). But even with that approach, you have to be careful because if you have text like "a3b2c2a1a1a1", you're going to overwrite the middle of the string with this algorithm because "a1" is longer than "a". You might have to do a pass to eliminate instances of things like "a1" and "a0" and get the string to a form where every encrypted form is shorter than or equal length to the decrypted form.

Maybe there's a better way to do it, but it doesn't seem that simple. But a question to you: would your algorithm have passed the case "a3b2c2a1a1a1"?

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

a0 and a1...nice observation

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

why did you say passed the case "a3b2c2a1a1a1"...why didn't you include a0 too?

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

If encrtyped form is a1b1c1d1, then decrypted form is abcd.

In this case encrypted form is not less than or equal to decrypted form.

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

@anon: I didn't need to. Many algorithms would flunk just the case I gave. It's perhaps better to consider "a3b1b1b1b1b1a3" because both algorithms starting from the front and algorithms starting from the back will fail that unless they first filter instances of letter1

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

When a string is written in this form, it is to compress the string. I dont think cases like a0 / a1 / b1b1b1 etc make sense here.

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

Eugene, you pointed out the traps to solve the problem but what exactly is the solution?

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

Pseudo code

``````start =0;
end = length of crypt array - 1;

while(start<end)
{
if(arr[end - 2] < end - 1) // condition to check whether we can decrypt from backwards
{
copy the elements from back of an array ;
end = end+2;
}
else  // deecrypt from front of an array
{
copy the elements from front of an array;
start = start +2;
}

}``````

correct me if i am wrong .. thank you

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

<pre lang="" line="1" title="CodeMonkey32792" class="run-this">
#include<iostream>
#include<math.h>

using namespace std;

int main()
{
char op[4];
int n=3;
int i,j,a,m;

for( i=0 ; i<pow(2,n) ;i++)
{
m=i;

for(j=0;j<n;j++)
{

a = 1;
a = m & 1;
m=(m>>1);

if(a==0)
{
op[j]='p';
}
else
{
op[j]='o';
}
}

op[j]='\0';
for(j=0;op[j];j++)
{
cout<<op[j];
}
cout<<"\n";
}
getchar();
return 0;
}
</pre><pre title="CodeMonkey32792" input="yes">
</pre>

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

``````#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

int main()
{
char str[100] ;
int l ;
int i , j ,k;
int ct ;
int final ;
int use ;
char ch ;
scanf("%s",str);

l = strlen(str);

ct = 0 ;
for(i = 1 ; i < l ; i+=2)
{
ct += (str[i] - '0');
}

final = max(l,ct);

i = final - 1;
j = l - 1;

while(j >=1)
{
use = str[j] - '0';
ch = str[j-1];
for(k = 0 ; k < use ; k++)
{
str[i] = ch;
i--;
}
j -= 2 ;
}

if(ct >= l)
{
str[ct] = '\0';
printf("%s\n",str);
}
else
{
for(i = 0 ; i < ct ; i++)
str[i] = str[i+l-ct] ;
str[ct] = '\0';
printf("%s\n",str);
}

return 0;
}``````

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

Your code wont work for this : b3a1a1a1a1a1a1a1a1a1a1b3
Reason being: final output is smaller than input and contains both expanding and contracting elements. If you keep overwriting from end, b3 in end will overwrite a'1'b3 .and you would lose information

So, the solution I guess should be :

Pass 1 : find final as you have done i.e final=max(l,ct)
and contract the contracting strings i.e make your string as b3aaaaaaaaaab3 - O(n) operation

Pass 2: Now this string can ONLY expand. Scan this string (your scanning method will change a little bit as now, odd indices dont neccesarily contain an integer. Deal with it somehow-not a big problem).
So scan this string and start writing from final backwards. - O(n)

Pass 3 : If some space is remaining in the front like in this cas the converted string would be : --------bbbaaaaaaaaaabbb
Where '--------' is trash containing b3a1a1a1. Shift your answer backwards to 'bbbaaaaaaaabbbb--------'

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

Your code wont work for this : b3a1a1a1a1a1a1a1a1a1a1b3
Reason being: final output is smaller than input and contains both expanding and contracting elements. If you keep overwriting from end, b3 in end will overwrite a'1'b3 .and you would lose information

So, the solution I guess should be :

Pass 1 : find final as you have done i.e final=max(l,ct)
and contract the contracting strings i.e make your string as b3aaaaaaaaaab3 - O(n) operation

Pass 2: Now this string can ONLY expand. Scan this string (your scanning method will change a little bit as now, odd indices dont neccesarily contain an integer. Deal with it somehow-not a big problem).
So scan this string and start writing from final backwards. - O(n)

Pass 3 : If some space is remaining in the front like in this cas the converted string would be : --------bbbaaaaaaaaaabbb
Where '--------' is trash containing b3a1a1a1. Shift your answer backwards to 'bbbaaaaaaaabbbb--------'

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

Your code wont work for this : b3a1a1a1a1a1a1a1a1a1a1b3
Reason being: final output is smaller than input and contains both expanding and contracting elements. If you keep overwriting from end, b3 in end will overwrite a'1'b3 .and you would lose information

So, the solution I guess should be :

Pass 1 : find final as you have done i.e final=max(l,ct)
and contract the contracting strings i.e make your string as b3aaaaaaaaaab3 - O(n) operation

Pass 2: Now this string can ONLY expand. Scan this string (your scanning method will change a little bit as now, odd indices dont neccesarily contain an integer. Deal with it somehow-not a big problem).
So scan this string and start writing from final backwards. - O(n)

Pass 3 : If some space is remaining in the front like in this cas the converted string would be : --------bbbaaaaaaaaaabbb
Where '--------' is trash containing b3a1a1a1. Shift your answer backwards to 'bbbaaaaaaaabbbb--------'

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

Nice Problem
1.if we start writing from right we may override some information
example a1b1c3
abccc
2. Similarly if we start writing from left we may override some information
example a3b1
aaab
A better example is the combination of both

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

if we start writing from right we may loose information

example a1b1c3

abccc

if we start writing from left we may loose information

example a3b1

aaab

better example would be the combination

Ques: a 3 b 1 a 1 c 3
I No. of char can be written: 1 2 3 4 5 6 7 8
II No. of char req to be written :1 3 4 4 5 5 6 8
III = I - II: 0-1-1 0 0 1 2 3
ans: a a a b a c c c
fill right to left until III is negative and fill left to right until III is positive

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

I don't understand what the logic is for this? Please elaborate more.

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

if we start writing from right we may loose information

example a1b1c3

abccc

if we start writing from left we may loose information

example a3b1

aaab

better example would be the combination

Ques: a 3 b 1 a 1 c 3
I No. of char can be written: 1 2 3 4 5 6 7 8
II No. of char req to be written :1 3 4 4 5 5 6 8
III = I - II: 0-1-1 0 0 1 2 3
ans: a a a b a c c c
fill right to left until III is negative and fill left to right until III is positive

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

Can u please elobarate the explanation

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

Are the numbers present in the crypt array will definitely be single digit?
If yes,we can relax to some extent.
Btw, we got to move the chunks to the right.
Lets design an algo which have minimum copies involved.

Beginning from the right end of the array have the advantage of avoiding the overwrites.
//Pseudo Code
int arr[MAX];
len = length of the crypted array-1;
j = MAX-1;
while(len>=0)
{
int rep = atoi(len);
char c = *(len-1)
while (rep>0)
{
arr[j] = c;
rep--;
j--;
}
len = len -2;
}

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

The most difficult case would be : b3a1a1a1a1a1a1a1a1a1a1b3
This string contains both expanding and contracting elements.

So, the solution I guess should be :

Pass 1 : Let li=length of input , lo= length of final output
So find value final as -- final=max(l,ct)
Now, contract the contracting strings i.e make your string as b3aaaaaaaaaab3 - O(n) operation

Pass 2: Now this string can ONLY expand. Scan this string (your scanning method will change a little bit now,as odd indices dont neccesarily contain an integer. Deal with it somehow-not a big problem).
So scan this string and start writing from final backwards. - O(n)

Pass 3 : If some space is remaining in the front like in this cas the converted string would be : --------bbbaaaaaaaaaabbb
Where '--------' is trash containing b3a1a1a1. Shift your answer backwards to 'bbbaaaaaaaabbbb--------'

Do let me know if any one finds an error in this method.

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

b3a1a1a1a1a1a1a1a1a1a1b3 Is the most difficult case because this would fail most of the algorithms written on this thred (pardon me if i am wrong as ive not gone through all of them)

Reasom being: If you start overwriting and putting bbb from front you would lose first a(bbb1a1...) and if you overwrite and putting bbb from end you would lose 1 (....a1abbb)

Also a correction : final=max(li,lo)

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

Sample code in C#.

void DecryptArray(char[] ch)
{
int index = 0;
int i = 0;
int k = 0;
char c = ' ';

Reverse(ch, 0, ch.Length - 1);

while (true)
{
if (ch[index] == ' ')
index++;
else
break;
}

for (int j = ch.Length - 1; j > index; j -= 2)
{
i = Convert.ToInt32(ch[j - 1].ToString());
c = ch[j];

while (i >= 1)
{
ch[k] = c;
k++;
i--;
}
}
}

void Reverse(char[] ch,int start,int end)
{
while (start < end)
{
char temp = ch[end];
ch[end] = ch[start];
ch[start] = temp;
start++;
end--;
}
}

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Lets the array size be N and string input size be M.

1) Copy ( M...0 ) to ( N .. ( N - M ). The order need to reverse so that there is no overwrite.
2) Now have two loop variables i = 0 , j = N - M.
3) Start a loop from j to N
4) start writing to i ..increment i as necessary.

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

You're assuming M < N. Consider the case "a3b1b1b1b1b1a3". Here N = 11 and M = 14.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@wavelet: Could you elaborate your algo?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

small modification for the above code ..

before entering the while loop .perform the below operation

if d given input is a1b2c3 , add the prev number to the present number which gives you the poistion of next character to place..
i.e in a1b2c3 edited string ll be a1b3c5 so b can be inserted from 1 'c' can be inserted from position 3.

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

If it's only ascii , we need only 127 for all ASCII. So the most significant bit can be reused to mark whether it's a count number or not. Also the limit is you can only have counter max 127. For example, you have a.....a (128 a), you need encode into:
"127"a1a (127 should be one byte)

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

It is a trivial Qustion

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

Nice soln

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

It is a trivial Question

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.