## Amazon Interview Question

Team: Machine Learning
Country: India
Interview Type: Phone Interview

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

I'm assuming sparse means most of the matrix is full of 0s, and of the nonzero elements, a tiny fraction are positive.

I would augment the matrix with another data structure to hold the set of all negative values elements (if position in matrix matters, keep track of that too).
A nice data structure might be a hashSet keyed on the (i,j) position of the negative number in matrix.

Amortize the cost of keeping the extra data structure up to date by updating it during each insert/delete/modify in the matrix. So all these operations can clearly be kept at O(1) average ( assuming well designed hash table).

Now the query to return all negative elements is O(numNegativeElements)... just return the keys in hash table. I think this is optimal.

IF we aren't allowed to augment, I'd tell the interviewer to enlighten me...

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

I'm assuming sparse means most of the matrix is full of 0s, and of the nonzero elements, a tiny fraction are positive.

I would augment the matrix with another data structure to hold the set of all negative values elements (if position in matrix matters, keep track of that too).
A nice data structure might be a hashSet keyed on the (i,j) position of the negative number in matrix.

Amortize the cost of keeping the extra data structure up to date by updating it during each insert/delete/modify in the matrix. So all these operations can clearly be kept at O(1) average ( assuming well designed hash table).

Now the query to return all negative elements is O(numNegativeElements)... just return the keys in hash table. I think this is optimal.

IF we aren't allowed to augment, I'd tell the interviewer to enlighten me...

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

it just clicked that may be the interviewer was expecting me to just talk about hashing used in databases

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

simple,hint has been given in question,maintain sparse tree store blocks that is zero at the end maintain link of next list of block with zero value blocks,such structure called a free list.

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

Can you explain or give a link to refer

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.