Water Trapped Between Towers

You are given an array with element represents the height of a tower with width equal to one unit. It started to rain. Find the amount of water trapped between towers?

For example, tower = [0, 1, 2, 1, 3, 2, 0, 2, 3] – then answer is 6 units between towers 3 and 7.

Maximum area rectangle of histogram

Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram.

For example, H = [4, 2, 1, 8, 6, 8, 5, 2] then the histogram has a rectangle of area of 20 showed in shaded.

Minimum length sum path

Given a binary tree, find out the minimum length sum path form root to leaf with sum S. What about finding minimum length sum path for BST? How does BST improve the search?

For example, the min length path for sum S=13 in T1 is 2 (6–>7 not, 6–>4–>3). For T2 min length path for sum S=3 is 3 (3–> -2 –>3).

HeapSort

HeapSort
Heapsort is a O(nlgn) time comparison based sorting algorithm which can sort in-place (swap operations are done on the array itself) but is not stable (i.e. order of element is not maintained). I have discussed general theories behind the idea of building a generic heap data structure in a separate post.

Print the 2D array in spiral order

Given a 2-dimensional array of integers, print the 2D array in spiral order.

For example:

```A = [1,  2,  3,  4,
5,  6,  7,  8,
9,  10, 11, 12,
13, 14, 15, 16]
```

Then spiral order output should be: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10].

linear time string matching using KMP matching algorithm

Given an input string S and a word w. Find the occurrences of the word w in the given string S in linear time. In other words, explain the linear time string matching using KMP matching algorithm.

For example, if S = “ABABAABA” and w = “ABA” then there are 3 occurrences of w in S at {0, 2, 5}.

Replace all occurrences of a pattern in a text by another string

Given a text and a pattern. Replace all the occurrences of the pattern in the text by another given string.

For Example: If text = “aabaabab” and pattern = “ab”. Then after replacing pattern in the text by “abc” the output should be “aabcaabcabc”.

Top K or K-most frequent words in a document

Given a document (or stream) of words. Find the top k most frequent words in the document (or stream).

For example, if stream = “aa bb cc bb bb cc dd dd ee ff ee dd aa ee”. That is, {“dd”=3, “ee”=3, “ff”=1, “aa”=2, “bb”=3, “cc”=2}. Then top 3 most frequent words are: {“dd”, “ee”, “bb”}.

Smallest Difference between 2 elements from 2 different array

Given two arrays. Find the smallest difference between two elements from both of the arrays.

For example: A=[0, -6, 4, 6, 5, -2], and A=[-4, 8, 2, 3, 10, 9] then then the smallest difference between two elements of the two array is 1 with pairs (4, 3) from the arrays repectively.

Longest palindrom by deleting/inserting elements

Given a string. Find minimum number of insertion (or deletions) required to make it a palindrom.

For example, S=”abacba” can be transformed into the longest palindrom P1=”abacaba” just by inserting 1 char.

Max/Min Heap

Heap is a special data structure that has a shape of a complete binary tree (except possibly the deepest internal node) with a special property. We call it ‘Heap Property’.

Heap property
All nodes are either greater than or equal to (for max heap) or less than or equal to (for min heap) each of its children.

Longest palindromic substring in O(n^2) time

Given a string, find the longest substring that is also a palondrom.

One simple solution is to find reverse of S and then find the longest common substring between S and reverse(s). This is also be the longest palindromic substring. That is,

LongestPalindromicSubStr(S) = LCS(S, reverse(S)).

Kth smallest/minimum element in a BST – Rank of a BST node

Given a binary search tree. Find the kth smallest element in the BST.

A quick solution would be to perform a modified inorder traversal with an extra parameter k. Each time inorder traversal is popping a node out of recursion/call stack (i.e. unwinding a recursion)then we keep decreasing the k. When k=0 then the current node in the call stack is the desired kth smallest node. This is O(n) time algorithm.