Interview Question
Country: India
I made mistake. The program assumes no two kids have the same score. If they have, the picked list should be like:
{lowest ,lowest, highest, sec lowest, sec highest, sec highest,...}
Basically, you start at the lowest end, continue to pick up kids with the same score until the next kid has a higher score. Then you start to pick up kids at the highest end until the next kid has lower score. And repeat the cycle until the all kids are picked.
This can be solved by topological sort. Build a graph by scanning the rating array from left to right:
g[i][j] = true => c[i] must be less to c[j].
Then we can assign the candies according to the topological order.
#include <iostream>
#include <stack>
using namespace std;
const int MAXN = 100000;
int g[MAXN][3];
int indeg[MAXN];
int val[MAXN];
int c[MAXN];
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> val[i];
if (n == 1) {
cout << 1 << endl;
return 0;
}
for (int i = 0; i < n - 1; i++) {
if (val[i] < val[i + 1]) {
g[i][++g[i][0]] = i + 1;
indeg[i + 1]++;
} else if(val[i] > val[i + 1]) {
g[i + 1][++g[i + 1][0]] = i;
indeg[i]++;
}
}
stack<int> sta;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) {
c[i] = 1;
sta.push(i);
}
}
while (!sta.empty()) {
int r = sta.top();
sta.pop();
for (int j = 1; j <= g[r][0]; j++) {
c[g[r][j]] = max(c[g[r][j]], c[r] + 1);
indeg[g[r][j]]--;
if (indeg[g[r][j]] == 0) sta.push(g[r][j]);
}
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += c[i];
}
cout << ans << endl;
return 0;
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <stack>
using namespace std;
const int MAXN = 100000;
int g[MAXN][3];
int indeg[MAXN];
int val[MAXN];
int c[MAXN];
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> val[i];
if (n == 1) {
cout << 1 << endl;
return 0;
}
for (int i = 0; i < n - 1; i++) {
if (val[i] < val[i + 1]) {
g[i][++g[i][0]] = i + 1;
indeg[i + 1]++;
} else if(val[i] > val[i + 1]) {
g[i + 1][++g[i + 1][0]] = i;
indeg[i]++;
}
}
stack<int> sta;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) {
c[i] = 1;
sta.push(i);
}
}
while (!sta.empty()) {
int r = sta.top();
sta.pop();
for (int j = 1; j <= g[r][0]; j++) {
c[g[r][j]] = max(c[g[r][j]], c[r] + 1);
indeg[g[r][j]]--;
if (indeg[g[r][j]] == 0) sta.push(g[r][j]);
}
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += c[i];
}
cout << ans << endl;
return 0;
}
Input
The first line of the input is an integer N, the number of children in Alice's class. Each of the following N lines contains an integer indicates the rating of each child.
Ouput
Output a single line containing the minimum number of candies Alice must give.
Sample Input
3
1
2
2
Sample Ouput
4
Explanation
The number of candies Alice must give are 1, 2 and 1.
Constraints:
N and the rating of each child are no larger than 10^5.
Maybe the output should be 5 since both the students of rate 2 will get i candy each ? correct me if i am wrong
Amit - Question clearly says that student with higher rating should get more candies. Nothing about equal rating. So in case of equal rating we can give less candies.
@nitingupta180.....the question also says that each kid must recieve at least one candy. So the answer has to be 5.You can't give one 2 a single candy and other 2 null candy.
@Shivam Maharshi : Again read the example test case.
Candies are given as follows:
1 - 1
2 - 2
2 - 1
Hope it clarifies your confusion
No.
These are ratings of student which can be same. I have taken above example. First read the question carefully, then you will get it. I can't understand where I have given NULL candy to some student.
Ohh...I'm sorry..my bad. I got the question correctly, Just din't read your input format properly. I got it now you are giving everyone at least 1 candy. But it seem a lil bit less obvious giving unequal amount of candies to the same performance kids even when they are seated consecutively.
Why ? We have to minimize no of candies and question only says about higher rating nothing about equal and less rating.
P.S. - I have solved it. Its accepted :-)
I think you just sort N kids from lowest to highest score and start giving the candies from 1 and 1+N.
It would be better to arrange low score kids between high scoring kids. That way you can have a distribution like 1,2,1,2,1,2,1,2,1... instead of 1,2,3,4,5,6,7,8...
Wow thank you...that was exactly how I approached this question at first but for some reason my fucked up brain told me that will cause her more candies...not sure what I was thinking but thanks for pointing it out!
Malluce - For sorting it would require space to store all the students' ratings. As you know N can be 10^5. I think there should be more efficient code if we use Dynamic Programming.
Malluce - You cannot change order of students as you will get wrong result.
Ex :
4,3,4 - requires 5 (2+1+2) candies.
As you have said after sorting
3,4,4 - It requires 4 (1+2+1) candies.
The correct answer is 5.
Since sorting will handle the same score (i.e., they are next to each other) I think we can just give them the same amount of candies.
I made a mistake earlier...I think it should more look like this:
1. Sort
2. Alter the highs and lows...if it is the same score then we group them together (e.g., 1, 2, 5, 2, 4, 4, 6 -> 1, 2, 2, 4, 4, 5, 6 -> 1, 6, 2, 2, 5, 4, 4. The candy should be 1, 2, 1, 1, 2, 1, 1)
And I believe sorting is O(nlogn) if you use merge or quick sort. I didn't plan to write the code out cuz I believe the approach/ concept is more important...thanks for the feedback tho! ;)
I have a doubt. How is the comparisons done ?
For the above case, are the comparison made like (1,6) (6,2),(2,2),(2,5),(5,4),(4,4) or (1,6),(2,2),(5,4) and so ?. If first case the person with the rating 6 should receive 3 candies since 1 is essential and 6 is more than 1 and 2. If i have not interpreted the question well, please comment me with right comparisons.
//
we have to consider how many kids are in a decreasing rank continuously
on that basis we can scan each kid and allocate no of candy to each student
order goes to o(n2) if all students sit in a sorted order
#include<stdio.h>
#include<conio.h>
int main()
{
int N,sum=0;;
printf("enter N : ");
scanf("%d",&N);
int a[N];
int i;
for(i=0;i<N;i++)
scanf("%d",&a[i]);
int prev=0;int preval=0;
for(i=0;i<N;i++)
{
int res=0;
int j=i;
int count=1,flag=0;
while(a[j]<=a[j+1] && j!=N-1)
{if(a[j]==a[j+1]){j++;continue;}else {count++;j++;flag++;}}
if(flag==0)
{count=1;res=count;}
if(a[i]<preval && count<=prev)
res=prev+1;
else if(a[i]==preval)
res=prev;
else
res=count;
preval=a[i];
a[i]=res;
prev=res;
}
for(int i=0;i<N;i++)
{ printf(" %d ",a[i]);
sum=sum+a[i];}
printf("\nMin candy is %d",sum);
getch();
return 0;
}
Assuming the placement of the kids in the line, I would use an iterative method that starts out with every kid receiving one candy, and then looking at the constraints one by one and adjusting until all the constraints are satisfied. This should yield the optimal solution:
vector<int> distribute_candies(const vector<int>& priorities) {
vector<int> candies(priorities.size());
fill(candies.begin(), candies.end(), 1);
vector<int> consistencyChecks;
for (int i = 0; i < priorities.size()-1; i++) consistencyChecks.push(i);
while (!consistencyChecks.empty()) {
int i = consistencyChecks.back();
consistencyChecks.erase(consistencyChecks.end()-1);
if (sign(priorities[i]-priorities[i+1]) != sign(candies[i]-candies[i+1]) {
if (priorities[i] < priorities[i+1]) candies[i]++;
else candies[i+1]++;
consistencyChecks.push_back(i);
if (i+1 < priorities.size()-1) consistencyChecks.push(i+1);
if (i-1 > 0) consistencyChecks.push(i-1);
}
}
}
If we can arrange the order of the kids, then I would sort the priority list, merging the first half of the list and the second half of the list so that we get a [lo, hi, lo, hi, lo, hi] order, and then distribute the candies as such: [1, 2, 1, 2, 1, 2, ...].
@All : Guys I don't think that sorting and then distributing will give correct answer. Consider following example.
4,3,4 - requires 5 (2+1+2) candies.
As you have said after sorting
3,4,4 - It requires 4 (1+2+1) candies.
The correct answer is 5.
I think this problem can only be solved by using recursion or dynamic programming.
hi all.i have solved alredy this problem from interviewstreet.
my algorithm has greedy approach.
here is my C++ code
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stdlib.h>
#include <utility>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <complex>
#include <algorithm>
#include <ctime>
#define gtime clock()
using namespace std;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, lo, hi) for(int i = (lo); i <= (hi); i++)
#define FORD(i, hi, lo) for(int i = (hi); i >= (lo); i--)
#define FE(it, cont) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
#define ALL(cont) (cont).begin(), (cont).end()
#define SZ(cont) (int)((cont).size())
#define PB push_back
#define MP make_pair
template<class T> vector<T> split(const string &s){stringstream ss(s);vector<T> a;T t;while(ss >> t)a.PB(t);return a;}
template<class T> T parse(const string &s){stringstream ss(s);T e;ss >> e;return e;}
template<class T> string toString(const T &e){stringstream ss();ss << e;return ss.str();}
typedef long long int64;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<string> vs;
const int64 oo = (1ll << 30);
const int MAXN = (int)1e5 + 1;
const int mod = (int)1e9;
const double eps = 1e-9;
const double pi = acos(-1);
int n;
int64 val[MAXN], ans[MAXN];
void update_left(int64 pos)
{
ans[pos--] = 1;
while(pos >= 0 && val[pos] > val[pos + 1])
{
ans[pos] = max(ans[pos], ans[pos + 1] + 1);
pos--;
}
}
void update_right(int64 pos)
{
ans[pos++] = 1;
while(pos < n && val[pos - 1] < val[pos])
{
ans[pos] = max(ans[pos - 1] + 1, ans[pos]);
pos++;
}
}
int main()
{
// freopen ("in.txt", "rt", stdin);
// freopen ("out.txt", "wt", stdout);
cin >> n;
REP(i, n)
cin >> val[i];
bool up = false;
bool down = false;
REP(i, n)
{
if(i + 1 < n && val[i] < val[i + 1] && !up)
{
update_left(i);
update_right(i);
up = true;
down = false;
}
if(i + 1 < n && val[i] > val[i + 1])
{
up = false;
down = true;
}
if(i + 1 < n && val[i] == val[i + 1])
{
if(down)
update_left(i);
up = false;
down = false;
}
}
if(!up)
{
update_left(n - 1);
}
int64 total = 0;
REP(i, n)
{
if(!ans[i])
ans[i] = 1;
total += ans[i];
}
//REP(i, n)cout << ans[i] << ' ';cout << endl;
cout << total << endl;
//system("pause");
return 0;
}
@Sandeep : 2nd test case is failing for my code.
My algo : I am counting total length of decreasing ratings till some greater rating is encountered. Then doing sum to n terms where n will be decreasinglength.
Can u find out error in my code. Thanks for the help
#include<stdio.h>
int main(void)
{
int totalCandies = 0;
int lastGivenCandy = 0;
int noOfStudents;
int decreasingLength = 0;
int rating1 = -100, rating2 = -101, flag = 0;
scanf("%d", &noOfStudents);
while(noOfStudents > 0)
{
if(flag == 0)
{
scanf("%d", &rating2);
noOfStudents--;
}
if(rating1 < 0)
{
lastGivenCandy = 1;
totalCandies += lastGivenCandy;
decreasingLength = 1;
flag = 1;
}
do
{
if(flag == 2)
{
rating1 = rating2;
scanf("%d", &rating2);
noOfStudents--;
if(rating2 > rating1)
{
if(decreasingLength > 1)
{
if(lastGivenCandy > decreasingLength)
{
decreasingLength -= 1;
}
else
{
totalCandies -= lastGivenCandy;
}
totalCandies += ((decreasingLength * (decreasingLength + 1)) / 2);
lastGivenCandy = 1;
}
lastGivenCandy++;
totalCandies += lastGivenCandy;
decreasingLength = 1;
}
else
{
decreasingLength++;
}
}
}while(rating2 <= rating1 && noOfStudents > 0);
rating1 = rating2;
flag = 2;
if(decreasingLength > 1)
{
if(lastGivenCandy > decreasingLength)
{
decreasingLength -= 1;
}
else
{
totalCandies -= lastGivenCandy;
}
totalCandies += ((decreasingLength * (decreasingLength + 1)) / 2);
lastGivenCandy = 1;
}
}
printf("%d",totalCandies);
return 0;
}
This can be solved in O(n) time. I think my solution in principle matches with the topological sorting idea.
The idea is to observe that the exact ranking of a student does not matter, but with respect to his next neighbors (whose candies in turn are decided by their next neighbors, and so on). So, it is sufficient to give the number of candies to a student, equal to maximum of the lengths of ever decreasing contiguous subsequence (of rankings) on his/her left and to his/her right, counted starting from him. Here "strictly increasing" or "strictly decreasing" is very import ant to minimize the candies.
Example: for students lined-up according to the rankings 1, 3, 3, 4, 5, 4, 3, 1
the third student has no other students on his left with ever decreasing rankings (starting from him) and no students on his right, so he receives max(0, 0) + 1(minimal candy) = 1 candies, and so on.
The algorithm does exactly the same:
1. let fromLeft[i] and fromRight[i] be the arrays holding lengths of ever decreasing contiguous subset including i'th element on left and right,
2. traverse the rankings from left to right and fill up fromLeft, with the formula
fromLeft[i] = fromLeft[i-1] + 1;
whenever ranking[i-1] < ranking[i]
3. traverse the rankings from right to left to similarly setup fromRight
4. The candies to a student at position i is
candies[i] = max{fromLeft[i] , fromRight[i]} + 1; // 1 for the minimal candy
5. output the sum in candies
Step 4 and 5 can be combined (as done in the code below). One does not need to save number of candies to each person, if only the minimal is required, saving O(n) space
// Calculate minimal number of candies required
int getMinimalCandies(const std::vector<double>& rankings, std::vector<int>& candies){
// number of students
int numStudents = (int) rankings.size();
// ever decreasing contiguous subsequence
// from every position to its right (left)
std::vector<int> onLeft(numStudents, 0), onRight(numStudents, 0);
// for each position, determine ever decreasing
// seq. on the left and on right
for (int i = 0; i < numStudents; i++) {
// if the ranking on immediate left was
// higher than this one
if (i && // don't do it for i = 0
rankings[i-1] < rankings[i]) {
// length of subsequence at this
// position is one more than the previous one
onLeft[i] = onLeft[i-1] + 1;
}
// similarly for decreasing ranking seq. on right
if ( (((numStudents - 1) - i) < numStudents - 1) &&
rankings[((numStudents - 1) - i) + 1] < rankings[(numStudents - 1) - i]) {
onRight[(numStudents - 1) - i] = onRight[((numStudents - 1) - i) + 1] + 1;
}
//
}
// candies to be given to every child is
// max-length(increasing seq. on left, decreasing seq. on right)
int totalCandies(0);
for (int i = 0; i < numStudents; i++){
candies[i] = std::max(onLeft[i], onRight[i]) + 1;
totalCandies += candies[i];
}
// return total number of candies to be distributed
return totalCandies;
}
// API, from main
std::cout << "The total number of minimal candies required are " << getMinimalCandies(rankings, candies) << std::endl;
// print individual candies (optional)
std::cout << "Distribute as ";
for (int i= 0; i < n; i++)
std::cout << candies[i] << "\t";
std::cout << std::endl;
A very easy implementation
Space Complexity: O(n)
Time Complexity : O(n)
Step 1: Start traversing the array from left to right and assign the value 1 to each index in dp array.
Step 2: Start traversing the array from left to right and if the person scored more marks then the person sitting to his left then dp of that person will be dp[i-1]+1;
Step 3: Start traversing the array from right to left and if the person scored more marks then the person sitting to his right then dp of that person will be max(dp[i],dp[i+1]+1);
Step 4 : Add all the values in dp array.
#include<bits/stdc++.h>
using namespace std;
long int arr[100005];
long int dp[100005];
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%ld",&arr[i]);
long int ans=0;
dp[0]=1;
for(i=1;i<n;i++)
{
if(arr[i]>arr[i-1])
dp[i]=dp[i-1]+1;
else
dp[i]=1;
}
for(i=n-2;i>=0;i--)
{
if(arr[i]>arr[i+1])
dp[i]=max(dp[i],dp[i+1]+1);
}
for(i=0;i<n;i++)
{
ans=ans+dp[i];
}
cout<<ans<<endl;
return 0;
}
int score[]={2,4,2,6,1,7,8,9,2,1};
int chocs[]=new int[score.length];
chocs[0]=1;
for(int i=1;i<score.length;i++){
if(score[i]>score[i-1]){
chocs[i]=chocs[i-1]+1;
}
else if(chocs[i-1]==1){
chocs[i]=1;
for(int j=i-1;j>=0;j--){
if( score[j] > score[j+1] )
chocs[j] = Math.max(chocs[j+1] + 1,chocs[j] );
else
break;
}
}
else{
chocs[i]=1;
}
}
int sum=0;
for(int i=0;i<chocs.length;i++){
sum+=chocs[i];
}
System.out.println(sum);
int score[]={2,4,2,6,1,7,8,9,2,1};
int chocs[]=new int[score.length];
chocs[0]=1;
for(int i=1;i<score.length;i++){
if(score[i]>score[i-1]){
chocs[i]=chocs[i-1]+1;
}
else if(chocs[i-1]==1){
chocs[i]=1;
for(int j=i-1;j>=0;j--){
if( score[j] > score[j+1] )
chocs[j] = Math.max(chocs[j+1] + 1,chocs[j] );
else
break;
}
}
else{
chocs[i]=1;
}
}
int sum=0;
for(int i=0;i<chocs.length;i++){
sum+=chocs[i];
}
System.out.println(sum);
A simple DP solution
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
if(n==1)
return 1;
int arr[n],dp[n];
for(int i=0;i<n;i++){
cin>>arr[i];
dp[i]=1;
}
int sum=0;{
for(int i=1;i<n;i++){
if(arr[i]>arr[i-1]){
dp[i]+=dp[i-1];
}
else{
if(dp[i-1]==1)
for(int j=i-1;j>=0;j--){
if(arr[j]>arr[j+1])
dp[j]=max(dp[j+1]+1,dp[j]);
else
break;
}
}
}
for(int i=0;i<n;i++){
sum+=dp[i];
//cout<<dp[i]<<" ";
}
cout<<sum;
}
return 0;
}
A Simple DP Solution
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
if(n==1)
return 1;
int arr[n],dp[n];
for(int i=0;i<n;i++){
cin>>arr[i];
dp[i]=1;
}
int sum=0;{
for(int i=1;i<n;i++){
if(arr[i]>arr[i-1]){
dp[i]+=dp[i-1];
}
else{
if(dp[i-1]==1)
for(int j=i-1;j>=0;j--){
if(arr[j]>arr[j+1])
dp[j]=max(dp[j+1]+1,dp[j]);
else
break;
}
}
}
for(int i=0;i<n;i++){
sum+=dp[i];
//cout<<dp[i]<<" ";
}
cout<<sum;
}
return 0;
}
a simple approach, sort the list with o(NlnN), then pick up alternatively elements from the two ends of the sorted list, you will have:
- hwer.han August 15, 2012{highest, lowest, sec highest, sec lowest, third highest, third lowest,.....}
That is it!