Amazon Interview Question for Software Engineers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
4
of 6 vote

Use a Trie.
Time : O(row * col)
Space : O(row * col)

1. Insert the first row in the trie.
2. Then for every row, check if the row is available (similar) in the trie, if yes ignore that row.
else print the row and insert into the trie.

- ram.prasad.prabu July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

One way could be -
1. compte a hashcode out of each row. (17 + 31*a[0] + 31^2*a[1].. <-- approximately)
2. insert into hashMap<hashCode, row>
3. iterate and print hashMap.values()

- X July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,

Can i know on what basis you have computed the hashcode (17 + 31*a[0] + 31^2*a[1])??

will it compute a unique hash for a unique row everytime ?

- iamKrankie July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To be exact, below is a better hashcode suggested by Effective java book.

@Override
public int hashCode() {
int result = 17;
result = 31 * result + a[0];
result = 31 * result + a[1];
result = 31 * result + a[2];
return result;
}

But above(approximate one) is good enough, as its close to java.lang.String's hashcode implementation if am not wrong.

These numbers are chosen as they are odd-primes and in depth detail can be found in the book.

- X July 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

here is the quick solution

Iterate over all the rows 
   append each of the entries of the rows and create a string,
   check if this string is present in he hashtable, if yes, move to next rwo, other wise insert
      it into hashtable

Complexity : O(N*M) time + O(N*M) space

- sonesh July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Unique rows: what does this mean here? rows which have all unique elements or else rows which are not repeated in the matrix more than once...

- rakhee63 July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it means that the sequence of elements in the rows must be unique.

- ritwik_pandey July 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we're printing the rows then only their string representation needs to be unique. Therefore you could use Arrays.toString(matrix[row]).hashcode() to generate the hashcode. Easiest would be to simply create a LinkedHashSet<String> (linked if order matters) and theSet.add(Arrays.toString(matrix[row])) and print theSet at the end. If you didn't want to store all of those strings then you could map the hashcode to an Integer row index and iterate the values to get the row indices to print at the end, but then you would have to generate the string representation of the row again. Depends on size of the data and expense of Arrays.toString(). O(n) complexity and space.

This looks cool but I'd bet there's a hashmap somewhere in the reduce of the distinct:

Arrays.stream(MATRIX)
          .map(row -> Arrays.toString(row))
          .distinct()
          .forEach(System.out::println);

- clish July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[][] FindUniqueRows(int[][] arr)
{
if (arr == null || arr.Length == 1)
return arr;

List<int[]> ret = new List<int[]>();
Dictionary<string, int> Temp = new Dictionary<string, int>();
string key = string.Empty;
for (int i = 0; i < arr.Length; i++)
{
key = string.Join("|", arr[i]);
if (Temp.ContainsKey(key))
Temp[key]++;
else
Temp[key] = 1;
}
var values = Temp.Where(value => value.Value == 1);
string[] ts;
foreach (KeyValuePair<string, int> kval in values)
{
ts = kval.Key.Split("|".ToCharArray());
ret.Add(Array.ConvertAll(ts, s=> int.Parse(s)));
}

return ret.ToArray();
}

- Anonymous July 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[][] FindUniqueRows(int[][] arr)
        {
            if (arr == null || arr.Length == 1)
                return arr;

            List<int[]> ret = new List<int[]>();
            Dictionary<string, int> Temp = new Dictionary<string, int>();
            string key = string.Empty;
            for (int i = 0; i < arr.Length; i++)
            {
                key = string.Join("|", arr[i]);
                if (Temp.ContainsKey(key))
                    Temp[key]++;
                else
                    Temp[key] = 1;
            }
            var values = Temp.Where(value => value.Value == 1);
            string[] ts;
            foreach (KeyValuePair<string, int> kval in values)
            {
                ts = kval.Key.Split("|".ToCharArray());
                ret.Add(Array.ConvertAll(ts, s=> int.Parse(s)));
            }

            return ret.ToArray();
        }

- Victor Liu July 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution is impossible since you need O(n*m) simply to read data.

- Anonymous July 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

java Arrays is your friend

static class Row {
    Object[] internalRow;  

    Row(Object[] row) {
       this.internalRow = row;
    }

