####Cracking The Coding Interview
An attempt to solve each and every question of Cracking the Coding Interview by Gayle Laakmann McDowell.
Started on 4th Jan, 14
####Arrays
1.1. Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures.
1.2. Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string.
1.3. Given two string, write a method to decide if one id the permutation of the other.
1.4. Write a method to replace all the spaces in a string with %20.
1.5. Implement a method to perform basic string compression using the counts of repeated characters. For example: the string aabccccaa would become a2b1c4a2. If the compressed string would not become smaller than the original string, then return original string.
1.6. Given an image represented by an NXN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? Not Done
1.7. Write an algorithm such that if an element in an MXN matrix is zero, its entire row and column is set to 0.
1.8. Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s1 is a rotation of s1 using only one call to isSubstring (e.g. "waterbottle" is a rotation of "erbottlewat")
####LinkedList
2.1. Remove duplicates from an unsorted linked list.
2.2. Implement an algorithm to find the kth to the last element of a singly linked list.
2.3. Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
2.4. Write a code to partition a linkedlist around a value of x, such that all nodes less than x come before all nodes greater or equal to x.
2.5. You have two numbers representated by a linked list, where each node contains a single digit. The digit are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two number and returns the sum as a linked list.
####Misc
Linked List practice questions.
####List of interview questions that I plan to do in future:
Linked List:
Given a linked list like a1-a2-a3-a4-b1-b2-b3-b4. Convert it into a1-b1-a2-b2-a3-b3-a4-b4.
Trees and Graph:
Program to convert a binary search tree into doubly linked list.
Dynamic Programming:
Given a MXN matrix. To find the number of ways to reach the mth row and nth column cell from 0,0 cell. Find the same if some of the cells are marked as not reachable.
First implemented using recursion then through dynamic programming.
Misc:
Given a sentence. Find all the characters which are repeated more than 1 time and print them in lexicographical order.
Program to sort m sorted arrays.
Given two sorted arrays. Find the median of the combined array.