Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
This idea in Java:
public void printDifference(String[] a, String[] b) {
TrieSet setA = new TrieSet(a);
TrieSet setB = new TrieSet(b);
for (String s : a) {
if (!setB.contains(s)) {
System.out.println(s);
setB.add(s); // To avoid printing the same word twice if "a" contains duplicates.
}
}
for (String s : b) {
if (!setA.contains(s)) {
System.out.println(s);
setA.add(s); // To avoid printing the same word twice if "b" contains duplicates.
}
}
}
Here is one possible implementation of the TrieSet class (a "real" implementation would also have methods to remove words from the set and to iterate through the elements, but adding and checking is sufficient for this question):
public class TrieNode {
private Map<Character, TrieNode> children;
private boolean isTerminal;
public TrieNode() {
children = new TreeMap<Character, TrieNode>();
isTerminal = false;
}
public TrieNode getChild(char c) {
return children.getOrDefault(c, null);
}
public TrieNode getOrCreateChild(char c) {
TrieNode child = getChild(c);
if (child != null) {
return child;
}
return addChild(c);
}
private TrieNode addChild(char c) {
TrieNode child = new TrieNode();
children.put(c, child);
return child;
}
public boolean isTerminalNode() {
return isTerminal;
}
public void markAsTerminalNode() {
isTerminal = true;
}
}
public class TrieSet {
TrieNode root = new TrieNode();
public TrieSet() {}
public TrieSet(String[] words) {
for (String s in words) {
add(s);
}
}
public void add(String s) {
TrieNode current = root;
for (int i = 0; i < s.length(); ++i) {
current = current.getOrCreateChild(s.charAt(i));
}
current.markAsTerminalNode();
}
public boolean contains(String s) {
TrieNode current = root;
for (int i = 0; i < s.length(); ++i) {
current = current.getChild(s.charAt(i));
if (current == null) {
return false;
}
}
return current.isTerminalNode();
}
}
The above algorithm with the above data structure has average and worst-case time complexity of "total number of characters" * log("size of the alphabet") (which is simply O(n) if the alphabet is fixed and you are guaranteed that all words are under a certain length). Using a HashSet instead of a TrieSet is also possible and reduces the expected runtime to O(n) no matter what, but increases the worst case to O(n^2).
package com.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class StringArrayNonMatch {
public static void main(String[] args) {
// TODO Arrays of strings
String [] a={"yes", "bus", "gut", "yes"}, b={"sr", "dae", "bus", "new", "dae"};
//String temp;
List<String> l1= new LinkedList<String>(Arrays.asList(a));
List<String> l2= new LinkedList<String>(Arrays.asList(b));
for(String temp:a){
if (!l2.contains(temp)){
System.out.print(temp+"\t");
l2.add(temp);
}
}
System.out.println();
for(String temp:b){
if (!l1.contains(temp)){
System.out.print(temp+"\t");
l1.add(temp);
}
}
// l1.clear();
// l2.clear();
}
}
public class two_strings {
public static void main(String []args)
{
String str1 = "sachin" ;
String str2 = "saurabh" ;
int n , m ;
boolean []arr = new boolean[256];
for(int i=0 ; i<str1.length(); i++)
{
n = str1.charAt(i);
arr[n]= true ;
}
for(int i=0 ; i<str2.length(); i++)
{
m = str2.charAt(i);
if(!arr[m])
{
System.out.print(str2.charAt(i));
}
}
}
}
public static void main(String args[]) {
String a[] = { "a", "b", "c", "d" };
String b[] = { "b", "c" };
if (a.length > b.length) {
compute(b, a);
} else {
compute(a, b);
}
}
private static String[] compute(String[] from, String[] to) {
List<String> fr = Arrays.asList(from);
List<String> t = Arrays.asList(to);
String[] comp = new String[t.size() - fr.size()];
int i = 0;
for (String str : t) {
if (!fr.contains(str)) {
comp[i] = str;
i++;
}
}
return comp;
}
public class ArrayIntersectioner{
public static <E> Collection<E> intersection(E[] arr1,E[] arr2){
Map<E, Integer> countMap1 = getCountMap(arr1);
Map<E, Integer> countMap2 = getCountMap(arr2);
List<E> list = new ArrayList<E>(countMap1.size());
for(Entry<E,Integer> e1 : countMap1.entrySet()){
E item = e1.getKey();
Integer count2 = countMap2.get(item);
if(count2 == null){
continue;
}
Integer count1 = e1.getValue();
int minCount = Math.min(count1, count2);
for(int i = 0; i< minCount; i++){
list.add(item);
}
}
return list;
}
private static <E> Map<E, Integer> getCountMap(E[] arr){
Map<E, Integer> map = new HashMap<>();
for(E e : arr){
Integer count = map.get(e);
map.put(e, count == null ? 1 : ++count);
}
return map;
}
public static void main(String[] args){
String a[]={"a","b","c","d"};
String b[]={"b","c"};
Collection<String> commons = ArrayIntersectioner.intersection(a, b);
System.out.println(commons);
}
}
Use hashtable of the size of the 1st array of linked lists.
* Insert all of the items from the 1st array.
* Insert all of the items from the 2nd array that already has item in the table.
* Go through the map and return the items for which the linked list is of size 1
In Java Set is implemented using HashTable. The code with Set is much simpler:
String[] a = {"a","b","c","d"};
String[] b = {"b", "c"};
Set<String> set = new HashSet<>(a.length);
for(String s : a){
set.add(s);
}
for(String s : b){
set.remove(s);
}
return set;
I'm not sure if we need to include letters in B that aren't in A. That can be easily fixed, assuming no duplicates,
String[] a = {"a","b","c","d"};
String[] b = {"b", "c"};
Set<String> set = new HashSet<>(a.length);
for(String s : a){
set.add(s);
}
for(String s : b){
if(!set.remove(s))
set.add(s);
}
return set;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Set;
public class NonCommonElements {
public static void main(String[] args) {
//String[] a = {"a","b","c","d","e"};
//String[] a = {"a","c"};
//String[] b = {"a"};
String[] a = { "a" , "b" , "c" , "d" , "d" };
String[] b = { "b" , "c" ,"z","a","r","f","g" };
}
public static void findNonCommomElements(String[] a, String[] b) {
HashMap<String,Boolean> count = new HashMap<String,Boolean>();
//scan the first string, put all boolean flag as true
for(int i =0; i < a.length; ++i) {
String temp = a[i];
if(count.get(temp) == null) count.put(temp, true);
}
//scan the second string, for duplicate elements change flag as false
for(int i = 0 ; i < b.length; ++i){
String temp = b[i];
if(count.get(temp) == null) count.put(temp, true);
else count.put(temp, false);
}
// now the hashmap has only the strings as true which are present
// in only one of the arrays
//scan the hashmap and print strings with boolean value true
Set<String> keys = count.keySet();
for(String key : keys) {
if(count.get(key) == true) {
System.out.printf("%s ", key);
}
}
}
}
We have two array : A1 and A2.
1. Calculate size of A1 and A2. //O(n)
2. Insert smaller array in hashMap //O(n)
Map<Character,Boolean> map = new HashMap<Character,Boolean>();
for(int i=0;i<A1.length;i++)
{
map.put(A1[i],false);
}
3. Now traverse second array(bigger one) ans set true in map for values present in A
for(int i=0; i<A2.length;i++) //O(n)
{
if(map.contains(A2[i]))
{
map.put(A2[i],true);
}
}
4. for(Character c:map.keySet()) //0(n)
{
if(!map.get(c))
{
System.out.print(c);
}
}
Overall complexity: Time : O(n)
Space: O(n)
In case all input is in characters only, then we can use array of characters.
Parse one array, and turn on corresponding index in array.
Parse second array, increment corresponding index by one.
Parse updated array, and whichever position has count one, they all r non-common.
good only if input is characters only.
Implementation using map
void printNonCommonElements()
{
std::string str1[]={"a","c","w","r","e"};
int len1=0,len2=0;
std::string str2[]={"b","c"};
map <std::string , int >lookupMap;
map <std::string ,int> commonElements;
/*PUT FIRST ARRAY IN MAP */
for(int i=0;i<5;i++)
{
lookupMap[str1[i]]=1;
}
/*FIND COMMON ELEMENTS */
for(int i=0;i<2;i++)
{
if(lookupMap[str2[i]]==1){commonElements[str2[i]]=1;
}
}
/*PRINT UNCOMMON ELEMNTS */
for(int k=0;k<5;k++)
{
if(!commonElements[str1[k]])cout<<str1[k];
}
for(int k=0;k<2;k++)
{
if(!commonElements[str2[k]])cout<<str2[k];
}
cout<<endl;
}
Linear time solution assuming no duplicate letters in same string and limited alphabet.
The idea is to convert each letter to power of 2 corresponding to its order in the alphabet. With that representation the same letter appearing the each of the string will cancel out.
Here's the code
#include <iostream>
#include <string>
using namespace std;
unsigned long bit_representation(string s, unsigned long accumulator) {
for (string::iterator i(s.begin()); i != s.end(); ++i) {
accumulator ^= 0x1 << (*i - 'a');
}
return accumulator;
}
int main() {
unsigned long accumulator(0x0);
string s1 = "abcdw";
string s2 = "bcezy";
accumulator = bit_representation(s1, accumulator);
accumulator = bit_representation(s2, accumulator);
string result;
for (char i(0); accumulator != 0; ++i) {
if (accumulator & 0x1) {
result.push_back('a' + i);
}
accumulator = accumulator >> 1;
}
cout << "Result is " << result << endl;
return 0;
}
Improved solution allowing for duplicate chars to appear in same string
#include <iostream>
#include <string>
using namespace std;
unsigned long bit_representation(string s) {
unsigned long accumulator(0x0);
for (string::iterator i(s.begin()); i != s.end(); ++i) {
accumulator |= 0x1 << (*i - 'a');
}
return accumulator;
}
int main() {
string s1 = "aabcdwwwww";
string s2 = "bcezy";
unsigned long s1_bits = bit_representation(s1);
unsigned long s2_bits = bit_representation(s2);
unsigned long bit_result = s1_bits ^ s2_bits;
string result;
for (char i(0); bit_result != 0; ++i) {
if (bit_result & 0x1) {
result.push_back('a' + i);
}
bit_result = bit_result >> 1;
}
cout << "Result is " << result << endl;
return 0;
}
vector<string> findUnique(vector<string> const& a, vector<string>const& b)
{
vector<string> result;
vector<string> c(a);
c.insert(c.end(), b.begin(), b.end());
sort(c.begin(), c.end());
for (vector<string>::const_iterator it = c.begin(); it != c.end(); it++) {
if (it != (c.end() - 1)) {
if (*it != *(it + 1))
result.push_back(*it);
else {
while (*it == *(it + 1))
it++;
}
} else
result.push_back(*it);
}
return result;
}
vector<string> findUnique(vector<string> const& a, vector<string>const& b)
{
vector<string> result;
vector<string> c(a);
c.insert(c.end(), b.begin(), b.end());
sort(c.begin(), c.end());
for (vector<string>::const_iterator it = c.begin(); it != c.end(); it++) {
if (it != (c.end() - 1)) {
if (*it != *(it + 1))
result.push_back(*it);
else {
while (*it == *(it + 1))
it++;
}
} else
result.push_back(*it);
}
return result;
}
package com.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class StringArrayNonMatch {
public static void main(String[] args) {
// TODO Arrays of strings
String [] a={"yes", "bus", "gut", "yes"}, b={"sr", "dae", "bus", "new", "dae"};
//String temp;
List<String> l1= new LinkedList<String>(Arrays.asList(a));
List<String> l2= new LinkedList<String>(Arrays.asList(b));
for(String temp:a){
if (!l2.contains(temp)){
System.out.print(temp+"\t");
l2.add(temp);
}
}
System.out.println();
for(String temp:b){
if (!l1.contains(temp)){
System.out.print(temp+"\t");
l1.add(temp);
}
}
// l1.clear();
// l2.clear();
}
}
package com.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class StringArrayNonMatch {
public static void main(String[] args) {
// TODO Arrays of strings
String [] a={"yes", "bus", "gut", "yes"}, b={"sr", "dae", "bus", "new", "dae"};
//String temp;
List<String> l1= new LinkedList<String>(Arrays.asList(a));
List<String> l2= new LinkedList<String>(Arrays.asList(b));
for(String temp:a){
if (!l2.contains(temp)){
System.out.print(temp+"\t");
l2.add(temp);
}
}
System.out.println();
for(String temp:b){
if (!l1.contains(temp)){
System.out.print(temp+"\t");
l1.add(temp);
}
}
// l1.clear();
// l2.clear();
}
}
package com.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class StringArrayNonMatch {
public static void main(String[] args) {
// TODO Arrays of strings
String [] a={"yes", "bus", "gut", "yes"}, b={"sr", "dae", "bus", "new", "dae"};
//String temp;
List<String> l1= new LinkedList<String>(Arrays.asList(a));
List<String> l2= new LinkedList<String>(Arrays.asList(b));
for(String temp:a){
if (!l2.contains(temp)){
System.out.print(temp+"\t");
l2.add(temp);
}
}
System.out.println();
for(String temp:b){
if (!l1.contains(temp)){
System.out.print(temp+"\t");
l1.add(temp);
}
}
// l1.clear();
// l2.clear();
}
}
package com.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class StringArrayNonMatch {
public static void main(String[] args) {
// TODO Arrays of strings
String [] a={"yes", "bus", "gut", "yes"}, b={"sr", "dae", "bus", "new", "dae"};
//String temp;
List<String> l1= new LinkedList<String>(Arrays.asList(a));
List<String> l2= new LinkedList<String>(Arrays.asList(b));
for(String temp:a){
if (!l2.contains(temp)){
System.out.print(temp+"\t");
l2.add(temp);
}
}
System.out.println();
for(String temp:b){
if (!l1.contains(temp)){
System.out.print(temp+"\t");
l1.add(temp);
}
}
// l1.clear();
// l2.clear();
}
}
String[] arr = {"A","C","B","D","B","E","F"};
String[] arr2 = {"D","F","R","S"};
Set s = new HashSet();
s.addAll(Arrays.asList(arr2));
s.addAll(Arrays.asList(arr));
System.out.println(s.toString());
simple add all in a set that will remove the duplecate and give you all uncommon elements
provided , that all the arrays don't have any duplecates , even if they have it will be taken care of
How about using two count arrays
Count array: size 26 (holds frequency of each character from the string)
Generating count array for both the strings is O(n) and space is also constant(as for any length of input we will only create 2 arrays of size 26).
and then traversing the count arrays together to find the non-common characters which is again O(n).
public class UncommonElements {
public static void main(String[] args){
System.out.println(findUncommonElements("abcdef", "abcdez"));
}
public static String findUncommonElements(String firstString, String secondString){
boolean [] characterArray1 = new boolean [256];
boolean [] characterArray2 = new boolean [256];
char[] firstStringArray = firstString.toCharArray();
char[] secondStringArray = secondString.toCharArray();
for (int i = 0; i < firstStringArray.length; i ++){
characterArray1[firstStringArray[i]] = true;
}
String output = "";
for (int j = 0; j < secondStringArray.length; j ++){
characterArray2[secondStringArray[j]] = true;
}
for (int k = 0; k < characterArray1.length; k ++){
if (characterArray1[k] != characterArray2[k]){
output += (char)k;
}
}
return output;
}
}
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;
public class TwoStringDiff {
public static void main(String[] args) {
String[] a = { "a" , "b" , "c" , "d" , "d" };
String[] b = { "b" , "c" ,"z","a","r","f","g" };
TreeSet<String> stringTreeset = new TreeSet<String>();
List<String> alist = Arrays.asList(a);
List<String> blist = Arrays.asList(b);
for (String aString : alist) {
if(!blist.contains(aString)){
stringTreeset.add(aString);
//System.out.println(aString);
}
}
for (String string : stringTreeset) {
System.out.println(string);
}
}
}
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;
public class TwoStringDiff {
public static void main(String[] args) {
String[] a = { "a" , "b" , "c" , "d" , "d" };
String[] b = { "b" , "c" ,"z","a","r","f","g" };
TreeSet<String> stringTreeset = new TreeSet<String>();
List<String> alist = Arrays.asList(a);
List<String> blist = Arrays.asList(b);
for (String aString : alist) {
if(!blist.contains(aString)){
stringTreeset.add(aString);
//System.out.println(aString);
}
}
for (String string : stringTreeset) {
System.out.println(string);
}
}
}
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;
public class TwoStringDiff {
public static void main(String[] args) {
String[] a = { "a" , "b" , "c" , "d" , "d" };
String[] b = { "b" , "c" ,"z","a","r","f","g" };
TreeSet<String> stringTreeset = new TreeSet<String>();
List<String> alist = Arrays.asList(a);
List<String> blist = Arrays.asList(b);
for (String aString : alist) {
if(!blist.contains(aString)){
stringTreeset.add(aString);
//System.out.println(aString);
}
}
for (String string : stringTreeset) {
System.out.println(string);
}
}
}
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;
public class TwoStringDiff {
public static void main(String[] args) {
String[] a = { "a" , "b" , "c" , "d" , "d" };
String[] b = { "b" , "c" ,"z","a","r","f","g" };
TreeSet<String> stringTreeset = new TreeSet<String>();
List<String> alist = Arrays.asList(a);
List<String> blist = Arrays.asList(b);
for (String aString : alist) {
if(!blist.contains(aString)){
stringTreeset.add(aString);
//System.out.println(aString);
}
}
for (String string : stringTreeset) {
System.out.println(string);
}
}
}
vector<char> find_non_common_elem(const vector<char> & a, const vector<char> & b){
vector<char> ans;
const vector<char> & larger_array = (a.size()>b.size()?a:b);
const vector<char> & smaller_array = (a==larger_array?b:a);
unique_ptr<int[]> hash_table(new int[larger_array.size()]{0});
for(int i=0;i<larger_array.size(); i++){
hash_table[larger_array[i]-'a'] = 1;
cout << hash_table[larger_array[i] - 'a'] << endl;
}
for(int i=0;i<smaller_array.size(); i++){
cout << hash_table[smaller_array[i]-'a'] << endl;
if(hash_table[smaller_array[i]-'a'] == 0)
ans.push_back(smaller_array[i]);
}
return ans;
}
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,k;
char str1[30],str2[30];
printf("enter both string \n");
gets(str1);
gets(str2);
non_common(str1,str2,strlen(str1)-1,strlen(str2)-1);
}
int non_common(char str1[] ,char str2[],int n1,int n2)
{
int var=0,tmp=0,i,xor;
for(i=0;i<=n1;i++)
var=var|(1<<(str1[i]-97));
for(i=0;i<=n2;i++)
tmp=tmp|(1<<(str2[i]-97));
xor=var^tmp;
for(i=0;i<26;i++)
{
if(xor&(1<<i))
printf("%c\t",(i+97));
}
}
public class Test {
public static void main(String[] args) {
String[] a = {"a","b","c","d"};
String[] b = {"b","c"};
boolean bo = false;
for(int i=0;i<a.length;i++)
{
bo = false;
for(int j=0;j<b.length;j++)
{
if(a[i] == b[j])
{
bo = true;
}
}
if(bo == false)
{
System.out.print(a[i]+"\t");
}
}
}
}
public class Test {
public static void main(String[] args) {
String[] a = {"a","b","c","d"};
String[] b = {"b","c"};
boolean bo = false;
for(int i=0;i<a.length;i++)
{
bo = false;
for(int j=0;j<b.length;j++)
{
if(a[i] == b[j])
{
bo = true;
}
}
if(bo == false)
{
System.out.print(a[i]+"\t");
}
}
}
}
String[] s = {"a","b","c","d"};
String[] s1 = {"b","c"};
public void nonRepeatingList(String[] s, String[] s1){
List<String> l = new LinkedList<String>();
for(String str : s){
l.add(str);
}
for(String str : s1){
if(l.contains(str)){
l.remove(str);
}
else{
l.add(str);
}
}
System.out.println("Final list with unique values : "+l);
}
C# console applicaiton
c class Program
{
static void Main(string[] args)
{
String[] Array1 = { "a", "b", "c", "d" };
Array1 = Array1.Distinct().ToArray();
String[] Array2 = { "b", "c" };
Array2 = Array2.Distinct().ToArray();
List<String> list = new List<String>();
List<String> list2 = new List<String>();
foreach (var item in Array1)
{
if (!list.Contains(item))
list.Add(item);
}
foreach (var item in Array2)
{
if (list.Contains(item))
list.Remove(item);
else
list.Add(item);
}
list.ForEach(Console.WriteLine);
Console.ReadLine();
}
}
public class two_strings {
public static void main(String []args)
{
String str1 = "sachin" ;
String str2 = "saurabh" ;
int n , m ;
boolean []arr = new boolean[256];
for(int i=0 ; i<str1.length(); i++)
{
n = str1.charAt(i);
arr[n]= true ;
}
for(int i=0 ; i<str2.length(); i++)
{
m = str2.charAt(i);
if(!arr[m])
{
System.out.print(str2.charAt(i));
}
}
}
}
The best choice is tries. It is the fastest way to organize searchable key-value pairs where keys are strings. It is very efficient in search. In this case we simply, use true as a value.
- heorhi August 24, 2014