Cracking The Coding Interview
Review Problems Examples & Solutions
Overview:
Cracking the coding interview is a book written by Gayle Laakmann Mcdowell, an engineer that has worked at companies like Google, Microsoft, and Apple. She holds a B.S. and M.S. in Engineering. The book has 189 programming questions ranging from the most basic of algorithms to the most trickiest.
Problem #1:
Implement an algorithm to determine if a string has all unique characters ?
You can find the code to my first solution to the problem, which ran in O(n²) time on my GitHub.
/*
This program implements an algorithm to determine if a string has all unique characters
*/#include<stdio.h>
#include<string.h>int main(){
char array[]= {"abcdefghijklmnopqrstuvwxyz"}; // Array of characters
int len = strlen(array); // the length of the array
int isUnique = 1; // Setting isUnique to true
//This is the algorithm that will determine if our array is unique
int i,j;
for(i=0; i<len; i++){
for(j=0; j<len; j++){
//Checking if the indexes are different if they are then we will compare the element at position i with the element at position j
if(i != j){
// Comparing elements in the array with other elements in the array if these are equal then the array of characters are not unique
if(array[i] == array[j]){
isUnique = 0; // Updating isUnique variable to be equal to 0 to represent false
}
}
}
}
if(isUnique == 1){
printf("All of the characters are unique. \n");
}
else
printf("All of the characters are NOT unique. \n");
return 0;
}
Solving the problem is one thing, but solving a problem as efficiently as possible is another. The solution was an O(n²) solution, but there is a better solution. A solution that runs O(n) time below. You can find this code on my GitHub.
/*
Description: implement an algorithm to determine if a string has all unique characters
*///Library
#include<stdio.h>
#include<string.h> //contains the strlen()//Declare Function
int isUniqueChars(char *string);int main(){
//Create a string, size 256 assuming the char set is ASCII, if not we can just increase the size
char string[128] = “helo”;
int isUnique = isUniqueChars(string); //Set this equal to the function that will return a value if the string is unique (1) or not (0)
if(isUnique == 1)
printf(“The string is unique\n”);
else
printf(“The string is NOT unique\n”);
return 0;
}/*
isUniqueChars() function returns 0 if the string is not unique and returns 1 if it is
This function runs O(n) time.
*/
int isUniqueChars(char *string){
int i;
int char_set[128]={0}; //Initializing all elements or numbers in the array to 0,
int len = strlen(string); //Assuming strlen runs O(n) times, we initialize len here so that we dont keep calling the function in the loop.
int val;// Declare val which will hold the ASCII value/number of the character
for(i=0; i<len; i++){
val = (int)string[i];
if(char_set[val] !=0)
return 0;
//Marking the element
char_set[val] = 1;
}
return 1; //This returns 1 if the string is unique
}
The above algorithm/C-program takes two arrays one that consists of characters (your String that we will be checking to see if it has all unique characters) and another array that consists of integers that has the size of the ASCII table. The second array, we will call array ‘B’. It is the key to making this program run O(n) time. Array B size is again equal to the size of the ASCII table, so this means that every possible character you can type on the keyboard can have it’s own unique position in the array for example the element at position 0 of Array B could be ‘a’(B[0] = ‘a’) and there will be no other element ‘a’ in array B, so we can only find ‘a’ at position 0.
By initializing the array B to be all values of 0, we can assume that we have not visited our unique value/element . Only after we see a character do we mark that character at it’s unique position in the B array to a value other than 0 such as 1 to indicate that we saw it in our string, for example B[‘a’] = 1. Note: Everything in the computer is a number even characters so ‘a’ = 97 in ASCII so we are saying B[97] = 1 if ‘a’ is in our string if ‘b’ was in our string the B[‘b’] → B[98] = 1. Now if we see another ‘a’ in our string, we can check to see if we already found it by asking if B[‘a’] = 1 if it does equal 1 then we already saw this letter in our string, and therefore our string is not unique, if B[‘a’] = 0 then we never saw that value before and so we can now set it to 1 to say we saw a for the first time. Below is a video of the solution in O(n) time.
The book Cracking the Coding Interview is a great book for coders, programmers, computer scientists, and software engineers, especially when trying to get a job. Even if you are not trying to get a job it has fun practice problems that will help you to think outside the box, and possibly write better more efficient code. If you don’t decide to buy the book at least rent it from your local library, you won’t be disappointed.
Check Out the following for more content / videos on Algorithm Analysis and Programming:
YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ
compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA
Website:
http://everythingcomputerscience.com/
Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/
Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/
GitHub:
https://github.com/randerson112358
Twitter:
https://twitter.com/CsEverything
Resources:
Cracking the Coding Interview
