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; }