Booking.com Interview Question
Android EngineersTeam: Android
Country: Netherlands
Interview Type: Phone Interview
public static List<Integer> generateCommonList(final List<List<Integer>> lists) {
Set<Integer> ansSet = new HashSet<>();
Set<Integer> uniqueNos = new HashSet<>();
lists.forEach(list ->
new HashSet<>(list).forEach(value -> {
if (uniqueNos.contains(value)) {
ansSet.add(value);
} else {
uniqueNos.add(value);
}
}));
return new ArrayList<>(ansSet);
}
A = {2, 5, 3, 2, 8,1}
B = {7, 9, 5, 2, 4, 10, 10}
C = {6, 7, 5, 5, 3, 7}
s1=A&B&C
s2=A&B
s3=A&C
s4=B&C
s=s1|s2|s3|s4
print(s)
Complexity seems very bad for this solution. I would just use a hash table and scan all array once.
key :- element and value will be set of id {}
for example, in above case hash table entry for 2 will be 2 -> { A, B} since its seem in two arrays.
Later just scan hash table and get result where value size is atleast 2.
public void extractArray(int[] a, int[] b, int[] c){
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i< a.length; i++){
int valueSearched = a[i];
System.out.println(valueSearched);
System.out.println("Loop1-----------");
boolean flag1 = false;
boolean flag2 = false;
for(int j =0; j<b.length;j++){
System.out.println(b[j]);
System.out.println("Loop2-----------");
if(!list.contains(valueSearched) && valueSearched == b[j]){
list.add(valueSearched);
break;
}
}
for(int k=0;k<c.length;k++){
System.out.println(c[k]);
System.out.println("Loop3-----------");
if(!list.contains(valueSearched) && valueSearched == c[k]){
list.add(valueSearched);
break;
}
}
}
System.out.println(Arrays.toString(list.toArray()));
}
{
public void extractArray(int[] a, int[] b, int[] c){
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i< a.length; i++){
int valueSearched = a[i];
System.out.println(valueSearched);
System.out.println("Loop1-----------");
boolean flag1 = false;
boolean flag2 = false;
for(int j =0; j<b.length;j++){
System.out.println(b[j]);
System.out.println("Loop2-----------");
if(!list.contains(valueSearched) && valueSearched == b[j]){
list.add(valueSearched);
break;
}
}
for(int k=0;k<c.length;k++){
System.out.println(c[k]);
System.out.println("Loop3-----------");
if(!list.contains(valueSearched) && valueSearched == c[k]){
list.add(valueSearched);
break;
}
}
}
System.out.println(Arrays.toString(list.toArray()));
}
}
Step 1) Sort all the n arrays in ascending order and create a set named "duplicate"
Step 2) create a heap with the first elements i.e. the smallest, of all the arrays.
Step 3) poll out the first 2 elements from heap and also insert 2 elements from the respective 2 arrays, who's elements are taken out of the heap.
Step 4) if the elements are same put it in the set. Throw away the first element, get the next element from heap and compare the current 2 elements and put in the set if same. Also insert another element from the respective array. Continue the process.
Integer[] A = {2, 5, 3, 2, 8, 1};
Integer[] B = {7, 9, 5, 2, 4, 10, 10};
Integer[] C = {6, 7, 5, 5, 3, 7};
List<Integer> AA = new ArrayList<>(Arrays.asList(A));
List<Integer> BB = new ArrayList<>(Arrays.asList(B));
List<Integer> CC = new ArrayList<>(Arrays.asList(C));
HashSet<Integer> total = new HashSet<>();
total.addAll(AA);
total.addAll(BB);
total.addAll(CC);
for (Integer s : total) {
if( (AA.contains(s) && BB.contains(s))){
System.out.println(s +" Present in arrays A & B");
} else if( (BB.contains(s) && CC.contains(s))){
System.out.println(s +" Present in arrays B & C");
} else if( (CC.contains(s) && AA.contains(s))){
System.out.println(s +" Present in arrays C & A");
}
}
package booking;
import java.util.*;
public class ConstructArray {
static void makeArr(int[] a, int[] b, int[] c) {
HashMap<Integer, Integer> map = new HashMap<>();
Integer[]A = removeDuplicates(a);
Integer[]B = removeDuplicates(b);
Integer[]C = removeDuplicates(c);
System.out.println(Arrays.toString(A));
System.out.println(Arrays.toString(B));
System.out.println(Arrays.toString(C));
for (int i : A)
map.put(i, 1);
for (int j : B) {
if (map.containsKey(j))
map.put(j, 1 + map.get(j));
else
map.put(j, 1);
}
for (int k : C) {
if (map.containsKey(k))
map.put(k, 1 + map.get(k));
else
map.put(k, 1);
}
for (int key : map.keySet()) {
if (map.get(key) > 1)
System.out.print(key);
}
}
static Integer[] removeDuplicates(int a[]){
HashSet<Integer> set = new HashSet<>();
for (int i:a)
set.add(i);
return set.toArray(new Integer[set.size()]);
}
public static void main(String[] args) {
int[] A = {2, 5, 3, 2, 8, 1};
int[] B = {7, 9, 5, 2, 4, 10, 10};
int[] C = {6, 7, 5, 5, 3, 7};
makeArr(A,B,C);
}
}
fun findDuplication(A: List<Int>, B: List<Int>, C: List<Int>) : List<Int> {
val setA = A.toSet()
val setB = B.toSet()
val setC = C.toSet()
val existsIn : Int.(Set<Int>, Set<Int>) -> Boolean = { first, second -> first.contains(this) && second.contains(this) }
val filter : (Int) -> Boolean = { it.existsIn(setA, setB) || it.existsIn(setA, setC) || it.existsIn(setC, setB) }
return setA.plus(setB).plus(setC).filter { filter(it) }
}
public class Solution2 {
public static void main(String[] args) {
int a[] = {9,9,9,9,8,8,8,7,7,6,5,4};
int b[] = {9,9,9,8,8,7,7,6,4,4,4,3,2};
int c[] = {9,9,9,8,8,7,7,6,5};
Integer[] A = removeDuplicates(a);
Integer[] B = removeDuplicates(b);
Integer[] C = removeDuplicates(c);
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
// for array a
ArrayList<Integer> list = (ArrayList<Integer>) Arrays.stream(a).boxed().collect(Collectors.toList());
System.out.println(list);
for(Integer i: A){
ArrayList<Integer> tSet = new ArrayList<>();
tSet.add(Collections.frequency(list, i));
map.put(i,tSet );
}
System.out.println(map);
list.clear();
// for array b
list = (ArrayList<Integer>) Arrays.stream(b).boxed().collect(Collectors.toList());
System.out.println(list);
for(Integer i: B){
if(map.containsKey(i)){
map.get(i).add(Collections.frequency(list, i));
}
else{
ArrayList<Integer> tSet = new ArrayList<>();
tSet.add(Collections.frequency(list, i));
map.put(i,tSet );
}
}
System.out.println(map);
list.clear();
// for array c
list = (ArrayList<Integer>) Arrays.stream(c).boxed().collect(Collectors.toList());
System.out.println(list);
for(Integer i: C){
if(map.containsKey(i)){
map.get(i).add(Collections.frequency(list, i));
}
else{
ArrayList<Integer> tSet = new ArrayList<>();
tSet.add(Collections.frequency(list, i));
map.put(i,tSet );
}
}
System.out.println(map);
for(int key: map.keySet()){
if(map.get(key).size()>1){
Collections.sort(map.get(key));
int count= map.get(key).get(0);
for(int i=0; i<count; i++){
System.out.print(key+", ");
}
}
}
//end of main function
}
static Integer[] removeDuplicates(int a[]){
HashSet<Integer> set = new HashSet<>();
for (int i:a)
set.add(i);
return set.toArray(new Integer[set.size()]);
}
}
public class Solution2 {
public static void main(String[] args) {
int a[] = {9,9,9,9,8,8,8,7,7,6,5,4};
int b[] = {9,9,9,8,8,7,7,6,4,4,4,3,2};
int c[] = {9,9,9,8,8,7,7,6,5};
Integer[] A = removeDuplicates(a);
Integer[] B = removeDuplicates(b);
Integer[] C = removeDuplicates(c);
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
// for array a
ArrayList<Integer> list = (ArrayList<Integer>) Arrays.stream(a).boxed().collect(Collectors.toList());
System.out.println(list);
for(Integer i: A){
ArrayList<Integer> tSet = new ArrayList<>();
tSet.add(Collections.frequency(list, i));
map.put(i,tSet );
}
System.out.println(map);
list.clear();
// for array b
list = (ArrayList<Integer>) Arrays.stream(b).boxed().collect(Collectors.toList());
System.out.println(list);
for(Integer i: B){
if(map.containsKey(i)){
map.get(i).add(Collections.frequency(list, i));
}
else{
ArrayList<Integer> tSet = new ArrayList<>();
tSet.add(Collections.frequency(list, i));
map.put(i,tSet );
}
}
System.out.println(map);
list.clear();
// for array c
list = (ArrayList<Integer>) Arrays.stream(c).boxed().collect(Collectors.toList());
System.out.println(list);
for(Integer i: C){
if(map.containsKey(i)){
map.get(i).add(Collections.frequency(list, i));
}
else{
ArrayList<Integer> tSet = new ArrayList<>();
tSet.add(Collections.frequency(list, i));
map.put(i,tSet );
}
}
System.out.println(map);
for(int key: map.keySet()){
if(map.get(key).size()>1){
Collections.sort(map.get(key));
int count= map.get(key).get(0);
for(int i=0; i<count; i++){
System.out.print(key+", ");
}
}
}
//end of main function
}
static Integer[] removeDuplicates(int a[]){
HashSet<Integer> set = new HashSet<>();
for (int i:a)
set.add(i);
return set.toArray(new Integer[set.size()]);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class ConvertArrayFrom3Array {
public static void main(String[] args) {
Integer[] arr1 = {2, 5, 3, 2, 8,1};
Integer[] arr2 = {7, 9, 5, 2, 4, 10, 10};
Integer[] arr3 = {6, 7, 5, 5, 3, 7};
/**
* Combine all the array and remove duplicates
*/
Set<Integer> set1 = new HashSet<>(Arrays.asList(arr1));
Set<Integer> set2 = new HashSet<>(Arrays.asList(arr2));
Set<Integer> set3 = new HashSet<>(Arrays.asList(arr3));
Set<Integer> set = new HashSet<>();
//set1.retainAll(set2);
set.addAll(Arrays.asList(arr1));
set.addAll(Arrays.asList(arr2));
set.addAll(Arrays.asList(arr3));
ArrayList<Integer> list = new ArrayList<>();
for (Integer val: set) {
if(set1.contains(val) && set2.contains(val) && set3.contains(val)) {
list.add(val);
}
else if(set1.contains(val) && set2.contains(val)) {
list.add(val);
}
else if(set2.contains(val) && set3.contains(val)) {
list.add(val);
}
else if(set1.contains(val) && set3.contains(val)) {
list.add(val);
}
}
System.out.println(list);
}
}
class Array:
def get_array_map(self, array):
temp_map_ele_array = {}
for ele in array:
if ele in temp_map_ele_array:
continue
else:
temp_map_ele_array[ele] = 1
return temp_map_ele_array
def find_elements_presence(self, arrays):
map_element_occurence = {}
for array in arrays:
temp_map_ele_array = self.get_array_map(array)
for k,v in temp_map_ele_array.items():
if k in map_element_occurence:
map_element_occurence[k] += 1
else:
map_element_occurence[k] = 1
res = []
for k,v in map_element_occurence.items():
if v>=2:
res.append(k)
return res
arrays = [[2, 5, 3, 2, 8,1],[7, 9, 5, 2, 4, 10, 10],[6, 7, 5, 5, 3, 7]]
arr = Array()
print(arr.find_elements_presence(arrays))
def intersections(arrays, insresectionCount):
count = Counter()
res = set()
for array in arrays:
for k in set(array):
count[k] += 1
if count[k] >= insresectionCount:
res.add(k)
return list(res)
arrays = [[2, 5, 3, 2, 8, 1, 1, 2, 2], [7, 9, 5, 2, 4, 10, 10], [6, 7, 5, 5, 3, 7]]
print(intersections(arrays, 2))
/**
* The idea is for each list of numbers is
* retained = intersect(list, board) ; result += retained ; board += list
*
*
* @author Omid Ghiasi Tarzi
*/
public static List<Integer> getDuplication(List<List<Integer>> lists) {
Set<Set<Integer>> board = new HashSet<>();
Set<Set<Integer>> resultSet = new HashSet<>();
List<Integer> resultList = new ArrayList<>();
for (List<Integer> list : lists) {
Map<Integer, Integer> localMap = new HashMap<>();
Set<Set<Integer>> localSet = new HashSet<>();
for (int i : list) {
localMap.put(i, localMap.getOrDefault(i, 0) + 1);
localSet.add(new LinkedHashSet<>(Arrays.asList(i, localMap.get(i))));
}
Set<Set<Integer>> retainedSet = new HashSet<>(localSet);
retainedSet.retainAll(board);
resultSet.addAll(retainedSet);
board.addAll(localSet);
}
for (Set<Integer> set : resultSet) {
resultList.add(set.iterator().next());
}
return resultList;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class Booking {
public static void main(String[] args) {
Integer[] A = { 2, 5, 3, 2, 8, 1 };
Integer[] B = { 7, 9, 5, 2, 4, 10, 10 };
Integer[] C = { 6, 7, 5, 5, 3, 7, 8 };
HashSet<Integer> set = new HashSet<>();
List<Integer> L1 = Arrays.asList(A);
List<Integer> L2 = Arrays.asList(B);
List<Integer> L3 = Arrays.asList(C);
set.addAll(L1);
set.addAll(L2);
set.addAll(L3);
List<Integer> list = new ArrayList<>();
for (int i : set) {
if ((L1.contains(i) && L2.contains(i)) || (L2.contains(i) && L3.contains(i))
|| (L1.contains(i) && L3.contains(i))) {
list.add(i);
}
}
System.out.println(list);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class Google {
public static void main(String[] args) {
Integer[] A = { 2, 5, 3, 2, 8, 1 };
Integer[] B = { 7, 9, 5, 2, 4, 10, 10 };
Integer[] C = { 6, 7, 5, 5, 3, 7, 8 };
HashSet<Integer> set = new HashSet<>();
List<Integer> L1 = Arrays.asList(A);
List<Integer> L2 = Arrays.asList(B);
List<Integer> L3 = Arrays.asList(C);
set.addAll(L1);
set.addAll(L2);
set.addAll(L3);
List<Integer> list = new ArrayList<>();
for (int i : set) {
if ((L1.contains(i) && L2.contains(i)) || (L2.contains(i) && L3.contains(i))
|| (L1.contains(i) && L3.contains(i))) {
list.add(i);
}
}
System.out.println(list);
}
}
package it.rob.java.test;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;
public class JavaTestMain {
// make an array from this three arrays which elements is present in at least two array
public static void main(String[] args) {
int[] a = {2, 5, 3, 2, 8, 1};
int[] b = {7, 9, 5, 2, 4, 10, 10};
int[] c = {6, 7, 5, 5, 3, 7};
giveSolution(a, b, c).forEach(i -> System.out.println(i));
}
private static Set<Integer> giveSolution(int[] a, int[] b, int[] c) {
Set<Integer> aSet = removeDuplicate(a);
Set<Integer> bSet = removeDuplicate(b);
Set<Integer> cSet = removeDuplicate(c);
Set<Integer> ab = compare(aSet, bSet);
Set<Integer> ac = compare(aSet, cSet);
Set<Integer> bc = compare(bSet, cSet);
ab.addAll(ac);
ab.addAll(bc);
return ab;
}
private static Set<Integer> compare(Set<Integer> a, Set<Integer> b) {
return a.stream().filter(number -> b.contains(number)).collect(Collectors.toSet());
}
private static Set<Integer> removeDuplicate(int[] arr) {
Set<Integer> setArr = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
setArr.add(arr[i]);
}
return setArr;
}
}
val a = arrayOf(2, 5, 3, 2, 8, 1)
val b = arrayOf(7, 9, 5, 2, 4, 10, 10)
val c = arrayOf(6, 7, 5, 5, 3, 7)
val merge = arrayListOf(a, b, c)
val map = mutableMapOf<Int, Int>()
val result = mutableListOf<Int>()
var size = 0
// O(3)
merge.forEach {
size = max(size, it.size)
}
// O(N * 3)
for (position in 0..size) {
merge.forEachIndexed { index, it ->
if (it.size > position + 1) {
if (map.containsKey(it[position])) {
if (map[it[position]] != index) {
result.add(it[position])
}
}
map[it[position]] = index
}
}
}
print(result)
package com.lucasmontano.algo
import org.junit.Test
import kotlin.math.max
/**
* You have three Arrays.
*
* A = {2, 5, 3, 2, 8,1}
* B = {7, 9, 5, 2, 4, 10, 10}
* C = {6, 7, 5, 5, 3, 7}
*
* make an array from this three arrays which elements is present in at least two array.
*
* This question was followed by instead of three arrays.
* If you have a list of array then what will be the solution?
* Also what will be the time complexity?
*
*/
class Algo4 {
@Test
fun `caseA`() {
val a = arrayOf(2, 5, 3, 2, 8, 1)
val b = arrayOf(7, 9, 5, 2, 4, 10, 10)
val c = arrayOf(6, 7, 5, 5, 3, 7)
val merge = arrayListOf(a, b, c)
val map = mutableMapOf<Int, Int>()
val result = mutableListOf<Int>()
var size = 0
// O(3)
merge.forEach {
size = max(size, it.size)
}
// O(N * 3)
for (position in 0..size) {
merge.forEachIndexed { index, it ->
if (it.size > position + 1) {
if (map.containsKey(it[position])) {
if (map[it[position]] != index) {
result.add(it[position])
}
}
map[it[position]] = index
}
}
}
print(result)
}
}
package com.lucasmontano.algo
import org.junit.Test
import kotlin.math.max
/**
* You have three Arrays.
*
* A = {2, 5, 3, 2, 8,1}
* B = {7, 9, 5, 2, 4, 10, 10}
* C = {6, 7, 5, 5, 3, 7}
*
* make an array from this three arrays which elements is present in at least two array.
*
* This question was followed by instead of three arrays.
* If you have a list of array then what will be the solution?
* Also what will be the time complexity?
*
*/
class Algo4 {
@Test
fun `caseA`() {
val a = arrayOf(2, 5, 3, 2, 8, 1)
val b = arrayOf(7, 9, 5, 2, 4, 10, 10)
val c = arrayOf(6, 7, 5, 5, 3, 7)
val merge = arrayListOf(a, b, c)
val map = mutableMapOf<Int, Int>()
val result = mutableListOf<Int>()
var size = 0
// O(3)
merge.forEach {
size = max(size, it.size)
}
// O(N * 3)
for (position in 0..size) {
merge.forEachIndexed { index, it ->
if (it.size > position + 1) {
if (map.containsKey(it[position])) {
if (map[it[position]] != index) {
result.add(it[position])
}
}
map[it[position]] = index
}
}
}
print(result)
}
}
package com.lucasmontano.algo
import org.junit.Test
import kotlin.math.max
/**
* You have three Arrays.
*
* A = {2, 5, 3, 2, 8,1}
* B = {7, 9, 5, 2, 4, 10, 10}
* C = {6, 7, 5, 5, 3, 7}
*
* make an array from this three arrays which elements is present in at least two array.
*
* This question was followed by instead of three arrays.
* If you have a list of array then what will be the solution?
* Also what will be the time complexity?
*
*/
class Algo4 {
@Test
fun `caseA`() {
val a = arrayOf(2, 5, 3, 2, 8, 1)
val b = arrayOf(7, 9, 5, 2, 4, 10, 10)
val c = arrayOf(6, 7, 5, 5, 3, 7)
val merge = arrayListOf(a, b, c)
val map = mutableMapOf<Int, Int>()
val result = mutableListOf<Int>()
var size = 0
// O(3)
merge.forEach {
size = max(size, it.size)
}
// O(N * 3)
for (position in 0..size) {
merge.forEachIndexed { index, it ->
if (it.size > position + 1) {
if (map.containsKey(it[position])) {
if (map[it[position]] != index) {
result.add(it[position])
}
}
map[it[position]] = index
}
}
}
print(result)
}
}
import java.util.*;
import java.util.stream.Collectors;
public class Main
{
public static void main(String[] args) {
System.out.println("Hello World");
Integer[] A = {2, 5, 3, 2, 8, 1};
Integer[] B = {7, 9, 5, 2, 4, 10, 10};
Integer[] C = {6, 7, 5, 5, 3, 7};
ArrayList<Integer> listA = new ArrayList(Arrays.asList(A));
ArrayList<Integer> listB = new ArrayList(Arrays.asList(B));
ArrayList<Integer> listC = new ArrayList(Arrays.asList(C));
ArrayList<Integer> output = new ArrayList<Integer>();
List<Integer> listAA = listA.stream().distinct().collect(Collectors.toList());
List<Integer> listBB = listB.stream().distinct().collect(Collectors.toList());
List<Integer> listCC = listC.stream().distinct().collect(Collectors.toList());
System.out.println(listAA);
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Integer a : listAA){
map.put(a,1);
}
for(Integer a : listBB){
map.put(a,(map.containsKey(a) ? map.get(a)+1:1));
}
for(Integer a : listCC){
map.put(a,(map.containsKey(a) ? map.get(a)+1:1));
}
for(Map.Entry<Integer, Integer> e : map.entrySet()){
if(e.getValue()> 1){
output.add(e.getKey());
}
}
System.out.println(map);
System.out.println(output);
}
}
import java.util.*;
import java.util.stream.Collectors;
public class Main
{
public static void main(String[] args) {
System.out.println("Hello World");
Integer[] A = {2, 5, 3, 2, 8, 1};
Integer[] B = {7, 9, 5, 2, 4, 10, 10};
Integer[] C = {6, 7, 5, 5, 3, 7};
ArrayList<Integer> listA = new ArrayList(Arrays.asList(A));
ArrayList<Integer> listB = new ArrayList(Arrays.asList(B));
ArrayList<Integer> listC = new ArrayList(Arrays.asList(C));
ArrayList<Integer> output = new ArrayList<Integer>();
List<Integer> listAA = listA.stream().distinct().collect(Collectors.toList());
List<Integer> listBB = listB.stream().distinct().collect(Collectors.toList());
List<Integer> listCC = listC.stream().distinct().collect(Collectors.toList());
System.out.println(listAA);
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Integer a : listAA){
map.put(a,1);
}
for(Integer a : listBB){
map.put(a,(map.containsKey(a) ? map.get(a)+1:1));
}
for(Integer a : listCC){
map.put(a,(map.containsKey(a) ? map.get(a)+1:1));
}
for(Map.Entry<Integer, Integer> e : map.entrySet()){
if(e.getValue()> 1){
output.add(e.getKey());
}
}
System.out.println(map);
System.out.println(output);
}
}
import java.util.*;
/**
* A = {2, 5, 3, 2, 8,1}
* B = {7, 9, 5, 2, 4, 10, 10}
* C = {6, 7, 5, 5, 3, 7}
*/
public class Main {
public static void main(String[] args) {
int[] A = {2, 5, 3, 2, 8, 1};
int[] B = {7, 9, 5, 2, 4, 10, 10};
int[] C = {6, 7, 5, 5, 3, 7};
HashMap<Integer, HashSet<String>> map = new HashMap<>();
for (int element : A) {
if (map.get(element) != null) {
map.get(element).add("A");
map.put(element, map.get(element));
} else {
HashSet<String> set = new HashSet<>();
set.add("A");
map.put(element, set);
}
}
for (int element : B) {
if (map.get(element) != null) {
map.get(element).add("B");
map.put(element, map.get(element));
} else {
HashSet<String> set = new HashSet<>();
set.add("B");
map.put(element, set);
}
}
for (int element : C) {
if (map.get(element) != null) {
map.get(element).add("C");
map.put(element, map.get(element));
} else {
HashSet<String> set = new HashSet<>();
set.add("C");
map.put(element, set);
}
}
// create the array
ArrayList<Integer> elements = new ArrayList<>();
for (Map.Entry<Integer, HashSet<String>> entry : map.entrySet()){
if (entry.getValue().size() > 1) {
elements.add(entry.getKey());
}
}
System.out.println(elements);
}
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* You have three Arrays.
*
* A = {2, 5, 3, 2, 8,1}
* B = {7, 9, 5, 2, 4, 10, 10}
* C = {6, 7, 5, 5, 3, 7}
*
* make an array from this three arrays which elements is present in at least two array.
*
* This question was followed by instead of three arrays.
* If you have a list of array then what will be the solution?
* Also what will be the time complexity?
*/
public class CommonElementsBetweenArrays {
public static void main(String[] args) {
int[] A = {2, 5, 3, 2, 8, 1};
int[] B = {7, 9, 5, 2, 4, 10, 10};
int[] C = {6, 7, 5, 5, 3, 7};
List<Set<Integer>> listsOfUniqueArrays = new ArrayList<>();
listsOfUniqueArrays.add(intArrayToSet(A));
listsOfUniqueArrays.add(intArrayToSet(B));
listsOfUniqueArrays.add(intArrayToSet(C));
Set<Integer> processedElements = new HashSet<>();
Set<Integer> duplicateElementsBetweenArrays = new HashSet<>();
for (Set<Integer> setOfIntegers : listsOfUniqueArrays) {
for (Integer integer : setOfIntegers) {
if (!processedElements.add(integer)) {
duplicateElementsBetweenArrays.add(integer);
}
}
}
int[] result = duplicateElementsBetweenArrays.stream().mapToInt(Integer::intValue).toArray();
for (int i : result) {
System.out.println(i+", ");
}
}
private static Set<Integer> intArrayToSet(int[] a) {
Set<Integer> integers = new HashSet<>();
for (int i : a) {
integers.add(i);
}
return integers;
}
}
var a1: Array<Any> = arrayOf(2, 5, 3, 2, 8, 1)
var a2: Array<Any> = arrayOf(7, 9, 5, 2, 4, 10, 10)
var a3: Array<Any> = arrayOf(6, 7, 5, 5, 3, 7)
var result = mutableSetOf<Any>()
var separator: String = "-"
// O(n)
var merged = a1.distinct().plus(separator).plus(elements = a2.distinct()).plus(separator).plus(elements = a3.distinct())
// O(n)
var repeatRate = hashMapOf<Any?, Int>()
var iv = 1
for(item in merged) { // O(n)
if(item != separator){
val rate = repeatRate[item] // O(c)
if(rate != null) {
repeatRate[item] = rate + 1 // O(c)
result.add(item) // O(c)
}
else repeatRate[item] = 1 // O(c)
}
else iv++ // O(c)
}
println(result)
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
public class Test{
public static void main(String []args){
Integer[] A = {2, 5, 3, 2, 8,1};
Integer[] B = {7, 9, 5, 2, 4, 10, 10};
Integer[] C = {6, 7, 5, 5, 3, 7};
Set<Integer> setA = new HashSet<>(Arrays.asList(A));
Set<Integer> setB = new HashSet<>(Arrays.asList(B));
Set<Integer> setC = new HashSet<>(Arrays.asList(C));
Set<Integer> full = new HashSet<>();
full.addAll(setA);
full.addAll(setB);
full.addAll(setC);
Set<Integer> output = new HashSet<>();
for (Integer entry : full){
int sharedCount = 0;
if (setA.contains(entry))
sharedCount++;
if (setB.contains(entry))
sharedCount++;
if (sharedCount > 0) {
if (setC.contains(entry))
sharedCount++;
}
if (sharedCount > 1)
output.add(entry);
}
System.out.println(output.toString());
}
}
import kotlin.math.max
fun main(args: Array<String>) {
val A = intArrayOf(2, 5, 3, 2, 8, 1)
val B = intArrayOf(7, 9, 5, 2, 4, 10, 10)
val C = intArrayOf(6, 7, 5, 5, 3, 7)
val maxValue = max(A.max()!!, max(B.max()!!, C.max()!!))
getCommonElementsInAtLeastTwoOfThree(maxValue, A, B, C)
}
fun getCommonElementsInAtLeastTwoOfThree(
maxValue: Int,
a: IntArray,
b: IntArray,
c: IntArray
) {
val A = IntArray(maxValue+1)
val B = IntArray(maxValue+1)
val C = IntArray(maxValue+1)
for (number in a) {
A[number]++
}
for (number in b) {
B[number]++
}
for (number in c) {
C[number]++
}
for (i in 0 until maxValue) {
if ((A[i] > 0 && B[i] > 0) || (B[i] > 0 && C[i] > 0) || (A[i] > 0 && C[i] > 0)) {
print("$i ")
}
}
}
func atLeastInTwoArrays(_ listOfArrays: [[Int]]) -> [Int] {
var array: [Int: Int] = [:]
for i in 0..<listOfArrays.count {
for index in 0..<listOfArrays[i].count {
if let current = array[listOfArrays[i][index]] {
array[listOfArrays[i][index]] = current + 1
} else {
array[listOfArrays[i][index]] = 1
}
}
}
var newArray:[Int] = []
for (item, times) in array {
if times > 1 {
newArray.append(item)
}
}
return newArray
}
func atLeastInTwoArrays(_ listOfArrays: [[Int]]) -> [Int] {
var array: [Int: Int] = [:]
for i in 0..<listOfArrays.count {
for index in 0..<listOfArrays[i].count {
if let current = array[listOfArrays[i][index]] {
array[listOfArrays[i][index]] = current + 1
} else {
array[listOfArrays[i][index]] = 1
}
}
}
var newArray:[Int] = []
for (item, times) in array {
if times > 1 {
newArray.append(item)
}
}
return newArray
}
HashMap<Integer, Set<Integer>> lookup = new HashMap<>();
List<Integer> result = new ArrayList<>();
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr[i].length; j++) {
Set<Integer> indices = lookup.getOrDefault(arr[i][j], new HashSet<Integer>());
indices.add(i);
lookup.put(arr[i][j], indices);
}
}
int k = arr.length;
for(Map.Entry<Integer, Set<Integer>> e: lookup.entrySet()) {
if(e.getValue().size() == k) result.add(e.getKey());
}
int res[] = result.stream().mapToInt(i->i).toArray();
return res;
from collections import defaultdict
class Solution:
# @param A : list of integers
# @param B : list of integers
# @param C : list of integers
# @return a list of integers
def solve(self, A, B, C):
counter = defaultdict(int)
ans = []
for arr in [A, B, C]:
for i in set(arr):
counter[i] += 1
for value, freq in counter.items():
if freq >= 2:
ans.append(value)
return sorted(ans)
from collections import defaultdict
class Solution:
# @param A : list of integers
# @param B : list of integers
# @param C : list of integers
# @return a list of integers
def solve(self, A, B, C):
counter = defaultdict(int)
ans = []
for arr in [A, B, C]:
for i in set(arr):
counter[i] += 1
for value, freq in counter.items():
if freq >= 2:
ans.append(value)
return sorted(ans)
import java.util.*;
public class Main {
static ArrayList<Integer> getDuplicateElementsAcrossArrays(ArrayList<ArrayList<Integer>> arrays) {
// keep a hashmap key = element, value = count of arrays
HashMap<Integer, Integer> arrayCounts = new HashMap<>();
// loop over list of arrays
// loop over array - check if element exists, increment the count, else add element, 1
// how do we avoid duplicate entries in the same array
for (int i = 0; i < arrays.size(); i++) {
ArrayList<Integer> array = arrays.get(i);
HashSet<Integer> duplicates = new HashSet<>();
for (int j = 0; j < array.size(); j++) {
int element = array.get(j);
if (!duplicates.contains(element)) {
if (arrayCounts.containsKey(element)) {
int arrayCount = arrayCounts.get(element);
arrayCounts.replace(element, arrayCount+1);
} else {
arrayCounts.put(element, 1);
}
duplicates.add(element);
}
}
}
ArrayList<Integer> elementsDuplicateAcrossArrays = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry: arrayCounts.entrySet()) {
if (entry.getValue() >= 2) {
elementsDuplicateAcrossArrays.add(entry.getKey());
}
}
return elementsDuplicateAcrossArrays;
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> arrays = new ArrayList<>();
// Add test data
ArrayList<Integer> array1 = new ArrayList<>();
array1.add(2);
array1.add(5);
array1.add(3);
array1.add(2);
array1.add(8);
array1.add(1);
ArrayList<Integer> array2 = new ArrayList<>();
array2.add(7);
array2.add(9);
array2.add(5);
array2.add(2);
array2.add(4);
array2.add(10);
array2.add(10);
ArrayList<Integer> array3 = new ArrayList<>();
array3.add(6);
array3.add(7);
array3.add(5);
array3.add(5);
array3.add(3);
array3.add(7);
arrays.add(array1);
arrays.add(array2);
arrays.add(array3);
// Call function
ArrayList<Integer> duplicateElements = getDuplicateElementsAcrossArrays(arrays);
for (int i = 0; i < duplicateElements.size(); i++) {
System.out.print(duplicateElements.get(i) + " ");
}
}
}
- Sunil S August 12, 2019