## Amazon Interview Question for Software Engineer / Developers

• 4

Country: India
Interview Type: Phone Interview

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

Read first string in a hash map with keys as the alphabets and values as the occurences of each key. Then read the second string character by character and keep subtracting the value based on every read. Then loop through the hash map and for non zero values; if found then the 2 strings cannot contain one another.

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

Complexity of the solution:
Lets take that, no collision in the Hashmap, in order to insert or search the data, complexity is O(1) - may not be the case always.

In order to insert a String into the Hasmap, Complexity is O(n)
In order to compare the second String with hasmap, Complexity is O(n).
Hence, total complexity is O(n)+O(n) ==> O(2n). We have not considered the complexity of the hasmap yet.

Can we have a better solution??

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

Did the interviewer put a constraint on the complexity?

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

"Can we have a better solution?"

A solution that involves O(m+n) steps like this one is optimal in terms of asymptotic complexity. It's not generally possible to solve this problem without looking at all the characters, and looking at all the characters takes O(m+n) time. So no, we can't have a much better algorithm.

One possibility is just to use an integer count array (say of size 26), one integer for each letter from a-z. That would lower the constant factor of the time complexity significantly. If you have Unicode characters, etc., you'll need a bigger array, so you have to consider whether you want to have that much space overhead.

Another possibility that is of O(mlogm + nlogn) complexity is to sort the letters in each string and see if the sorted strings are identical.

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

Just take the XOR of all the characters present in both the strings, it will come to zero, which shows both are anagram :)

int main()
{
int A=0, B=0;
char a[]="stressed";
char b[]="desserts";

int C;
for(int i=0;i<4;i++)
{ A= a[i]^A; B= b[i]^B; }

if(!A^B)
{ cout<<"\n\nThey are anagrams :)"; }
else
{ cout<<"\n\nThey are different words :("; }

return 0;
}

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

what happens when a char is XORed with 0?
referring to 10th line of your code.

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

this won't work, consider such two strings: "aa", "bb",
they have totally different chars but their XOR is 0.

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

Just do a simple XOR of both strings, resulting in a O(N) time complexity.

``````bool anagrams(char *s1, char *s2)
{
int l1, l2, xv;
int i;

xv = 0;
if (NULL == s1 || NULL == s2)
return false;

l1 = strlen(s1);
l2 = strlen(s2);
if (0 == l1 || 0 == l2)
return false;

if (l1 != l2)
return false;

/* All corner cases verfied, start XOR'ing two strings */
for(i = 0; i < l1; i++){
xv ^= s1[i];
xv ^= s2[i];
}

/* If the two strings did not cancel each other out then they are not anagrams */
if (xv)
return false;

return true;``````

}

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

Take an int array of size 26, Read each character from string1 and increment a value in int array based on the character (if the character is 'a' increment the value at index 0 of int array, use ascii value of each character to get the position/index in array i.e substract 97 from each character to get position, make sure you convert all chars to lower case before doing this)

Read each character of string2 and decrement the value in the same int array.

Check for non zero values in the int array.

Complexity would be O(2n+26)

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

Hi Amit,
This won't behave correctly if both words have all same characters
char a[]="aaa";
char b[]="bbb";
then A = 0
B = 0
!A^B = 1

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

Hi Amit,
This won't behave correctly if both words have all same characters
char a[]="aaa";
char b[]="bbb";
then A = 0
B = 0
!A^B = 1

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

First take the first string starting from first char
and find the occurrence of that char in second string and make it null.
Repeat the same process for all chars in first string.Finally if second string is empty then both are anagrams otherwise not.

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

This O(n2) solution .., it could be in linear :)

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

Sort the strings and then compare. If they are equal, return TRUE else FALSE.

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

How about the worst case complexity?
If i take, quick sort for sorting the strings, then O(n2) would be the complexity for each string.
With this solution, to sort two strings it can reach to O(n2) + O(n2).
Can we have better solution?

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

I agree with NewCoderInTown, Here is the code to do that

``````public boolean isShuffled(String s1, String s2)
{
char[] charArrayS1 = s1.toCharArray();
char[] charArrayS2 = s2.toCharArray();
Arrays.sort(charArrayS1);
Arrays.sort(charArrayS2);
return  Arrays.equals(charArrayS1,charArrayS2);
}``````

if you are still concerned with complexity you can't do it more better than this.

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

can somebody pls give examples???

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

``````Exmples:
String1 - mad, String2 - dam
String1 - cat, String2 - act
In the above, shuffling the characters in String1 makes String2.``````

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

