# Algorithms and Data Structures

### 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

**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**

*harder**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.

`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

`Reverse a String`

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

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

`Unordered Map`

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

`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.

`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.

`Insert-Sort in Descending Order (2.1-2)`

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

`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.

`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)\) |

`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.

`QuickSort`

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

`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.

## 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.

`Stack`

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

Question 10.1

`Minimum/Maximum value in an array`

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

`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

`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.

`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.

`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.

`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.

`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