I was asked such an interview question.

Given an unsorted array of positive integers, and also a target value K, find two elements that sum up to K.

So I suggested, sort the array first, and then start from the last (maximum) element that is smaller than K, x_max and then use binary search to find K-x_max. Well the complexity for sorting is O(n log n) and for finding is another O(n log n). Any improvement if the array is sorted? I stuck there, 5 seconds later, he tipped me with something like how about using two index pointers. WOW, great hint. Now the complexity for this step is O(n). Below is one solution.

#include <iostream>
using namespace std;
void quickSort(int *arr, int left, int right) {
if(left>=right) {return;}
int Start=left;
int End = right;
int pivot=(left+right)/2;
int pivotV=*(arr+pivot);
int tmp;
while(left<right) {
if(*(arr+left) <= pivotV) {
left++;
}
if(*(arr+right)>=pivotV) {
right--;
}
if(*(arr+left)>pivotV && *(arr+right)<pivotV) {
tmp=*(arr+left);
*(arr+left)=*(arr+right);
*(arr+right)=tmp;
left++;
right--;
}
}
*(arr+pivot)=*(arr+right);
*(arr+right)=pivotV;
quickSort(arr, Start, left-1);
quickSort(arr, right+1, End);
}
void ksum(int *arr, int len, int k) {
int left, right, ktmp;
left=0;
right=len-1;
while(left<right) {
ktmp=*(arr+left)+*(arr+right);
if(ktmp==k) {
cout << *(arr+left) << " + " << *(arr+right) << " = " << k << endl;
return;
} else if(ktmp>k) {right--;} else {left++;}
}
cout << "Couldn't find the two elements!\n";
return;
}
int main() {
int a[10]={10,3,4,9,8,7,2,1,5,6};
quickSort(a, 0, 9);
ksum(a, 10, 12);
return 0;
}