From wiki, A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.[1] (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.)
Monthly Archives: September 2015
Median (or kth Smallest) of a sorted 2D array
Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array.
For example,
Kth Smallest Element and median of Two Sorted Arrays
Given two sorted arrays find the element which would be kth in their merged and sorted combination.
For example, A=[1, 1, 2, 3, 10, 15] and B=[-1, 2, 3, 4, 6, 7] then k=8th smallest element would be 4 as it appears in 8th position of the merged sorted array=[-1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 10, 15].
Permutation and Combination
Permutation means arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {a,b,c}, namely: (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), and (c,b,a). These are all the possible orderings of this three element set.
Uniform Random sampling of Unbalanced Binary Tree
Given an unbalanced binary tree, write code to select k sample node at random
Self-Intersecting spiral moves
You are given a list of n float numbers x_1, x_2, x_3, … x_n, where x_i > 0. A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise).
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it’s self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn’t cross
Equal partitioning with minimum difference in sum
Given an array consisting of N Numbers.
Divide it into two Equal partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum. If number of elements are odd difference in partition size can be at most 1.