Problem Statement

Google recently asked about this problem.
Given a list of numbers and a number k, return whether any two digits from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Understanding the problem

We need to find if the sum of any two numbers from the list adds up to k.
Let's pick up any number A from the list of numbers
Number = A

To get sum as value k, the expected number to be present in the list corresponding to A should be (k - A)
Expected Number = k - A

Selected and expected number should add up to k
Number + Expected Number = A + (k-A) = k
We find if expected number present in the list for each number.

Example

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
k = 17
Number = 10
Expected Number = 7
We find the expected value of 7 is present in the numbered list, and hence, we output true.

HashSet in C#

HashSet is an unordered collection containing unique elements.

  1. It has the standard collection operations Add, Remove, Contains, but since it uses a hash-based implementation, these operations are O(1). (As opposed to List for example, which is O(n) for Contains and Remove.)
  2. HashSet also provides standard set operations such as union, intersection, and symmetric difference.
  3. A HashSet holds a set of objects, but in a way that it allows you to easily and quickly determine whether an object is already in the set or not. It does so by internally managing an array and storing the object using an index which is calculated from the hashcode of the object.

Take a look below

    // START: Basic Add and Union Operations
    HashSet<int> theSet1 = new HashSet<int>();
    theSet1.Add(1);
    theSet1.Add(2);
    theSet1.Add(2);
    // theSet1 contains 1,2

    HashSet<int> theSet2 = new HashSet<int>();
    theSet2.Add(1);
    theSet2.Add(3);
    theSet2.Add(4);
    // theSet2 contains 1,3,4

    theSet1.UnionWith(theSet2);
    // theSet1 contains 1,2,3,4
    
    // END: Basic Add and Union Operations
    
    // START: Handling Items already present in the set
    bool added = theSet1.Add(2); // added is true
    added = theSet1.Add(2); // added is false
    // END: Handling Items already present in the set

Implementation of Sets

There are different implementations of Sets.

  1. Some make insertion and lookup operations super fast by hashing elements. However, that means that the order in which the elements were added is lost.
  2. Other implementations preserve the added order at the cost of slower running times.

The HashSet class in C# goes for the first approach, thus not preserving the order of elements.

  1. It is much faster than a regular List. Some basic benchmarks showed that HashSet is decently faster when dealing with primary types (int, double, bool, etc.).
  2. It is a lot faster when working with class objects. So that point is that HashSet is fast.

Drawbacks of using Hashset

  • The only catch of HashSet is that there is no access by indices. To access elements you can either use an enumerator or use the built-in function to convert the HashSet into a List and iterate through that.

Solution

Below program uses HashSet to solve the mentioned problem of finding whether any two numbers from the list add up to k.
Below code can be run at rextester

// http://rextester.com/LCV10786
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
/*
This problem was recently asked by Google.
Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var numberedList = new List<int>(){10, 15, 3, 7};
            var hashNumberedList = new HashSet<int>();
            var k = 17;
            var found = false;
            foreach(var number in numberedList){
                var expectedNumber = k - number;
                if(hashNumberedList.Contains(expectedNumber))
                {
                    found = true;
                    break;
                }
                if(!hashNumberedList.Contains(number))
                {
                    hashNumberedList.Add(number);
                }
            }
            Console.WriteLine(found);
        }
    }
}