Interview Questions: Reductions Help Center

Learn more

Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.

Question 1

Longest path and longest cycle. Consider the following two problems

  • LongestPath: Given an undirected graph G and two distinct vertices s and t, find a simple path (no repeated vertices) between s and t with the most edges.

  • LongestCycle: Given an undirected graph G′, find a simple cycle (no repeated vertices or edges except the first and last vertex) with the most edges.
Show that LongestPath linear-time reduces to LongestCycle.

Question 2

3Sum and 4Sum. Consider the following two problems:

  • 3Sum: Given an integer array a, are there three distinct indices i, j, and k such that a_i + a_j + a_k = 0?

  • 4Sum: Given an integer array b, are there four distinct integers i, j, k, and \ell such that b_i + b_j + b_k + b_\ell = 0?
Show that 3Sum linear-time reduces to 4Sum.

Question 3

3Sum and 3Linear. Consider the following two problems:

  • 3Linear: Given an integer array a, are there three indices (not necessarily distinct) i, j, and k such that a_i + a_j = 8 \, a_k?

  • 3Sum: Given an integer array b, are there three indices (not necessarily distinct) i, j, and k such that b_i + b_j + b_k = 0?
Show that 3Linear linear-time reduces to 3Sum.
    
You cannot submit your work until you agree to the Honor Code. Thanks!