Amazon Interview Question
Backend DevelopersCountry: United States
Evaluate the product of the list and keep popping it off until the list is not empty.
Solution in Python:
class CartesianIterator:
def __init__(self, sets):
self.result = [[]]
for pool in sets:
self.result = [x + [y] for x in self.result for y in pool]
def hasNext(self):
return len(self.result) != 0
def next(self):
return self.result.pop(0)
Test Code:
Test code
# Example 1
c = CartesianIterator([[1,2,3], [4,5]])
while c.hasNext():
print(c.next(), end=', ')
print()
# Example 2
c = CartesianIterator([['a','b','c'], ['p', 'q'], ['r', 's']])
while c.hasNext():
print(c.next(), end=', ')
print()
Output:
[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5],
['a', 'p', 'r'], ['a', 'p', 's'], ['a', 'q', 'r'], ['a', 'q', 's'], ['b', 'p', 'r'], ['b', 'p', 's'], ['b', 'q', 'r'], ['b', 'q', 's'], ['c', 'p', 'r'], ['c', 'p', 's'], ['c', 'q', 'r'], ['c', 'q', 's'],
Solution in Java, using recursion
import java.util.List;
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
class PermIterator {
private Iterator<Set<String>> it;
int count = 0;
PermIterator (Set<Set<String>> n) {
count =n.size();
it = n.iterator();
}
public Set<String> next() {
count--;
return it.next();
}
public boolean hasNext() {
if (count > 0)
return true;
return false;
}
}
public class IteratorForPermKArrays {
public static Set<Set<String>> multiply(String[] x, String[] y, String[] z) {
List<List<String>> input = new ArrayList<>();
input.add(Arrays.asList(x));
input.add(Arrays.asList(y));
input.add(Arrays.asList(z));
Set<Set<String>> result = permK(input);
return result;
}
//Time O(nXk) = O(n^2), Space O(n^2), n is the max length of arrays, K is number of arrays
public static Set<Set<String>> permK(List<List<String>> in) {
final Set<Set<String>> out = new HashSet<Set<String>>();
permUtil(new ArrayList<List<String>>(in), new HashSet<String>(), out);
return out;
}
private static void permUtil(List<List<String>> in, Set<String> part, Set<Set<String>> out) {
if (in.isEmpty()) {
out.add(part);
return;
}
if (out.contains(part))
return;
List<List<String>> nextIn = new ArrayList<List<String>>(in);
for (String s : nextIn.remove(0)) {
Set<String> nextPart = new LinkedHashSet<String>(part);
nextPart.add(s);
permUtil(nextIn, nextPart, out);
}
}
public static void main(String[] args) {
String[] x = {"a","b","c"};
String[] y = {"p","q"};
String[] z = {"r","s"};
Set<Set<String>> result = multiply(x,y,z);
System.out.println("Permutation of arrys:");
PermIterator k = new PermIterator(result);
while(k.hasNext()){
System.out.println(k.next());
}
}
}
import java.util.*;
import java.util.stream.Collectors;
public class CartesianIteration {
public static void main(String... arg) {
CartesianIterator<Character> characterCartesianIterator = new CartesianIterator<>(
Arrays.asList(
Arrays.asList('a', 'b', 'c'),
Arrays.asList('p', 'q'),
Arrays.asList('r', 's')));
while (characterCartesianIterator.hasNext()) {
System.out.println(characterCartesianIterator.next());
}
}
}
class CartesianIterator<T> implements Iterator<List<T>> {
private List<List<T>> results;
private int iterCursor = 0;
public CartesianIterator(List<List<T>> ListOfLists) {
results = process(ListOfLists);
}
public List<List<T>> process(List<List<T>> lists) {
List<List<T>> tempResults = new ArrayList<>();
if (lists.size() == 1) {
return lists
.get(0)
.stream()
.map(Arrays::asList)
.collect(Collectors.toList());
}
for (T t : lists.get(0)) {
for (List<T> recursionInnerList : process(lists.subList(1, lists.size()))) {
List<T> innerList = new ArrayList<>(Collections.singletonList(t));
innerList.addAll(recursionInnerList);
tempResults.add(innerList);
}
}
return tempResults;
}
@Override
public boolean hasNext() {
return iterCursor < results.size();
}
@Override
public List<T> next() {
return results.get(iterCursor++);
}
}
- NoOne March 11, 2018