Thursday, March 14, 2013

Facebook interview question - placing objects



Move Objects

There are N objects kept in a row. The ith object is at position x_i. You want to partition them into K groups. You want to move all objects belonging to the same group to the same position. Objects in two different groups may be placed at the same position. What is the minimum total amount by which you need to move the objects to accomplish this?
Input: The first line contains the number of test cases T. T test cases follow. The first line contains N and K. The next line contains N space seperated integers, denoting the original positions x_i of the objects.
Output: Output T lines, containing the total minimum amount by which the objects should be moved.
Constraints: 1 <= T <= 1000
1 <= K <= N <= 200
0 <= x_i <= 1000
Sample Input:
3
3 3
1 1 3
3 2
1 2 4
4 2
1 2 5 7
Sample Output:
0 1 3
Explanation:
For the first case, there is no need to move any object. For the second case, group objects 1 and 2 together by moving the first object to position 2. For the third case, group objects 1 and 2 together by moving the first object to position 2 and group objects 3 and 4 together by moving object 3 to position 7. Thus the answer is 1 + 2 = 3.


Solution:

Let i = 1,2,...end denote the loc id, pos_i denote the position of loc i, wei_i denote the number of objects in loc i in the beginning.

f_1(i,j) is the min cost of grouping objects from loc i to loc j together.

f_k(i) is the min cost of grouping objects from loc i to the end into k groups

Then f_k(i) = min_{i<=m < end}{f_1(i,m) + f_{k-1}(m+1)}



class Solution{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.nextLine());
     
        for(int i = 0; i < T; i++){
            String line = sc.nextLine();
            Scanner lc = new Scanner(line);
            int N = lc.nextInt(); int K = lc.nextInt();
         
            line = sc.nextLine();
            lc = new Scanner(line);
            int[] buf = new int[N];
            int k = 0;
            while(lc.hasNextInt()){
                buf[k++] = lc.nextInt();
            }
            System.out.println(minNum(N,K,buf));
        }
    }
 
    public static int numMove(int i, int j, int[] pos, int[] wei){
        if(i == j) return 0;
        int ret = -1;
        for(int k = i; k <=j; k++){
            int sum = 0;
            for(int t = i; t <=j; t++){
                sum += wei[t] * Math.abs(pos[t] - pos[k]);
            }
            if(ret < 0) ret = sum;
            else ret = Math.min(sum, ret);
        }
     
        return ret;
    }

    public static int minNum(int N, int K, int[] buf){
        if(N <= K) return 0;
        Set<Integer> temp = new TreeSet<Integer>();
        for(int i = 0; i < buf.length; i++) temp.add(buf[i]);
     
        int end = temp.size();
     
        if(end <= K) return 0;

        int[] pos = new int[end];
        int k = 0;
        for(int i : temp){pos[k++] = i;}
     
        int[] wei = new int[end];
        for(int i = 0; i < wei.length; i++){
            int sum = 0;
            for(int j = 0; j < buf.length; j++){
                if(buf[j] == pos[i]) sum ++;
            }
            wei[i] = sum;
        }
     
        int[][] map1 = new int[end][end];
        int[] update = new int[end];
     
        for(int i = 0; i < end; i++){
            for(int j = i; j < end; j++){
                map1[i][j] = numMove(i,j,pos,wei);
            }
        }
     
        for(int i = 0; i < update.length; i++){
            update[i] = map1[i][end-1];
        }
     
        for(k = 2; k <= K; k++){
            for(int i = 0; i < update.length; i++){
                if(i + k >= end) {
                    update[i] = 0; continue;
                }
                int min = -1;
                for(int m = i; m <= end -2; m++){
                    int newvalue = map1[i][m] + update[m+1];
                    if(min < 0) min = newvalue;
                    else min = Math.min(min,newvalue);
                }
                update[i] = min;
            }
        }
        return update[0];
     
    }
 
}

1 comment:

Manacher's Longest Palindromic Substring Algorithm

http://manacher-viz.s3-website-us-east-1.amazonaws.com/#/