BigCommerce

  www.bigcommerce.com
  www.bigcommerce.com

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 Question, Sign In with Facebook or Sign Up