Linkedin Interview Question
Country: United States
There is no need to using HashMap and here is the simplified one
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Solution
{
public static void main (String[] args) throws java.lang.Exception
{
TwoSumImpl obj = new TwoSumImpl();
obj.store(1);
obj.store(-2);
obj.store(3);
obj.store(6);
System.out.println("test val " + 4 + " result " + obj.test(4));
System.out.println("test val " + -1 + " result " + obj.test(-1));
System.out.println("test val " + 9 + " result " + obj.test(9));
System.out.println("test val " + 10 + " result " + obj.test(10));
System.out.println("test val " + 5 + " result " + obj.test(5));
System.out.println("test val " + 0 + " result " + obj.test(0));
}
}
interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);
/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param val, 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
*/
boolean test(int val);
}
class TwoSumImpl implements TwoSum{
ArrayList<Integer> list = new ArrayList<Integer>();
public void store(int input){
list.add(input);
}
public boolean test(int val){
for(Integer in : list) {
if(list.contains(val - in.intValue()))
return true;
}
return false;
}
}
There is no need to using HashMap for randomCoder1988 solution
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Solution
{
public static void main (String[] args) throws java.lang.Exception
{
TwoSumImpl obj = new TwoSumImpl();
obj.store(1);
obj.store(-2);
obj.store(3);
obj.store(6);
System.out.println("test val " + 4 + " result " + obj.test(4));
System.out.println("test val " + -1 + " result " + obj.test(-1));
System.out.println("test val " + 9 + " result " + obj.test(9));
System.out.println("test val " + 10 + " result " + obj.test(10));
System.out.println("test val " + 5 + " result " + obj.test(5));
System.out.println("test val " + 0 + " result " + obj.test(0));
}
}
interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);
/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param val, 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
*/
boolean test(int val);
}
class TwoSumImpl implements TwoSum{
ArrayList<Integer> list = new ArrayList<Integer>();
public void store(int input){
list.add(input);
}
public boolean test(int val){
for(Integer in : list) {
if(list.contains(val - in.intValue()))
return true;
}
return false;
}
}
public class TwoSum {
/**
* Stores @param input in an internal data structure.
*/
Map<Integer, Integer> storeMap = new HashMap<Integer, Integer>();
public void store(int input) {
//if the input value exists in the map
if (storeMap.containsKey(input)) {
storeMap.put(input, storeMap.get(input) + 1);
} else {
storeMap.put(input, 1);
}
}
/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param val, 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 val) {
for (Integer currVal : storeMap.keySet()) {
Integer otherNumber = val - currVal;
//if the map contains the other number
if (storeMap.containsKey(otherNumber)) {
if (otherNumber.equals(currVal)) {
//If the number is the same as current, then check if another number exists
Integer count = storeMap.get(currVal);
//another same number exists
if (count > 1) {
return true;
}
} else {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
TwoSum twoSum = new TwoSum();
twoSum.store(1);
twoSum.store(-2);
twoSum.store(3);
twoSum.store(6);
twoSum.store(6);
System.out.println("Test " + twoSum.test(4));
System.out.println("Test " + twoSum.test(-1));
System.out.println("Test " + twoSum.test(9));
System.out.println("Test " + twoSum.test(12));
System.out.println("Test " + twoSum.test(10));
System.out.println("Test " + twoSum.test(5));
System.out.println("Test " + twoSum.test(0));
}
}
1) Go through the list and store every possible sum in a hash table. O(n^2) preprocessing step and O(1) look up each time method is called. O(n) space.
2) Go through list and store every element in hash table. O(n) preprocessing step and O(n) look up each time method is called. O(n) space. --> for each element, is value minus element in hash map?
3) Sort the list as preprocessing step, O(nlogn). Use 2 pointers to go through list from both ends, incrementing left pointer if sum is too low, and decrementing right pointer if sum is too high, O(n). Space O(1).
public class TwoSum {
/**
* Stores @param input in an internal data structure.
*/
Map<Integer, Integer> storeMap = new HashMap<Integer, Integer>();
public void store(int input) {
//if the input value exists in the map
if (storeMap.containsKey(input)) {
storeMap.put(input, storeMap.get(input) + 1);
} else {
storeMap.put(input, 1);
}
}
/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param val, 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 val) {
for (Integer currVal : storeMap.keySet()) {
Integer otherNumber = val - currVal;
//if the map contains the other number
if (storeMap.containsKey(otherNumber)) {
if (otherNumber.equals(currVal)) {
//If the number is the same as current, then check if another number exists
Integer count = storeMap.get(currVal);
//another same number exists
if (count > 1) {
return true;
}
} else {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
TwoSum twoSum = new TwoSum();
twoSum.store(1);
twoSum.store(-2);
twoSum.store(3);
twoSum.store(6);
twoSum.store(6);
System.out.println("Test " + twoSum.test(4));
System.out.println("Test " + twoSum.test(-1));
System.out.println("Test " + twoSum.test(9));
System.out.println("Test " + twoSum.test(12));
System.out.println("Test " + twoSum.test(10));
System.out.println("Test " + twoSum.test(5));
System.out.println("Test " + twoSum.test(0));
}
}
public class TwoSum {
/**
* Stores @param input in an internal data structure.
*/
Map<Integer, Integer> storeMap = new HashMap<Integer, Integer>();
public void store(int input) {
//if the input value exists in the map
if (storeMap.containsKey(input)) {
storeMap.put(input, storeMap.get(input) + 1);
} else {
storeMap.put(input, 1);
}
}
/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param val, 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 val) {
for (Integer currVal : storeMap.keySet()) {
Integer otherNumber = val - currVal;
//if the map contains the other number
if (storeMap.containsKey(otherNumber)) {
if (otherNumber.equals(currVal)) {
//If the number is the same as current, then check if another number exists
Integer count = storeMap.get(currVal);
//another same number exists
if (count > 1) {
return true;
}
} else {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
TwoSum twoSum = new TwoSum();
twoSum.store(1);
twoSum.store(-2);
twoSum.store(3);
twoSum.store(6);
twoSum.store(6);
System.out.println("Test " + twoSum.test(4));
System.out.println("Test " + twoSum.test(-1));
System.out.println("Test " + twoSum.test(9));
System.out.println("Test " + twoSum.test(12));
System.out.println("Test " + twoSum.test(10));
System.out.println("Test " + twoSum.test(5));
System.out.println("Test " + twoSum.test(0));
}
}
protocol TwoSumProtocol {
func store(val: Int)
func test(val: Int) -> Bool
}
// optimized for Insert
class TwoSum: TwoSumProtocol {
var values = Set<Int>()
func store(val: Int) {
values.insert(val)
}
func test(val: Int) -> Bool {
for value in values {
let difference = val - value
if values.contains(difference) {
return true
}
}
return false
}
}
//Optimized for GET
class TwoSum: TwoSumProtocol {
var values = Set<Int>()
var sums = Set<Int>()
func store(val: Int) {
for value in values {
sums.insert(value + val)
}
values.insert(val)
}
func test(val: Int) -> Bool {
return sums.contains(val)
}
}
protocol TwoSumProtocol {
func store(val: Int)
func test(val: Int) -> Bool
}
// optimized for Insert
class TwoSum: TwoSumProtocol {
var values = Set<Int>()
func store(val: Int) {
values.insert(val)
}
func test(val: Int) -> Bool {
for value in values {
let difference = val - value
if values.contains(difference) {
return true
}
}
return false
}
}
//Optimized for GET
class TwoSum: TwoSumProtocol {
var values = Set<Int>()
var sums = Set<Int>()
func store(val: Int) {
for value in values {
sums.insert(value + val)
}
values.insert(val)
}
func test(val: Int) -> Bool {
return sums.contains(val)
}
}
import java.util.HashSet;
import java.util.Set;
public class TwoSumA implements TwoSum {
private int[] arr;
private int length;
private Set s;
public TwoSumA(){
this.arr = new int[50];
this.length = 0;
this.s = new HashSet<Integer>() ;
}
public void store(int input ){
arr[length] = input;
length ++;
for(int i = 0 ;i <= length -1; i ++){
s.add(new Integer(input + arr[i])) ;
}
}
public boolean test(int val){
// for( int i = 0 ; i <= length - 1; i ++){
// for( int j = 0; j <= length - 1; j ++){
// if( arr[i] + arr[j] == val)
// return true;
// }
// }
// return false;
if( s.contains(new Integer(val))) return true;
else return false;
}
}
Here is C++ version of solution.
If I can use the hashtable with load factor close to 1. This algorithm will run in O(N) where N is the number of elements in the hashtable.
In this solution, I used map, which gives O(log N) search time.
Therefore, the running time is O( N log N).
#include <map>
#include <iostream>
using namespace std;
class TwoSum {
public:
void store(int input)
{
if (hashtable.find(input) == hashtable.end())
{
hashtable[input] = input;
}
}
bool test(int val)
{
map<int, int>::iterator iter;
for (iter = hashtable.begin(); iter != hashtable.end(); iter++)
{
int cur = iter->second;
int left = val - cur;
if (hashtable.find(left) != hashtable.end())
return true;
}
return false;
}
private:
map<int, int> hashtable;
};
- randomCoder1988 April 08, 2015