Hi, I got one of my friends who works at Google to do a mock interview for me and he hit me with this question.
Given 2 numbers, N & K, Create all binary strings of length N which satisfy following condition: Product of consecutive bit pairs should sum to K.
e.g.: N = 5, K = 2:
[11100, 00111, 11101, 11011, 10111, 01110]I couldn't find it on the online, so posting here. He was kind enough to give a decent hint while closing the interview and I have coded up a solution based on the hint but I want to get my solution reviewed.
public List<String> pairWiseSumOfProduct(int N, int K) {
List<String> res = new ArrayList<>();
res.addAll(solve(N, K, 1));
res.addAll(solve(N, K, 0));
return res;
}
private List<String> solve(int n, int k, int b) {
List<String> res = new ArrayList<>();
if (n <= k || k < 0) return Collections.emptyList();
if (n == 1) return List.of(b+"");
for (String s: solve(n - 1, k - b, 1)) res.add(b + s);
for (String s: solve(n - 1, k, 0)) res.add(b + s);
return res;
}Comments (2)
