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. Observe that, maxheap always contain largest […]
Category Archives: Algorithms
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: {((())), (()()), (())(), ()(()), ()()()} How do we solve this problem? Let’s start with base cases. n=0 : result set is empty (no solution) n=1 : result set is {()} […]
Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of […]
Given a stream of characters, find the first non-repeating i.e. unique character occurred. For example, in a stream [a,c,b,a,d,a,…] first unique is ‘c’ but if another ‘c’ character comes to stream [a,c,b,a,d,a c,…] then first unique would be ‘b’. We need some data structure that can maintain the order of each character appearing first time […]
Find the single number that duplicates one or more times in an array in O(1) space and O(n) time without modifying the array Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only […]
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. The idea behind solving […]
Given a set S of digits [0-9] and a number n. Find the smallest integer larger than n (ceiling) using only digits from the given set S. You can use a value as many times you want. For example, d=[1, 2, 4, 8] and n=8753 then return 8811. For, d=[0, 1, 8, 3] and n=8821 […]
1. Given a set of positive numbers less than equal to N, where one number is missing. Find the missing number efficiently. 2. Given a set of positive numbers less than equal to N, where two numbers are missing. Find the missing numbers efficiently. 3. Given a sequence of positive numbers less than equal to […]
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. 1 / \ 2 3 / / \ 4 5 6 \ / 7 8 Use parent pointer to find the […]
Given a Boolean Matrix, find k such that all elements in k’th row are 0 and k’th column are 1. Do it in O(n) time Given a binary matrix mat[n][n], find k such that all elements in k’th row are 0 and all elements in k’th column are 1. The value of mat[k][k] can be […]