Flip Kart Coding Test

Question 1 / 1 (The Wicked Manager Problem)
There is a fictional company called fooBar in fooLand. The CEO of fooBar, fooMan, directs all managers to minimize the total hike that they give to employees, while ensuring that the hike is fair to them. Usually, this is done by giving more hike to employees who are rated better. So, for example, if an employee is rated 2 and is given hike 3x, an employee rated 3 should be given a hike greater than 3x. Hikes are always in multiples of x only and the minimum hike to be given to any employee is x.
This year, however, a wicked manager, barMan comes up with a brilliant strategy. He assumes that each employee would get to know the hike of only the two employees who sit next to him (one on the left, one on the right). And therefore, he reasons(using whole of his analytical left brain), that as long as he could make hikes fair for each employee with respect to the two employees that sit next to him, he would fulfill the dual objective of being "fair" as well as minimizing the total hike given. Just for clarification, the employees of each team sit in one big line.
barMan hires you to calculate the hike to be given to each employee. Over to you. You are supposed to come up with the total hike number that will excite barMan and make him roll on the floor laughing. You are given that no two employee sitting next to each other would have a common rating.





Input:
The order of rating of each employee should be in the order in which they sit. First line will be the value of x. The second line will be the number of employees 'n'. The next 'n' lines specify the rating of each employee. Rating can be integers from 1 to 105. (weird, right?)
1 <= n <= 105.

1 <= x <= 104.

Sample input 1:

10

4

1

4

6

2

Output:

70

Why?

If we have the hikes as first employee gets 10, second gets 20, third gets 30 and fourth gets 10, we satisfy all our constraints.


Sample input 2:

50

10

4

8

13

21

15

1

13

67

8

94

Output:

1050

Why?
Here the respective hikes are 50,100,150,200,100,50,100,150,50,100


Sample Input 3:

1

10

6

4

5

8

10

9

4

5

3

6

Output:

20

Why?

Here the respective hikes are 2,1,2,3,4,2,1,2,1,2







Solution in Java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;

public class RatingProblem {
private static int minHike = 0;
private static long[] ratings;
static int max = -1;
static long givenHike[] ;
static long totalHike=0;

public static void main(String[] args) {

readFile();
for (int i = 0; i < 100000; i++) { ratings[i]=(int)(Math.random()*100); } givenHike = new long[ratings.length]; if (ratings.length >= 2) {
if (ratings[0] > ratings[1]) {
smallerNumber(0);
} else {
givenHike[0] = minHike;
max=1;
}
}
for (int i = max; i < ratings.length - 1; i++) { if (ratings[i] > ratings[i - 1] && ratings[i] > ratings[i + 1] ) {
max=-1;
smallerNumber(i);
if(givenHike[i-1]>=givenHike[i]){
givenHike[i]=givenHike[i-1]+minHike;
}
i=max;
} else if (ratings[i] > ratings[i - 1] && ratings[i] < ratings[i + 1]) { givenHike[i] = givenHike[i - 1] + minHike ; } else { givenHike[i] = minHike; } } if (ratings[ratings.length - 1] > ratings[ratings.length - 2]) {
givenHike[ratings.length - 1] = givenHike[ratings.length - 2] + minHike;
} else {
givenHike[ratings.length - 1] = minHike;
}
for (int i = 0; i < givenHike.length; i++) { totalHike+=givenHike[i]; System.out.print(givenHike[i] + " "); } System.out.println("Output : "+totalHike); } public static void readFile() { String[] args1 = { "D:/rating-input.txt" }; if (null != args1 && args1.length > 0) {
try {
BufferedReader brInput = new BufferedReader(new FileReader(new File(args1[0])));
String strInput = null;
minHike = Integer.valueOf(brInput.readLine());
int sizeOfArray = Integer.valueOf(brInput.readLine());
if(minHike>=10000||sizeOfArray>=100000){
return;
}
ratings = new long[sizeOfArray];
int count = 0;
while ((strInput = brInput.readLine()) != null) {
ratings[count++] = Integer.valueOf(strInput);
}
} catch (Exception e) {

}
}
}

public static void smallerNumber(int j) {
if (j == ratings.length-1) {
max = j;
givenHike[j]=minHike;
return;
}
if (j < ratings.length-1 && ratings[j] > ratings[j + 1]) {
smallerNumber(j + 1);
givenHike[j]=givenHike[j+1]+minHike;
}else{
max=j;
givenHike[j]=minHike;
return;
}
}
}








Complexity O(n).