I was asked this question in Amazon Bangalore interview for SDE-3. I would love to understand the optimal solution for this problem.

Problem :

Given a list of items such that each item has a number of attributes and values defined, find the minimun number of attributes which uniquely idenitfy any item. The number of items and number of attributes could vary in the input.

Example

Given items = [ "I1" : {"k1":"x1", "k2":"y1", "k3":"z1"}, "I2" : {"k1":"x2", "k2":"y1", "k3":"z1"}, "I3" : {"k1":"x1", "k2":"y2", "k3":"z2"}, "I4" : {"k1":"x2", "k2":"y2", "k3":"z1"} ]

Any of k1, k2, k3 alone is not unique across items so a single attribute is not enough. Combination of K1 and K2 is unique. We need to know only the value of k1 and k2 to uniquely identify an item. Combination of k1 and k2 is unique across all the items.

TestCase :

Input: items = [ "I1" : {"k1":"x1", "k2":"y1", "k3":"z1"}, "I2" : {"k1":"x2", "k2":"y1", "k3":"z1"}, "I3" : {"k1":"x1", "k2":"y2", "k3":"z2"}, "I4" : {"k1":"x2", "k2":"y2", "k3":"z1"} ]

Output: keys = [k1, k2]

Solution:

I can only think of a brute force solution where we try all the combinations of attributes. We can slightly improve the brute force by trying a binary search for the count of attributes. for example if there are N attributes then we can try if we get unique combination with N/2 keys. If yes then try to find unique combination with N/4 keys otherwise try to find unique combination with 3N/4 keys.

I dont think this is the correct approach though as time complexity of this solution is very high (higher than !N ).