Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
The solution examples are obviously wrong.
Formally, the question can be any of these two :
1. Is a set x, subset of *any* of the sets contains in a list?
2. Is a set x, subset of *all* of the sets contains in a list?
If the question was [1], then "But checking for {1,2} in {1,5,6}, {2,3,1} should return false as {1,5,6} does not contain all elements of {1,2} 2 is missing" is wrong. Obviously.
If the question was [2], then "For example checking for set1 = {1,2} in {1,2,3}, {5,6} should return true" would be wrong.
The other fancy things I can think of are:
[3] Is a set x, subset of union of the sets contains in a list?
That would not work also.
See solutions...
This solution is O(kn) where k is the number of sets in the list and n is the size of those sets.
public static boolean isContained(Set<Integer> test, Set<Integer>[] sets) {
int total = test.size();
Map<Integer, Boolean> testMap = new HashMap<>(total);
for ( Integer i : test ) { testMap.put(i, true); }
for ( Set<Integer> s : sets ) {
int counter = 0;
for ( Integer k : s ) {
if ( testMap.get(k) != null ) {
counter++;
if ( counter >= total ) { return true; }
}
}
}
return false;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test_aws
{
/*
* Identifying if all the elements of a set (in enterity) is present in a list of sets.
*
* For example checking for set1 = {1,2} in {1,2,3}, {5,6} should return true as {1,2} is present in {1,2,3}. Similiary it will be true for {1,2,8,9}, {1,2,4}
* But checking for {1,2} in {1,5,6}, {2,3,1} should return false as {1,5,6} does not contain all elements of {1,2} 2 is missing
*/
class FindSets
{
public FindSets()
{
List<HashSet<int>> baseset = new List<HashSet<int>>() { new HashSet<int>() { 8, 2, 3 }, new HashSet<int>() { 4, 5, 6 }, new HashSet<int>() { 1,2 } };
HashSet<int> set = new HashSet<int>() { 1,2};
bool i = false;
i= findset(baseset, set);
Console.WriteLine(i.ToString());
}
public bool findset(List<HashSet<int>> baseset, HashSet<int> set)
{
foreach (HashSet<int> s in baseset) {
if (Checkifequal(s,set))
{
return true;
}
}
return false;
}
public bool Checkifequal(HashSet<int> mains, HashSet<int> set)
{
int firstelement;
firstelement = set.ElementAtOrDefault(0);
int[] maina = mains.ToArray();
var index = Array.IndexOf(maina, firstelement);
if (index>=0)
{
for(int i = 0;i<set.Count;i++)
{
if (set.ElementAtOrDefault(i) != mains.ElementAtOrDefault(index + i))
return false;
}
return true;
}
else return false;
}
}
}
package com.sk.misc;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class SetPresence {
public static void main(String[] args) {
Set<Integer> s1 = new HashSet<Integer>();
s1.addAll(Arrays.asList(1, 2));
Set<Integer> ss1 = new HashSet<Integer>();
ss1.addAll(Arrays.asList(1, 2, 4));
Set<Integer> ss2 = new HashSet<Integer>();
ss2.addAll(Arrays.asList(1, 2, 8, 9));
Set<Integer> x1 = new HashSet<Integer>();
x1.addAll(Arrays.asList(1, 2));
Set<Integer> xx1 = new HashSet<Integer>();
xx1.addAll(Arrays.asList(1, 5, 6));
Set<Integer> xx2 = new HashSet<Integer>();
xx2.addAll(Arrays.asList(2, 3, 1));
System.out.println(exists(s1, ss1, ss2));
System.out.println(exists(x1, xx1, xx2));
}
@SafeVarargs
public static boolean exists(Set<Integer> set, Set<Integer>... setList) {
for (Set<Integer> s : setList) {
if (!s.containsAll(set)) {
return false;
}
}
return true;
}
}
package test.test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* Author: Rohan Tare
*
*/
public class FindSetInListofSet
{
public static void main( String[] args )
{
Set<Integer> setToFind = new HashSet<Integer>();
List<Set<Integer>> listOfSet = new ArrayList<Set<Integer>>();
setToFind.add(1);
setToFind.add(7);
Set<Integer> newSet1 = new HashSet<Integer>();
newSet1.add(1);
newSet1.add(5);
newSet1.add(6);
listOfSet.add(newSet1);
Set<Integer> newSet2 = new HashSet<Integer>();
newSet2.add(2);
newSet2.add(3);
newSet2.add(6);
listOfSet.add(newSet2);
Set<Integer> newSet3 = new HashSet<Integer>();
newSet3.add(4);
newSet3.add(7);
newSet3.add(8);
listOfSet.add(newSet3);
Set<Integer> newSet4 = new HashSet<Integer>();
newSet4.add(5);
newSet4.add(1);
newSet4.add(2);
listOfSet.add(newSet4);
Set<Integer> newSet5 = new HashSet<Integer>();
newSet5.add(9);
newSet5.add(6);
newSet5.add(1);
listOfSet.add(newSet5);
boolean result = isSetExists(setToFind,listOfSet);
System.out.println(result);
}
private static boolean isSetExists(Set<Integer> setToFind, List<Set<Integer>> listOfSet) {
if (setToFind == null || setToFind.isEmpty() || listOfSet == null || listOfSet.isEmpty()) {
return false;
}
Map<Integer, Set<Integer>> myMap = prepareMap(listOfSet);
Set<Integer> currentIndexSet = null;
Set<Integer> finalIndexSet = null;
for(Integer currentVal : setToFind) {
if (myMap.get(currentVal) != null) {
currentIndexSet = myMap.get(currentVal);
if ( finalIndexSet == null) {
finalIndexSet = currentIndexSet;
}
finalIndexSet.retainAll(currentIndexSet);
}
}
System.out.println(finalIndexSet);
if (finalIndexSet.isEmpty())
return false;
else return true;
}
private static Map<Integer, Set<Integer>> prepareMap( List<Set<Integer>> listOfSet) {
Map<Integer, Set<Integer>> myMap = new HashMap<Integer, Set<Integer>>();
int index = 0;
for (Set<Integer> currentSet : listOfSet) {
for (Integer currentVal : currentSet) {
if(myMap.containsKey(currentVal)) {
myMap.get(currentVal).add(index);
}else {
HashSet<Integer> setOfIndex = new HashSet<Integer>();
setOfIndex.add(index);
myMap.put(currentVal, setOfIndex);
}
}
index++;
}
return myMap;
}
}
package test.test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* Author: Rohan Tare
*
*/
public class FindSetInListofSet
{
public static void main( String[] args )
{
Set<Integer> setToFind = new HashSet<Integer>();
List<Set<Integer>> listOfSet = new ArrayList<Set<Integer>>();
setToFind.add(1);
setToFind.add(7);
Set<Integer> newSet1 = new HashSet<Integer>();
newSet1.add(1);
newSet1.add(5);
newSet1.add(6);
listOfSet.add(newSet1);
Set<Integer> newSet2 = new HashSet<Integer>();
newSet2.add(2);
newSet2.add(3);
newSet2.add(6);
listOfSet.add(newSet2);
Set<Integer> newSet3 = new HashSet<Integer>();
newSet3.add(4);
newSet3.add(7);
newSet3.add(8);
listOfSet.add(newSet3);
Set<Integer> newSet4 = new HashSet<Integer>();
newSet4.add(5);
newSet4.add(1);
newSet4.add(2);
listOfSet.add(newSet4);
Set<Integer> newSet5 = new HashSet<Integer>();
newSet5.add(9);
newSet5.add(6);
newSet5.add(1);
listOfSet.add(newSet5);
boolean result = isSetExists(setToFind,listOfSet);
System.out.println(result);
}
private static boolean isSetExists(Set<Integer> setToFind, List<Set<Integer>> listOfSet) {
if (setToFind == null || setToFind.isEmpty() || listOfSet == null || listOfSet.isEmpty()) {
return false;
}
Map<Integer, Set<Integer>> myMap = prepareMap(listOfSet);
Set<Integer> currentIndexSet = null;
Set<Integer> finalIndexSet = null;
for(Integer currentVal : setToFind) {
if (myMap.get(currentVal) != null) {
currentIndexSet = myMap.get(currentVal);
if ( finalIndexSet == null) {
finalIndexSet = currentIndexSet;
}
finalIndexSet.retainAll(currentIndexSet);
}
}
System.out.println(finalIndexSet);
if (finalIndexSet.isEmpty())
return false;
else return true;
}
private static Map<Integer, Set<Integer>> prepareMap( List<Set<Integer>> listOfSet) {
Map<Integer, Set<Integer>> myMap = new HashMap<Integer, Set<Integer>>();
int index = 0;
for (Set<Integer> currentSet : listOfSet) {
for (Integer currentVal : currentSet) {
if(myMap.containsKey(currentVal)) {
myMap.get(currentVal).add(index);
}else {
HashSet<Integer> setOfIndex = new HashSet<Integer>();
setOfIndex.add(index);
myMap.put(currentVal, setOfIndex);
}
}
index++;
}
return myMap;
}
}
package test.test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* Author: Rohan Tare
*
*/
public class FindSetInListofSet
{
public static void main( String[] args )
{
Set<Integer> setToFind = new HashSet<Integer>();
List<Set<Integer>> listOfSet = new ArrayList<Set<Integer>>();
setToFind.add(1);
setToFind.add(7);
Set<Integer> newSet1 = new HashSet<Integer>();
newSet1.add(1);
newSet1.add(5);
newSet1.add(6);
listOfSet.add(newSet1);
Set<Integer> newSet2 = new HashSet<Integer>();
newSet2.add(2);
newSet2.add(3);
newSet2.add(6);
listOfSet.add(newSet2);
Set<Integer> newSet3 = new HashSet<Integer>();
newSet3.add(4);
newSet3.add(7);
newSet3.add(8);
listOfSet.add(newSet3);
Set<Integer> newSet4 = new HashSet<Integer>();
newSet4.add(5);
newSet4.add(1);
newSet4.add(2);
listOfSet.add(newSet4);
Set<Integer> newSet5 = new HashSet<Integer>();
newSet5.add(9);
newSet5.add(6);
newSet5.add(1);
listOfSet.add(newSet5);
boolean result = isSetExists(setToFind,listOfSet);
System.out.println(result);
}
private static boolean isSetExists(Set<Integer> setToFind, List<Set<Integer>> listOfSet) {
if (setToFind == null || setToFind.isEmpty() || listOfSet == null || listOfSet.isEmpty()) {
return false;
}
Map<Integer, Set<Integer>> myMap = prepareMap(listOfSet);
Set<Integer> currentIndexSet = null;
Set<Integer> finalIndexSet = null;
for(Integer currentVal : setToFind) {
if (myMap.get(currentVal) != null) {
currentIndexSet = myMap.get(currentVal);
if ( finalIndexSet == null) {
finalIndexSet = currentIndexSet;
}
finalIndexSet.retainAll(currentIndexSet);
}
}
System.out.println(finalIndexSet);
if (finalIndexSet.isEmpty())
return false;
else return true;
}
private static Map<Integer, Set<Integer>> prepareMap( List<Set<Integer>> listOfSet) {
Map<Integer, Set<Integer>> myMap = new HashMap<Integer, Set<Integer>>();
int index = 0;
for (Set<Integer> currentSet : listOfSet) {
for (Integer currentVal : currentSet) {
if(myMap.containsKey(currentVal)) {
myMap.get(currentVal).add(index);
}else {
HashSet<Integer> setOfIndex = new HashSet<Integer>();
setOfIndex.add(index);
myMap.put(currentVal, setOfIndex);
}
}
index++;
}
return myMap;
}
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
public class Q1_17_7_17 {
public static void main(String[] args) {
Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(3);
Set<Integer> set1 = new HashSet<Integer>();
set1.add(1);
set1.add(2);
set1.add(3);
Set<Integer> set2 = new HashSet<Integer>();
set2.add(5);
set2.add(6);
List<Set<Integer>> list = new ArrayList<Set<Integer>>();
list.add(set1);
list.add(set2);
System.out.println(validate(set, list));
}
private static boolean validate(Set<Integer> set, List<Set<Integer>> list){
if(set == null || list == null){
return false;
}
Boolean[] decisionArr = new Boolean[list.size()];
int counter = 0;
Iterator<Set<Integer>> it = list.iterator();
//Iterate over the list of set
while(it.hasNext()){
Set<Integer> set_1 = it.next();
boolean found = true;
Iterator<Integer> it_1 = set.iterator();
while(it_1.hasNext()){
Integer i = it_1.next();
if(!set_1.contains(i)){
found = false;
break;
}
}
if(found){
decisionArr[counter++] = true;
}else{
decisionArr[counter++] = false;
}
}
//Done iterating over the list of sets
for (int i = 0; i < decisionArr.length; i++) {
if(decisionArr[i]){
return true;
}
}
return false;
}
}
- anweshthecool0 July 11, 2017