Daily Archives: February 11, 2015

Next greater element

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.

examples:
input: 1111
output: not possible

inout: 1234
output: 1243

input: 12345765
output: 12346557

Solution:
Assume the input is a int[] num.
1. Scan from the end, and find the 1st position i, where num[i] < num[i+1]. Let i be smallPos.
2. Scan from the end again, find the 1st position j, where num[smallPos] < num[j]. Let j be largePos.
3. Do exchange between num[smallPos] and num[largePos].
4. Do exchange from num[smallPos+1] and num[num.length – 1], num[smallPos+2] and num[num.length – 2], num[smallPos+3] and num[num.length – 3] and so on.
This time, I used node.js to solve this problem.
The visiting format is http://allenlipeng47.com:3000/nge/{input}
For example: http://allenlipeng47.com:3000/nge/66355331
There are 2 files: app.js and npe.js:
node/app.js
node/mymodule/npe.js

npe.js:

  1. /*
  2. Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.
  3. The input num is a char array type.
  4. */
  5. function npe(num){
  6.     num = num.split(”);
  7.     if(num.length==1){
  8.         return ‘not possible’;
  9.     }
  10.     var smallPos = num.length – 2;
  11.     while(smallPos >=0 && num[smallPos] >= num[smallPos+1]){
  12.         smallPos–;
  13.     }
  14.     if(smallPos < 0){
  15.         return ‘not possible’;
  16.     }
  17.     var largePos = num.length – 1;
  18.     while(num[largePos] <= num[smallPos]){
  19.         largePos–;
  20.     }
  21.     var tmp = num[smallPos];
  22.     num[smallPos] = num[largePos];
  23.     num[largePos] = tmp;
  24.     for(largePos = num.length – 1, ++smallPos; smallPos < largePos; smallPos++, largePos–){
  25.         var tmp = num[smallPos];
  26.         num[smallPos] = num[largePos];
  27.         num[largePos] = tmp;
  28.     }
  29.     num = num.join(”);
  30.     return num;
  31. }
  32. module.exports = npe;

app.js

  1. var express = require(‘express’)
  2. var app = express();
  3. app.get(‘/nge/:id’, function (req, res){
  4.     var npe = require(‘./mymodule/npe.js’);
  5.     var result = npe(req.params.id);
  6.     res.send(result);
  7. })
  8. app.get(‘*’, function (req, res){
  9.     res.send(‘Welcome to Li Peng\’s node.js!’);
  10. })
  11. var server = app.listen(3000, function(){
  12.     var host = server.address().address
  13.     var port = server.address().port
  14. });

Return index with probability proportional to its weight

This question is from careercup. link
Problem description:
Write a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).
The stream ends with the special pair {0,0}.
The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights sum when stream has ended).
Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption.
Example: If this was the stream: {1,2},{2,2},{3,4},{4,10}, then id 2 would be returned with probability 1/9.

Analysis:
Assume the input from [0,W0], [1,W1],…[n,Wn], the selected index is i. Let totalWeight=sum(W0,…,Wn).
Now consider a new input [n+1,Wn+1], the probability to keep index I is totalWeight / (totalWeight + Wn+1), and probbability to have a new index n+1 is Wn+1 / (totalWeight + Wn+1).

Instead of a input stream, I used int[][] array for short.

public static int getRandom(int[][] input) {
    double totalWeight = input[0][1];
    int result = 0;
    for (int i = 1; i < input.length; i++) {
        if (input[i][0] == 0 && input[i][1] == 0) {
            break;
        }
        double newTotalWeight = totalWeight + input[i][1];
        double newChance = ((double) input[i][1]) / newTotalWeight;
        if (Math.random() <= newChance) {
            result = i;
        }
        totalWeight = newTotalWeight;
    }
    return result;
}

public static void main(String[] args) {
    int[][] input = { { 1, 4 }, { 2, 2 }, { 3, 2 }, { 0, 0 } };
    int result = getRandom(input);
    System.out.println(result);
    /*
     * Following runs for 1000 times to check the answer correctness.
     *
     * int[] test = new int[3]; for (int i = 0; i < 1000; i++) {
     * test[getRandom(input)]++; } for (int i = 0; i < test.length; i++) {
     * System.out.print(test[i] + “\t”); }
     */
}

Find peak in matrix

This is eveolved from 1D problem – find local min.
I would say this is a interesting problem and hvae great solution. The definition of “local” is near elements, ans in same row or column.
There is junmin’s implementation, link , which is similar to mine. And another very clear material from mit, link.

  1. package weeklychallenge3;
  2. import java.util.Arrays;
  3. public class PeakInMatrix {
  4.     public static void main(String[] args) {
  5.         int[][] matrix = {
  6.                 { 9, 3, 5, 2, 4, 9, 8 },
  7.                 { 7, 2, 5, 1, 4, 0, 3 },
  8.                 { 9, 8, 2, 3, 4, 4, 8 },
  9.                 { 7, 6, 3, 1, 3, 2, 3 },
  10.                 { 9, 0, 6, 0, 4, 6, 4 },
  11.                 { 9, 7, 8, 0, 5, 3, 0 },
  12.                 { 2, 1, 2, 1, 1, 1, 1 }
  13.             };
  14.         int[] result = findPeakInMatrix(matrix);
  15.         System.out.println(Arrays.toString(result));
  16.     }
  17.     public static int[] findPeakInMatrix(int[][] matrix) {
  18.         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  19.             return null;
  20.         }
  21.         int leftCol = 0, rightCol = matrix[0].length, totalRow = matrix.length, totalCol = matrix[0].length;
  22.         int midCol = 0, maxIndex = 0;
  23.         while (leftCol <= rightCol) {
  24.             midCol = (leftCol + rightCol) >> 1;
  25.             maxIndex = 0;
  26.             for (int i = 1; i < totalRow; i++) {
  27.                 maxIndex = (matrix[i][midCol] > matrix[maxIndex][midCol]) ? i : maxIndex;
  28.             }
  29.             if (midCol – 1 >= 0    && matrix[maxIndex][midCol – 1] > matrix[maxIndex][midCol]) {
  30.                 rightCol = midCol;
  31.             } else if (midCol + 1 < totalCol && matrix[maxIndex][midCol + 1] > matrix[maxIndex][midCol]) {
  32.                 leftCol = midCol;
  33.             } else {
  34.                 break;
  35.             }
  36.         }
  37.         return new int[] { maxIndex, midCol };
  38.     }
  39. }

Find all intervals covering an integer

For example, we have intervals
[1,3]
[2,7]
[3,6]
[5,5]
[8,9]

If we give a number 3, it should return:
[1,3]
[2,7]
[3,6]

Solution 1, Linear solution
An obvious solution is to iterate all intervals. This takes O(n) time.

Solution 2, Range tree.
Maintain 2 BST for left and right bound.
 
Find the range for left bound and right bound, and do intersection