Amazon Interview Question
Software EngineersCountry: India
Interview Type: Written Test
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()
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 ?
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.
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...
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);
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();
}
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();
}
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());
}
}
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();
}
}
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;
}
}
Use a Trie.
- ram.prasad.prabu July 14, 2015Time : 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.