Solve "find pairs for sum"

I have encountered this problem 3x in the wild thus far:
  1. www.InterviewCake.com
  2. Cracking the Coding Interview
  3. www.Pramp.com

1 files changed, 19 insertions, 0 deletions

diff --git a/scratch/facebook/moderate/find-pairs-for-sum.py b/scratch/facebook/moderate/find-pairs-for-sum.py
new file mode 100644
index 000000000000..69c2fc431296
--- /dev/null
+++ b/scratch/facebook/moderate/find-pairs-for-sum.py
@@ -0,0 +1,19 @@
+import random
+
+def find_pairs(xs, n):
+    """
+    Return all pairs of integers in `xs` that sum to `n`.
+    """
+    seeking = set()
+    result = set()
+    for x in xs:
+        if x in seeking:
+            result.add((n - x, x))
+        else:
+            seeking.add(n - x)
+    return result
+
+xs = [random.randint(1, 10) for _ in range(10)]
+n = random.randint(1, 10) + random.randint(1, 10)
+print("Seeking all pairs in {} for {}...".format(xs, n))
+print(find_pairs(xs, n))