BigCommerce Interview Question: Given an array of integers to... | Glassdoor

Interview Question

Senior Software Developer Interview Sydney (Australia)

Given an array of integers too large to fit into memory

 , identify duplicates. The memory constraint was continuously tightened as possible solutions were suggested.
Answer

Interview Answer

1 Answer

0

My first solution was to use a sequential search - O(1) space and O(n^2) time.

My second solution was to use a bitmap index, assuming we could allocate enough words to represent the entire range of integers as sequential bits - O(n) worst case time.

Other possible solutions included doing an on disk bucket sort using in place quicksort (or mergesort) as the sub-sort.

Interview Candidate on Jul 18, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.