Councyl Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Same logic as the other answer, but correct implementation. The other answer will result in multiple answers being printed in certain cases, and will in fact give an incorrect answer for certain cases as well.
Eg:
GOOD,11,12
BAD,11,13
BAD,12,14
will give multiple mapping in the other code, where as there is a distinct answer.
def main():
n = int(input())
good_nums = set([])
bad_nums = set([])
maybe_bad_nums = []
all_nums = set([])
for _ in range(n):
s = input().strip().split(",")
tag = s[0]
nums = [int(k) for k in s[1:]]
all_nums.update(nums)
if tag == "GOOD":
for k in nums:
good_nums.add(k)
else:
maybe_bad_nums.append(nums)
ans = solve(good_nums, maybe_bad_nums)
if ans:
print(ans)
else:
for i in sorted(all_nums):
final_tag = "GOOD" if i in good_nums else "BAD"
print(str(i) + ": " + final_tag)
def solve(good_nums, maybe_bad_nums):
ans = None
for maybe_bad_num_list in maybe_bad_nums:
maybe_bad = set(maybe_bad_num_list)
definitely_bad = list(maybe_bad - good_nums)
if len(definitely_bad) > 1:
# We don't return from here because it is possible that
# some other tagging makes the answer "NO CONSISTENT"
# which is stronger than multiple mapping
ans = "MULTIPLE MAPPING"
elif len(definitely_bad) == 0:
# We can return from here since a solution does not exist
return "NO CONSISTENT"
return ans
if __name__ == "__main__":
main()
Output:
2
BAD,10,11
BAD,11,12
MULTIPLE MAPPING
2
GOOD,10,11,12
BAD,10,11
NO CONSISTENT
2
GOOD,10,11
BAD,11,12
10: GOOD
11: GOOD
12: BAD
3
GOOD,11,12
BAD,11,13
BAD,12,14
11: GOOD
12: GOOD
13: BAD
14: BAD
I think the thing to realise here is that if there are multiple IDs that could be bad, then there are multiple mappings - any one of them could be bad to validate everything (leaving the others in a state of "not enough info").
With that in mind, you need to construct two sets - one of things that must be good, because they were in a GOOD class, and one of things that could be bad, because they were in a BAD class.
Your answer then comes from simple set difference:
Python 2.7
inp = " "
good = set()
potentialbad = set()
#Parse input in good and potential bads
while inp is not "":
inp = raw_input()
csv = inp.split(",")
classification = csv[0]
ids = [x.strip() for x in csv[1:]]
if(classification == "GOOD"):
good.update(ids)
else:
potentialbad.update(ids)
#Get the possible bads through set subtraction
if len(potentialbad) > 0:
bad = potentialbad - good
if len(bad) == 0:
print "NOT CONSISTENT"
elif len(bad) >= 2:
print "MULTIPLE MAPPING"
else:
for g in sorted(good):
print "{}, GOOD".format(g)
for b in bad:
print "{}, BAD".format(b)
else:
for g in sorted(good):
print "{}, GOOD".format(g)
The goal is to build a list of all GOOD ids and all BAD ids and the remaining UNKNOWN ids.
- Matt November 08, 2017I'd start by putting all IDs found on GOOD rows into the good list.
Then I'd remove all good ids from the BAD rows.
If any bad row has only a single ID remaining after the known good ids are removed, that id must be bad, so add it to the BAD list.
If any remaining BAD rows still have multiple IDs, those are the ids that you cannot reasonably conclude as BAD or GOOD so they would be the MULTIPLE MAPPING results.
If any BAD rows have 0 IDs after the known good ids are removed then that would be the NO CONSISTENT case.