| There are two collections of o... | ||||||||||
|
30 Day Risk-Free Guarantee:
100% money back if you're unsatisfied. Book (308 Pages):
 Video (One Hour):
 Resume Review (24 - 48hr)
All Products / Services
|
||||||||||
There are two collections of objects C1 and C2. C1 can be any thing - Flowers, Fruits, Foot Balls etc.. and C2 also same. How can you find out if C1 is a subset of C2 or C2 is a subset of C1 or both are equal? Provide algorithm, code and test cases.
The interviewer was expecting a linear algorithm - the algorithm with a time complexity of O(n)
7
Use hashtable to store C1 and C2. Linear time to solve the problem. the downside is that it needs extra memory. Can anybody give an in place O(n) solution?
I can also think of hashtable only. But extra memory required is not O(n). It is order of types of objects present. So i think it is quite acceptable.
good solution
# have an associative array called assocArray[]
# Pass 1: put all the words of set C1 in the assocArray[]
# Pass 2: check if the current word from C2 is there in the array or not
* at any point if you find a word from C2 not existing in the assocArray, exit() declaring that C2 is not a subset of C1
* if the whole set C2 gets exhausted, declare C2 is a subset of C1.
If we kno the complete set of possible objects...den we can have counter for each object/.....
For each element in c1 increment the corresponding counter.....
For each element if c2 decrement the corresponding counter.....
Scan counter,,..
If each element is 0 then c1=c2.
else If all counters are positive or zero....c1 is subset of c2
else If all counters are negative or zero....c1 is subset of c2
else nothing
The gist of the approach is the same. Although I wonder if there's a better solution to this problem.
items1 = set([1, 3, 4])
items2 = set([4, 3, 1])counts = dict([(item, 1) for item in items1])
for item in items2:
counts[item] = 3 if item in counts else 2items1Subset = False; items2Subset = False
for item in counts:
if counts[item] == 2:
items1Subset = True
elif counts[item] == 1:
items2Subset = Trueif items1Subset and items2Subset:
print "Items1 and Items2 are different"
elif items1Subset:
print "Items1 is subset"
elif items2Subset:
print "Items2 is subset"
else:
print "Items1 and Items2 are identical"
In thi question, C1 and C2 can have different objects at the same time. That means, C1 can have Apples, Oranges, Roses, Coke bottles, Some Integer numbers etc at the same time. Similarly, C2 can have different objects.
The interviewer was asking for test cases if all the objects were Integers. Also, the test cases for mixed collection of objects.