Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

boolean checkIfElementExistInSet(List<Set<Integer>> setList,Set<Integer> inputSet) {
		int n = inputSet.size();
		for(Set currSet:setList) {
			int c = 0;
			for(int number:currSet) {
				if(inputSet.contains(number)) {
					c++;
				}
			}
			if(c!=n) {
				return false;
			}
		}
		return true;
	}

- anweshthecool0 July 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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...

- NoOne July 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
    }

- funk July 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// if it was [1] <= is subset 
exists(list_of_sets) where { my_set <= $.o }
// if it was [2] subset is not invertible, so...
!exists(list_of_sets) where { !(my_set <= $.o) }
// if it was [3] | is union, OR 
my_set <= reduce( list_of_sets ) as { $.p | $.o }

- NoOne July 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

        }

    }
}

- KD July 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- learnsomething247 July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Rohan Tare July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- Rohan Tare July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- Rohan Tare July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- ultikhopdi July 17, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More