Find the first element that occurs only once [duplicate]

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;
}