Interview Question
Country: India
Sorting the list O(nlog(n)) + using Binary Search O(log(n)) = O(nlog(n))
Implementation in Python/3.6.1
def binary_search(l, number, i, j):
if i >= len(l) or j < 0:
return False
if i == j and l[i] != number:
return False
mid = int((i + j) / 2)
if l[mid] == number:
return True
if number <= l[mid]:
return binary_search(l, number, i, mid - 1)
return binary_search(l, number, mid + 1, j)
def find_numbers(ul, number):
l = sorted(ul)
min_ = l[0]
end_index = len(l) - 1
for i in range(min_, number - min_ + 1):
if binary_search(l, i, 0, end_index) and binary_search(l, number - i, 0, end_index):
return [i, number - i]
return None
if __name__ == '__main__':
unsorted_list = [10, 1, 3, 5, 2, 6, 11]
number = 18
print(find_numbers(unsorted_list, number))
number = 5
print(find_numbers(unsorted_list, number))
We can put the accessed items in a hash table for fast access. The total cost would be O(n log n).
#include <iostream>
#include <time.h>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
const int nums = 100;
const int goal = 150;
const int mod = 100;
int main()
{
srand(time(0));
vector<int> vec (nums);
unordered_map<int, int> mpn;
int i = 0;
for(i = 0; i < nums; i++)
vec[i] = rand() % mod;
for(i = 0; i < nums; i++)
{
if(mpn.count(goal - vec[i]) > 0)
cout << mpn[goal - vec[i]] << " and " << i << " make the goal." << endl;
if(!mpn.count(vec[i]))
mpn[vec[i]] = i;
}
}
The fastest solution: O(N).
Loop the array and keep each number visited in an hash table. For each number in the array check the hash if we have in the hash sum-currentnumber, if we do, we are done.
std::pair<int, int> findNumbersSumEqual(const std::vector<int>& numbers, int sum)
{
std::unordered_set<int> visited;
for(size_t i=0; i<numbers.size(); ++i) {
// search the diff in the map
int secondNumber = sum - numbers[i];
if(visited.count(secondNumber)) {
// we already saw this number before in the array
return {numbers[i], secondNumber};
} else {
// Keep this number in the hash
visited.insert(numbers[i]);
}
}
return {INT_MAX,INT_MAX}; // No match was found
}
- Vir Pratap Uttam October 13, 2017