-
Notifications
You must be signed in to change notification settings - Fork 13
Home
These are my solutions to the Cracking the Coding Interview 6th edition by Gayle Laakmann McDowell. The solutions are in C# and there are test cases provided as well. There are also a few other misc questions that I found/answered along the way that aren't in the book.
Chapter 1: Arrays and Strings
Chapter 2: Linked Lists
Chapter 3: Stacks and Queues
Chapter 4: Trees and Graphs
Chapter 5: Bit Manipulation
Chapter 6: Math and Logic Puzzles
Chapter 7: Object-Oriented Design
Chapter 8: Recursion and Dynamic Programming
Chapter 9: System Design and Scalability
Chapter 10: Sorting and Searching
Chapter 11: Testing
Chapter 12: C and C++
Chapter 13: Java
Chapter 14: Databases
Chapter 15: Threads and Locks
Chapter 16: Moderate
Chapter 17: Hard
1.1 Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
1.2 Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.
1.3 URLify: Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in java, please use a character array so that you can perform this operation in place.) EXAMPLE Input: "Mr John Smith " Output: "Mr%20John%20Smith"
1.4 Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words. EXAMPLE Input: Tact Coa Output: True (permutations: "taco cat", "atco cta", etc.)
1.5 One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one dit (or zero edits) away. EXAMPLE pale, ple -> true pales, pale -> true pale, bale -> true pale, bake -> false
1.6 String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.
1.7 Rotate Matrix: 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?
1.8 Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.
1.9 String Rotation: 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 s2 is a rotation of s1 using only one call to isSubstring (e.g.,"waterbottle" is a rotation of "erbottlewat").
2.1 Remove Dups: Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?
2.2 Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.
2.3 Delete Middle Node: Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node. EXAMPLE Input: the node c from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e
2.4 Partition: Write code to parition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.
2.5 Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits 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 numbers and returns the sum as a linked list. EXAMPLE Input: (7 -> 1 -> 6) + (5 -> 9 -> 2). that is, 617 + 295. Output: 2 -> 1 -> 9. That is, 912. FOLLOW UP Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is 617 + 295. Output: 9 -> 1 -> 2. That is, 912.
2.6 Palindrome: Implement a funciton to check if a linked lits is a palindrome.
2.7 Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return th eintersection node. Node that the intersection is defined based on reference, not value. That is if the kth node of the first linked list is exactly the same node (by reference) as the jth node of the second linked list, then they are intersecting.
2.8 Loop Detection: Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE Input: A -> B -> C -> D -> E -> C [the same C as earlier] Output: C
3.1 Three in One: Describe how you could use a single array to implement three stacks.
3.2 Stack Min: How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop, and min should all operate in O(1) time.
3.3 Stack of Plates: Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack). FOLLOW UP Implement a function popAt(int index) which performans a pop operation on a specific sub-stack.
3.4 Queue via Stacks: Implement a MyQueue class which implements a queue using two stacks.
3.5 Sort Stack: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.
3.6 Animal Shelter: An animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the built-in LinkedList data structure.