Daily Archives: December 20, 2014

Find weighted median in matrix

Evolve the problem to 2-dimension array.
There is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum.

The solution is that find the weighted median from x and y direction.
For example, the matrix is as follow:

Then, the sequence in x direction is 4 3 1 6 5, the sequence in y direction is 7 4 5 3. We find the weighted median both in x and y direction.

For the sequence 7 4 5 3, we think like this, there are 4 cities in a line, which continuously locate at 1, 2, 3, 4. The weight of them are 7, 4, 5, 3.
So the sequence is 1 1 1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4. So the median is 10th , which is 2, which symbolizes 4. By the same way, we can find the 10th element in 4 3 1 6 5 exists in 6. So the weighted median is array[3][1].

Find weighted median in an array — meeting problem

Problem description:
Assume in x-coodinate, there are  cities. The city i locates at xi position, and has pi people. Now people in those cities want to find a place to have a meeting. We should find the location l, where it spend least cost for all people(make the following formula smallest).

We know how to find the median. Just get the middle number. For example, 1 2 3 5 6, the median is 3.
What if each number has a weight?
For example numbers: 1 2 3 5 6
weights:1 3 2 2 5
In this case, we just discrete the numbers by its weight. So, the number sequence will become:
1 2 2 2 3 3 5 5 6 6 6 6 6
Find the median of the new sequence, which is 5.
Accordingly, we solved the meeting problem above.

Burning candle problem

Problem description:
You are given n candles with size of each candle present as an element in an integer array i.e a[i] represent length of ith candle. There is a tradition according to which you celebrate by lighting a candle every night. The candles are lit such that there are k candles lit on the kth day. For ex. 1 candle on day 1 , 2 candles on day 2 and so on. Each night a candle burns 1 inch.
you need to write a program to find out maximum number of days you can celebrate the tradition with the n candles and their lengths?

In my opinon, it is a greedy algorithms. The trick of this quesiton, is that you burn those longest candle for each day. Until one day, you can’t find enough candles to burn. Use a descend linked-list to store the candle. Each time, select the candles from the beginning of the array.