CMSC389O: The Coding Interview

A comprehensive, practical introduction to technical interviews. We'll go over basic topics such as Big O and String Manipulation and then dive into more complex topics such as Bit Manipulation and Dynamic Programming.

big o.

Big-O notation is a central concept in algorithm analysis. We cover common complexity classes with several examples and applications of Big-O notation to technical interviews.

arrays and strings.

Arrays are one of the most central data structures in computer science. Sooner or later you’ll be faced with an Array question when interviewing with any company. Strings, being just character arrays, offer a great way to test Array skills without relying on more complicated data types.

“Fast i, Slow j” is a concept used for various array methods, including partition, a central piece of various sorting algorithms such as Quicksort. Next, “Sliding Window” approaches allow for linear-time algorithms for various problems with otherwise O(n2) limitations. Finally, arrays can often be used for indexing, in place of a map or set; as a heuristic, if your algorithm relies on a map/set and can get away with an array, use the latter.

Three problems were also covered in this lecture: Target sum (finding two elements that sum closest to 0), Valid Parenthesis (checking whether a sequence of parenthesis is syntactically correct), and Pangram (finding whether a string has all 26 characters of the alphabet).

sorting and searching.

We cover characteristics of different sorting algorithms (mergesort, counting sort, etc) and applications of sorting.

We also present a high level overview of searching algorithms: linear search, binary search, breadth-first and depth-first searches, and substring search.

inheritance.

We cover inheritance, one of the main pillars of Object-Oriented-Programming. We discus basic intuitions, overloading, and overriding. Two example class hierarchies are covered in which these concepts are applied.

We cover LinkedLists, including techniques like two pointers, traversal, and cycle detection. We show when to use these techniques, and give numerous examples of problems involving LinkedLists.

graphs.

A primer on Graphs. We cover what graphs are, common terminology, code representation and basic algorithms such as BFS and DFS.

we love mail!

Reach out to us at