Given an int array and an int X, find out if two elements sum up to X

Question

Suresh · Accepted Answer

First sort the array
find idx where array[i] > X;
if (idx == 0) then quit.


march through each element until idx
{
  diff = X - array[i] 
  if (diff >array[i])  then check right elements until idx 
  else
  check for elements on left until i.
}

Sen · Answer

with O(n) runtime using hashtable: 

 public static String findNums(int[] array, int sum){
        String nums; 
        
        Hashtable lookup = new Hashtable();
        
        for(int i = 0; i < array.length; i++){
            try{
            lookup.put(array[i], i);
            } catch (NullPointerException e) {
                System.out.println("Unable to input data in Hashtable: " + e.getMessage());
            }
        }
        
        int num2;
        int num1;
        
        for (int i = 0; i < array.length; i++){
            num2 = sum - array[i];
            Integer index = (Integer)lookup.get(num2);
            if ((lookup.containsKey(num2)) && (index != i)){
                num1 = array[i];
                nums = array[i] + ", and " + num2;
                return nums;
            }
        }
       
        
        return "No numbers exist";
     }

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas