akirademoss/CTCI

Cracking the Coding Interview Solutions

I've chosen to most thoroughly review and internalize chapters 1, 2, 3, 4, 8, and 10 of the book Cracking the Coding Interview. This document contains my solutions for strategically chosen problems from the book Cracking the Coding Interview. Contents of this file include the output of my main method tests for each of my solutions. This will evolve as I study more problems, review, revisit and optimize previous solutions.

Chapter 1: Arrays and Strings

Question 1.) Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures.

Question 2.) Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

Question 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 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.)

Question 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 edit (or zero edits) away.

Question 7.) Rotate Matrix: Given an image represented by an MxN 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?

Chapter 2: Linked Lists

Question 1.) Remove Dups: Write code to remove duplicates from an unsorted linked list.

Question 2.) Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.

Question 3.) Delete Middle Node: Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.

Chapter 3: Stacks and Queues

Question 1.) Three in One: Describe how you could use a single array to implement three stacks.

Question 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 0(1) time.

Question 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. SetO-fStacks 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 performs a pop operation on a specific sub-stack.

Chapter 4: Trees and Graphs

Question 1.)

Chapter 8: Recursion and Dynamic Programming

Question 1.)

Chapter 10: Sorting and Searching

Question 1.)