Interview Questions

Algorithm 算法 Coursera Java Interview

Question 1

2-SUM in quadratic time. Design an algorithm for the 2-SUM problem that takes time proportional to $N^2$ in the worst case. You may assume that you can sort the $N$ integers in time proportional to $N^2$ or better.

brute force

If we use brute force to solve Two Sum, it will cost us $O(n^2)$ to find the answer.

import java.util.ArrayList;
import java.util.Scanner;
import java.io.*;
public class TwoSumBrute{
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(new File("Data.txt"));
        ArrayList<Integer> data = new ArrayList<Integer>();
        while (scan.hasNextInt()) {
        data.add(scan.nextInt());
        }
        int x = 20;
        int N = data.size();
        for (int i = 0; i < N; i++){ 
            for (int j = i + 1; j < N; j++){
                if (data.get(i) + data.get(j) == x) {
                    System.out.println("i = " + data.get(i)+" j = " + data.get(j));
                }
            }
        }    
    }
}

Sorting

We can sort the array to make it easier. For Two Sum, if the array is sorted, we can use two pointers pointing to the head and the end. If the sum is smaller than target, we can move the first pointer right. If the sum is larger than target, we can move the second pointer left. We will continue doing this until we find the target or the position of first pointer is larger than the second pointer. We can also use this in 3 Sum. We can use each entry as a candidate. For example, we now searching 2 other elements in the array that makes their sum equals to target – num[i]. We can just check the entries from i + 1 to num.length – 1, with the method mentioned above.
The complexity of this method is better than brute force method. Sorting the array costs $O(nlogn)$. So, for Two Sum, it costs $O(nlogn)$..

import java.util.Arrays;
public class TwoSumSort{
}

HashMap

We can use HashMap to improve this algorithm. For example, it can improve Two Sum from $O(nlogn)$ to $O(n)$. That is, saving every number in the HashMap as well as its position. And then we can go through the array and check for the existence number target – i in $O(1)$. So we only need $O(n)$.

public class TwoSumHash {
}