public interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
public void store(int input);

/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param test, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5, and 0
*/
public boolean test(int test);
}

Question

public interface TwoSum {
/**
 * Stores @param input in an internal data structure.
 */
public void store(int input);

/**
 * Returns true if there is any pair of numbers in the internal data structure which
 * have sum @param test, and false otherwise.
 * For example, if the numbers 1, -2, 3, and 6 had been stored,
 * the method should return true for 4, -1, and 9, but false for 10, 5, and 0 
 */
public boolean test(int test);
}

G · Accepted Answer

HashSet is insufficient for the "2x" case, i.e., if 6 is tested in the above example. There's only one 3, so it should return false, but the HashSet approach would return true. A HashMap with value == count could be used to handle this edge case (i.e., return true only if count > 1).

Jun · Answer

For even optimal solution, there no need for HashMap, just use HashSet and store the difference.

Anonymous · Answer

void printPairs(int arr[], int arr_size, int sum)
{
  int i, temp;
  set s;
 
  for(i = 0; i = 0 && (s.find(temp) != s.end()))
    {
      printf("Pair with given sum %d is (%d, %d) 
", sum, arr[i], temp);
    }
    s.insert(arr[i]);
  }
}

Seluj · Answer

Write one loop to store the data array in a hashmap =
loop through the data array again and find if value-data[i] is also in the array.

The trick is that we will have O(2n) because of the two looops which for large number will be O(n) time.

So:

public class TwoSumImpl implements TwoSum{

public boolean test(int [] a, int value)
{
     HashMap  mapOfInt = new HashMap();
     boolean testResult = false;

     for(int i=0;i

Seluj · Answer

That's right Jun...using the HashSet you can simply say if hashSet.contains(value-a[i])

LinkedIn

Pergunta de entrevista da empresa LinkedIn

Respostas da entrevista

Empresas seguidas

Buscas de vagas