Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
# assumes sorted and unique
def get_union(a,b):
if not b:
return a
if not a:
return b
p = q = 0
union = []
while p < len(a) and q < len(b):
if a[p] < b[q]:
union.append(a[p])
p += 1
elif a[p] > b[q]:
union.append(b[q])
q += 1
else:
union.append(a[p])
p += 1
q += 1
if p < len(a):
union.extend(a[p:])
if q < len(b):
union.extend(b[q:])
return union
a = [2, 10, 14, 19, 51, 71]
b = [2, 9, 19, 40, 51]
u = get_union(a,b)
print u
u_from_stdlib = set(a) | set(b)
assert len(u) == len(set(u))
assert len(set(u) ^ u_from_stdlib) == 0, "symmetric difference exists"
{
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51} ;
int union[]= getUnion(a,b);
for(int i=0;i<union.length-1;i++){ System.out.println(union[i]);
}
}
private static int[] getUnion(int[] a, int[] b) {
int u[] = new int[a.length+b.length];
int i=0,j=0,k=0;
boolean flag =true;
while(flag){
if(a[i] == b[j]){
u[k] =b[j];
k+=1;
j+=1;
i+=1;
}
else if(a[i]<b[j]){
u[k]=a[i];
k+=1;
i+=1;
}
else{
u[k]=b[j];
k+=1;
j+=1;
}
if(j==b.length){
flag=false;
}
}
return u;
}
}
{public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51} ;
int union[]= getUnion(a,b);
for(int i=0;i<union.length-1;i++){ System.out.println(union[i]);
}
}
private static int[] getUnion(int[] a, int[] b) {
int u[] = new int[a.length+b.length];
int i=0,j=0,k=0;
boolean flag =true;
while(flag){
if(a[i] == b[j]){
u[k] =b[j];
k+=1;
j+=1;
i+=1;
}
else if(a[i]<b[j]){
u[k]=a[i];
k+=1;
i+=1;
}
else{
u[k]=b[j];
k+=1;
j+=1;
}
if(j==b.length){
flag=false;
}
}
return u;
}
}
{
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51} ;
int union[]= getUnion(a,b);
for(int i=0;i<union.length-1;i++){
System.out.println(union[i]);
}
}
private static int[] getUnion(int[] a, int[] b) {
int u[] = new int[a.length+b.length];
int i=0,j=0,k=0;
boolean flag =true;
while(flag){
if(a[i] == b[j]){
u[k] =b[j];
k+=1;
j+=1;
i+=1;
}
else if(a[i]<b[j]){
u[k]=a[i];
k+=1;
i+=1;
}
else{
u[k]=b[j];
k+=1;
j+=1;
}
if(j==b.length){
flag=false;
}
}
return u;
}
}
def get_union(a,b):
a_len = len(a)
b_len = len(b)
print(a_len, b_len)
result = []
hashmap = {}
for i in range(len(a)-1):
if (i > a_len or i>b_len):
break
# print(mn, mx)
if hashmap.get(a[i]) == None:
result.append(a[i])
hashmap[a[i]] = True
if hashmap.get(b[i]) == None:
result.append(b[i])
hashmap[b[i]] = True
return result
def get_union(a,b):
a_len = len(a)
b_len = len(b)
print(a_len, b_len)
result = []
hashmap = {}
for i in range(len(a)-1):
if (i > a_len or i>b_len):
break
# print(mn, mx)
if hashmap.get(a[i]) == None:
result.append(a[i])
hashmap[a[i]] = True
if hashmap.get(b[i]) == None:
result.append(b[i])
hashmap[b[i]] = True
return result
static void union(int arr1[], int[] arr2) {
int i = 0, j = 0, k = 0;
List<Integer> list = new ArrayList<>();
boolean flag = true;
while (flag) {
if (arr1[i] == arr2[j]) {
list.add(arr1[i]);
i++;
j++;
} else if (arr1[i] < arr2[j]) {
list.add(arr1[i]);
i++;
} else {
list.add(arr2[j]);
j++;
}
if (j == arr2.length) {
flag = false;
}
}
if (arr1.length > arr2.length) {
int min = arr2.length;
for (int x = min; x < arr1.length; x++) {
list.add(arr1[x]);
}
} else {
int min = arr1.length;
for (int x = min; x < arr2.length; x++) {
list.add(arr2[x]);
}
}
System.out.println();
for (Integer x : list) {
System.out.print(x + " ");
}
}
public List<Integer> union(int[] nums1, int[] nums2) {
List<Integer> result = new LinkedList<Integer>();
helper(result, nums1, nums2, 0, 0);
return result;
}
void helper(List<Integer> result, int[] nums1, int[] nums2, int nums1Index, int nums2Index) {
if(nums1Index >= nums1.length && nums2Index >= nums2.length) return;
if(nums1Index >= nums1.length) {
result.add(nums2[nums2Index]);
helper(result, nums1, nums2, nums1Index, nums2Index + 1);
return;
}
if(nums2Index >= nums2.length) {
result.add(nums1[nums1Index]);
helper(result, nums1, nums2, nums1Index + 1, nums2Index);
return;
}
if(nums1[nums1Index] == nums2[nums2Index]) {
result.add(nums1[nums1Index]);
helper(result, nums1, nums2, nums1Index + 1, nums2Index + 1);
return;
}
if(nums1[nums1Index] < nums2[nums2Index]) {
result.add(nums1[nums1Index]);
helper(result, nums1, nums2, nums1Index + 1, nums2Index);
return;
}
result.add(nums2[nums2Index]);
helper(result, nums1, nums2, nums1Index, nums2Index + 1);
}
public int[] GetUnion(int[] intArr1, int[] intArr2){
int arrLen1 = intArr1.Length;
int arrLen2 = intArr2.Length;
Dictionary<int, int> dict = new Dictionary<int,int>();
while(arrLen1 > 0
|| arrLen2 >0){
if(arrLen1 > 0){
if(arrLen2 == 0){
if(!dict.ContainsKey(intArr1[intArr1.Length - arrLen1])){
dict.Add(intArr1[intArr1.Length - arrLen1],intArr1[intArr1.Length - arrLen1]);
}
arrLen1--;
}
else if(intArr1[intArr1.Length - arrLen1]<=intArr2[intArr2.Length - arrLen2]){
if(!dict.ContainsKey(intArr1[intArr1.Length - arrLen1])){
dict.Add(intArr1[intArr1.Length - arrLen1],intArr1[intArr1.Length - arrLen1]);
}
arrLen1--;
}else if(intArr1[intArr1.Length - arrLen1]>intArr2[intArr2.Length - arrLen2]){
if(!dict.ContainsKey(intArr2[intArr2.Length - arrLen2])){
dict.Add(intArr2[intArr2.Length - arrLen2],intArr2[intArr2.Length - arrLen2]);
}
arrLen2--;
}
}
else if(arrLen2 > 0){
if(arrLen1 == 0){
if(!dict.ContainsKey(intArr2[intArr2.Length - arrLen2])){
dict.Add(intArr1[intArr2.Length - arrLen2],intArr1[intArr2.Length - arrLen2]);
}
arrLen1--;
}
else if(intArr2[intArr2.Length - arrLen2]<=intArr1[intArr1.Length - arrLen1]){
if(!dict.ContainsKey(intArr2[intArr2.Length - arrLen2])){
dict.Add(intArr2[intArr2.Length - arrLen2],intArr2[intArr2.Length - arrLen2]);
}
arrLen1--;
}else if(intArr2[intArr2.Length - arrLen2]>intArr1[intArr1.Length - arrLen1]){
if(!dict.ContainsKey(intArr1[intArr1.Length - arrLen1])){
dict.Add(intArr1[intArr1.Length - arrLen1],intArr1[intArr1.Length - arrLen1]);
}
arrLen2--;
}
}
}
return dict.Select(v=>v.Value).ToArray();
}
public static Integer[] generateUnion(int[] a, int[] b){
int i = 0, j = 0;
List<Integer> list = new ArrayList<Integer>();
while(i<a.length && j<b.length){
if(a[i]<b[j]){
list.add(a[i]);
i++;
}else if(a[i]>b[j]){
list.add(b[j]);
j++;
}else{
list.add(b[j]);
i++;
j++;
}
}
if(i<a.length){
for (int k = i; k < a.length; k++) {
list.add(a[k]);
}
}else if(j<b.length){
for (int k = j; k < b.length; k++) {
list.add(b[k]);
}
}
return (Integer[])list.toArray(new Integer[list.size()]);
}
If you can't use Javascript union function and need to preserve the sorting:
let union = function(arr1, arr2) {
let out = {};
let len = Math.max(arr1.length, arr2.length);
for(let i=0; i<len; i++) {
if(arr1[i]) {
out[arr1[i]] = true;
}
if(arr2[i]) {
out[arr2[i]] = true;
}
}
return Object.keys(out);
};
var a = [2, 10, 14, 19, 51, 71];
var b = [2, 9, 19, 40, 51];
console.log(union(a,b));
console.log(union(b,a));
public class AmazonQ1 {
private static Set<Integer> uniqueSet = new HashSet<>();
/**
* Complexity O(n)
* @param a
* @param b
* @return
*/
public static void union(int[] a, int[] b){
int i = 0;
int j= 0;
int k = 0;
while(i < a.length && j < b.length){
if(a[i] == b[i]){
uniqueSet.add(a[i++]); // O(1)
j++;
}else {
uniqueSet.add(a[i++]);
uniqueSet.add(b[j++]);
}
}
while(i < a.length){
uniqueSet.add(a[i++]);
}
while(j < b.length){
uniqueSet.add(b[j++]);
}
}
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51};
union(a, b);
uniqueSet.forEach(System.out::println);
}
}
import java.util.Arrays;
import java.util.TreeSet;
public class Test {
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51};
var union = new TreeSet();
Arrays.stream(a).forEach(union::add);
Arrays.stream(b).forEach(union::add);
System.out.print("Union=" + union);
}
}
import java.util.Arrays;
import java.util.TreeSet;
public class Test {
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51};
var union = new TreeSet();
Arrays.stream(a).forEach(union::add);
Arrays.stream(b).forEach(union::add);
System.out.print("Union=" + union);
}
}
import java.util.Arrays;
import java.util.TreeSet;
public class Test {
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51};
var union = new TreeSet();
Arrays.stream(a).forEach(union::add);
Arrays.stream(b).forEach(union::add);
System.out.print("Union=" + union);
}
}
import java.util.Arrays;
import java.util.TreeSet;
public class Test {
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51};
var union = new TreeSet();
Arrays.stream(a).forEach(union::add);
Arrays.stream(b).forEach(union::add);
System.out.print("Union=" + union);
}
}
import java.util.Arrays;
import java.util.TreeSet;
public class Test {
public static void main(String[] args){
int a[] = {2, 10, 14, 19, 51, 71};
int b[] = {2, 9, 19, 40, 51};
var union = new TreeSet();
Arrays.stream(a).forEach(union::add);
Arrays.stream(b).forEach(union::add);
System.out.print("Union=" + union);
}
}
package test1;
import java.util.Stack;
public class Test1 {
public static Stack<Integer> s = new Stack<>();
public static void main(String[] args) {
int a[] = { 2, 10, 14, 19, 51, 71 };
int b[] = { 2, 9, 19, 40, 51 };
merge(a, b);
System.out.println(s);
}
private static void merge(int a[], int b[]) {
int t1, t2 = 0;
for (int i = 0; i < a.length; i++) {
t1 = a[i];
for (int j = 0; j < b.length; j++) {
t2 = b[j];
if (s.isEmpty()) {
if (t1 < t2)
s.push(t1);
else if (t1 > t2)
s.push(t2);
else
s.push(t1);
} else {
if (t1 == t2) {
if (s.peek() < t1) {
s.push(t1);
}
} else {
if (t1 < t2) {
if (s.peek() < t1) {
s.push(t1);
break;
}
} else {
if (s.peek() < t2) {
s.push(t2);
}
}
}
}
}
}
}
}
In Swift
- Rahul Jain May 20, 2018let setA:Set = [2, 10, 14, 19, 51, 71]
let setB:Set = [2, 9, 19, 40, 51]
let unionOfAandB = setA.union(setB)
for item in unionOfAandB
{
print("items is \(item)")
}