Location: Moutain View, California
Problem:
You are given a multi-dimensional array with each index consisting of two attributes (Score, Answers)
Each element in the array represents the test results of a student on a True or False exam. Each question is worth exactly one point.
Answers is a boolean array consisting of True or False values, representing answers the student gave to a test. Example: [True, False, True]
Scores is an integer 0 <= scores <= len(Answers) which represents how many questions they got correct.
Assuming everybody got the same test, by reconstructing these answers, what is the most amount of points I can score with 100% certainty?Example:
Input: [[1,[True,False]], [0,[True,True]]]
Output: 2
Explanation:
Since the second student scored 0 points on [True, True], this implies the correct answer key was [False, False], which grants us a score of 2 questions correct.
---
Input: [[2,[True, True, True]], [1,[True, False, True]], [1,[False, True, True]], [1,[False, False, False]]]
Output: Return 3.
Since the 2,[True,True,True] answers differs from [1,[True,False,True]] by one, its determined the middle questions correct value is True.
Using that we can also conclude the only answer correct on [1,[False, True, True]] is the middle one, therefore the remaining answers must be the inverse.
And the answer key must be: [True, True, False] -> Return 3
---
Input: [[4, [True, False, True, False, True]], [3,[True, True, True, False, True]], [1,[False, False, True, True, False]]]
Output: 5
The answer to the second question (1-indexing) must be False by comparing the 1st and 2nd student.
Since the 2nd question is False, this is the only question the last student got correct.
Therefore the remaining correct answers must be the last students inverse.
Leaving the correct answer key as: [True, False, False, False, True] -> Return 5
---
Input: [[1,[True, True, True]], [1,[True, False, False]]]]
Output: 2.
Explanation:
If 1,[True, False, False] then 2,[False, True, True] must be valid.
Therefore we can conlude the first answer is False by comparing it to the first student.
Afterwards we cannot infer anything else about the answers. One of the remaining values must be True and one is False.
Yet we cannot say which is which with 100% certainity.
But since 2,[False, True, True] is already valid, we can return 2.
Follow Up:
What if an entry in the answers array could be blank, representing the student did not answer that question?
Example:
[[2,[False, Blank, True]],[1,[Blank, False, Blank]] => Return 3. Correct answer key is [False, False, True]
[2,[False, False, True]],[1,[Blank, False, True],[1,[False,Blank,False]]] => Return 3. Correct answer key is [False, True, True]**2nd Testcase:**
Input: [2,[False, False, True]],[1,[Blank, False, True],[1,[False,Blank,False]]]
Output: Return 3. Correct answer key is [False, True, True]
Explanation:
The first number must be false because by contradiction if 2,[False, False, True] and 1 [Blank, False, True].
Then the first question as False was correct.
The third number must be True because if the first number was False then 1,[False, Blank,False].
Then False was the incorrect answer for the last question, therefore the correct was True.
The second number must be True because if 2,[False, False, True] and the first number is already False, the last number is True.
Then we must of gotten the second number wrong, therefore it is True for the second number.
This leads to [False, True, True] as a certainty and therefore a total of 3.