Problem Statement
You are given an array which contains an increasing sequence of numbers from 1 to N. There is one number missing in the sequence. The task at hand is find the missing number in minimum running time.
Input: An array A of numbers in increasing order, with one number missing.
Output: The missing integer
Constraint: The sequence is strictly increasing. The algorithm should finish in minimum time.
Approach for Finding Missing Number
At first, it looks like a simple problem which can be solved in O(N) time. Indeed it is. Here are the steps:
Start traversing from the...

Read More
# thinking right

## Finding K nearest distances

Problem Statement
You are given millions of two dimensional point and a utility method to calculate their distances from the origin. Write a code to return the nearest K unique distances from the origin.
If there are more than one point at the same distance, the distance must be just returned once. For e.g. If there are five points (1,1), (2,1), (1,2), (2,2) and (3,3) and the value of K is 3, then we need to return the following:
1.414 - distance of (1,1) from origin.
2.236 - distance of (2,1) or (1,2) from origin as both will be same.
2.828 - distance of (2,2) from origin
Test ...

Read More
## Find maximum element in array of alternate sequences

Problem Statement
Given an array of elements which is first increasing and then decreasing, find maximum element in array of alternate sequences. Here is how an alternate sequence may look like :
{ 1, 3, 4, 7, 9, 6, 4, 2, 1 }
Test Cases
Here are few test scenarios which we must take into account before jumping into the code.
input array is null
input is empty array
input has 1 element
input has 2 element - increasing sequence.
input has 2 element - decreasing sequence.
input has N elements with proper increasing-decreasing sequence
input has increasing sequence
input...

Read More