Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2

Return: [1,1],[1,1]

The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Given nums1 = [1,2], nums2 = [3],  k = 3 

Return: [1,3],[2,3]

All possible pairs are returned from the sequence:
[1,3],[2,3]

Very interesting problem. The approach is actually BFS. Let (x, y) be the last element position (the first position is (0, 0)) added to result, then the next element will either be (x + 1, y) or (x, y + 1). The rest of the part is just normal BFS.

    public List<Integer> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<Integer> rst = new ArrayList<>();
        int len1 = nums1.length;
        int len2 = nums2.length;
        if (len1 == 0 || len2 == 0) {
            return rst;
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(k, new Comparator<int[]>() {
            @Override
            public int compare(int[] first, int[] second) {
                return nums1[first[0]] + nums2[first[1]] - (nums1[second[0]] + nums2[second[1]]);
            }
        });
        boolean[][] visited = new boolean[len1][len2];
        queue.add(new int[]{0, 0});
        visited[0][0] = true;
        int[][] neighbors = {{0, 1}, {1, 0}};
        while (!queue.isEmpty() && rst.size() < k) {
            int[] currPos = queue.poll();
            rst.add(new int[]{nums1[currPos[0]], nums2[currPos[1]]});
            for (int[] n : neighbors) {
                int x = currPos[0] + n[0], y = currPos[1] + n[1];
                if (x < len1 && y < len2 && !visited[x][y]) {
                    queue.add(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
        }
        return rst;
    }

Lexicographical Numbers

Maintaining a lexicographical order means that every 10 comes ahead of every 2. One approach is to use recursion. For every number added to list, we first check if its tenfold is in the range, if it is, recursively add its tenfold. Then we increment the number.

public List<integer> lexicalOrder(int n) {
        List<integer> rst = new ArrayList<>();
        if (n < 1) {
            return rst;
        }
        getList(1, rst, n);
        return rst;
    }
    
    private void getList(int curr, List rst, int n) {
        rst.add(curr);
        if (curr * 10 <= n) {
            getList(curr * 10, rst, n);
        }
        if (curr < n && curr % 10 < 9) {
            getList(curr + 1, rst, n);
        }
    }

Guess Number Higher or Lower II

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Hint:

1. The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in thefirst scenario.
2. Take a small example (n = 3). What do you end up paying in the worst case?
3. Check out this article if you're still stuck.
4. The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
5. As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?

The question asks us to find the minimum money we need to pay in the worst scenario. The hint suggests its a minimax problem. I think try to understand the whole algorithm is too complicated. Let's explain it in an easy way. Given range [lower, upper] and a number y, we want to find the minimum money we need to pay before we make the correct guess.For a wrong guess x != y, we know the  next guess lies in [lower, x - 1] or [x + 1, upper], the worst scenario exists in the maximum of the money to pay between these two ranges. So the minimum money we need to pay in range [lower, upper] is:

Math.min(money[lower][upper], Math.max(solve(lower, x - 1), solve(x + 1, upper))) for x in [lower, upper], inclusive. 

    public int getMoneyAmount(int n) {
        int[][] money = new int[n + 1][n + 1];
        return solve(money, 1, n);
    }
    
    public int solve(int[][] money, int lower, int upper) {
        if (lower >= upper) {
            return 0;
        }
        if (money[lower][upper] != 0) {
            return money[lower][upper];
        }
        money[lower][upper] = Integer.MAX_VALUE;
        for (int i = lower; i <= upper; i++) {
            money[lower][upper] = Math.min(money[lower][upper], 
            Math.max(solve(money, lower, i - 1), solve(money, i + 1, upper)) + i);
        }
        return money[lower][upper];
    }

Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Binary operations. Using XOR for the sum and AND for the carry.
Think it in a binary way. If two bits are both 1, then adding them will lead a 0 and a 1 in the next position. So a^=b gives us the result of current bit and a&b gives us the carry. We then move the carry to next bit.

public int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a ^= b;
            b = carry << 1;
        }
        return a;
    }

Super Pow

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8

Example2:

a = 2
b = [1,0]

Result: 1024

This is another mathematical problem. The basic idea is to use exponentiation by squaring, i.e.:

x^n = x(n/2) * x(n/2) * x if n % 2 != 0
       = x(n/2) * x(n/2) if n % 2 == 0


For the actual problem, since b is represented by array:

a^b = a^(10*len*b[len - 1] + ... + b[0]) = (a^(10 * len))^(b[len - 1])*...*(a^b[0])

Besides

(a * b) % c = ((a % c) * (b % c)) % c

public class Solution {
    private int modConstant = 1337;
    public int superPow(int a, int[] b) {
       int len = b.length;
  int rst = 1;
  for (int i = len - 1; i >= 0; i--) {
   rst = rst * quick_pow(a, b[i]) % modConstant;
   a = quick_pow(a, 10);
  }
  return rst;
    }
    
 int quick_pow(int a, int b) {
  int rst = 1;
  a %= modConstant;
  while (b > 0) {
   if (b % 2 !=0) rst = rst * a % modConstant;
   a = a * a % modConstant;
   b /= 2;
  }
  return rst;
 
    }
}

Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14 

Returns: False

Nothing special, bisection method. You can choose any initial value. I choose num / 2, but I believe there are better ways. Let me know.

    public boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }
        long sqrt = num / 2;
        while (sqrt > 0 && sqrt < num) {
            long square = sqrt * sqrt;
            if (square == num) {
                return true;
            } else if (square > num) {
                sqrt /= 2;
            } else {
                if ((sqrt + 1) * (sqrt + 1) > num) {
                    return false;
                }
                sqrt++;
            }
        }
        return false;
    }

Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

