Table of Contents:

Introduction

These are C++/Python solutions to some of the algorithm problems in the Introduction to Algorithms book by Cormen et. al. Zhenchao Gan has some pseudocode solutions to similar problems on his github page.

Please note that it is not typical that you would be directly asked to implement most of these algorithms. But knowing these algorithms and how to implement them in code would help you in faster answering your questions.

These solutions have been tested using g++ 4.8.4 with c++ 11/14 support on Ubuntu 14.04. The solutions are being developed over time. You may find more solutions on this page if you check in at a a later time.

Soft-balls

Usually, there will be a first soft-ball question which you are expected to finish in a reasonable amount of time before a harder question that will test your understanding of data structures. I gleaned these soft-ball questions from the internet (since I am bound by an NDA, I am not allowed to share the questions I got) and answer a few of them in this section. The first question is usually for the interviewer to figure out if you can actually write code. You are being hired to write code. Better be ready to prove it. If you do not pass this stage, you might not make it to the next stage(s) of interview(s). I’ve heard a lot of people flunk it at this stage. So it is worth the while boning up on your basic coding skills. If you are a PhD student, you might be thinking coding is beneath you. But trust me, you actually have to practice writing the code without an IDE in order not to make mistakes during the whiteboard/doc coding interview(s).

Array decays to a pointer

In C++, know that the raw array A[] decays to a pointer.

Code

Atoi Implementation

Atoi converts the pointee in the pointer char* argv (or pointees in the pointer to an array char *argv[]/char **argv) to an integer. This code should be easily adaptable for atoll and its other variants

Code

Reverse a String

This is a fairly common interview question. Implemented in evil C.

C Code

Const Iterator on a vector dynamic set

This is to test your understanding of dynamic set operations and how a pointer that reads from memory should not modify the data it is reading from. A similar question might be to implement a print function from a data structure (in this case, remember to add a const keyword in front of the print member function).

C++ 11 Code

Unordered Map

Interviewers sometimes ask this to get a feel for your understanding of data structures.

C++ 11 Code

Multiplying-two-square-matrices

This is also a fairly common question. The standard time-based multiplication requires \(\theta(n^3)\) time. If you are asked to optimize the code, Strassen’s algorithm allows us to do the multiplication in \(\theta(n^{\, lg 7})\ \approx \theta^{2.8074}\) time.

Python Code

Sorting

Here, I illustrate with examples two \(\theta(n \, lg \, n)\) worst-case algorithms (i.e. mergesort and heapsort), and two \(\theta(n^2)\) worst-case algorithms (i.e. insertion sort and quicksort). I also implement the randomized version of the quicksort algorithm in Python.

Insert-Sort (CLRS 2.1-1)

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array \(A= (31, 41, 59, 26, 41, 58)\).

This sorts in increasing order from left to right.

C++ 11 Code

Insert-Sort in Descending Order (2.1-2)

Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.

C++ 11 Code

LineSearch (2.1-3)

Consider the searching problem:

Input: A sequence of n numbers \(A = (a_1, a_2, \ldots , a_n) \) and a value \(\nu.\)

Output: An index i such that \(\nu = A[i] \) or the special value NIL if \(\nu\) does not appear in \(A\). Write pseudocode for linear search, which scans through the sequence, looking for \(\nu\). Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Complexity: \(O(n)\) as you have to go though every element in the list in the worst case.

C++ 11 Code

Merge-Sort (2.3-1)

Using Figure 2.4 as a model, illustrate the operation of merge sort on the array \( A = (3, 41, 52, 26, 38, 57, 9, 49) \).

Complexity: Worst case: \(\theta(n \, lg \, n)\) Average Case: \(\theta(n \, lg \, n)\)

C++ 11 Code

Python Code

HeapSort

Complexity: Worst case: \(O(n \, lg \, n)\). The Max-Heapify algorithm is \(O(lg \, n)\) while the build-max heap algorithm takes \(O(n)\) time.

C++ 11 Code

Python Code

QuickSort

Complexity: Worst case: \(\theta(n^2\) Average Case: \(\theta(n^2\)

Python Code

Randomized-QuickSort

Complexity: Worst case: \(\theta(n^2)\) Average Case: \(\theta(n^2)\)

Here, the only difference from quicksort is that we randomize the choice of the end of our subarray.

Python Code

Data Structures

This is the meat of most big-tech company interviews and you should try your best to know what is going on under the hood in these algorithms. CLRS is a good reference. Covering the Part II section of the book is very important to understanding these algorithms. In this section, I provide implementations in C++ 11 and python for randomized binary trees, hash maps and lists

Queues

Complexity: Each enqueue and queue dictionary operation takes \(O(1)\) time.

C++ 11 Code

Stack

Complexity: Each of pop, and push operation takes \(O(1)\) time.

Question 10.1

C++ 11 Code

Minimum/Maximum value in an array

Complexity: \(O(n)\) worst-case time.

Python 2.7 Code

Simulatneous minimum and maximum in an array

Section 9.1 in CLRS.

This algorithm has a worst case running time of \(O(\frac{3n}{2})\).

We are maintaining both the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, at a cost of 2 comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then we compare the smaller with the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements

Python 2.7 Code

Deque

10.1-5 in CLRS Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double-ended queue) allows insertion and deletion at both ends. Write four \(O(1)\)-time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.

Python Code

Array-based List

Complexity is \(O(n)\) because of INSERT and FIND. My implementation supports a dynamic array-based list: it doubles the size of the list every time a new element is inserted that increases the index of the array beyond the default maximum.

Cxx 11 Code

Singly-Linked List

Complexity is \(O(n)\) because the SEARCH dictionary operation may have to traverse the entire length of the list if the value being searched is not in the list. The nodes are created with a freelist memory allocator derived from an overloaded new operator.

Cxx 11 Code

Doubly-Linked List

Complexity is \(O(n)\) because the SEARCH dictionary operation may have to traverse the entire list if the value being searched is not in the list. Again, I overloaded the new and delete operators with a freelist to better manage memory when we are inserting, searching or deleting large records.

Cxx 11 Code

Binary Search Tree

The worst case running time for any of the dynamic set operations, INSERT, SEARCH, DELETE, SUCCESSOR, PREDECESSOR, MINIMUM, MAXIMUM on a binary tree of height \(h\) is \(O(h)\). If the tree has \(n\)-elements, it has a worst-case running time of \(O(lg \, n)\) with

Cxx 11 Code