Two Amazon Interview Questions

February 26, 2016

In the previous exercise I wrote a solution that doesn’t work, so I guess I have to try again with two more Amazon interview questions:

Create a set data structure that provides the following operations, which must all operate in constant time: insert, delete, member?, and random. The random operation should return a random element from the set.

and

Given an array, find the first element that appears an even number of times.

Your task is to answer the two interview questions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

5 Responses to “Two Amazon Interview Questions”

  1. Janne said

    Hash tables are not constant time. They’re amortized O(1), which is very different – try implementing a hard-realtime system with hash tables.

  2. matthew said

    @Janne – I’d have thought it depends on the situation, if you either don’t need to resize because you know in advance the required table size or you spread the cost of resizing the table over many insertions, and if your hash function is perfect or in practice produces a good distribution, then most people would be happy calling that constant (or at least bounded) time.

    Anyway, the suggested random selection seems to be randomly selecting a (non-empty) hash table bucket, then selecting an element in that bucket – this isn’t going to produce a uniform distribution. If you are going for linked list buckets, better to allocate the list nodes from a separate array, then randomly select from that array rather than from the hash bucket array.

  3. Xin said

    Does random operate in constant time? Is not it O(n)?

  4. matthew said

    The answer given here has a nice way of making a uniform selection:

    http://stackoverflow.com/questions/8629447/efficiently-picking-a-random-element-from-a-chained-hash-table

    If there are N buckets and L is the length of the longest hash table bucket chain, first randomly choose a non-empty bucket, then choose j from 0 to L-1 (inclusive), if bucket has a jth element in its chain, return that, otherwise choose another j.

    Assuming items are spread randomly across the hash buckets, average runtime should be O(1).

  5. matthew said

    I’m getting it wrong now: that should be, if there is no jth element in the bucket, start again by choosing another bucket.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: