Amazon Interview Question
Development Support EngineersWhat if I reverse the input lists to the function?
i.e. instead of func(L1,L2), I pass func(L2,L1)
I said put all the character of the first string a binary tree(hash would have been better?) so that retreival takes only log n time. Then get the characters of the second string one by one and check if the tree contains that element. If true remove that element.
Finally if the tree is empty they are equal and vice versa.
I guess I have answered this question right because of reading answers to questions(which are more difficult) like this in Career cup.
as its said, dont worry about complexity..
sort the characters of first string, and then of the second.
see if first_sorted is prefix of second_sorted.
this assumes, duplicates have to be accounted for ( first cotains two 'a's then second should also have.
Associate prime no.s to each chars from a to z.
Now get id for first string => aabc = 2 * 2 * 3 * 5;
similarly get the id for second string.
if the remainder(secondString/firstString) == 0
return true;
else
return false;
public static boolean containsChars(String s1, String s2){
if (s2.length()<s1.length()) return false;
int[] charFlag=new int[26];
for(int i=0;i<26;i++)
charFlag[i]=0;
s1=s1.toLowerCase(); s2=s2.toLowerCase();
for(int i=0;i<s2.length();i++)
{
charFlag[s2.charAt(i)-'a']--;
if(i<s1.length()) charFlag[s1.charAt(i)-'a']++;
}
for(int i=0;i<26;i++)
if (charFlag[i]>0) return false;
return true;
}
// this function could only deal with a~z without case sensitive, otherwise use hashtable
Hi, This code works fine..
import java.util.*;
import java.io.*;
public class stringVerify {
private boolean compareString(String a, String b){
HashMap h=new HashMap();
HashMap h1=new HashMap();
int count=0;
int count1=0;
String com;
boolean flag=true;
//String key=null,key1=null;
int lenA=a.length();
int lenB=b.length();
//System.out.println("Im here");
for(int i=0;i<lenA;i++){
if(h.isEmpty()){
com=Character.toString(a.charAt(i)).toLowerCase();
h.put(com, count+1);
//System.out.println(h);
continue;
}
else{
com=Character.toString(a.charAt(i)).toLowerCase();
if(h.containsKey(com)){
Integer s1=(Integer)h.get(com);
//System.out.println("S2is:"+s1);
s1++;
h.put(com, s1);
}
else {
h.put(com, count+1);
}
}
}
for(int i=0;i<lenB;i++){
if(h1.isEmpty()){
com=Character.toString(b.charAt(i)).toLowerCase();
h1.put(com, count1+1);
//System.out.println(h);
continue;
}
else{
com=Character.toString(b.charAt(i)).toLowerCase();
if(h1.containsKey(com)){
Integer s2=(Integer)h1.get(com);
//System.out.println("S2is:"+s2);
s2++;
h1.put(com, s2);
}
else {
h1.put(com, count1+1);
}
}
}
System.out.println("String B has:"+h1);
System.out.println("String A has:"+h);
Iterator it1=h.keySet().iterator();
Iterator it2=h1.keySet().iterator();
//while(it1.hasNext()){
// System.out.println(it1);
// }
//h.getKeys();
int size1=h.size();
int size2=h1.size();
//System.out.println("Im here");
while(size1!=0&& it1.hasNext()&&it2.hasNext()){
//System.out.println("Im in while");
//System.out.println(it1.next().toString());
//System.out.println(it1);
String key=it1.next().toString();
//System.out.println("Key-1 is:"+key);
String key1=it2.next().toString().trim();
//System.out.println("Key-2 is:"+key1);
if(key.equals(key1)){
// System.out.println("Im here- Keys");
size1--;
Integer q=(Integer)h.get(key);
Integer p=(Integer)h1.get(key1);
//System.out.println("The Values are:"+q+p);
if(q==p){
// System.out.println("Keys are same");
flag=true;
continue;
}
else{
flag=false;
break;
}
}
else{
size1--;
continue;
}
}
//Iterator it1 = h.keySet().iterator();
//Iterator it2=h1.keySet().iterator();
System.out.println(flag);
return flag;
}
public static void main(String args[]){
stringVerify s= new stringVerify();
BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
String a=null,b=null;
System.out.println("Enter String a:");
try{
a=r.readLine();
//System.out.println(a);
System.out.println("Enter String b:");
b=r.readLine();
boolean f= s.compareString(a,b);
//System.out.println(b);
}
catch(Exception e){
}
}
}
boolean functionName(String s1,String s2) {
// sort both the string....
return s1.equalsIgnoreCase(s2);
}
//
import java.util.*;
public class Test {
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
String str1 = new String("aabc"); //$NON-NLS-1$
String str2 = new String("aaabc"); //$NON-NLS-1$
char charArr1[] = str1.toCharArray();
char charArr2[] = str2.toCharArray();
Arrays.sort(charArr1);
Arrays.sort(charArr2);
str1 = ""; //$NON-NLS-1$
str2 = ""; //$NON-NLS-1$
for(int i=0;i<charArr1.length;i++)
{
str1 += charArr1[i];
}
for(int i=0;i<charArr2.length;i++)
{
str2 += charArr2[i];
}
System.out.println("str1="+str1); //$NON-NLS-1$
System.out.println("str2="+str2); //$NON-NLS-1$
if(str2.contains(str1))
{
System.out.println("Contains"); //$NON-NLS-1$
}
else
System.out.println("Doesn't Contain"); //$NON-NLS-1$
}
}
import java.util.Arrays;
public class test {
public static void main(String[] args) {
String s1= "aabc";
String s2 ="abc";
char[] c1= s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
String s3 = String.valueOf(c1);
String s4= String.valueOf(c2);
System.out.println(s4.contains(s3));
}
}
We can also do it using a hashmap.
- Anonymous January 21, 2008Take the second string and have a hashmap with key being the alphabets and value being the number of occurences for that alphabet. Now take the first string and find if a value exists in the hashmap for each character in the string. For duplicates, we can decrement the value in he hashmap.
If for any char, the val in hashmap is zero then the scond string doent contain all the characters of the first.