## Amazon Interview Question for Backend Developers

• 0
of 0 votes

Country: United States

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

``````/*
Observe the problem of cartesian product from arbitrary no.
of lists. Suppose the lists are : L1, L2, L3, ... Ln
with sizes s1, s2, s3, .. sn
Let the element in the i'th position of k'th list is Lk[i].
The configuration of such indices at any point is, then :
0 0 0 0 ... 0 // n times for the first tuple
0 0 0 0 ....1 // for the 2nd tuple...
...
0 0 0 0 ....(sn-1) // for the sn Tuple.
After than, the first column will be reset, and carry will be generated,
so that the next tuple will be:
0 0 0 0 ...1 0  // for the ( sn + 1) Tuple.

Thus, generating next tuple's index is generating the carry, if any,
and resetting the indices from the index which generated the carry to the end,
and incrementing the index of the left one. This again can generate carry,
so it is a ripple effect from rightmost side to the left most side.
Thus, hasNext() is always possible, till the leftmost list is not exhausted by carry.
next() is the tricky one, where we need to define the carry and the ripple from right to left.
When there is no carry, we can stop having the ripple.
*/
def inc_iterator( some_list, cur_iterator ){
if ( cur_iterator.hasNext ){
return [ false , cur_iterator ]
} else {
return [ true, some_list.iterator ]
}
}
def cartesian ( list_of_list ){
iterators = list ( list_of_list ) as { \$.o.iterator } // get the iterators
my_tuple = select( iterators ) where { \$.o.hasNext() } as  { \$.o.next() }
if ( size( my_tuple) < size(list_of_list) ) return [] // empty tuple
println( my_tuple )
carry = false
while ( !carry ){
for ( i : [ size(list_of_list) - 1 : -1 ] ){
#(carry,iter) = inc_iterator( list_of_list[i], iterators[i] )
if ( i == 0 && carry ) { return } // because now I am having carry to the left
iterators[i] = iter
my_tuple[i] = iter.next
break ( i != 0 && !carry )
}
println( my_tuple )
}
}
cartesian ( [ ['a','b', 'c'] , ['p', 'q' ], ['r','s' ] ] )``````

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

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'],``````

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

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());
}
}
}``````

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

``````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++);
}
}``````

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