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.
Daily Archives: June 1, 2014
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.