Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
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.
Space overhead is O(n).
Can we have a better solution??
"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.
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;
}
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;
}
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)
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
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.
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?
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.
//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[26] = {0}, s2[26] = {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;
}
--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[26];
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;
}
public static boolean isStringSame(String str1,String str2){
int [] array=new int [256];
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;
}
public static void main(String a[])
{
String s1,s2;
boolean flag=true;
s1=a[0];
s2=a[1];
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");
}
CareerCup
Questions
Salaries
Forum
Resume
Chat
Blog
RSS
Sign In ▼
Amazon Interview Question for Software Engineer / Developers
amazon-interview-questions 22 Answers
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.
Space overhead is O(n).
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
Reply to Comment
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
Reply to Comment
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
Reply to Comment
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
Reply to Comment
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
Reply to Comment
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
Reply to Comment
0
of 0 vote
can somebody pls give examples???
- Anon on April 17, 2012
Exmples:
String1 - dad, String2 - add
String1 - mad, String2 - dam
String1 - cat, String2 - act
In the above, shuffling the characters in String1 makes String2.
- saikrishna chunchu on April 17, 2012
Reply to Comment
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[26] = {0}, s2[26] = {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
Reply to Comment
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[26];
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
Reply to Comment
0
of 0 vote
public static boolean isStringSame(String str1,String str2){
int [] array=new int [256];
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
Reply to Comment
0
of 0 vote
public static void main(String a[])
{
String s1,s2;
boolean flag=true;
s1=a[0];
s2=a[1];
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
Reply to Comment
Subscribe to future comments.
Add a Comment
Name:
Writing Code? Surround your code with
and
to preserve whitespace.
Add Question
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)
Google (478)
Adobe (219)
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.
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. Or, sign up for our expedited Grade My Resume service, and get results more quickly.
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
Information
Team, Contact & About
Chat Room
Chat Room Guide
Salaries
RSS
Behavioral Preparation Grid
Sample Resumes
Products
Cracking the Coding Interview
The Google Resume
CtCI iPhone App
Videos
Services
Mock Interviews
Grade My Resume
Resume Review
Wiser Profile (LinkedIn Review)
Social
CareerCup on Facebook
CtCI on Facebook
Gayle McDowell on Facebook
CareerCup on Twitter
Gayle on Twitter
CareerCup.com © 2012
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 April 17, 2012