CareerCup

use hash table

use hash table....
if the is no collision no repeated char ...

i have a doubt..
using hashtable, how do we get to know the first element of the array to be non repeating?
eg, array- e e a i r a
in hash table we have it as-
a-a
e-e
i
r
ans shud be 'e'. but we have 'a' in the hash table..

i have a doubt..
using hashtable, how do we get to know the first element of the array to be non repeating?
eg, array- e e a i r a
in hash table we have it as-
a-a
e-e
i
r
ans shud be 'e'. but we have 'a' in the hash table..

linked list seems to be one option....but the complexity is bad...

Sorting is one option too :)

One more solution ...
Assume all letters ... use hash of 26 locations initial all locations as zero
1. Scan the array,
if(hashArray[arr[i]-65]==0)
hashArray[arr[i]-65] = i;
else
hashArray[arr[i]-65] = -1 ;
2. Scan the hasharray and find the min amongst elements excluding 0 and -1. say min
3. print arr[min]

Basically this logic can be expanded furthur to other range of characters just that the hash array to search will be bigger

One more solution ...
Assume all letters ... use hash of 26 locations initial all locations as zero
1. Scan the array,
if(hashArray[arr[i]-65]==0)
hashArray[arr[i]-65] = i;
else
hashArray[arr[i]-65] = -1 ;
2. Scan the hasharray and find the min amongst elements excluding 0 and -1. say min
3. print arr[min]

Basically this logic can be expanded furthur to other range of characters just that the hash array to search will be bigger

(1) use an array of 256 length and initialized to 0
(2) increment respective position in the array related to that char
(3) iterate thro string and find the first 0-values position in the array, the char correspoding to that location is the required answer

Use a bitHash . use a bool vector . initialise it with zero . for every char found we toggle that bit . If in course of iteration we are trying to switch a bit off , we have found the char .
t.c -O(n)
s.c- very less : 256 bits or 8 int instead of 256 int arr.

Here's Python:

def first_non_rep(array):
    INF = len(array)
    if not INF:
        return None
    tbl = {}
    for i, c in enumerate(array):
        tbl[c] = INF if c in tbl else i
    min_c = min(tbl[c] for c in tbl)
    if min_c == INF:
        return None
    return array[min_c]

print(first_non_rep('abracadabra'))

xor