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
Monthly Archives: June 2014
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”}.
Sliding window min/max – Dynamic Programming
Given an array of integer A[] and the size of sliding window w. Assume that the window of size w starting from left keeps sliding by moving the window one element to right each time. Find the stream of sliding minimums in optimal way. A sliding minimum is the minimum element of current window.
Permutation Rank
Find the rank of a number in the lexicographic order of its permutations
For example: 312 has rank 5 in the sorted permutation list {123, 132, 213, 231, 312, 321}. A brute force method would be to generate all the permutation and sort them. This will be in exponential order as to generate all the permutation.
Count smaller elements on the right
Given an array of Integer. Find number of smaller elements at each position. Array may have duplicate elements.
The brute force solution for this problem would be to traverse the array from right to left and count number of smaller element on the right in O(n^2).
Swap alternate nodes in a singly linked list
Given a single Linked List. Swap every other alternate nodes.
For example, given 1–>2–>3–>4–>5–>null then output 3–>4–>5–>2–>1–>null. Note that, the list was transformed in several steps.
- First step, swap 1 and 3 i.e. 3–>2–>1–>4–>5–>null
- Second step, swap 2 and 4 i.e. 3–>4–>1–>2–>5–>null
- last step, swap 1 and 5, i.e. 3–>4–>5–>2–>1–>null
Search first occurrence of a duplicated element in a sorted array
Given an array of integer with duplicated elements. Find the first occurrence of a given number in the array.
For example: A = [1, 1, 1, 2, 2, 3, 3, 3, 4]. So, first occurrence of 2 is in index 3, first occurrence of 4 is in index 8.
Find min path between two nodes of a binary tree
Given two nodes in a binary tree with parent pointer. Find the min path from between two nodes. Note that root of the tree is not given
Let’s start with an example as follows.
Search in a sorted but rotated array
A sorted array has been rotated (in one direction) for unknown number of times. Search a value in the array
Find the rightmost cousin of a binary tree
Given a node in a binary tree. Find the rightmost cousin of the give node.
Let’s start with an example.
1
/ \
2 3
/ / \
4 5 6
\ /
7 8
Rightmost cousin of 4 is 6, right most cousin of 7 is 8 and so on.