CareerCup

I assumed all characters are ASCII, and then I created a bool array of 200, reading one character at a time and then marking the corresponding ASCII (numeric) value as true every time I encounter a character. When I see a character and its value in bool array has already been set to true, then I returned 'duplicate' otherwise 'correct'

For the second part, I said that since we know the upper limit of string length, we can follow the O(n^2) approach (check each character by all other characters). We will be repeating the loop at most 400 times (20x20). The interviewer, I guess, was not impressed

Actually, the second part depends a lot on what you answered for part a. I think the best solution so far is the bitmap one as described by babbupandey.

You can use a hash to store each char. If a char is already in the hash, it contains a duplicate.

If you are allowed to modify the string you can sort it and then search for two adjacent characters being the same char.

For part B - what do you mean by 20 chars? Length of string is not greater than 20 or there are 20 different letters in the string? You can use an array of size 20 or an int (right-most 20 bits of it to be more precise).

Code to follow :)

I think if we keep arranging the ASCII values in Binary Search Tree as we parse the string. So if the ASCII values matches with any node than its a duplicate or else we insert the ASCII value in BST. This will take maximum time as O(height of tree)

sort the array & take two char variable previous & current if at any time prev =current return as repeated element....Time complexity O(nlogn) Space constant

bool find_dup(char *s)
{
int len = strlen(s);
bool hash[256] = {false};
for (int i =0; i<len; i++)
{
if (!hash[s[i]])
hash[s[i]] = true;
else
return true;
}
return false;
}

Sort using merge sort with complexity O(nlogn) and then traverse the string by comparing adjacent chars if they equal string contains at least one char repeated..

We can reduce the array size to 52 if the string strictly contains only alphabets,
array[52];
eg: if the string is 'abCd'
take a variable as int like int k;
then k=string[0]-'a';
then array[k]++;
if array[k] is already more than zero then it means the character k is being repeated,
for C
k= string[2]-'A'+26;
then array[k]++;

you can use an array of size 256 (for ASCII)like int arr[256]

int arr[256],a;
for(int i=0;i<strlen(str);i++)
{
a=str[i];
if(arr[a]!=0)
arr[a]++;//if that character is appearing for first time
else
return 0;//already seen character
}

correction:
replace if(arr[a]!=0) with if(arr[a]==0)