## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: Phone Interview

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

``a.length() + ' ' + a + b``

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

a or b may not contain a digit (a.length())

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

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.

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

Need a space in case the first letter in string a is a number.

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

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

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

No, if you know the length of str1, the rest of the string is str2.

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

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.

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

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.

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

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.

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

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.

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

a.length() + ' ' + a + b

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

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.

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

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

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

what if both strings have same repeating characters?
ex: str1=aaa, str2=aa

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

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.

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

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.

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

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.

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

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.

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

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.

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

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?

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

I don't think you can solve this without using encoding. See my answer with encoding.

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

simple
write the new string as
a+b
where
a is str1
b is str2
+ is by convention the joining char

if a has + then escape it as usual using \.

while parsing separate at + keeping in mind escaped +'s in a.

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

just write str3 as a+b
where
a is str1
b is str2
+ is used by convention as the "join" point.

If a has '+' escape it using \. Escape \ using \

when parsing split at + but parsing escaped + and \ properly.

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

Agree... given approach does not work with un-equal strings.
Marcello's approach works if extra memory is given.

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

str1+str2+' '+no. of char in first string

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

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

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

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 "\+".

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

You can use XML construct to represent two strings in a third string. The characters "
' < > & should be replaced with corresponding escape characters before placing in the XML tags.
E.g.,

``str3 = <String1> AT&ampT</String1><String2>Tmobile</String2>``

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

we can add hashcode of the two strings to the concatenatd string

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

str1="sw" str2="ks"
str3=sw' 'ks(i.e str3=sw+' '+ks)
when we see a space we break and assign it to str1 and the characters after space to str2
.here str3.length()=str1.length()+str2.length()+1.

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

It could be done by adding the length of the first
string as first character in the string and at the end adding the hash code.

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

If the strings are equal length, we can weave the 2 strings together.

weave(abc, xyz) will return axbycz.

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

Maybe they're being cute and want you to realize that 'null' is a valid delimiter...

``str3 = str1 + null + str2 + null +null``

You can contrive two scenarios: str1="a", str2="" and str1="", str2="a". Without a delimiter there is no way to tell the difference between the resulting str3's.

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

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.

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

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"

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

how about strings have unequal length?

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

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?

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

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.

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.