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.
String matching using suffix tree
Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?
Suffix Tree Definition
Subarray with sum divisible by k
Given an array of random integers, find subarray such that sum of elements in the element is divisible by k.
For example, For A=[2, -3, 5, 4, 3, -1, 7]. The for k = 3 there is a subarray for example {-3, 5, 4}. For, k=5 there is subarray {-3, 5, 4, 3, -1, 7} etc.
Lowest Common Ancestor
Given a binary tree and two nodes. Find Least Common Ancestor (LCA) of the two nodes.
For example given the tree T below. LCA(T, 5, 6) = 3, LCA(T, 4, 6) = 1, etc.
Subset sum problem – Dynamic Programming
Given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?
For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete. A variant of this problem could be formulated as –
Coin sum problem – Dynamic Programming
Given a value n cents and m type of coins with values { c1, c2, .. , cm} cents each. How many ways can we make the n cents by using the coins as many times as you want?
For example, for n = 5 and C = {1, 2, 5}, there are 4 solutions {{1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}}.
Max sum subsequence with non-consecutive elements – Kadane’s Algorithm (DP)
Given an array of integer. Find the maximum sum subsequence such that elements are not consecutive.
For example, A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=11 with the subarray [1, 4, 2, 4].
K closest points
Given an array containing N points find the K closest points to the origin in the 2D plane. You can assume K is much smaller than N and N is very large.
Find anagrams of a string in another string
Given a string (haystack) and a pattern (needle). Find all the anagrams of the pattern that are contained in the string.
For example: str = “abateatas” and pattern = “tea”. Then output should be the anagrams of “tea” contained as a substring in str. So, the desired output = {“ate”, “eat”, “tea”}.