The first-round interviewer was really nice, but the problem was super long. Reading and understanding the problem plus the examples can take maybe 20 minutes. Roughly, it is merging two trees (YAML files), where every node has merge rules, and there are a lot of rules. The approach is DFS plus rule matching.
The second-round interviewer gave me a knapsack problem, but for this one DP or DFS with caching may not be as good as a greedy. You are given the value of each item and the count of each item, every item has a weight of 1, and you are given a max weight W and asked for the maximum total value. The greedy approach is O(n log n), DP is O(n x W), and the optimal solution is quickselect at O(n).
Discussion
Loading comments…