Microsoft Interview Question
Developer Program EngineersCountry: -
Interview Type: Phone Interview
If encrtyped form is a1b1c1d1, then decrypted form is abcd.
In this case encrypted form is not less than or equal to decrypted form.
@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
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.
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
<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>
#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;
}
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--------'
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--------'
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--------'
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
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
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;
}
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.
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)
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--;
}
}
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.
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.
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.
- eugene.yarovoi October 31, 2011Maybe 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"?