## Linkedin Interview Question for Senior Software Development Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

code

``````interface TwoSumInterface{
public void store(int value);
public boolean test(int value);
}

public class TwoSumInterfaceImpl implements TwoSumInterface {
private Set<Integer> localStore = new HashSet<Integer>();

@Override
public void store(int value) {
}

@Override
public boolean test(int newValue) {
for(int currentNumber:localStore){
if(localStore.contains(newValue - currentNumber)) {
return true;
}
}
return false;
}
}``````

Store Time Complexity: O(1), Space Complexity : O(n)
Test Time Complexity O(n), Space Complexity : O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can solve this problem with O(n) for test() and O(log(n)) for store().
- For store(): use insert() function of set to always have a sorted set
- For test(): use left and right variable to narrow down the range of finding the 2 target numbers.

``````#include <iostream>
#include <vector>
#include <set>

using namespace std;

class NumberManager {
public:
void store(int number){
numbers.insert(number);
}
bool check(int number){
set<int>::iterator left = numbers.begin();
set<int>::iterator right = --numbers.end();

while (left != right){
if (number == *left + *right){
return true;
} else if (number > *left + *right){
left++;
} else {
right--;
}
}
return false;
}
void printNumbers(){
for (set<int>::iterator left = numbers.begin(); left != numbers.end(); left++){
cout << *left << " ";
}
cout << endl;
}
private:
set<int> numbers;

};

int main(){
NumberManager test;
test.store(1);
test.store(3);
test.store(2);
test.printNumbers();
cout << test.check(3) << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Your code does not pass the test for 4. 4 should return true but returns false.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach 1: use a hashtable, O(1) to insert and O(n) to check
Approach 2: any form of sorted container, AVL, B-Tree, ... for O(lg(n)) insert and with vucuong020195 method to test

From the big-o 1) looks better, I'm not sure if that's really the case in real world - how ever, depends very much on the tree implementation, could be quite bad if with lots of pointers etc...

Comment hidden because of low score. Click to expand.
0
of 0 vote

You could have used a HashSet to insert values in the data store.
In the test, you should have iterated over all the values of the HashSet and check if
(target - hashSet[i]) is present in the HashSet.
If yes, then return true or else return false.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer really depends on the frequency of operations and space:

* If test() is expected to be called more number of times than store(), then it is better to insert all combination of sums into unordered_set during store() itself. Each store operation would be O(n) to add all the numbers already stored with the input to store(). Then test() would be an O(1) operation.
* If store() is called more than test() (num stores > num tests), then insert the input to store() in unordered_set. Store() would be O(1), test would be O(n).
* If we have no additional space for unordered_set, make store() O(logN) by sorted insert and test() would be O(N).

Comment hidden because of low score. Click to expand.
0
of 0 vote

- use a TreeSet - which ensures guaranteed ordering. inserts take O(log(n))
- for test - O(n) - dump it to an object list and use two pointers from first and last to get the sum. If no extra space need to be used then use containsKey method for each value of n. i.e. O(nlog(n))

``````import java.util.TreeSet;

public class TwoSumImpl {

private TreeSet<Integer> cache = new TreeSet<Integer>();

public void store(int input) {
// store the elements in the TreeSet
}

public boolean test(int val) {
Object[] numbers = cache.toArray();
int i = 0;
int k = numbers.length - 1;
while (i < k) {
if (((Integer) numbers[i] + (Integer) numbers[k]) == val) {
return true;
} else if (((Integer) numbers[i] + (Integer) numbers[k]) < val) {
i += 1;
} else {
k -= 1;
}
}
return false;
}

public static void main(String... args) {
TwoSumImpl twoSum = new TwoSumImpl();

twoSum.store(1);
twoSum.store(2);
twoSum.store(3);
boolean status = twoSum.test(4);
if (status == true) {
System.out.println("Verified the implementation");
} else {
System.out.println("Could not find the number");
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I would use HahMap for O(n) complexity. So that for storing data it is O(1) and for testing it is O(n), as we can check the complement of the number.
{{ test - value(key-test) }}
for the length of hash keys

Comment hidden because of low score. Click to expand.
0
of 0 vote

Filtering based on the difference. Slightly similar to a java solution suggested somewhere above.

``````// can be local or public
val localStore = new ArrayBuffer[Int]
def store(number: Int) = localStore.append(number)
def test(newNumber: Int): Boolean = localStore.exists( number => localStore.contains(newNumber - number))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class TwoSum
{
std::unordered_map<int, bool> _store;

public void Store(int input)
{
_store[input] = true;
}

public bool Test(int val)
{
for(auto it = _store.begin(); it < _store.end(); it++)
{
int dif = val - it.first;
if (_store.find(dif) != _store.end())
{
return true;
}
}

return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class TwoSum {
public:
void Store(int n)
{
++map_[n];
}
bool Test(int sum)
{
for (auto el : map_) {
int remainder = sum - el.first;
auto it = map_.find(remainder);
if (it != map_.end()) {
if (remainder != el.first ||
it->second > 1)
{
return true;
}
}
}
return false;
}

private:
unordered_map<int, int> map_;
};``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.