Amazon Interview Question
SDE1sTeam: Hyderabad
Country: India
Interview Type: Phone Interview
Why we need a space?? a.length() + a + b should suffice??
We always know that the encoded string starts with length of first string so str3(0) is always defines the length.
How i can get two string back after genrating...
as i thing..
it should be len(str1)+str1+len(str2)+str2..
please correct me if i am wrong..
But this space is also a string other than a and b and according to this question you can't use third string. Correct me if I am wrong.
But this space is also a string other than a and b and according to this question you can't use third string. Correct me if I am wrong.
But this space is also a string other than a and b and according to this question you can't use third string. Correct me if I am wrong.
Assuming both strings are non-empty, I can think of one approach. We repeat first character of each string number of string length times and for both the strings, arithmetic operation must match with string length, or we backtrack (when first character repeates consecutively within the string)
Case 1
S1 = "ab" S2 = "cd"
Results string S3 = "aabccd"
While reading S3, repeating 'a' 2 times means, first string is of length 2, we already read the beginning of the string 'a' (the second 'a') so we read 1 one and if we read 1st string correctly then 2nd string's arithmetic must match (i.e. 2 'c' means S2 length 2 and first char being 'C')
case 2: repeating first character
S1 = "aa" S2 = "bc"
S3 = "aaabbc"
We first incorrectly conclude 3 'a' mean string S1 length is 3 and try to construct S1="abb" but then here S2 construction fails, so we must back track S1 and try S1 length as 2 and repeat. This time we succeed.
Sorry guys for the repeat answer below. For some reason answer posting was acting weird for me and would not show my answer despite of repeating it
Assuming both strings are non-empty, I can think of one approach. We repeat first character of each string number of string length times and for both the strings, arithmetic operation must match with string length, or we backtrack (when first character repeates consecutively within the string)
Case 1
S1 = "ab" S2 = "cd"
Results string S3 = "aabccd"
While reading S3, repeating 'a' 2 times means, first string is of length 2, we already read the beginning of the string 'a' (the second 'a') so we read 1 one and if we read 1st string correctly then 2nd string's arithmetic must match (i.e. 2 'c' means S2 length 2 and first char being 'C')
case 2: repeating first character
S1 = "aa" S2 = "bc"
S3 = "aaabbc"
We first incorrectly conclude 3 'a' mean string S1 length is 3 and try to construct S1="abb" but then here S2 construction fails, so we must back track S1 and try S1 length as 2 and repeat. This time we succeed.
Assuming both strings are non-empty, I can think of one approach. We repeat first character of each string number of string length times and for both the strings, arithmetic operation must match with string length, or we backtrack (when first character repeates consecutively within the string)
Case 1
S1 = "ab" S2 = "cd"
Results string S3 = "aabccd"
While reading S3, repeating 'a' 2 times means, first string is of length 2, we already read the beginning of the string 'a' (the second 'a') so we read 1 one and if we read 1st string correctly then 2nd string's arithmetic must match (i.e. 2 'c' means S2 length 2 and first char being 'C')
case 2: repeating first character
S1 = "aa" S2 = "bc"
S3 = "aaabbc"
We first incorrectly conclude 3 'a' mean string S1 length is 3 and try to construct S1="abb" but then here S2 construction fails, so we must back track S1 and try S1 length as 2 and repeat. This time we succeed.
Assuming both strings are non-empty, I can think of one approach. We repeat first character of each string number of string length times and for both the strings, arithmetic operation must match with string length, or we backtrack (when first character repeates consecutively within the string)
Case 1
S1 = "ab" S2 = "cd"
Results string S3 = "aabccd"
While reading S3, repeating 'a' 2 times means, first string is of length 2, we already read the beginning of the string 'a' (the second 'a') so we read 1 one and if we read 1st string correctly then 2nd string's arithmetic must match (i.e. 2 'c' means S2 length 2 and first char being 'C')
case 2: repeating first character
S1 = "aa" S2 = "bc"
S3 = "aaabbc"
We first incorrectly conclude 3 'a' mean string S1 length is 3 and try to construct S1="abb" but then here S2 construction fails, so we must back track S1 and try S1 length as 2 and repeat. This time we succeed.
Assuming both strings are non-empty, I can think of one approach. We repeat first character of each string number of string length times and for both the strings, arithmetic operation must match with string length, or we backtrack (when first character repeates consecutively within the string)
Case 1
S1 = "ab" S2 = "cd"
Results string S3 = "aabccd"
While reading S3, repeating 'a' 2 times means, first string is of length 2, we already read the beginning of the string 'a' (the second 'a') so we read 1 one and if we read 1st string correctly then 2nd string's arithmetic must match (i.e. 2 'c' means S2 length 2 and first char being 'C')
case 2: repeating first character
S1 = "aa" S2 = "bc"
S3 = "aaabbc"
We first incorrectly conclude 3 'a' mean string S1 length is 3 and try to construct S1="abb" but then here S2 construction fails, so we must back track S1 and try S1 length as 2 and repeat. This time we succeed.
Assuming both strings are non-empty, I can think of one approach. We repeat first character of each string number of string length times and for both the strings, arithmetic operation must match with string length, or we backtrack (when first character repeates consecutively within the string)
Case 1
S1 = "ab" S2 = "cd"
Results string S3 = "aabccd"
While reading S3, repeating 'a' 2 times means, first string is of length 2, we already read the beginning of the string 'a' (the second 'a') so we read 1 one and if we read 1st string correctly then 2nd string's arithmetic must match (i.e. 2 'c' means S2 length 2 and first char being 'C')
case 2: repeating first character
S1 = "aa" S2 = "bc"
S3 = "aaabbc"
We first incorrectly conclude 3 'a' mean string S1 length is 3 and try to construct S1="abb" but then here S2 construction fails, so we must back track S1 and try S1 length as 2 and repeat. This time we succeed.
1. if extra memory is allowed, an array of lengths of 1st string can be used introduced. 3rd string would be computed as str1+str2. when the string needs to be resurrected back, you print first K chars from the 3rd string (K is taken from the lengths array), N-K chars would be your 2nd string.
2. if extra memory is not allowed you can put the length of str1 at the beginning of str3. say you have: str1="abc" str2="def", str3="3abcdef".
3. if non of above is not acceptable then I would ask what encoding is assumed?
Save the data as a byte array. Reserve the first X bytes for the length of the first string (X depends on how many bytes may be needed to encode the largest possible string you can have). After that, place the bytes corresponding to the first string, and then the bytes corresponding to the second string.
To read back the strings, you would first read the first four bytes, which would tell you both how many more bytes you need to read to get the first string, and at what offset you should start reading if you want to access the second string (str1.length + X, relative to the start of your byte array).
Concetanate the two strings with "+". Also, escape existing "+" with "\+" and "\" with "\\".
Example:
str1 str2 str3
abc cde abc+cde
abc+ cde abc\++cde
abc +cde abc+\+cde
ab+c cde ab\+c+cde
abc c+de abc+c\+de
abc\ cba abc\\+cba
abc\+ cba abc\\\++cba
abc\ \cba abc\\+\\cba
To get back the original strings find the only "+" which is not escaped. Split the string there and unescape "\\" and "\+".
Merge 2 strings by considering 1 char at a time. For ex: str1=abcd, str2=zxcv then str3=azbxccdv. To regenerate str1 & str2 consider the alternating characters of str3.
How do you handle repeating chars and/or different string lengths?
(S1 = "a" S2 = "bc" ) Or (S1 = "ac" and S2= "b") will give same output "abc" , what will you reconstruct S1 and S2 as, given S3= "abc"
1. if extra memory is allowed, an array of lengths of 1st string can be used introduced. 3rd string would be computed as str1+str2. when the string needs to be resurrected back, you print first K chars from the 3rd string (K is taken from the lengths array), N-K chars would be your 2nd string.
2. if extra memory is not allowed you can put the length of str1 at the beginning of str3. say you have: str1="abc" str2="def", str3="3abcdef".
3. if non of above is not acceptable then I would ask what encoding is assumed?
I think this 'weaving' solution has potential. We simply need to keep track of where the weaving started at. For example, if str1=abc and str2=ab, we can print
str3=a+bacb.
The decoder would have to scan append into str1 until it encounters the '+' weaving point, from where on it would append alternate character to str1 and other to str2;
Needless to say this more complex than the other solutions presented here, however the answer may not be wrong.
- xtr February 20, 2015