Microsoft Interview Question Software Engineer in Tests
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.
# 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 2
items1Subset = False; items2Subset = False
for item in counts:
if counts[item] == 2:
items1Subset = True
elif counts[item] == 1:
items2Subset = True
if 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"
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?
- Anonymous October 09, 2008