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

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()

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

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 ?

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

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.

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

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

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

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

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

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

return ret.ToArray();
}

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

return ret.ToArray();
}``````

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.

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

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

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

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

``````package test;

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

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 (){

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;

Iterator<int[]> iterator = set.iterator();

int counter = 0;
AmazonUniqueRows amazonUniqueRows = new AmazonUniqueRows();

while (iterator.hasNext()){
int[] arrayIt = iterator.next();

for (int number: arrayIt){
}
counter++;
}

amazonUniqueRows.dump();

}

}``````

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 {
}
}
return unique;
}
}

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.

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