2D array of 1s and 0s.

Given a 2-Dimensional(NXN) array A[][]. Change A[] such that if A[i][j]=1 Set all ith row and jth column elements as '1'. Can you do it in O(N*N)

Given a function Random(5), then how to implement a function of random(n)?

Given a function Random(5), which will return a number of {1, 2, 3, 4, 5} by random, then how to implement a function of random(n)?

Two ways to find number is power of 2.

Two ways to find number is power of 2.

n & n-1 == 0
n & -n == n.

Shorted common superstring

Given an array of strings(Say S[]), and a big string (Say B). Now how to find shortest substring from a big string B, which contains all strings (S[] ).

Find kth smallest element in min heap

How to find kth smallest element in min heap in klogk ?. Note it is not klogN.

Multiply array elements without using division operator

suppose there is an array A[N] of N numbers. We have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

catalon number

In how many different ways can you put brackets properly using only curly braces only for n times?
For eg:
If n = 1 => {} Only 1 is possible
If n = 2 => {}{}, {{}} 2 are possible


Answer: Use catalon number c(2n n)n/(n+1).

How to shuffle array

How to shuffle array?.

Also, how will you shuffle if array size is not known, i mean it can stream of numbers.

How to add two linked list

How to add two linked list where each list is a list of numbers like 1 -> 2 -> 3 -> 4 .
You should not use recursion or reversing the list.

Note: Two lists can differ by size.

Fill level order next and prev links in binary search tree

In a binary search tree, each node has 2 extra pointers namely levelOrderNext and levelOrderPrev. You need to give an algorithm with constant space so that the nodes are linked properly in level order in CONSTANT space.

Find the kth smallest elements of 2 sorted arrays

Find the kth smallest elements of 2 sorted arrays

How to design notepad

How to design notepad such that insertion and deletion should be efficient?.

How to store binary tree in a file?

How to store binary tree in file and retrieve back?.

Minimum average waiting time of processes

Processing times for 5 processes were given. You need to find out the minimum average waiting time the processes have to wait in order to get executed if N PROCESSORS are given.

Hint: Try to do it for 1 processor and then 2 processor and you will get for N processor.

Array pre processing

Given an integer array A[], what preprocessing you need to do so that when given i and j such that i <= j, you can tell in O(1) time the number of elements in the array having values between and including i and j.

find second shortest path in given graph

Given a graph's shortest path algorithm, how can you make use of it to find the second shortest path?

how many times the given number is repeated in a sorted array

How to find the no. of times the given number is repeated in a sorted array?.

Joseph problem

There are n persons numbered from 0 to n - 1 standing in a circle. The person number k, counting from the person number 0, is executed. After that the person number k of the remaining persons is executed, counting from the person after the last executed one. The process continues until only one person is left. This person is a survivor. The problem is, given n and k detect the survivor's number in the original circle.

In-place_matrix_transposition

How to do in-place matrix transposition?.

Note, if it is n*n matrix, then we can just do one traversal and swap [i][j] with [j][i].
But what if it is not square matrix?.

Find subarray which has equal number of 1s and 0s

How to find subarray from a array of 0s and 1s such that subarray should have equal number of 1s and 0s.

For eg:
11100 --> 1100
00111 ---> 0011

Find number in rotated sorted array.

How to search for a given number in a sorted array which are circularly rotated by few times.

Find three numbers in array which occur only once.

Given an array of n integers, such that each number in the array appears exactly twice, except for three numbers (say a, b and c) which appear exactly once. In O(n) time and O(1) space find a,b and c.

Find next larger number

Given: a number containing N decimal digits (N can be very large), represented as a string. Problem: find the permutation of this string that represents the first number that is bigger than the given one, or return null if such number does not exist. Example: 279,134,399,742 -> 279,134,423,799

Post office problem

How to place P post-offices in a city of N houses such that if every house wants to post a letter on a day then the overall distance traveled is minimum.
Consider city has 2d , each house is represented by a point, and we need to find P points such that sum of diff of P points and N points should be minimal.

How will you find whether a number is a proper square or not?

How will you find whether a number is a proper square or not?

sum of two linked list

