You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it.

You are given a list of points in the plane, write a program that
outputs each point along with the three other points that are closest
to it. These three points ordered by distance.
The order is less then O(n^2) .

For example, given a set of points where each line is of the form: 

ID x-coordinate y-coordinate

1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99

Your program should output:

1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1

Approach:

First Have all the points in an array and sort them according to their X axis, which would give:

3 -12.2 12.2 

1 0.0 0.0 

2 10.1 -10.1 

4 38.3 38.3 

5 79.99 179.99 

Then for every point P, calculate the distance from 3 points in the front and 3 point in the back:

For Ex: Point with Id=3 (-12.2, 12.2) does not have 3 points in the back.

Always store only min 3 distances and the corresponding point Ids - Max heap can help here.

Then Sort the points according to their Y Axis, which would give:

2 10.1 -10.1 

1 0.0 0.0 

3 -12.2 12.2 

4 38.3 38.3 

5 79.99 179.99 

Again calculate for every point p, distances from 3 points in the front and 3 points in the back - Always maintaining the Max heap of size 3.

Total complexity: 2nlogn + 4kn + klogk = O(nlogn)

k = 3 here.

Bit counting - Expected order is the number of bits set.

Count number of set bits in a number.

output:

Bit Count: 6
1100110101

Dutch National Flag Problem.

Re-arrange an array containing only 0s,1s and 2s, so that all 1s follow all 0s and all 2s follow 1s. e.g. 00000011111111222222. Linear time algorithm.


Input: {0,0,1,1,2,2,0,0,2,0,1,1,1,0,1};
Output: (0 0 0 0 0 0 1 1 1 1 1 2 2 2 }

Count words in a sentence. Words can be separated by more than one space.

Count words in a sentence. Words can be separated by more than one space.


Input: "  an b  c   d";
output: 4

Remove Duplicate slashes

Remove Duplicate slashes

"/root//foo/bar"=> "/root/foo/bar"

Water Cup Pyramid Problem.

There is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on..
It looks something like this 
    1
   2 3
 4 5 6
every cup has capacity C. you pour L liters of water from top . when cup 1 gets filled , it overflows to cup 2,3 equally, and when they get filled , Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both the cups and so on.
Now given C and L .Find the amount of water in kth cup.


Idea:
Pour L into coup 1. Divide into its children if overflows. Do this for subsequent elements, until find k.
LeftChildIndex = index + height[index] + 1 for the first child,
RightchildIndex = LeftChildIndex  + 1 for the next.


Suppose C=3.0 and L=23.0 then lets find out the amount of water in 8th Cup.
OutPut:

CUP: 1 :H: 0 :W: 3.0
CUP: 2 :H: 1 :W: 3.0
CUP: 3 :H: 1 :W: 3.0
CUP: 4 :H: 2 :W: 3.0
CUP: 5 :H: 2 :W: 3.0
CUP: 6 :H: 2 :W: 3.0
CUP: 7 :H: 3 :W: 0.25
CUP: 8 :H: 3 :W: 2.25
Water Amount in 8th cup: 2.25

find all the possible subset of the array of size k

Given an array of size n, find all the possible sub set of the array of size k(all the subsets must be of size k).


Algorithm:
Suppose array size is of length 5 ie A = {1,2,3,4,5};
and we need all the subsets of size k=3.


If we were supposed to find all the subsets then we would have taken all the binary representations of numbers from 1 to (2^5 - 1) and then according to the bits set, we would have chosen the corresp. number from Array A.


Now the idea is get the minimum number where all "k" lower bits are set.
In our case that would be = "00111" => 7 in decimal
Now find the next decimal number > 7 where 3 bits are set.
Keep on finding the next numbers till you hit "11100" = 28 since that is the largest binary number with 3 bits set of length 5.


Given an integer, method to find the next smallest number that have the same numbers of bits set:
1. Traverse from right to left, Once we have passed a 1, turn on the next 0. 
ex: 101110 becomes 111110
2. Turn off the one that's just to the right side of that (where you switched on '0' to '1').
now 111110 becomes 110110.
3. Make the number as small as possible by rearranging all the 1's to be as far as right as possible.
ex: 110110 becomes 110011.


Sample output of below code:

Subsets of size 3 are: 
3 4 5 
2 4 5 
2 3 5 
2 3 4 
1 4 5 
1 3 5 
1 3 4 
1 2 5 
1 2 4 
1 2 3