## Interview Question

Country: India

Comment hidden because of low score. Click to expand.
3
of 5 vote

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:
{highest, lowest, sec highest, sec lowest, third highest, third lowest,.....}
That is it!

Comment hidden because of low score. Click to expand.
0

BTW, you will always end up with either
[2,1,2,1,....,1,2]
or
[2,1,.......,2,1]

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Does NOT work for 1,2,3,4,4,4

Comment hidden because of low score. Click to expand.
0

why it will not work!?

1,4,2,4,3,4
will result
1,2,1,2,1,2

Comment hidden because of low score. Click to expand.
0

This is actually interviewstreet question. And you cannot change the order. that means you cannot sort.

Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

Time complexity is O(n)

Comment hidden because of low score. Click to expand.
1
of 1 vote

/* 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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Maybe the output should be 5 since both the students of rate 2 will get i candy each ? correct me if i am wrong

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

@Shivam Maharshi : Again read the example test case.
Candies are given as follows:
1 - 1
2 - 2
2 - 1

Comment hidden because of low score. Click to expand.
0

1 - 1
2 - 2
3 - 1
@nitingupta180...did u mean this... ?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 :-)

Comment hidden because of low score. Click to expand.
0

Ohh....Well great then..!!

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Not in any company. It is programming challenge on interview street.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you just sort N kids from lowest to highest score and start giving the candies from 1 and 1+N.

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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! ;)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an ongoing challenge on InterviewStreet.

Comment hidden because of low score. Click to expand.
0

Anonymous : This problem is not part of any ongoing contest. This is just a practice problem at interview street.

Comment hidden because of low score. Click to expand.
0
of 0 vote

//
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;
}``````

Comment hidden because of low score. Click to expand.
0

O(n^2) times out in this challenge. You can do it in NlogN.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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, ...].

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

I think this problem can only be solved by using recursion or dynamic programming.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

Comment hidden because of low score. Click to expand.
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

}

// 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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

hi

Comment hidden because of low score. Click to expand.
0
of 0 vote

zsklg'lkaen'g;a
va arw r
gtaesrgesrdf

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.