Interview Cake

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

Your company delivers breakfast via autonomous quadcopter drones. And something mysterious has happened.

Each breakfast delivery is assigned a unique ID, a positive integer. When one of the company's 100 drones takes off with a delivery, the delivery's ID is added to an array, deliveryIdConfirmations. When the drone comes back and lands, the ID is again added to the same array.

After breakfast this morning there were only 99 drones on the tarmac. One of the drones never made it back from a delivery. We suspect a secret agent from Amazon placed an order and stole one of our patented drones. To track them down, we need to find their delivery ID.

Given the array of IDs, which contains many duplicate integers and one unique integer, find the unique integer.

The IDs are not guaranteed to be sorted or sequential. Orders aren't always fulfilled in the order they were received, and some deliveries get cancelled before takeoff.

We can do this in time.

No matter how many integers are in our input array, we can always find the unique ID in space!

A brute force approach would use two nested loops to go through every ID and check every other ID to see if there's a duplicate.

This would take time and space. Can we bring that runtime down?

Well, we know every integer appears twice, except for one integer, which appears once. Can we just track how many times each integer appears?

We could iterate through the array and store each integer in a hash table, where the keys are the integers and the values are the number of times we’ve seen that integer so far. At the end, we’d just need to return the integer we saw one time.

// Assume we've already implemented a hash table // that maps string keys to values typedef struct HashTable HashTable; HashTable * hashTableNew(void); void hashTableFree(HashTable *hashTable); int hashTableInsert(HashTable *hashTable, const char *key, const void *value, size_t valueSize); void * hashTableFind(const HashTable *hashTable, const char *key); // Hash table iterator type typedef struct HashTableEntry HashTableEntry; typedef HashTableEntry *HashTableIterator; // Get an iterator for iterating through all entries in the hash table HashTableIterator hashTableIterationStart(const HashTable* hashTable); // Advance the iterator to the next entry in the hash table HashTableIterator hashTableIterationNext(const HashTableIterator it); // Check that iteration has finished int hashTableIterationIsEnd(const HashTableIterator it); // Access key and value of entry pointed by iterator const char * hashTableIteratorKey(const HashTableIterator it); void * hashTableIteratorValue(const HashTableIterator it); int findUniqueDeliveryId(const int *deliveryIds, size_t size) { size_t i; HashTable *idsToOccurences; HashTableIterator it; int uniqueId = 0; idsToOccurences = hashTableNew(); for (i = 0; i < size; i++) { int *count; char key[16]; // Large enough to hold string representation of INT_MAX snprintf(key, sizeof(key), "%d", deliveryIds[i]); count = hashTableFind(idsToOccurences, key); if (count != NULL) { (*count)++; } else { int initialCount = 1; hashTableInsert(idsToOccurences, key, &initialCount, sizeof(int)); } } it = hashTableIterationStart(idsToOccurences); while (!hashTableIterationIsEnd(it)) { if (*(int *)hashTableIteratorValue(it) == 1) { uniqueId = atoi(hashTableIteratorKey(it)); break; } it = hashTableIterationNext(it); } hashTableFree(idsToOccurences); return uniqueId; }

Alright, we got our runtime down to . That's probably the best runtime we can get—to find our unique integer we’ll definitely have to look at every integer in the worst case.

But now we've added space, for our hash table. Can we bring that down?

Well, we could track whether or not we've only seen the integer once, instead of counting the number of times we've seen it. When we see an integer, we'll add it as a key in our hash table with a value of 1. If we see it again, we'll change its value to 0. At the end, our non-repeated order ID will be the one integer with a value of 1.

How much space does this save us? Not enough to bring down our space cost—we're still storing n integers. Even if each 0 and 1 only used 1 bit, that'd still be space overall.

Any other ideas?

Let’s zoom out and think about what we’re working with. The only data we have is integers. How are integers stored?

Our machine stores integers as binary numbers using bits. What if we thought about this problem on the level of individual bits?

Let's think about the bitwise operations AND, OR, XOR, NOT and bit shifts.

Is one of those operations helpful for finding our unique integer?

We’re seeing every integer twice, except one. Is there a bitwise operation that would let the second occurrence of an integer cancel out the first?

If so, we could start with a variable uniqueDeliveryId set to 0 and run some bitwise operation with that variable and each number in our array. If duplicate integers cancel each other out, then we’d only be left with the unique integer at the end!

Which bitwise operation would let us do that?

We XOR all the integers in the array. We start with a variable uniqueDeliveryId set to 0. Every time we XOR with a new ID, it will change the bits. When we XOR with the same ID again, it will cancel out the earlier change.

In the end, we'll be left with the ID that appeared once!

int findUniqueDeliveryId(const int *deliveryIds, size_t size) { size_t i; int uniqueDeliveryId = 0; for (i = 0; i < size; i++) { uniqueDeliveryId ^= deliveryIds[i]; } return uniqueDeliveryId; }

time, and space.

This problem is a useful reminder of the power we can unlock by knowing what's happening at the "bit level."

How do you know when bit manipulation might be the key to solving a problem? Here are some signs to watch out for:

  1. You want to multiply or divide by 2 (use a left shift to multiply by 2, right shift to divide by 2).
  2. You want to "cancel out" matching numbers (use XOR).

Reset editor

Powered by qualified.io

. . .