//Given two strings, find that the if the letters in both the strings are same? i.e. can we be able to make string2 out of string1 by shuffling the words and vice versa.

#include<stdio.h>
#include<string.h>

int isshuffled(char *str, char *shuff)
{
int i,s1 = {0}, s2 = {0},flag=1;

if(strlen(str) != strlen(shuff))
return 0;

for(i=0; i<strlen(str); i++)
{
s1[(int)str[i]-97] = s1[(int)str[i] - 97] + 1;
s2[(int)shuff[i]-97] = s2[(int)shuff[i]-97] + 1;
}
for(i=0; i<26; i++)
{
if(s1[i] != s2[i])
{
flag = 0;
return flag;
}
}
return flag;
}

int main()
{
if(isshuffled("apple","plpea"))
printf("\nShuffled string is made from original string");
else
printf("\nShuffled string is NOT made from original string");

return 0;
}

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

``````--C#--
private bool IsShuffled(String s1, String s2)
{
if ((null == s1) || (null == s2)
|| s1.Length == 0 || s2.Length == 0
|| s1.Length != s2.Length
)
{
return false;
}
//Identify characters in s1
char[] chars = new Char;
for (int i = 0; i < s1.Length; i++)
{
chars[(int)(s1[i] - 'a')]++;
}

//Identify characters in s2
for (int i = 0; i < s2.Length; i++)
{
chars[(int)(s2[i] - 'a')]--;
}

//If both strings have the same characters, then chars[] should have 0 for all
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] != 0)
{
return false;
}
}
return true;
}``````

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

public static boolean isStringSame(String str1,String str2){

int [] array=new int ;

for (int i=0;i<str1.length();++i){
array[str1.charAt(i)]++;
}

for (int i=0;i<str2.length();++i){
array[str1.charAt(i)]--;
}

for (int i=0;i<array.length;++i){
if (array[i]!=0){
return false;
}
}

return true;

}

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

``````public static void main(String a[])
{
String s1,s2;
boolean flag=true;
s1=a;
s2=a;
char c;
int val;
Hashtable h=new Hashtable();
for(int i=0;i<s1.length();i++)
{
c=s1.charAt(i);
if(!h.containsKey(c)	)
h.put(c,new Integer(1));
else
h.put( c, new Integer( ( (Integer)h.get(c) ).intValue()+1) );
}
if(s1.length()==s2.length())
{
for(int i=0;i<s2.length();i++)
{
c=s2.charAt(i);
if(h.containsKey(c))

{	val=((Integer)h.get(c)).intValue();
if(val==1)
h.remove(c);
else
h.put(c,new Integer(val-1));
}
else
{
flag=false;
break;
}
}
if(flag)
{
if(h.isEmpty())
System.out.println("ANAGRAM!!!");
else
flag=false;
}
}
else
{
flag=false;
}
if(!flag)
System.out.println("NOT ANAGRAMS");
}``````

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

CareerCup

Questions
Salaries
Forum
Resume
Chat
Blog

Amazon Interview Question for Software Engineer / Developers

Given two strings, find that the if the letters in both the strings are same? i.e. can we be able to make string2 out of string1 by shuffling the words and vice versa.
- saikrishna chunchu on April 17, 2012 in India
Amazon Software Engineer / Developer Algorithm

Country: India
Interview Type: Phone Interview

2
of 2 vote

Read first string in a hash map with keys as the alphabets and values as the occurences of each key. Then read the second string character by character and keep subtracting the value based on every read. Then loop through the hash map and for non zero values; if found then the 2 strings cannot contain one another.
- Mihir on April 17, 2012

Complexity of the solution:
Lets take that, no collision in the Hashmap, in order to insert or search the data, complexity is O(1) - may not be the case always.

In order to insert a String into the Hasmap, Complexity is O(n)
In order to compare the second String with hasmap, Complexity is O(n).
Hence, total complexity is O(n)+O(n) ==> O(2n). We have not considered the complexity of the hasmap yet.

Can we have a better solution??
- saikrishna chunchu on April 17, 2012

Did the interviewer put a constraint on the complexity?
- yeswanth.devisetty on April 17, 2012

"Can we have a better solution?"

A solution that involves O(m+n) steps like this one is optimal in terms of asymptotic complexity. It's not generally possible to solve this problem without looking at all the characters, and looking at all the characters takes O(m+n) time. So no, we can't have a much better algorithm.

