Amazon Interview Question for Software Engineer / Developers


Team: Kindle-Periodicals
Country: India
Interview Type: In-Person




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

set<char, int> visit; // find the non-unique characters
      set<char> visit2; // put the st1 chars into to hashset
      for (int i=0; str2; i++) 
             visit[str2[i]]++;
      for (i=0; i < str1.size(); i++)
                  visit2[str1[i]] = 1;
      for (auto it = visit.begin(); visit.end(); it++)
                  if (visit2[it->first] == 0)
                           return false;
       return true;

- Anonymous July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use hashing

- coded March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Break down the problem into two tasks.

i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose.

ii) Finding if all the characters hashed in the first string are available in the second string. You can use a bool flag array for this purpose.

- Crash Blossoms March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

i think hashing will require O(n^2) because we will have to compare each non unique item from str1 with all the items in str2...

i think the optimal solution is to:
1- sort the string with the larger length
2- search for all the non unique items in str1 using binary search in str2

this will be O(nlogn) solution

- hitman March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n^2) for hash map?? Dude do you know what hashing is?

- King@Work March 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

He he he… Good question king!

- Snehasish Barman March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If one were to store the contents of an array/string into a HashMap, then they need to traverse the array, pushing the contents into the HashMap which is O(N) ;
And for maintaining the HashMap, it would require an additional space of O(N);
Hope this is useful to you :).

- @Hitman May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

assuming the strings are not too huge.. we represent each character by a prime number.
then multiple each primeOf(char) of str1 and store it in str1_long
mulitply each primeOf(char) of str2 and store it in str2_long

then str2_long should be divisible by str1_long

- quake4 March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this will check whether all the characters in str1 are in str2 or not but not whether all non-unique chars in str1 are in str2. Correct me if wrong

- Vijay March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use two boolean flag1[256], flag2[256]. Firstly, set the character of str2 to true in flag2. Then traverse str1, if flag1[i] == false, then set it true. else find it in flag2, if flag2 is not true, means this duplicate character is not in str2, so return false. at last of the function, return true. O(n)

- tengdongyang March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be divided into 2 sub problems.
1) Finding out unique elements in str1
2) For each unique element in str1, find out if it is there in str2
Assuming the chars in string are in ascii set.

int uniqueChars(char str1[],char str2[]){
static int a[256],b[256];
int i=0,j=0;
int ret = 1;
while(str1[i] != '\0'){
a[str1[i]]++;
i++;
}
while(str2[j] != '\0'){
b[str2[j]]++;
j++;
}
i = 0;
while(str1[i] != '\0'){
if(a[str1[i]] == 1){
if(b[str1[i]] == 0){
ret = 0;
break;
}
}
i++;
}
return ret;
}

- rkt March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just a small tweak, in the last while loop it should be if(a[str1[i]] >1) as we are finding non unique chars and not unique ones. Except for that the code seems good

- Vijay March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just a small tweak, in the last while loop it should be if(a[str1[i]] >1) as we are finding non unique chars and not unique ones. Except for that the code seems good

- Vijay March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ahh my bad..you are right

- rkt March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suffix Tree?

- Anonymous March 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert both strings to arrays. Add all the elements of string2 into a HashSet. Then check for each element in a loop whether elements of string1 are contained in that HashSet. Complexity should be O(n).

- Deepika March 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

string s1 = "aatetdd";
string s2 = "adasfasfasft";
var result=s1.Union(s2).Except(s1.Intersect(s2));
foreach (char c in result)
{
Console.WriteLine(c);
}

- using .net 3.5 June 24, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More