Given a 2D array of 1 and 0, Find the largest rectangle of 1’s or 0’s ie. rectangle (may not be square) which is made up of all 1’s or 0’s.
Monthly Archives: June 2014
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].
Pairs with a difference of k
Given n numbers , n is very large. Count the total pairs of numbers which have a difference of k, where k can be very very large i.e. k>n . The solution should have as low of a computational time complexity as possible.
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”.
Kth smallest/largest element in an array
Given an array of integer. Find the kth smallest element in the array in a most efficient manner.
For example: A = [2, 1, 0, 3, -1, 3] and k=3 then the 3rd smallest element is 1. This is also (6-3) = 3rd largest element.
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”}.
Element repeated more than n/2 times – Fast majority vote algorithm
Find the element which repeated more than n/2 times in an given array of integers.
For example, A=[2, 2, 3, 2, 3, 3, 1, 3, 1]. We can clearly see that 3 is the majority.
Pair of array elements that add up to a given sum
Given an array of integers and a value. Find all the pairs that sums up to the value in O(n) time with only one pass over the array. Can you do it efficiently without any space constraint?
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.
Prime numbers less than equal to N in O(n) time
Given an integer N, find all the prime numbers less than in sorted order.
Median of a stream of integer
Given that integers are read from a data stream. Find median of elements read so for in efficient way.
For example, median of the stream, A = [1, 5, 3, 2, 6, 2, 3] is = 3.
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.