Yahoo Interview Question
Testing / Quality Assurances#include<stdio.h>
char nrc(char *s)
{
int flag;
char *p;
while(*s)
{
flag=0;
p=s;
p++;
if(*s!='#')
{
while(*p)
{
if(*s==*p)
{
*p='#';
flag=1;
}
p++;
}
if (flag==0)
return *s;
}
s++;
}
}
int main()
{
char str[]="teeter";
char j=nrc(str);
printf("first non repeated character is %c\n",j);
return 0;
}
The above algorithm is O(N^2). This can be done in O(N) time and O(1) space.
char nrc(char *s) {
int hashTable[256];
int i;
char *tmp;
if (s == NULL) { return '\0';}
for (i = 0; i < 256; i++) { hashTable[i] = 0;}
tmp = s;
while (tmp != NULL) {
hashTable[*tmp]++;
tmp++;
}
for (i = 0; i < 256; i++) {
if (hashTable[i] == 1) {
return (char)i;
}
}
return '\0';
}
it can be further improved by checking the number to see if it is already > 0 during the first scan and hashing
char nrc(char *s) {
int hashTable[256];
int i;
char *tmp;
if (s == NULL) { return '\0';}
for (i = 0; i < 256; i++) { hashTable[i] = 0;}
tmp = s;
while (tmp != NULL) {
hashTable[(int)*tmp]++;
tmp++;
}
for (i = 0; i < 256; i++) {
if (hashTable[i] == 1) {
return (char)i;
}
}
return '\0';
}
here`s my 2 penny.
Keep an array of structs(index 0-256);
struct st
{
int age;
int count;
}
keep a global variable that increments for every character parsed and put that as the age for the corresponding char.
finally go thru the array and print the element with the count=1 and least age.
T: Unfortunally your solution returns the non-repetitive char with the loweest ASCII number, Not the FIRST non-repetitive char.
For example: dbdcaecdf
Your method would return 'a', not 'b'.
Because:
for (i = 0; i < 256; i++) {
if (hashTable[i] == 1)
{ return (char)i; }
}
char Non_rep(const string& str)
{
if (str==null) return 1;
typedef string::const_iterator striter;
striter it= str.begin();
map<char, int> counter;
while (it!= str.end())
{
++counter[*it];
++it;
}
for (map<char, int>::const_iterator mapiter=counter.begin(); mapiter!=counter.end(); ++mapiter)
{
if (mapiter->second==1)
return mapiter->first;
}
cout<<"all dup"<<endl;
};
Let the number of elements be n, assuming case insensitive problem.
O(n) time to hash it on the hash table.
O(26) to find the first slot with minimum index non-negative value.
- Stores the index on the hash table
- Set the hash table value to -1 on collision
Three types of Hash values
a. -2 , Initial value, implies no hashed value on this index.
b. -1 , more than 2 occurrences found.
c. Index, which implies a single occurrence so far.
Improvinf T's orignal code and taking other's comment
char Nrc (char *str)
{
int HashTable[256] = {0}; //initialize array with zero
char *tmp = NULL;
// if the string is empty or parameter is NULL, return not found
if(!str || !*str)
return 0;
tmp = str;
while(*tmp)
HashTable[*tmp++]++;
tmp = str;
while(NULL != *tmp && 1 =! HashTable[*tmp])
tmp++;
return *tmp; // Would take care of found/not found (returning the last char-NULL)
}
If your code has "silly bug", it may not be hard to correct it. If your ALGORITHM has a "silly" or "non-silly" bug, it is a disaster! It means your ALGORITHM worths nothing, zero, zip! Asumming it does cause problem.
Here is a algorithm. Assuming we are dealing with on a, b, c, d, and e five characters.
Also assuming we are dealing with long strings: dddcdd
1. Exam first six chars "dddcdd", so we have at least one repeat char(d). If we find one non-repeat on, say 'c', we store it in non-repeat candidate pair array NP(char, index), So, we have NP(0) = ('c', 4). We also store d in RP array: RP(0) = 'd'.
2. Get next................. ++++
If your code has "silly bug", it may not be hard to correct it. If your ALGORITHM has a "silly" or "non-silly" bug, it is a disaster! It means your ALGORITHM worths nothing, zero, zip! Asumming it does cause problem.
Here is a algorithm. Assuming we are dealing with on a, b, c, d, and e five characters.
Also assuming we are dealing with long strings: dddcdd
1. Exam first six chars "dddcdd", so we have at least one repeat char(d). If we find one non-repeat on, say 'c', we store it in non-repeat candidate pair array NP(char, index), So, we have NP(0) = ('c', 4). We also store d in RP array: RP(0) = 'd'.
2. Get next................. ++++
Searching the hash table for count=1 would find a nonrepeated character, but it wouldn’t necessarily be the first one in the original string.
Therefore, you need to search your count values in the order of the characters in the original string. Just look up the count value for each character until you find a 1. When you find a 1, you’ve located the first nonrepeated character and you break from the algorithm.
In the worst case, we might have to look up the count value for each character in the string to find the first nonrepeated character. Hash/Array lookup is O(1), the worst case would be two operations for each character in the string, giving 2n, which is still O(n).
char * FindFirstNonRepeat(char *s){
char * tmp = *s;
char a[256] = {0};
while(!s){
a[*s]++;
s++;
}
While(!tmp){
If(a[*tmp]==1) return *tmp
Tmp++;
}
Return -1;
}
How about implementing it using priority search tree? The operation to find the first non-repetitive character would correspond to
minXinRectangle(0, strlen(input_str)-1, 1)
in that case the complexity would be O(log n).
If you insist on O(n), then a much convoluted way of doing this would be to create 2 data structures - 1. hash table indexed by ascii which contains count; 2. a temporary array storing the unique characters(not necessarily non-repetitive) in the order they show up. Then what we do is
void find_and_print_first_non_repetitive_char(char s[])
{
int* temp = (int*) malloc(strlen(s) * sizeof(int));
int table[256];
int j = 0;
for (int i = 0;i < strlen(s);i++)
{
char c = s[i];
if (table[c] == 0)
{
temp[j++] = (int)c;
table[c]++;
}
}
for (int i = 0;i < j;i++)
{
if (temp[i] == 1)
{
printf("first non-repetitive character: %c\n", temp[i]);
}
}
}
Java implementation using LinkedHashMap.
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstNonRepetetive {
public static void main(String[] args) {
String s = "teeterra";
System.out.println("FirstNonRepetetive:"
+ getFirstNonRepetetiveCharacter(s));
}
private static char getFirstNonRepetetiveCharacter(String string) {
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
char c;
for (int i = 0; i < string.length(); i++) {
c = string.charAt(i);
if (map.get(c) == null) {
map.put(c, 1);
} else {
map.put(c, map.get(c) + 1);
}
}
Iterator<Character> keys = map.keySet().iterator();
char key = 0;
boolean found = false;
while (keys.hasNext()) {
key = keys.next();
if (map.get(key) == 1) {
found = true;
break;
}
}
if (found) {
return key;
} else {
return 0;
}
}
}
Improvinf T's orignal code and taking other's comment
- ujjwal May 02, 2009