The question asks about how many ways to get the sum. This doesn't need to use backtracking. DP is a better solution. For any amount i, if a number n is less than the current amount, the current amount can be acquired by (i - n + n), thus number of ways to get current amount is incremented by dp[i - n].

public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= target; i++) {
            for (int n : nums) {
                if (i >= n) {
                    dp[i] += dp[i - n];
                }
            }
        }
        return dp[target];
        
    }

Linked List Random Node

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

A probability problem. The easiest solution is to traverse the whole list, find the count (number of nodes in the list) and randomly pick one node with 1 / count probability. As the question mentioned, if the list is too long, it will be too hard to get the length. One approach is to keep counting and choose the position at 1 / count. Traverse through the whole list and return the last number. The intuition is, for any number x, the probability is : 1 / x * (x / (x + 1))... (n - 1)/n = 1 / n.

public class Solution {
    
    ListNode head;
    Random random;

    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode curr = head;
        int toReturn = 0;
        for (int cnt = 1; curr != null; cnt++, curr = curr.next) {
            if (random.nextInt(cnt) == 0) {
                toReturn = curr.val;
            }
        }
        return toReturn;
    }
}

Kth largest element

Same as find the kth smallest element: i.e., using quick select. Similar to quick sort, make sure that each time after the index method partition returns, the element at that index is the correct index when the array is sorted.

    /*
     * @param k : description of k
     * @param nums : array of nums
     * @return: description of return
     */
    public int kthLargestElement(int k, int[] nums) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return 0;
        }
        return quickSelect(nums, 0, nums.length - 1, nums.length - k + 1);
    }
    
    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        
        int position = partition(nums, left, right);
        if (position + 1 == k) {
            return nums[position];
        } else if (position + 1 < k) {
            return quickSelect(nums, position + 1, right, k);
        } else {
            return quickSelect(nums, left, position - 1, k);
        }
    }
    
    public int partition(int[] nums, int l, int r) {
        int left = l, right = r;
        int pivot = nums[left];
        
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        

        nums[left] = pivot;
        return left;         
    }