Bloomberg L.P. Interview Question: Given a sorted sequence of 1 ... | Glassdoor

Interview Question

Financial Applications Engineer Interview New York, NY

Given a sorted sequence of 1 million numbers, write a

program to find all pairs of numbers that add to 10.

1

x=rand(1000000,1);
y=10*x;
x=ceil(y);
y=length(x);

a=1;
for z=1:y
for z1=1:y
if (x(z)+x(z1))== 10
r(a,1)=x(z);
r(a,2)=x(z1);
a=a+1;
end
end
end

MATLAB'd

ayaz khan on Feb 1, 2013
0

&amp; if they want non repetitive numbers:

[code cont'd]

g=size(r);
b=g(1,1)-1;
c=g(1,2);
q=1;
for d=1:b
if r(d,1)~=r(d+1,1) &amp;&amp; r(d,2)~=r(d+1,1)
l(q,1)=r(d,1);
l(q,2)=r(d,2);
q=q+1;
end
end

ayaz khan on Feb 1, 2013
1

Not really optimal.
I'll give you my approach:
1) First you do binary search, to located the Last 10.
2) Create 2 pointers, 1 at the start, and the other from the last 10.
3) Bring them closer together creating a new array of all pairs summing up to 10.
4) If 1 pointer gets out of sync, save the index of that pointer (only once), and skip all same numbers till the pointers get in sync again.
5) Recurse within all the indices you skipped.
6) Return the list of pairs.

John. on Feb 19, 2013