Testpress Python Software Developer Interview Questions and Answers

Interview preparation tips for other job seekers - Given an array arr[] consisting of N positive integers representing the ratings of N children, the task is to find the minimum number of candies required for distributing to N children such that every child gets at least one candy and the children having the higher rating get more candies than its neighbours.

Examples:

Input: arr[] = {1, 0, 2}
Output: 5
Explanation:
Consider the distribution of candies as {2, 1, 2} that satisfy the given conditions. Therefore, the sum of candies is 2 + 1 + 2 = 5, which is the minimum required candies.
Input: arr[] = {1, 2, 2}
Output: 4
Approach: The given problem can be solved by using the Greedy Approach. Follow the steps below to solve the problem:
Initialize an array, say ans[] to store the amount of candies assigned to every child, and initialize it with 1 to every array element ans[].
Traverse the given array
arr[] and if the value of arr[i + 1] is greater than arr[i], then update the value of ans[i + 1] as ans[i] + 1.
Traverse the given array from the back
and perform the following steps:
If the value of arr[i] is greater than arr[i + 1] and the value of ans[i] is less than or equal to ans[i + 1], then update the value of ans[i] as ans[i + 1] + 1.
After completing the above steps,
print the sum of array
ans[] as the resultant sum of candies.
Below is the implementation of the above approach: