Cracking

Solving problems from the Cracking the Coding Interview book.

Project structure

com.xenoteo
└── chapterX
    └── questionY
        ├── Main.java
        ├── Solution.java
        └── README.md

In Solution.java the actual solution is provided, sometimes with different approaches. The main algorithmic logic is in this file.

In Main.java there are some examples of use of Solution class.

In README.md there is a description of the problem.

Note: for some problems another file structure can be provided (e.g., if more classes are required).

Problems

Arrays and Strings

• 1.1 (+tests) Is Unique
• 1.2 (+tests) Check Permutation
• 1.3 (+tests) URLify
• 1.4 (+tests) Palindrome Permutation
• 1.5 (+tests) One Away
• 1.6 (+tests) String Compression
• 1.7 (+tests) Rotate Matrix
• 1.8 (+tests) Zero Matrix
• 1.9 (+tests) String Rotation

Linked Lists

• 2.1 (+tests) Remove Dups
• 2.2 (+tests) Return Kth to Last
• 2.3 (+tests) Delete Middle Node
• 2.4 (+tests) Partition
• 2.5 (+tests) Sum Lists
• 2.6 (+tests) Palindrome
• 2.7 (+tests) Intersection
• 2.8 (+tests) Loop Detection

Stacks and Queues

• 3.1 (+tests) Three in One
• 3.2 (+tests) Stack Min
• 3.3 (+tests) Stack of Plates
• 3.4 (+tests) Queue via Stacks
• 3.5 (+tests) Sort Stack
• 3.6 (+tests) Animal Shelter

Trees and Graphs

• 4.1   (+tests) Route Between Nodes
• 4.2   (+tests) Minimal Tree
• 4.3   (+tests) List of Depths
• 4.4   (+tests) Check Balanced
• 4.5   (+tests) Validate BST
• 4.6   (+tests) Successor
• 4.7   (+tests) Build Order
• 4.8   (+tests) First Common Ancestor
• 4.9   (+tests) BST Sequences
• 4.10 (+tests) Check Subtree
• 4.11              Random Node
• 4.12 (+tests) Path with Sum

Bit Manipulation

• 5.1 (+tests) Insertion
• 5.2 (+tests) Binary to String
• 5.3 (+tests) Flip Bit to Win
• 5.4 (+tests) Next Number
• 5.6 (+tests) Conversion
• 5.7 (+tests) Pairwise Swap
• 5.8 (+tests) Draw Line

Math and Logic Puzzles

Note: there are solutions only for those problems where coding approach can be used. If there is no coding solution for a specific problem, then this problem can or should be solved without it.

• 6.7   (+tests) The Apocalypse
• 6.8   (+tests) The Egg Drop Problem
• 6.9   (+tests) 100 Lockers
• 6.10 (+tests) Poison

Helpers

• Simple linked list implementation based on nodes and generator for generating linked lists from an array.
• Simple linked list based stack and stack with limited capacity, using the same interface (+tests).
  • FullStackException to indicate that a stack is full.
  • Abstract class for easier and more optimal testing of different stacks.
• Interface for queues.
  • EmptyQueueException to indicate that a queue is empty.
  • Abstract class for easier and more optimal testing of different queues.
• Adjacency list based graph.
• Simple binary tree.
  • TreeNodeFactory for creating a tree node of a certain type.