-2

During an interview today I was asked to write a function that accepted an array of integers and return the positions of two values in the array that the sum was 10.

My code was

C#

public string ReturnIntegers(int[] arrayOfIntegers)
{
   for(int j = 0; j < arrayOfIntegers.Length - 1; j++)
   {
      for(int k = j + 1; k < arrayOfIntegers.Length; k++)
      {
          sum = arrayOfIntegers[j] + arrayOfIntegers[k];
          if(sum == 10)
             return j + "," + k;
      }

}

Assuming the array entered has more than 2 values. My interviewer said that this had a magnitude of n^2 if the array contained a billion values. What is a better solution (performance) to support a large number of values.

  • 2
    recommended reading: Why do interview questions make poor Programmers.SE questions? – gnat Oct 21 '15 at 20:10
  • 1
    For larger arrays creating a map of "Potential match -> position of pair" will reduce complexity from n^2 to n provided map building and access is constant. – Ordous Oct 21 '15 at 20:10
  • 2
    Geeksforgeeks almost always has a treatment for questions like this. – Robert Harvey Oct 21 '15 at 20:14
  • 2
    Voting to close, without a definition of "better", this is fully opinionated. "better" could mean faster, simpler, more readable, more concise, more maintainable, more robust - whatever you prefer. – Doc Brown Oct 21 '15 at 20:46
  • 2
    @DocBrown this gets especially awkward because "better" for an interview can mean any number of things. More easily maintained? Not excessively clever? Cleverly written? Concise? Using some funky LINQ? – user40980 Oct 21 '15 at 20:53
1

There are really two questions here

  1. could the algorithm have been implemented in a better/cleaner manner
  2. is there a better algorithm.

Two things leap out at me your implementation. Firstly there is nothing to handle the case where there is no soloution. The function just reaches the end without reachign a return statement. In some languages this is a compile error, in others it gives undefined behaviour. I don't know about C# specifically. The other is you are returning the result as a String, that usually isn't a very efficient way of doing things.

Regarding the algorithm the algorithm you have chosen has a complexity of order n² . So for large lists it will be slow. On the other hand it doesn't allocate any aditional memory/create any new objects and for small lists I expect it is actually the fastest soloution.

For large lists it may be better to do something like (note: this is untested and I don't code in c#)

public string ReturnIntegers(int[] arrayOfIntegers)
{
   Dictionary d<int,int> = new Dictionary<int,int>

   for(int j = 0; j < arrayOfIntegers.Length - 1; j++)
   {
      d.add(10-arrayOfIntegers[j]),j)
   }          
   for(int k = 0; k < arrayOfIntegers.Length; k++)
   {
       if (d.ContainsKey(arrayOfIntegers[k])) {
           j = d[arrayOfIntegers[k]]
           return j + "," + k;
       }
   }
   return null;
}
  • 1
    How is the better? You are looping through the array twice. Once to fill a dictionary object, then to search for a number. – Kyle Johnson Oct 21 '15 at 21:48
  • Thank you also for the feedback. You are correct. I did't check for no solution. Forgive me this was an online interview and we used collabedit – Kyle Johnson Oct 21 '15 at 21:49
  • Assuming an input with exactly one correct answer, your code performs on average approximately n²/4 comparisions (where n is the number of items in the list). My code performs n dictionary insertions followed by an average of n/2 dictionary lookups. For large lists this will be a much smaller number of operations and hence much faster. – Peter Green Oct 22 '15 at 12:01
  • If you put your if(d.containsKey()) in the first loop I think you can do it in O(n) time – Ewan Oct 22 '15 at 12:05
  • @Peter - You might have me on performance if the array is large but your code will use more memory. Your dictionary object will take up more memory than my 3 int variables. I guess that is the trade-off. stackoverflow.com/questions/1898161/memory-vs-performance – Kyle Johnson Oct 22 '15 at 17:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.