Exponential search

Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.

Interpolation search

Given a sorted array of integers and a target, find out if a target exists in the array or not. If target exists in the array, print index of it.

Binary Search

Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.

Print all triplets that forms Geometric Progression

Given a sorted array of distinct positive integers, print all triplets that forms Geometric Progression with integral common ratio.   A Geometric Progression is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. For example, the sequence 2, …

Calculate sum of all elements in a sub-matrix in constant time

Given a M x N matrix and two coordinates (p, q) and (r, s) which represents top-left and bottom-right coordinates of a sub-matrix of the given matrix, calculate the sum of all elements present in the sub-matrix in O(1) time. Here, 0 < = p < r < M and 0

Find probability that a person is alive after taking N steps on the island

Given an island in the form of square matrix and a point inside the matrix where a person is standing. The person is allowed to move one step in any direction (right, left, top, down) on the matrix. If he steps outside the matrix, he dies. Calculate the probability that he is alive after he …