I found this problem in ‘Cracking the Code Interview’ book. It’s actually the first problem given (1.1) in the book. It is a pretty common question asked in interviews. The problem is about writing a function that returns true if all characters in string are unique, and false otherwise. There is actually a lot more to it that it may look like first. I implemented a few solutions in C.
#define FALSE 0 #define TRUE 1 /* implement function that returns true is all characters in a string are unique, and false otherwise */ // time O(n^2). No extra space needed int uniqueCharac1(char *ptr1) { char *ptr2; while (*ptr1++ != '\0') { ptr2 = ptr1; while (*ptr2++ != '\0') { if (*ptr2 == *ptr1) { printf("Letter %c repeated\n", *ptr2); return FALSE; } } } return TRUE; } //time O(n). Extra space O(1). Using bitmap int uniqueCharac2(char *ptr) { unsigned int bit_field = 0x0; // needs 27 bits (one bit per letter). // int gives 4 bytes (32 bits) int character; while (*ptr++ != '\0') { character = *ptr - 'a' + 1; // 'a' is 1 //printf("Letter %c is number %d\n", *ptr, character); // checking if bit set if (bit_field && (1<<character)) { printf("Letter %c repeated\n", *ptr); return FALSE; } // setting bit bit_field |= (1<<character); } return TRUE; } char * quicksort(char *string) { // TO DO return string; } int binarysearch(char *string, char letter) { // TO DO return TRUE; } //time O(n*log n). No extra space needed. Using quicksort int uniqueCharac3(char *ptr) { char *sorted = quicksort(ptr); while (*ptr++ != '') { if (binarysearch(ptr + 1, *ptr)) { printf("Letter %c repeated\n", *ptr); return TRUE; } } return FALSE; } int main(int argc, char **argv){ char string[] = "asdfqwersdfga"; if (uniqueCharac1(string)) {printf("Characters in %s are unique\n", string); } if (uniqueCharac2(string)) {printf("Characters in %s are unique\n", string); } }