Find the first element that occurs only once

Question

This was a Google interview puzzle.

The problem is to find the first element in an array that occurs only once.

For example, abaaacdgadgf is given. We need to output b.

The simple solution seems to be to first count every element using a hashtable, and then loop through again to get the first element. It will use 2 loops.

Is it possible to get the result only use 1 loop?

I tried to figure it out, but it seems impossible.

Answer 1

The hash table points to items in a linked list. When adding an item the hashtable entry is created and the pointer added to the tail of the list. When a duplicate is found then the item can be removed from the list.

The first element to occur only once will be the first item in the list.

This code is a little untidy because most of the code is linked list implementation.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct stLISTITEM
{
    char data;
    struct stLISTITEM* previous;
    struct stLISTITEM* next;
} LISTITEM;

char firstCharThatOccursOnce(const char* s) {
    char ret;
    LISTITEM* head;
    LISTITEM* tail;
    LISTITEM* table[CHAR_MAX + 1] = {NULL}; /* Just pretend this is a hash table please */
    LISTITEM* cur;
    int i;

    head = malloc(sizeof(*head));
    tail = malloc(sizeof(*tail));

    head->next = tail;
    tail->previous = head;
    tail->data = '\0'; /* If all characters are repeated then return NULL character */

    for (; *s; s++) {
        cur = table[*s];

        if (cur == NULL) {
            /* Item hasn't been seen before */

            cur = malloc(sizeof(*cur));
            cur->data = *s;

            /* Add it to the end of the list */
            tail->previous->next = cur;
            cur->previous = tail->previous;
            tail->previous = cur;
            cur->next = tail;

            /* Add it to the table */
            table[*s] = cur;
        }
        else if (cur->next == NULL) {
            /* Seen it before, but already removed */
        }
        else {
            /* Seen it before, remove from list */
            cur->previous->next = cur->next;
            cur->next->previous = cur->previous;

            cur->next = NULL;
            cur->previous = NULL;
        }
    }

    ret = head->next->data;

    for (i = 0; i <= CHAR_MAX; i++) {
        free(table[i]);
    }

    free(head);
    free(tail);

    return ret;
}

int main(int argc, char const *argv[])
{
    char result = firstCharThatOccursOnce("abaaacdgadgf");

    printf("'%c' (%i)\n", result, result);

    return 0;
}

Answer 2

Here my solution:

Each 'char' has 4 stats possible:

• 1 : never seen.
• 2 : seen one
• 3 : eliminated because of multi occurence.
• 4 : qualified

I create an array of size 26(for each 'char') for storing stats of chars Qualified elements are put at the end of dual linked list.

Scan the input data and do all the update as necessary. Then scan the list from begin to end. The first non 'eliminated (state 3)' is your answser.

complexity : n+(26x3) where n = length(dataset)

Answer 3

Yes. In the hashtable, instead of maintaining counts, maintain the first index where the element was encountered. Also maintain a sorted set of all unique-so-far elements, keyed on that index. Afterwards, just look for the minimal key remaining in the sorted set.

encountered = dict()
unique = sorted_set()

for i in range(len(A)):
    elem = A[i]
    if elem in encountered:
        first_index = encountered[elem]
        del unique[first_index]
    else:
        unique[i] = elem
        encountered[elem] = i

min_index = unique.keys()[0]
first_unique_elem = A[min_index]

Answer 4

I haven't read the other answers simply because I want to give it a go myself.
Let's iteratively improve our solution.
Our analysis in terms of time and space complexity will require us to state a few things clearly at first:
Let

N = length of string 
M = numbers of characters in alphabet

Brute force algorithm is to traverse the string and for each element of string we search to its right to see if it has a duplicate.
Time Complexity:O(N²)
Space Complexity:O(1)

Can we do better?
Sure, we can traverse the string and make count of many times a character appears.Make another traversal through the string to find the first character that has count 1.
Time Complexity:O(N+M)
Space Complexity:O(M)

Why is this O(N+M)?
Because we need to initialize the elements of the count array to 0 first.So even if input is "a", we need to initialize the count array for M elements.

Can we do better?
First let's state to the interviewer that this task is Omega(N), simply because we have to see each element of the string atleast once.Realize this by seeing a input instance of "aaaaaaz"
So we are not aiming to better our time complexity, simply making the actual running time better by doing just one traversal through the string.
This is indeed possible.

for(int i=0;i<N;i++)
{
  if(visited[i]==-2)continue;
  if(visited[i]==-1)visited[i]=i;continue;
  visited[i]=-1;
}
int F=N;
char res=' ';
for(int i=0;i<M;i++)
{
  if(visited[i]>=0)
  {
    F=min(F,visited[i]);
    res=A[visited[i]];
  }
}
return res;

Time Complexity:O(N+M)
Space Complexity: O(M)

Can we do better?

Can we do this in O(N) perhaps?
I'm still thinking of a way to do this in true O(N).IF I hit upon a solution, I will update this answer.

Answer 5

Instead of a hash table you may use a trie. If input data conspire against your hash function, a hashtable will get you quadratic performance. The trie is immune to that.

As for another loop, I would not worry about it too much. It's the same complexity asymptotically. Whatever you win by eliminating the loop, you are likely to lose in increased complexity of the rest of the code.