Google (Phone Screen) | SDE L4 | Canada | March 2022
Anonymous User
615
Phone Screeninginterview questionInterview

Was asked the following variant of Combination Sum on phone screen. I wasn't super familiar with the combination sum/backtracking family of problems, had assumed that this must be a DP problem; panic ensued, and I flunked the interview. Long way to go!

Question:
Given a number N, generate all possible sequence of increasing numbers less than or equals to N such that the difference between any two of them are powers of two. The resulting set of sequences must cover all powers of two within the limit of the given number. The sequences can be returned in any order.

Example:
For N=5, the following are the target sequences:

{(1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5), (1, 2, 3, 5), (1, 2, 4), (1, 3), (1, 3, 5), (1, 5)}

Explanation: The first sequence covers the differences of 2^0, 2^1 and 2^2.

For N=10, the output is the following:

{(1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6, 7), (1, 2, 3, 4, 5, 6, 7, 8), (1, 2, 3, 4, 5, 6, 7, 8, 9), (1, 2, 3, 4, 5, 6, 7, 8, 9, 10), (1, 2, 3, 4, 5, 6, 7, 8, 10), (1, 2, 3, 4, 5, 6, 7, 9), (1, 2, 3, 4, 5, 6, 8), (1, 2, 3, 4, 5, 6, 8, 10), (1, 2, 3, 4, 5, 6, 10), (1, 2, 3, 4, 5, 7), (1, 2, 3, 4, 5, 7, 9), (1, 2, 3, 4, 5, 9), (1, 2, 3, 4, 6), (1, 2, 3, 4, 6, 8), (1, 2, 3, 4, 6, 10), (1, 2, 3, 4, 8), (1, 2, 3, 5), (1, 2, 3, 5, 7), (1, 2, 3, 5, 9), (1, 2, 3, 7), (1, 2, 4), (1, 2, 4, 6), (1, 2, 4, 6, 10), (1, 2, 4, 8), (1, 2, 6), (1, 2, 10), (1, 3), (1, 3, 5), (1, 3, 5, 9), (1, 3, 7), (1, 5), (1, 9)}

The code I came up with for the solution is below. This of course is my interpretation of the problem after the interview, and you are free to interpret it differently, and/or come up with a better solution. I'd be curious to know!

import math

class CombinationSumPow2:
    def twosPowerRaisedTillN(self, n):
        twosPowArr = [2**i for i in range(int(math.log(n,2)+1))]
        self.n = n
        ret = set()
        self.dfs(0, twosPowArr, [1], ret)
        return ret

    def dfs(self, idx, twosPowArr, path, ret):
        if path[-1]>self.n:
            ret.add(tuple(path[:-1]))
            return
        for i in range(idx, len(twosPowArr)):
            self.dfs(i, twosPowArr[idx:], path+[path[-1]+twosPowArr[i]], ret)
Comments (3)