How would you implement a sparse array (key could be any integer,
but only a few would be used) with limited memory.

Question

How would you implement a sparse array (key could be any integer,
but only a few would be used) with limited memory.

New Graduate · Accepted Answer

A hash table.

A linked list is possible but random access isn't efficient

Anonymous · Answer

need to support efficient sequential read as well. b-tree

Tom · Answer

Hash table

Adrian · Answer

Assuming sparse means many values are zero:
have 2 arrays: one to store non-zero indexes, the other to store the values at the non-zero index. If queried number is not in the index set, return 0.

Amazon

Amazon interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches