Booking.com Interview Question
Software DevelopersCountry: Netherlands
Interview Type: Phone Interview
import java.util.*;
public class retainex {
public static void main(String[] args) {
int a[]={1,2,3,4,5,6};
int b[]={4,5,6,7,8,9};
TreeSet<Integer> tr1=new TreeSet<Integer>();
TreeSet<Integer> tr2=new TreeSet<Integer>();
for(int i=0;i<=a.length-1;i++)
{
tr1.add(a[i]);
tr2.add(b[i]);
}
tr1.retainAll(tr2);
Iterator<Integer> it= tr1.iterator();
while(it.hasNext())
{
System.out.println(it.next());
}
}
}
package com.valli.AlgortithmProblems;
public class CommonElements {
public static void findCommonElements(int a1[],int a2[]){
if((a1.length==0)||(a2.length==0)){
return;
}
for(int i=0,j=0;i<a1.length-1||j<a2.length-1;){
if(a1[i]==a2[j]){
System.out.println(a1[i]);
i++;j++;
}else if(a1[i]<a2[j]){
i++;
}else
{
j++;
}
}
}
public static void main(String[] args) {
int a1[] =new int[]{1,2,3,3,3,4,5,5,6,6};
int a2[] = new int[]{2,3,3,3,3,4,5,6};
findCommonElements(a1, a2);
}
}
import java.util.*;
import java.io.*;
/*
* @author Tejashree pc
*/
public class Intersection {
public static void main(String[] args) throws IOException
{
Scanner s=new Scanner(System.in);
int A[], B[];
System.out.println("Number of elements in A should be less than or equal to number of elements in B.");
System.out.println("Enter the number of elements in Multiset A:");
int a=s.nextInt();
System.out.println("Enter the number of elements in Multiset B:");
int b=s.nextInt();
boolean fA[]=new boolean[a];
boolean fB[]=new boolean[b];
A=new int[a];
B=new int[b];
System.out.println("Enter the elements in Multiset A:");
for(int i=0;i<a;i++)
{
System.out.print("A"+i+": ");
A[i]=s.nextInt();
fA[i]=false;
System.out.println();
}
System.out.println("Enter the elements in Multiset B:");
for(int i=0;i<b;i++)
{
System.out.print("B"+i+": ");
B[i]=s.nextInt();
fB[i]=false;
System.out.println();
}
int ii=0;
List<Integer> I=new ArrayList<>();
System.out.print("Intersection of Multisets A and B = C = [ ");
for(int i=0; i<a; i++)
{
for(int j=0; j<b; j++)
{
if(!fB[j] && A[i]==B[j])
{
I.add(A[i]);
fA[i]=true;
fB[j]=true;
System.out.print(I.get(ii++)+" ");
break;
}
}
}
System.out.print("]");
}
}
import java.util.*;
import java.io.*;
/*
* @author Tejashree pc
*/
public class Intersection {
public static void main(String[] args) throws IOException
{
Scanner s=new Scanner(System.in);
int A[], B[];
System.out.println("Number of elements in A should be less than or equal to number of elements in B.");
System.out.println("Enter the number of elements in Multiset A:");
int a=s.nextInt();
System.out.println("Enter the number of elements in Multiset B:");
int b=s.nextInt();
boolean fA[]=new boolean[a];
boolean fB[]=new boolean[b];
A=new int[a];
B=new int[b];
System.out.println("Enter the elements in Multiset A:");
for(int i=0;i<a;i++)
{
System.out.print("A"+i+": ");
A[i]=s.nextInt();
fA[i]=false;
System.out.println();
}
System.out.println("Enter the elements in Multiset B:");
for(int i=0;i<b;i++)
{
System.out.print("B"+i+": ");
B[i]=s.nextInt();
fB[i]=false;
System.out.println();
}
int ii=0;
List<Integer> I=new ArrayList<>();
System.out.print("Intersection of Multisets A and B = C = [ ");
for(int i=0; i<a; i++)
{
for(int j=0; j<b; j++)
{
if(!fB[j] && A[i]==B[j])
{
I.add(A[i]);
fA[i]=true;
fB[j]=true;
System.out.print(I.get(ii++)+" ");
break;
}
}
}
System.out.print("]");
}
}
# I started writing a Perl script and in the middle of it, realized it's fairly easy to do it in bash.
# Not fancy but gets the job done. If I'm in hurry and not looking for votes :-), I would do the
# bash version any day. Yes, it can be improved and no it's not flawless. Here is the quick
# version. BTW this method can be used for numbers and strings both.
$ cat careercup_5158359730749440.sh
#!/bin/bash
get_intersection () {
for num in $arrA
do
echo $num
done | sort > /tmp/arrA.$$
for num in $arrB
do
echo $num
done | sort > /tmp/arrB.$$
echo "Intersection of ($arrA) and ($arrB) is: ("`comm -12 /tmp/arrA.$$ /tmp/arrB.$$`")"
rm -f /tmp/arrA.$$ /tmp/arrB.$$
}
arrA="0 1 1 2 2 5"
arrB="0 1 2 2 2 6"
get_intersection
arrA="0 1 1"
arrB="0 1 2 3 4 5 6"
get_intersection
$ careercup_5158359730749440.sh
Intersection of (0 1 1 2 2 5) and (0 1 2 2 2 6) is: (0 1 2 2)
Intersection of (0 1 1) and (0 1 2 3 4 5 6) is: (0 1)
import java.util.*;
public class retainex {
public static void main(String[] args) {
int a[]={1,2,3,4,5,6};
int b[]={4,5,6,7,8,9};
TreeSet<Integer> tr1=new TreeSet<Integer>();
TreeSet<Integer> tr2=new TreeSet<Integer>();
for(int i=0;i<=a.length-1;i++)
{
tr1.add(a[i]);
tr2.add(b[i]);
}
tr1.retainAll(tr2);
Iterator<Integer> it= tr1.iterator();
while(it.hasNext())
{
System.out.println(it.next());
}
}
}
public static void main(String[] args) {
int[] setOne = new int[6];
setOne[0] = 1;
setOne[1] = 1;
setOne[2] = 2;
setOne[3] = 4;
setOne[4] = 5;
setOne[5] = 6;
int[] setTwo = new int[8];
setTwo[0] = 1;
setTwo[1] = 11;
setTwo[2] = 21;
setTwo[3] = 41;
setTwo[4] = 5;
setTwo[5] = 6;
setTwo[6] = 6;
setTwo[7] = 7;
List<Integer> resultArray = new ArrayList<Integer>();
for (int i=0;i<setOne.length;i++) {
if(setOne[i]==setTwo[i]){
resultArray.add(setOne[i]);
}
}
System.out.println(resultArray);
}
package com.valli.AlgortithmProblems;
public class CommonElements {
public static void findCommonElements(int a1[],int a2[]){
if((a1.length==0)||(a2.length==0)){
return;
}
for(int i=0,j=0;i<a1.length-1||j<a2.length-1;){
if(a1[i]==a2[j]){
System.out.println(a1[i]);
i++;j++;
}else if(a1[i]<a2[j]){
i++;
}else
{
j++;
}
}
}
public static void main(String[] args) {
int a1[] =new int[]{1,2,3,3,3,4,5,5,6,6};
int a2[] = new int[]{2,3,3,3,3,4,5,6};
findCommonElements(a1, a2);
}
}
package booking;
import java.util.ArrayList;
public class Booking {
public static void main(String[] args) {
int a[] = {0,1,1,2,2,5};
int b[] = {0,1,2,2,2,6};
System.out.println(findUnion(a, b));
int c[] = {0,1,1};
int d[] = {0,1,2,3,4,5,6};
System.out.println(findUnion(c,d));
}
public static ArrayList<Integer> findUnion(int first[], int second[]){
int firstLength = first.length;
int secondLength = second.length;
ArrayList<Integer> c = new ArrayList<>();
int min = Math.min(firstLength, secondLength);
for(int i=0; i<min; i++){
if(first[i] == second[i]){
c.add(first[i]);
}
}
return c;
}
public static void multiIntersection(Integer[] A, Integer[] B){
if(A.length==0||B.length==0){
return;
}
//Sort the arrays
insertionSort(A);insertionSort(B);
int lenA=A.length, lenB=B.length;
for(int i=0,j=0;i<lenA&&j<lenB;){
if(Objects.equals(A[i], B[j])){
System.out.print(A[i++]+" ");
j++;
}
else if(A[i]>B[j]) j++;
else i++;
}
System.out.println("");
}
public static void multiIntersection2(Integer[] A, Integer[] B, int N){
if(A.length==0||B.length==0){
return;
}
int lenA=A.length, lenB=B.length;
//N is the max number value among the arrays such as if A=[0,2,7], B=[0,1,6],
//N=7
Integer[] C=new Integer[N];
Arrays.fill(C, 0);
for(int i=0;i<lenA;i++){
C[A[i]]=C[A[i]]+1;
}
for(int j=0;j<lenB;j++){
if(C[B[j]]>0){
C[B[j]]--;
System.out.print(B[j]+" ");
}
}
}
public static void multiIntersection(Integer[] A, Integer[] B){
if(A.length==0||B.length==0){
return;
}
//Sort the arrays
insertionSort(A);insertionSort(B);
int lenA=A.length, lenB=B.length;
for(int i=0,j=0;i<lenA&&j<lenB;){
if(Objects.equals(A[i], B[j])){
System.out.print(A[i++]+" ");
j++;
}
else if(A[i]>B[j]) j++;
else i++;
}
System.out.println("");
}
public static void multiIntersection2(Integer[] A, Integer[] B, int N){
if(A.length==0||B.length==0){
return;
}
int lenA=A.length, lenB=B.length;
//N is the max number value among the arrays such as if A=[0,2,7], B=[0,1,6],
//N=7
Integer[] C=new Integer[N];
Arrays.fill(C, 0);
for(int i=0;i<lenA;i++){
C[A[i]]=C[A[i]]+1;
}
for(int j=0;j<lenB;j++){
if(C[B[j]]>0){
C[B[j]]--;
System.out.print(B[j]+" ");
}
}
}
One solution that comes to my mind is, simply sort both the arrays and start comparing from the beginning. Vomit the integer if they are equal else move forward in the array with the samller-integer.
Easy to read, simple and effective Java solution using Set:
public List<Integer> intersectArrays(int[] a, int[] b) {
Map<Integer, Integer> map = new HashMap<>(); // number of appearances
List<Integer> result = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
int curNum = 1;
if (map.containsKey(a[i]))
curNum = map.get(a[i]) + 1;
map.put(a[i], curNum);
}
for (int i = 0; i < b.length; i++) {
if (!map.containsKey(b[i]))
continue;
int curNum = map.get(b[i]);
if (curNum > 0) {
curNum--;
result.add(b[i]);
}
map.put(b[i], curNum); // update decreased counter
}
return result;
}
public int[] getBagIntersection2(int a[], int b[]) {
a = Arrays.copyOf(a, a.length);
b = Arrays.copyOf(b, b.length);
Arrays.sort(a);
Arrays.sort(b);
List<Integer> resultList = new LinkedList<Integer>();
int aIndex = 0;
int bIndex = 0;
while(aIndex <a.length && bIndex < b.length) {
if(a[aIndex] == b[bIndex]) {
resultList.add(a[aIndex]);
aIndex++;
bIndex++;
} else if(a[aIndex] > b[bIndex]){
bIndex++;
} else {
aIndex++;
}
}
return toIntArray(resultList);
}
public int[] getBagIntersection2(int a[], int b[]) {
a = Arrays.copyOf(a, a.length);
b = Arrays.copyOf(b, b.length);
Arrays.sort(a);
Arrays.sort(b);
List<Integer> resultList = new LinkedList<Integer>();
int aIndex = 0;
int bIndex = 0;
while(aIndex <a.length && bIndex < b.length) {
if(a[aIndex] == b[bIndex]) {
resultList.add(a[aIndex]);
aIndex++;
bIndex++;
} else if(a[aIndex] > b[bIndex]){
bIndex++;
} else {
aIndex++;
}
}
return toIntArray(resultList);
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (map.containsKey(a[i])) {
map.put(a[i], map.get(a[i]) + 1);
} else {
map.put(a[i], 1);
}
}
for (int i = 0 ; i < b.length; i ++) {
if (map.containsKey(b[i]) && map.get(b[i]) > 0) {
System.out.println(b[i]);
map.put(b[i], map.get(b[i]) - 1);
}
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (map.containsKey(a[i])) {
map.put(a[i], map.get(a[i]) + 1);
} else {
map.put(a[i], 1);
}
}
for (int i = 0 ; i < b.length; i ++) {
if (map.containsKey(b[i]) && map.get(b[i]) > 0) {
System.out.println(b[i]);
map.put(b[i], map.get(b[i]) - 1);
}
}
Using HashMap in O(n)
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (map.containsKey(a[i])) {
map.put(a[i], map.get(a[i]) + 1);
} else {
map.put(a[i], 1);
}
}
for (int i = 0 ; i < b.length; i ++) {
if (map.containsKey(b[i]) && map.get(b[i]) > 0) {
System.out.println(b[i]);
map.put(b[i], map.get(b[i]) - 1);
}
Objective-C:
-(NSArray *)intersectBetweenTwoArrays:(NSArray *)arr1 array2:(NSArray *)arr2 {
NSMutableArray * intersection = [NSMutableArray array];
NSCountedSet *set1 = [NSCountedSet setWithArray:arr1];
NSCountedSet *set2 = [NSCountedSet setWithArray:arr2];
for (NSNumber *n1 in set1) {
NSInteger count1 = [set1 countForObject: n1];
NSInteger count2 = [set2 countForObject: n1];
NSInteger min = MIN(count1, count2);
while (min-- != 0) {
[intersection addObject: n1];
}
}
return intersection;
}
import java.util.*;
public class Solution {
public static void main (String args[]) {
int [] array1 = new int[] {0, 1, 1, 2, 2, 5};
int [] array2 = new int[] {0, 1, 2, 2, 2, 6};
List<Integer> results = new Solution().solve(array1, array2);
for (Integer i : results){
System.out.print(i.intValue()+" ");
}
}
private Map<Integer, Integer> map;
public Solution(){
this.map = new HashMap<>();
}
private void add(int value) {
if (!this.map.containsKey(value)) {
this.map.put(value, 1);
}else{
this.map.put(value, this.map.get(value)+1);
}
}
public List<Integer> solve(int [] array1, int[] array2) {
for (int i : array1)
add(i);
List<Integer> results = new LinkedList<>();
for (int i : array2) {
if (map.containsKey(i)) {
if (map.get(i) > 1) {
results.add(i);
map.put(i, map.get(i)-1);
}else{
results.add(i);
map.remove(i);
}
}
}
return results;
}
}
public void intersect()
{
int a[] = {0,1,1};
int b[] = {0,1,2,3,4,5,6};
int max, min;
Map <Integer, Integer> aMap = new HashMap<Integer, Integer>();
Map <Integer, Integer> bMap = new HashMap<Integer, Integer>();
for(int i=0;i<a.length;i++)
{
if(aMap.containsKey(a[i]))
aMap.put(a[i], aMap.get(a[i])+1);
else
aMap.put(a[i], 1);
}
for(int j=0;j<b.length;j++)
{
if(bMap.containsKey(b[j]))
bMap.put(b[j], bMap.get(b[j])+1);
else
bMap.put(b[j], 1);
}
for(int key : aMap.keySet())
{
if(bMap.containsKey(key))
{
max = Math.max(aMap.get(key), bMap.get(key));
min = Math.min(aMap.get(key), bMap.get(key));
if(max==min)
System.out.print(key + " ");
else
for(int m = 1;m<=min;m++)
System.out.print(key + " ");
}
}
}
function findIntersection(arA, arB) {
var pivot = arA.length > arB.length ? arB : arA;
var baseComparator = arA.length > arB.length ? arA : arB;
var intersection = [];
for(var i = 0; i < pivot.length; i++) {
if(pivot[i] == baseComparator[i]) {
intersection.push(pivot[i]);
}
}
return intersection;
}
Python:
def interscetion(A,B):
len1 = len(A)
len2 = len(B)
C = []
if len1 == 0 or len2 == 0:
return C
dict1 = {}
dict2 = {}
for i in range(0,len1):
if A[i] in dict1:
dict1[A[i]] += 1
else:
dict1[A[i]] = 1
for i in range(0,len2):
if B[i] in dict2:
dict2[B[i]] += 1
else:
dict2[B[i]] = 1
for keys,values in dict1.items():
if keys in dict2:
dict2values = dict2[keys]
if dict2values <= values:
temp = dict2values
else:
temp = values
for i in range (0,temp):
C.append(keys)
return C
C = interscetion(A,B)
print C
/**
* @author Omid Ghiasi Tarzi
*/
static List<Integer> intersect(List<Integer> list1,List<Integer> list2){
list1=new ArrayList<>(list1);
list2=new ArrayList<>(list2);
Collections.sort(list1);
Collections.sort(list2);
int i=0;
int j=0;
List<Integer> result=new ArrayList<>();
while(i<list1.size()&&j<list2.size()){
if(list1.get(i)<list2.get(j)){
i++;
}else if(list1.get(i)>list2.get(j)){
j++;
}else{
result.add(list1.get(i));
i++;
j++;
}
}
return result;
}
/**
* @author Omid Ghiasi Tarzi
*/
static List<Integer> intersect(List<Integer> first, List<Integer> second) {
Set<OrderedInt> firstSet = toOrderedIntSet(first);
Set<OrderedInt> secondSet = toOrderedIntSet(second);
firstSet.retainAll(secondSet);
return firstSet.stream().map(i -> i.value).collect(Collectors.toList());
}
private static Set<OrderedInt> toOrderedIntSet(List<Integer> list) {
Set<OrderedInt> resultSet = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i : list) {
map.put(i, map.getOrDefault(i, 0) + 1);
resultSet.add(new OrderedInt(i, map.get(i)));
}
return resultSet;
}
static class OrderedInt {
int value;
int order;
OrderedInt(int value, int order) {
this.value = value;
this.order = order;
}
@Override
public boolean equals(Object o) {
OrderedInt other = (OrderedInt) o;
return value == other.value && order == other.order;
}
@Override
public int hashCode() {
return 31 * (31 * value + order);
}
}
public static List<Integer> solution(int[] a, int[] b) {
Queue<Integer> counters = Arrays.stream(a)
.boxed().collect(Collectors.toCollection(LinkedList::new));
List<Integer> result = new ArrayList<>();
for (int i: b){
if (counters.peek() == null){
break;
}
if (counters.poll() == i){
result.add(i);
}
}
return result;
}
First store all elements of A (and their counts) in a HashMap. Then traverse B and if the count for current element is greater than 0, then add this element to the result and decrement the count.
- Sunny August 21, 2015