    public boolean equals( Object obj ) {
        if ( ! obj instanceof Row ) return false;
        Row other = (Row)obj;      
        return Arrays.deepEquals(this.internalRow, other.internalRow );
    }

    public  int hashCode() {
        return Arrays.deepHashCode(this.internalRow);
    }

    public String toString() {
        return Arrays.toString(this.internalRow);
    }
}

void printUniqueRows ( Object[][] matrix ) {
   Set<Row> s = new HashSet<Row>();
   for ( int i = 0; i < maxtrix.length; ++i ) {
       Object[] row = matrix[i];
       s.add( new Row(row) );
   }

   for ( Row r: s ) {
        System.err.println(r.toString());
   }    
}

- stephenpince July 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;


public class AmazonUniqueRows {
	
	Node[] buckets = new Node[2];
	int numberBuckets, size;

	private static class Node {
		
		int value;
		int key;
		Node next = null;
		
		public Node (int value, int key){
			this.key = key;
			this.value = value;
			
		}
		
	}
	
	public void add (int key, int value ){
		
		int indexHash = hash( key);
		Node node = buckets[indexHash];
		Node newNode = new Node(value, key);
		
		if (node == null){
			buckets[indexHash] = newNode;
			numberBuckets ++;
			size ++;
		}else{
			
			while (node.next!=null){
				node = node.next;
			}
			node.next = newNode;
			size ++;
		}
		
		if (numberBuckets == buckets.length){
			rehash();
		}
		
	}
	
	private void rehash() {
		
		Node[] bucketsResize = new Node[numberBuckets*2];
		int counter = 0;
		
		for (Node node:buckets ){			
			bucketsResize[counter++] =  node;			
		}
		
		buckets = bucketsResize;
		
	}

	void dump() {
		
		int[] finalMatriz = new int[size];
		int counterMatriz =0;
		
		for (int i = 0; i < numberBuckets; i++) {
			
			Node list = buckets[i];
			while (list != null) {
				finalMatriz[counterMatriz++] = list.value;
				list = list.next;
				
			}
		}
		
		System.out.println(Arrays.toString(finalMatriz));
		
	} 
	
	public int hash(int key){
		return key;
	}
	
	
	public static void main(String[] args) {
		
		process();

	}
	
	
	private static void process (){
		
		LinkedHashSet<int[]> set = new LinkedHashSet<int[]>();
		
		int[] arrayOne = new int[3];
		int[] arrayTwo = new int[3];
		int[] arrayThree = new int[4];
		int[] arrayFive = new int[2];
		
		arrayOne[0]=  1;
		arrayOne[1] = 3;
		arrayOne[2] = 4;
		
		arrayTwo[0]=  20;
		arrayTwo[1] = 12;
		arrayTwo[2] = 14;
		
		arrayThree[0]=  19;
		arrayThree[1] = 35;
		arrayThree[2] = 46;
		arrayThree[3] = 27;
		
		arrayFive[0]=  50;
		arrayFive[1] = 16;		
		
		set.add(arrayOne);
		set.add(arrayTwo);
		set.add(arrayThree);
		set.add(arrayFive);
		
		Iterator<int[]> iterator = set.iterator();
		
		int counter = 0;
		AmazonUniqueRows amazonUniqueRows = new AmazonUniqueRows();
		
		while (iterator.hasNext()){
			int[] arrayIt = iterator.next();
			
			for (int number: arrayIt){
				amazonUniqueRows.add(counter, number);
			}
			counter++;
		}
		
		amazonUniqueRows.dump();
		
	}

}

- israAzul June 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I am also not sure whether it is possible in O(n)
my solution will be in O(m*n) :-

import java.util.ArrayList;
import java.util.List;

public class Test {
public static void main(String args[]){

int arr[][]= {{10,11,12},{1,7,9},{11,12,12},{13,13,13}};
for (int i = 0; i < arr.length; i++) {
if(subArray(arr[i])){
for (int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + " ");
}
}

System.out.println();
}
}


public static boolean subArray(int arr[]){
boolean unique = true;
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++) {
if(list.contains(arr[i])){
return false;
}else {
list.add(arr[i]);
}
}
return unique;
}
}

- Infinite Possibilities July 13, 2015 | 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