System Engineer Specialist

A thief is robbing a store and can carry a maximum weight of ‘W’ into his knapsack. There are 'N' items available in the store and the weight and value of each item is known to the thief. Considering the constraints of the maximum weight that a knapsack can carry, you have to find the maximum profit that a thief can generate by stealing items.

Note: The thief is not allowed to break the items.

For example, N = 4, W = 10 and the weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. Then the best way to fill the knapsack is to choose items with weight 6, 1 and 3. The total value of knapsack = 3 + 6 + 4 = 13.

The problem was something similar to finding the Lowest common ancestor of two nodes in a tree. There were various parts to the problem where we needed to find LCA in a DAG, tree and binary search tree.

This problem was to related to finding the majority element in a array. The interviewer discussed various approaches to solve this problem. In the end he even asked to prove the correctness of Boyer-Moore Majority Voting Algorithm.

Smallest positive missing number in an unsorted array using constant space.