Basic 2 sum problem. Finding pair of numbers that add to current sum.

Question

dux2 · Accepted Answer

put all numbers in a hashtable (number -> # of shows)
then, for each number, calculate its expected counterpart (sum minus first) and test if contained in the hashtable. if first=expected, number of shows in hashtable shall be >1.
Avegage: O(n)

Rich · Answer

import java.util.*;
public class HelloWorldCheckPairs{

     public static void main(String []args){
        System.out.println("Hello World");
        
        int[] test = {1,2,3,4,6,4,5,5,8,6};
        int sumGoal = 10;
        checkPairs(test, sumGoal);
        
     }
     
     public static void checkPairs(int[] input, int sumGoal) {
         Hashtable ht = new Hashtable();
         for (int i = 0; i< input.length; i++) {
             
            int pairNum = sumGoal-input[i];
             if (ht.containsKey(pairNum)){
                 
                for (int j = 0; j < (int) ht.get(pairNum); j++) {
                    System.out.println("(" + input[i] + "," + pairNum + ")" );
                }
             }
             
             if (ht.containsKey(input[i])) {
                 ht.put(input[i], ((int) ht.get(input[i])) + 1);
             } else {
                 ht.put(input[i],1);
             }
             
         }
         
     }
}

Microsoft

Microsoft Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches