Market Survey

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Uber

Problem statement

Right Answer: For a particular question, the highly chosen option till that point in time is treated as the correct answer. If multiple options have the exact count, then out of those options, the one which was chosen recently is treated as the correct answer.

Score of a Participant: One point will be awarded for each correct answer. No negative points for wrong answers.

Instant Result: This is shared with the Participant instantly after completing his/her exam. (this is equal to the number of correct answers)

Final Result: Only the final top scorer(TOPPER) is announced along with his score.

Note: 
At the end of all M Participants completing the exam, the final correct answers get decided.
Based on these answers score of each candidate gets recalculated, and the one with the highest score is the TOPPER!!!
If more than one Participant gets the top score, then the one who attempted the exam first is treated as TOPPER.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of questions and number of participants, respectively.

The second line of each test case contains ‘N’ space-separated integers representing the default answers.

The following ‘M’ lines of each test case contain ‘N’ space-separated integers, denoting answers given by each participant.

Output Format:

For each test case, print two lines.

The first line for each test case contains ‘M’ space-separated integers representing the instant results of every participant.

The second line of each test case contains a single integer representing the TOPPER.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer in the form of an array of length ‘M’+1. The first ‘M’ integers represent instant results, and the last element denotes the TOPPER.

Constraints:

1 ≤ T ≤ 10
1 ≤ M, N ≤ 1000
0 ≤ responses and default answer ≤ 4

Time limit: 1 Sec
Sample Input 1 :
2
10 2
1 2 3 4 1 2 3 4 1 2
1 2 4 4 3 2 3 1 1 3
2 3 4 4 1 2 3 1 1 2
4 3
1 2 3 4
2 1 4 3
4 1 2 3
1 3 2 1
Sample Output 1 :
6 6 
1
0 2 0 
1
Explanation For Sample Input 1 :
For First Case - 

Number of questions = 10
Number of Participants = 2
Default answers : 1 2 3 4 1 2 3 4 1 2
(Latest Key is same as Default answers)
First Participant answers : 1 2 4 4 3 2 3 1 1 3
Right answers : 6 (= Instant result of first Participant)
Latest Key : 1 2 4 4 3 2 3 1 1 3
Second Participant’s answers : 2 3 4 4 1 2 3 1 1 2
Right answers : 6 (= Instant result of second Participant)
Latest Key : 1 2 4 4 1 2 3 1 1 2
Final key : 1 2 4 4 1 2 3 1 1 2
(Final Key is same as Latest Key at the end of all Participants completing the exam)
Right answers of Participant1 = Right answers of Participant2 = 8.
So topper is the first Participant with a score of 8.

For the second case - 

Number of questions = 4
Number of Participants = 3
Default answers : 1 2 3 4
(Latest Key is same as Default answers)
First Participant answers : 2 1 4 3
Right answers : 0 (= Instant result of first Participant)
Latest Key : 2 1 4 3
Second Participant’s answers : 4 1 2 3
We will continue similarly and get instant answers for all participants and find the TOPPER.
Sample Input 2 :
2
2 2
2 1
1 3
1 2
4 1
4 2 2 1
3 0 1 1
Sample Output 2 :
0 1 
1
1 
1
Hint

Try implementing as per the instructions in the statement.

Approaches (1)
Brute Force

We just follow the instructions of the statement and for each participant, we first calculate the most frequent answer for that participant and then publish the instant results. After we have found instant results for each participant then we find out the topper which has the maximum number of correct answers as compared to the final frequent answers. Implementation details are as per the following algorithm.

 

Algorithm:

 

Given Function

  • Declare and initialize integer array instant = default
  • Declare integer array ans
  • Declare 2D integer array freq of size N * 4
  • Declare integer array maxFreq of size n initialized to all zeroes
  • Iterate over i from 0 to m-1
    • Declare and initialize integer correct = 0
    • Iterate over j from 0 to n-1
      • If survey[i][j] == instant[j]
        • Increment correct
    • Append correct to ans
    • Iterate over j from 0 to n-1
      • If survey[i][j] = 0
        • Continue
      • Increment freq[j][survey[i][j]-1]
      • Declare and initialize integer frequency = freq[j][survey[i][j]-1]
      • If frequency > maxFreq[j]
        • maxFreq[j] = frequency
        • instant[j] = survey[i][j]
  • Declare and initialize integer topper = 0, maxCorrect = 0
  • Iterate over i from 0 to m-1
    • Declare and initialize integer correct = 0
    • Iterate over j from 0 to n-1
      • If survey[i][j] == instant[j]
        • Increment correct
    • If correct > maxCorrect
      • maxCorrect = correct
      • topper = i+1
  • Append topper to ans
  • Return ans
Time Complexity

O(N * M) where 'N' and 'M' are no. of questions and no. of participants.

 

We need to iterate over all the participants and for each participant we look for all ‘N’ questions. So total time is O(M) * O(N) = O(M * N).

Space Complexity

O(N + M) where 'N' and 'M' are no. of questions and no. of participants.

 

We need space to store variables like instant, freq, which are O(N) in size, and ans which is O(M) in size. So total space required will be O(N) + O(M) = O(N + M).

Code Solution
(100% EXP penalty)
Market Survey
Full screen
Console