rhdsmnd/epi

Solving Elements of Programming Interviews Questions

Elements of Programming Interviews Framework

Note: This is my personal side project; it's not officially affiliated with or recognized by the Elements of Programming Interviews book

Background/Motivation

When first solving EPI (Elements of Programming Interviews) problems, I realized that most of the code I was writing had little to do with the solution. Instead, most of my time was spent on secondary tasks like parsing file input and output, writing test harnesses, and rewriting basic data structures. At the core, each problem should only need one function, give or take several helper functions, and the function that executes it.

Luckily, most of the secondary tasks were similar from problem to problem and I decided to create components that could take care of them. Namely, a test harness that could parse test files and data structures not offered (or needed extra functionality) by the JDK. The first can be found in the “test_util” directory, and the second in the “data_structures” directory.

Test Harness (under “test_util”)

Data Structures (under “data_structures”)

epi's Issues

Generate Javadocs from comments

Secondary:

First finish implementation of core data structures with testing and utility functions for equality, string parsing at minimum: trees, graphs, single/double linked lists (using the java api for stacks and hashmaps).

---

Use automatically generated javadoc from commented classes & methods to provide information for the use and behavior of the library.

Implement linked lists

Waiting on:
Trees as per #2

---

Implement singly/doubly linked lists with unit tests, value equality, and string parsing (to and from).

UnorderedTree value equality

OrderedTree has an isEquals method that returns true if the type, structure, and values of its nodes are equal of the compared trees. The problem becomes trickier with UnorderedTrees: I'm not even exactly sure what the time complexity is for the naive implementation (O(n^2), n is size of smaller tree?). Again, only considering at the moment.

Implement Graph Library

Secondary: Finish implement Trees (Ordered, Unordered, Binary, maybe BST & Red-Black) and finish several EPI problems using the data structure & parsing utilities.

---

First, look for graph library implemented for 61B project. Could even include client applications as example usage. If found just refactor, otherwise implement from scratch. Inner classes for nodes/edges, generic types for keys and values, sorting/traversal/search utilities, separate hashsets for nodes and edges in graph object.

Improve build & packaging data structures

Waiting on:
#3

---

Clean build system for the core data structures (ds) implemented in #3 , possibly converting the ds library into maven/gradle project to allow for easy building and packaging as JAR or at the least using variables for compilation in Makefiles instead of repeated hard-coded locations and options.

Implement Tree Exceptions

Implement exceptions for invalid Tree state or functionality. I.e. attempting to assign a child tree type to a parent of a different type.