More array problems

Today I summarize some array problems that an be solved using hash tables.

Remove duplicates in an array.

Before starting with this question, we should ask the interviewer what`s the type of elements in the array. If the answer is character, well, the only thing we need is a boolean array of size 256 (assuming the charset is ASCII). If the answer is integer or other larger types, we should use a hash table.

We solve this question using two indecies, reader and writer. We iterate each element using reader and find its existence in hash table. If it does not exist, we insert an entry in hash table, copy the value indexed by reader to that of writer, and increment both indecies. Otherwise, we increment only the reader index.

This solution costs O(n) time and O(n) space. If extra space is not allowed, we can use any in-place sorting algorithm (e.g. quick sort) to sort the array and then use similar reader and writer technique to remove duplicates. This will cost O(nlogn) time and O(1) space.

Decide if two strings are anagrams.

If number of each character in two strings are the same, then they are anagrams. We can scan the first string and increment the number of occurence of each character using a hash table. Then we scan the second string, decrementing the counter of each encountered character. In the end, if all the entries in the hash table are zero, then the two strings are anagrams.

Another extremely simple solution is to sort two strings and compare if there are equal.

Find the intersection of two arrays.

We assume that there is no duplicate in each array. We scan the first array and mark the occurence of each element. Then we scan the second array and find if each element can be found in hash table. If so, we append it to the result.

Given a number N, find pairs of number a1, a2 in an array such that a1 + a2 = N.

We will scan the array for two passes. In the first pass, we calculate N - a1, where a1 is each element. We insert it into hash table which key is N - a1 and value is a1`s index. Then in the second pass, we use N - a2, where a2 is each element, to find the target index using the hash table.