Given an array of integers (OR a linked list), and an integer K - write an algorithm to find two elements of the array which sum up to K.
* Time complexity of Theta(N) where N is the amount of elements in the array/list.
* The algorithm can access the array / list only once.
* The size of the array / list is unknown beforehand.
* The elements should sum up to K exactly.

Question

Given an array of integers (OR a linked list), and an integer K - write an algorithm to find two elements of the array which sum up to K. 
* Time complexity of Theta(N) where N is the amount of elements in the array/list.
* The algorithm can access the array / list only once.
* The size of the array / list is unknown beforehand.
* The elements should sum up to K exactly.

Sigiloso · Accepted Answer

iterate linearly over the array and insert elements into HashMap (can use chain hashin o open addressing - doesn't matter).
for each element P in the Hashmap, find the element Q where Q = K-P.
*insertion and search in a Hashmap use time complexity of O(1) amortized on average, thus overall time complexity of the algorithm is: O(2*N) = O(N) as requested.

Intel Corporation

Pergunta de entrevista da empresa Intel Corporation

Resposta da entrevista

Empresas seguidas

Buscas de vagas