One possibility is just to use an integer count array (say of size 26), one integer for each letter from a-z. That would lower the constant factor of the time complexity significantly. If you have Unicode characters, etc., you'll need a bigger array, so you have to consider whether you want to have that much space overhead.

Another possibility that is of O(mlogm + nlogn) complexity is to sort the letters in each string and see if the sorted strings are identical.
- eugene.yarovoi on April 17, 2012
1
of 1 vote

Take an int array of size 26, Read each character from string1 and increment a value in int array based on the character (if the character is 'a' increment the value at index 0 of int array, use ascii value of each character to get the position/index in array i.e substract 97 from each character to get position, make sure you convert all chars to lower case before doing this)

Read each character of string2 and decrement the value in the same int array.

Check for non zero values in the int array.

Complexity would be O(2n+26)
- Anonymous on April 17, 2012

Hi Amit,
This won't behave correctly if both words have all same characters
char a[]="aaa";
char b[]="bbb";
then A = 0
B = 0
!A^B = 1
- Aditya Soni on April 17, 2012

Hi Amit,
This won't behave correctly if both words have all same characters
char a[]="aaa";
char b[]="bbb";
then A = 0
B = 0
!A^B = 1
- Aditya Soni on April 17, 2012
1
of 1 vote

Just take the XOR of all the characters present in both the strings, it will come to zero, which shows both are anagram :)

int main()
{
int A=0, B=0;
char a[]="stressed";
char b[]="desserts";

int C;
for(int i=0;i<4;i++)
{ A= a[i]^A; B= b[i]^B; }

if(!A^B)
{ cout<<"\n\nThey are anagrams :)"; }
else
{ cout<<"\n\nThey are different words :("; }

return 0;
}
- Amit on April 17, 2012

what happens when a char is XORed with 0?
referring to 10th line of your code.
- yeswanth.devisetty on April 17, 2012

this won't work, consider such two strings: "aa", "bb",
they have totally different chars but their XOR is 0.
- iti on April 17, 2012
1
of 1 vote

First take the first string starting from first char
and find the occurrence of that char in second string and make it null.
Repeat the same process for all chars in first string.Finally if second string is empty then both are anagrams otherwise not.
- svkrishna on April 17, 2012

This O(n2) solution .., it could be in linear :)
- Amit on April 17, 2012
1
of 1 vote

Just do a simple XOR of both strings, resulting in a O(N) time complexity.

bool anagrams(char *s1, char *s2)
{
int l1, l2, xv;
int i;

xv = 0;
if (NULL == s1 || NULL == s2)
return false;

l1 = strlen(s1);
l2 = strlen(s2);
if (0 == l1 || 0 == l2)
return false;

if (l1 != l2)
return false;

/* All corner cases verfied, start XOR'ing two strings */
for(i = 0; i < l1; i++){
xv ^= s1[i];
xv ^= s2[i];
}

/* If the two strings did not cancel each other out then they are not anagrams */
if (xv)
return false;

return true;

}

- ashot madatyan on April 18, 2012
0
of 0 vote

Sort the strings and then compare. If they are equal, return TRUE else FALSE.
- NewCoderInTown on April 17, 2012

How about the worst case complexity?
If i take, quick sort for sorting the strings, then O(n2) would be the complexity for each string.
With this solution, to sort two strings it can reach to O(n2) + O(n2).
Can we have better solution?
- saikrishna chunchu on April 17, 2012

I agree with NewCoderInTown, Here is the code to do that

public boolean isShuffled(String s1, String s2)
{
char[] charArrayS1 = s1.toCharArray();
char[] charArrayS2 = s2.toCharArray();
Arrays.sort(charArrayS1);
Arrays.sort(charArrayS2);
return Arrays.equals(charArrayS1,charArrayS2);
}

if you are still concerned with complexity you can't do it more better than this.

- jinalshah2007 on April 18, 2012
0
of 0 vote

can somebody pls give examples???
- Anon on April 17, 2012

Exmples:
String1 - mad, String2 - dam
String1 - cat, String2 - act
In the above, shuffling the characters in String1 makes String2.

- saikrishna chunchu on April 17, 2012
0
of 0 vote

//Given two strings, find that the if the letters in both the strings are same? i.e. can we be able to make string2 out of string1 by shuffling the words and vice versa.

#include<stdio.h>
#include<string.h>

