Amazon Interview Question for Backend Developers


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' ] ] )

- NoOne March 11, 2018 | Flag Reply
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'],

- prudent_programmer March 23, 2018 | Flag Reply
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());
        }
	} 
}

- lavivien17 April 09, 2018 | Flag Reply
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++);
    }
}

- abrahamimohiosen April 14, 2018 | 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