Take a number 1234. It can be represented in the form of a linked list, where the head of the list points to the node having value 1, that one pointing to 2, that one to 3, and then 4.
Similarly 2 linked lists are given. Their digit count is known to you in advance. You need to add the 2 lists and create a new list without changing the existing list (reversing) or using recursion.

Balanced bit array

You are given a bit array (i.e each element is 0 or 1) A[1..n].
A bit array is called balanced if the number of times 01 appears is same as the number of times 10 appears. By 01 appearing we mean that A[i] = 0 and A[i+1] = 1 for some i.
i.e.
S1 = { i : A[i] = 0 and A[i+1] = 1}
S2 = {j : A[j] = 1 and A[j+1] = 0}
The array is balanced if number of elements in S1 is same as number of elements in S2.
Eg: A = [1,0,1] is balanced.
A = [0,0,0,0,0,0] is balanced too.
Give an algortihm to determine if a bit array A[1...n] is balanced.

shuttering subsequence problem

A and B are two strings of a finite alphabet. Let B^i be the string B concatenated i times to itself. E.g, if B = ab, then B^3 is ababab. The Stuttering Subsequence Problem is:
Given strings A and B, find the largest i such that B^i is a subsequence of A. Give an algorithm to solve the Stuttering Subsequence problem. Note, the problem asks for a subsequence check, and not a substring check.

Data structure to store anagrams

What data structure you'll use as a dictionary to store the anagrams of a word.The idea was to store in a way to efficiently get and print all the anagrams.

Petrol bunk problem

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.
ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

Reach the end of array

Given an array of positive integers( including 0 ).
Each value in the array indicates how many jumps you can take to the right. So, e.g. if array[3] = 2, it means that position 4 & 5 are reachable from position 3.
Find out if the last element is reachable from the front

Reverse linked list using one pointer

How to reverse linked list using single extra pointer?.
We should not use recursion.

Maximum sub matrix in a given matrix

How to find maximum sum of sub matrix in a given matrix of numbers?.

Given a Chess board and 3 coins, how many number of ways you can place them so that all the coins are in the same diagonal?

Given a Chess board and 3 coins, how many number of ways you can place them so that all the coins are in the same diagonal?

Count the number of numbers up to n which are both square and cube.

Count the number of numbers up to n which are both square and cube.
e.g., for 1 < n < 1000 answer is 2 (64, 729)

Maximum sub array sum in array

You have an array of N elements and you have to find the subarray of out of this array whose sum is maximum. The condition is no two element that you chose in your subarray should be adjacent to each other in the original array. How will you do this polynomial time??

How to find shortest common superstring ?

Given list of small words and a big word, how to find smallest substring from a big word which contains given list of small words?.

Find universal vertex in given graph represented as adjacency matrix.

How to find universal vertex in a graph represented as adjacency matrix in o(V) time.

Universal vertex has |V|-1 incoming edges and 0 outgoing edges.

how to find binary tree is symmetry or not?

how to find binary tree is symmetry or not?

There is a stream of input coming. How will you randomly pick k elements from it?

There is a stream of input coming. How will you randomly pick k elements from it?
(Reservoir algorithm)

Given an array how will you shuffle it?

Given an array how will you shuffle it?
(Algorithm proposed by Knuth)

Find number which occur more than n/2 times in an array?

Find number which occur more than n/2 times in an array?
Find number which occur exactly n/2 times in an array?

o(n) time and o(1) space complexity.

Find two repeated numbers in an array

How to find two repeated number in an array[513] , it contains numbers from 1 to 511. So there are two numbers which are repeated. All remaining numbers are distinct.
How to find the two repeated number?.

Row with maximum zeros

Given N*N 2D matrix of 1's and 0's, all rows are sorted .
Find the row which contain's max no. of 0's.

How to convert number to its hex format

How to convert number to its hex format?.

Reference:

substring comparison

Give efficient algorithm to find whether one string is substring of other string.

How to print binary tree vertically?

Given a binary tree, give efficient algorithm to do vertical level order traversal.

Longest increasing subsequence

How to find longest increasing subsequence ?.

Sequence is series of integers like 4,5,-1,2,3 ...

Maximum subset sum of array

How to find subset of array whose sum is maximum?.

How to merge two BST?

How to merge two BST .

Welcome

Heartly welcome to everybody.

Let's start posting our mind blowing algorithms here.