int isshuffled(char *str, char *shuff)
{
int i,s1 = {0}, s2 = {0},flag=1;

if(strlen(str) != strlen(shuff))
return 0;

for(i=0; i<strlen(str); i++)
{
s1[(int)str[i]-97] = s1[(int)str[i] - 97] + 1;
s2[(int)shuff[i]-97] = s2[(int)shuff[i]-97] + 1;
}
for(i=0; i<26; i++)
{
if(s1[i] != s2[i])
{
flag = 0;
return flag;
}
}
return flag;
}

int main()
{
if(isshuffled("apple","plpea"))
printf("\nShuffled string is made from original string");
else
printf("\nShuffled string is NOT made from original string");

return 0;
}
- desaiparthd on April 17, 2012
0
of 0 vote

--C#--
private bool IsShuffled(String s1, String s2)
{
if ((null == s1) || (null == s2)
|| s1.Length == 0 || s2.Length == 0
|| s1.Length != s2.Length
)
{
return false;
}
//Identify characters in s1
char[] chars = new Char;
for (int i = 0; i < s1.Length; i++)
{
chars[(int)(s1[i] - 'a')]++;
}

//Identify characters in s2
for (int i = 0; i < s2.Length; i++)
{
chars[(int)(s2[i] - 'a')]--;
}

//If both strings have the same characters, then chars[] should have 0 for all
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] != 0)
{
return false;
}
}
return true;
}

- IC on April 18, 2012
0
of 0 vote

public static boolean isStringSame(String str1,String str2){

int [] array=new int ;

for (int i=0;i<str1.length();++i){
array[str1.charAt(i)]++;
}

for (int i=0;i<str2.length();++i){
array[str1.charAt(i)]--;
}

for (int i=0;i<array.length;++i){
if (array[i]!=0){
return false;
}
}

return true;

}
- kettlescott on April 18, 2012
0
of 0 vote

public static void main(String a[])
{
String s1,s2;
boolean flag=true;
s1=a;
s2=a;
char c;
int val;
Hashtable h=new Hashtable();
for(int i=0;i<s1.length();i++)
{
c=s1.charAt(i);
if(!h.containsKey(c) )
h.put(c,new Integer(1));
else
h.put( c, new Integer( ( (Integer)h.get(c) ).intValue()+1) );
}
if(s1.length()==s2.length())
{
for(int i=0;i<s2.length();i++)
{
c=s2.charAt(i);
if(h.containsKey(c))

{ val=((Integer)h.get(c)).intValue();
if(val==1)
h.remove(c);
else
h.put(c,new Integer(val-1));
}
else
{
flag=false;
break;
}
}
if(flag)
{
if(h.isEmpty())
System.out.println("ANAGRAM!!!");
else
flag=false;
}
}
else
{
flag=false;
}
if(!flag)
System.out.println("NOT ANAGRAMS");
}

- farhana on April 18, 2012

Name:

Writing Code? Surround your code with

``and``

to preserve whitespace.

CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.

How Can You Help CareerCup?

NEW! Cracking the Coding Interview iPhone App. Search for it on the iPhone / iPad App Store.
Top Companies

Amazon (3031)
Microsoft (1347)
Bloomberg LP (541)
Yahoo (201)
NVIDIA (166)
Qualcomm (166)
Goldman Sachs (142)
Epic Systems (113)
More Companies »

Top Jobs

Software Engineer / Dev... (6027)
Software Engineer in Te... (597)
Financial Software Deve... (242)
Developer Program Engin... (142)
Testing / Quality Assur... (95)
Program Manager (68)
Analyst (62)
Development Support Eng... (58)
Virus Researcher (25)
Quality Assurance Engin... (21)
More Jobs »

Top Topics

Algorithm (3079)
Coding (663)
Data Structures (358)
C (358)
C++ (356)
Terminology & Trivia (294)
Java (282)
Brain Teasers (237)
Object Oriented Design (208)
Arrays (204)
More Topics »

Chat is disabled. Don't you want to hear what people are chatting about? Enable Chat.
Report a Bug or Issue
Books

The Google Resume is a comprehensive book walking you through every aspect of getting a job at a top tech company, while Cracking the Coding Interview focuses on software engineering interviews.

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.

Resume Review

Most engineers make critical mistakes on their resumes. We can fix your resume with our custom resume review service. Or, sign up for our expedited Grade My Resume service, and get results more quickly.

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.

Information

Chat Room
Chat Room Guide
Salaries
Behavioral Preparation Grid
Sample Resumes

Products

Cracking the Coding Interview
CtCI iPhone App
Videos

Services

Mock Interviews
Resume Review

Social

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.