HeapSort

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 […]

Generate Parentheses

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 {()} […]

Floor and Ceiling of a Key in Sorted Array – Search Min Diff Element

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 […]

First non-repeating or unique character in a stream of characters

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

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 […]

Find Missing Number

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 […]

Find k such that kth row is all zero and kth col is all one in a matrix

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 […]