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.

Largest rectangle of 1’s or 0’s.. Read the full post (380 words, estimated 1:31 mins reading time)

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.

This is a preview of

Largest rectangle of 1’s or 0’s.. Read the full post (380 words, estimated 1:31 mins reading time)

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.

This is a preview of

Water Trapped Between Towers. Read the full post (357 words, estimated 1:26 mins reading time)

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.

This is a preview of

Maximum area rectangle of histogram. Read the full post (1244 words, estimated 4:59 mins reading time)

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

This is a preview of

Minimum length sum path. Read the full post (863 words, estimated 3:27 mins reading time)

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

This is a preview of

HeapSort. Read the full post (405 words, estimated 1:37 mins reading time)

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

This is a preview of

Print the 2D array in spiral order. Read the full post (441 words, estimated 1:46 mins reading time)

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.

This is a preview of

Pairs with a difference of k. Read the full post (769 words, estimated 3:05 mins reading time)

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

This is a preview of

linear time string matching using KMP matching algorithm. Read the full post (1652 words, 1 image, estimated 6:36 mins reading time)

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

This is a preview of

Replace all occurrences of a pattern in a text by another string. Read the full post (463 words, estimated 1:51 mins reading time)

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.

This is a preview of

Kth smallest/largest element in an array. Read the full post (1099 words, estimated 4:24 mins reading time)

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”}.

This is a preview of

Top K or K-most frequent words in a document. Read the full post (748 words, estimated 3:0 mins reading time)

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.

This is a preview of

Element repeated more than n/2 times – Fast majority vote algorithm. Read the full post (399 words, estimated 1:36 mins reading time)

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?

This is a preview of

Pair of array elements that add up to a given sum. Read the full post (459 words, estimated 1:50 mins reading time)

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.

This is a preview of

Smallest Difference between 2 elements from 2 different array. Read the full post (390 words, estimated 1:34 mins reading time)

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.

This is a preview of

Longest palindrom by deleting/inserting elements. Read the full post (745 words, estimated 2:59 mins reading time)

Given an integer N, find all the prime numbers less than in sorted order.

This is a preview of

Prime numbers less than equal to N in O(n) time. Read the full post (889 words, estimated 3:33 mins reading time)

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.

This is a preview of

Median of a stream of integer. Read the full post (727 words, estimated 2:54 mins reading time)

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.

This is a preview of

Max/Min Heap. Read the full post (855 words, estimated 3:25 mins reading 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)).

This is a preview of

Longest palindromic substring in O(n^2) time. Read the full post (454 words, estimated 1:49 mins reading time)

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.

This is a preview of

Kth smallest/minimum element in a BST – Rank of a BST node. Read the full post (437 words, estimated 1:45 mins reading time)