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

Sigiloso · 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

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas