[Leetcode] Random pick with weight

 class Solution {

    private int[] prefixSums;

    private int totalSum;

    public Solution(int[] w) {

        this.prefixSums = new int[w.length];

        int prefixSum = 0;

        for (int i = 0; i < w.length; ++i) {

            prefixSum += w[i];

            this.prefixSums[i] = prefixSum;

        }

        this.totalSum = prefixSum;

    }

    public int pickIndex() {

        double target = this.totalSum * Math.random();

        int i = 0;

        // run a linear search to find the target zone

        for (; i < this.prefixSums.length; ++i) {

            if (target < this.prefixSums[i])

                return i;

        }

        // to have a return statement, though this should never happen.

        return i - 1;

  }

} 

[Leetcode] Partition to K Equal Sum Subsets

BackTracking Approach

 class Solution {

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % k != 0 || maxNum > sum / k) {
            return false;
        }
        return canPartitionKSubsetsFrom(nums, k, new boolean[nums.length], sum / k, 0, 0);
    }
    
    private boolean canPartitionKSubsetsFrom(int[] nums, 
                                             int k,
                                             boolean[] visited, 
                                             int targetSubsetSum, 
                                             int curSubsetSum, 
                                             int nextIndexToCheck) {
        if (k == 0) {
            return true;
        }
        
        if (curSubsetSum == targetSubsetSum) {
            return canPartitionKSubsetsFrom(nums, 
                                            k - 1,
                                            visited,
                                            targetSubsetSum,
                                            0,
                                            0);
        }
        
        for (int i = nextIndexToCheck; i < nums.length; i++) {
            if (!visited[i] && curSubsetSum + nums[i] <= targetSubsetSum) {
                visited[i] = true;
                if (canPartitionKSubsetsFrom(nums, 
                                             k,
                                             visited,
                                             targetSubsetSum,
                                             curSubsetSum + nums[i],
                                             i + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        
        return false;
    }
}

Asked in Google Internship Interview 3rd round

Ugly Numbers :
http://www.geeksforgeeks.org/archives/753