Interview Question
Country: United States
To analyze this question, I think you should not jump right into coding, you should imagine plotting a graph of X vs. rating. The people at the relative minimum will get the lowest hike, then go from there left and right and increment each one by the minimum hike until you hit the relative maximum, so instead of doing any crazy manipulation, I will just find all relative max and min.
Using your example: 1,4,6,2. 1 and 2 are the relative min, so they get the least.
The thing to look out for are when 2 adjacent people have the same rating.
I will leave the rating to you and only write a function to output the hikes (I will write it in Java, haven't wrote Java code in a while so it may be slightly off)
/*** Editing: did not realize that 2 people adjacent will not have same rating ***/
public void(int minhike, int[] ratingArr, int[] hikeArr)
{
int count = ratingArr.length;
int[] relativeMax = new int[count];
int[] relativeMin = new int[count];
// these 2 can be some list to reduce space, I am too lazy to do it now
int i=1,j=0,k=0,l=0,m=0;
bool increasing = (ratingArr[0] < ratingArr[1]);
bool first = increasing;
for(i=1;i<count;i++)
{
if (increasing)
{
if(ratingArr[i] < ratingArr[i-1]) {relativeMax[j++] = i-1; increasing = false;}
//change from increasing to decreasing
}
else if(ratingArr[i] > ratingArr[i-1]) {relativeMin[k++] = i-1; increasing = true;}
//the other way
// this way 1 is included in the relativeMax or Min, but we have to take care of the last one
}
if(increasing) relativeMax(j++)=i-1
else relativeMin(k++)=i-1 // log the last one too.
//Now relative Max and Min are logged. j and k will be differ by at most 1, they may be equal.
for(i=0; i < j;i++)
{
hikeArr[relativeMin[i]] = minhike;
if(first) // if it started by increasing
{
if(i < k) // in case if k > j
for(l = relativeMin[i] + 1; i < relativeMax[i];l++)
hikeArr[l] = hikeArr[l-1] + minhike;
if(i != 0)
for(l = relativeMin[i] - 1; i > relativeMax[i-1];l--)
hikeArr[l] = hikeArr[l+1] + minhike;
}
else //started decreasing we can be assure that j <= k
{
for(l = relativeMin[i] + 1; i < relativeMax[i+1];l++)
hikeArr[l] = hikeArr[l-1] + minhike;
for(l = relativeMin[i] - 1; i > relativeMax[i];l--)
hikeArr[l] = hikeArr[l+1] + minhike;
}
// At this point, all hike except the relative max's are stored. Also, if 2 consecutive value are both relatively min/max, I only store one.
for(i = 0 ; i < k; i++)
{
l = relativeMax[i];
if(l = 0) hikeArr[0] = hikeArr[1] + minhike;
else if (l = count - 1) hikeArr[l] = hikeArr[l-1] + minhike;
else hikeArr[l] = (hikeArr[l-1] > hikeArr[l+1] ? hikeArr[l-1] : hikeArr[l+1]) + minhike;
}
}
}
It is given that no two adjacent employee would have common rating. Excluding this case, I agree with the fact that two relative minimum rated employee can sit next to each other but they should not be given same hike.
Let me know any such case in which code (I wrote) would fail.
This is a simple problem of finding max decreasing subsequence and can be solved in O(n).
l[i] decreasing subsequence upto i.
l[0]=1
for i=1 to i=n-1
l(i)=l(i-1)+1 if a[i] < a[i-1]
= 1 if a[i] > a[i-1]
x=max(l[i]) , where 10x is the hike given to the first employee.
This will be more clear with an example.
The rating of the employees 3 2 3 2 1
So l(0)=1 l(1)=2 l(2)=1 l(3)=2 l(4)=3
x=max(l(i))= 3
So the employees get hike in the order 30, 20,30,20,10
This will not give the right answer. Consider the example: 1, 4, 6, 2
according to you logic L[i] = {1, 1, 1, 2} . What according to you must be done next is not clear.
Moreover the right anwer is 10, 20, 30, 10 = 70 (total hike), which will not be the outcome according to your logic in anycase.
Even for example you have taken to demonstrate, the hikes must be: 20, 10, 30, 20, 10
I think there's an algorithm with time cost O(n).
Design a function f(i). When ith staff is bigger than (i+1)th staff, f(i + 1) = f(i) - 1. Otherwise f(i + 1) = f(i) + 1.
I will divide the staffs into several monotonous intervals. Each interval must have an element with hike 1x. The element bewteen two adjacent intervals will belong to the larger one. Then let each interval length be l(k), and the cost will be l(k) * (l(k) + 1) / 2.
Here's the code in C++:
int main() {
int x, n;
int dat[128];
scanf("%d %d", &x, &n);
for (int i = 0; i < n; ++ i) {
scanf("%d", &dat[i]);
}
int tmp = 0; //a flag to indicate weather it's increasing or decreasing
//if tmp > 0 the sequence is increasing and the value is the consequense increasing num in the array
int cal[128], cnt = 0; //cal saves the length of each monotonous interval
for (int i = 0; i < n - 1; ++ i) {
if (dat[i + 1] > dat[i]) {
if (tmp < 0) {
cal[cnt ++] = abs(tmp);
tmp = 1;
} else {
tmp ++;
}
} else {
if (tmp > 0) {
cal[cnt ++] = abs(tmp);
tmp = -1;
} else {
tmp --;
}
}
}
cal[cnt ++] = abs(tmp);
for (int i = 0; i < cnt - 1; ++ i) {
if (cal[i + 1] > cal[i]) {
cal[i + 1] ++;
} else {
cal[i] ++;
}
}
int ret = 0;
for (int i = 0; i < cnt; ++ i) {
ret += cal[i] * (cal[i] + 1) / 2;
}
printf ("%d\n", ret * x);
}int main() {
int x, n;
int dat[128];
scanf("%d %d", &x, &n);
for (int i = 0; i < n; ++ i) {
scanf("%d", &dat[i]);
}
int tmp = 0; //a flag to indicate weather it's increasing or decreasing
//if tmp > 0 the sequence is increasing and the value is the consequense increasing num in the array
int cal[128], cnt = 0; //cal saves the length of each monotonous interval
for (int i = 0; i < n - 1; ++ i) {
if (dat[i + 1] > dat[i]) {
if (tmp < 0) {
cal[cnt ++] = abs(tmp);
tmp = 1;
} else {
tmp ++;
}
} else {
if (tmp > 0) {
cal[cnt ++] = abs(tmp);
tmp = -1;
} else {
tmp --;
}
}
}
cal[cnt ++] = abs(tmp);
for (int i = 0; i < cnt - 1; ++ i) {
if (cal[i + 1] > cal[i]) {
cal[i + 1] ++;
} else {
cal[i] ++;
}
}
int ret = 0;
for (int i = 0; i < cnt; ++ i) {
ret += cal[i] * (cal[i] + 1) / 2;
}
printf ("%d\n", ret * x);
}
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.Vector;
public class MinimumHike {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int minimumSal = 10;
//initialize the rank of of the employee
int a[] = new int[]{4, 1, 6, 2};;
//create two arrays
//one will hold rank|position
String[] rankWithPosition = new String[a.length];
//other will hold the salary hike in multiple of minimumSal in such a way that overall
//salary increase is mimimum. Here array index will be used to store the sitting position
String[] finalSalaryFigure = new String[a.length];
for(int i = 0 ; i < a.length ; i++ ){
rankWithPosition[i] = a[i] + "|" +i;
}
//Now sort the rankWithPosition, so that the data is in ascending order of rank
Arrays.sort(rankWithPosition);
//now iterate thru the sorted array
int lastAssignedSalary = minimumSal;
for(int j = 0 ; j < rankWithPosition.length ; j++){
String rank = rankWithPosition[j];
String[] stk = rank.split("|");
//position is always the second part
//get the sitting position of the first guy
int position = Integer.parseInt(stk[3]);
//get the posiiton and see if
//guy before and after it has salary already decide in finalSalaryFigure or not
//if not then assign the same salary as the last assigned
//else increment the last assigned salary by minimumSal
int positionBefore = position - 1 ;
int positionAfter = position + 1;
boolean isBeforeGuySalaryDecided = false;
boolean isAfterGuySalaryDecided = false;
if(positionBefore < 0 || finalSalaryFigure[positionBefore] != null){
isBeforeGuySalaryDecided = true;
}
if(positionAfter > (finalSalaryFigure.length -1) || finalSalaryFigure[positionAfter] != null){
isAfterGuySalaryDecided = true;
}
if(isBeforeGuySalaryDecided){
lastAssignedSalary = lastAssignedSalary + minimumSal;
finalSalaryFigure[position] = Integer.toString(lastAssignedSalary);
}else{
//assign the last assigned salary without incrementing
finalSalaryFigure[position] = Integer.toString(lastAssignedSalary);
}
}
//}
//test it
for(int k=0 ; k < finalSalaryFigure.length ; k++){
System.out.println("The salaries of guys are" + finalSalaryFigure[k]);
}
}
}
import java.util.Scanner;
public class Foobar {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int x=in.nextInt();
int n=in.nextInt();
int []B=new int [n+1];
for(int i=1; i<=n; i++){
int f=in.nextInt();
B[i]=f;
}
int []A=new int [n+1];
int k=1;
A[1]=1;
while(k<n){
if(B[k]<B[k+1]){
A[k+1]=A[k]+1;
}
if(B[k+1]<B[k]){
A[k+1]=1;
}
k++;
}
int j=n;
while(j>0){
if(A[j]>A[j-1]){
j--;
} else if(A[j]==A[j-1]){
A[j-1]+=1;
j--;
} else if(A[j]<A[j-1]){
j--;
}
}
int sum=0;
for(int h=1; h<n+1; h++){
sum=sum+A[h]*x;
}
System.out.print(" \n"+sum);
}
}
input: x=10, n=14
8 5 6 5 7 10 5 3 6 5 7 2 1 3
final arrangment= 2 1 2 1 2 3 2 1 2 1 3 2 1 2
sum= 250
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <iostream>
#define N 14
using namespace std;
int main()
{
int rat[N],hike[N];
int i,temp;
int x=10;
for(i=0;i<N;i++)
cin>>rat[i];
hike[0]=x;
for(i=1;i<N;i++)
{
if(rat[i]>rat[i-1])
{
hike[i] = hike[i-1]+x;
}
else if(rat[i]<rat[i-1])
{
hike[i] = x;
}
else
{
hike[i] = hike[i-1];
}
}
cout<<"after first pass\n";
for(i=0;i<N;i++)
cout<<hike[i]<<" ";
for(i=N-2;i>=0;i--)
{
if(rat[i]>rat[i+1])
{
temp = x + hike[i+1];
if(temp>hike[i]) hike[i] = temp;
}
}
cout<<"after second pass\n";
for(i=0;i<N;i++)
cout<<hike[i]<<" ";
return 0;
}
Here is my code.
Start with the first employers hike a[2].
a[0] is x.
a[1] is no of employee .
int k=0;l,total=0;
for(i=2;i<=a[1]=1;i++){
if (a[i+1]>a[i]){
total=total+a[0]*(k+1);
k=k+1;}
else (a[i+1]<a[i]){
l=1;j=i;
while(a[j+1]<a[j]){
l=l+1;
j++;}
total = total + max{l,k+1}*a[0];
k=max{l,k};
}
}
return(total);
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class GetLeastHike
{
public static void main(String args[]) throws Exception
{
int i,j, totalHike=0;
try
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter minimum hike:");
int x = Integer.parseInt(br.readLine()); //value of x minimum hike
System.out.println("enter no of employees:");
int n = Integer.parseInt(br.readLine());
int empRating[] = new int[n];
int empHike[] = new int[n];
for(i=0;i<n;i++)
{
System.out.println("enter rating of "+ (i+1) + " employee");
empRating[i] = Integer.parseInt(br.readLine());
}
empHike[0]= x;
for(i=1;i<n;i++)
{
if(empRating[i]>empRating[i-1])
{
empHike[i] = empHike[i-1] + x;
}
else
{
empHike[i] = x;
if(empHike[i-1] == x)
{
for(j=i; j>0;j--)
{
if( empHike[j] == empHike[j-1])
{
empHike[j-1] = empHike[j-1] + x;
}
else
{
break;
}
}
}
}
}
System.out.println("Rating\tHike");
for(i=0;i<n;i++)
{
System.out.println(empRating[i] +"\t" +empHike[i]);
totalHike = totalHike+empHike[i];
}
System.out.println("Total Hike: "+totalHike);
}
catch (IOException ex)
{
ex.printStackTrace();
}
}
}
- Pooja Basia August 24, 2013import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class MinimizeEmpHikes { public static void main(String[] args) { try{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println("enter minimum hike:"); int x = Integer.parseInt(br.readLine()); //value of x minimum hike System.out.println("enter no of employees:"); int n = Integer.parseInt(br.readLine()); int i,minR,count = 0; List<Integer> min1 = new ArrayList<Integer>(); int []ratingArr = new int[n]; int []solutionArr = new int[n]; for(i=0; i<n ; i++) { System.out.println("enter rating of "+ (i+1) + " employee"); ratingArr[i] = Integer.parseInt(br.readLine()); } minR = ratingArr[0]; for(i=0; i<n; i++) { solutionArr[i] = 0; } //find 1st min // todo: optimize module to find next min for(i=0;i<n;i++) { if(ratingArr[i] <= minR) { /*if(min1.contains(ratingArr[i])) continue; else*/ minR = ratingArr[i]; } } // assigning rating.. find ith minimum element/rating..check next n next->next elements rating n hikes then assign hike while(count < n) { min1.add(minR); //array of min / rating in ascending order*/ for(i=0;i<n;i++) if(ratingArr[i] == minR) //next min element { //assign hike if(min1.size() == 1) solutionArr[i] = x; else { if(i-2 >= 0) { if(ratingArr[i] == ratingArr[i-2]) solutionArr[i] = solutionArr[i-2]; // in this case i-2 has already been assigned a value. else if(i+2 < n) solutionArr[i] = Math.max(Math.max(solutionArr[i-1],solutionArr[i-2]), Math.max(solutionArr[i+1], solutionArr[i+2])) + x; else if(i+1 < n) solutionArr[i] = Math.max(Math.max(solutionArr[i-1],solutionArr[i-2]), solutionArr[i+1]) + x; else solutionArr[i] = Math.max(solutionArr[i-1],solutionArr[i-2]) + x; } else if(i-1 >=0) { if(i+2 < n) solutionArr[i] = Math.max(solutionArr[i-1], Math.max(solutionArr[i+1], solutionArr[i+2])) + x; else if(i+1 < n) solutionArr[i] = Math.max(solutionArr[i-1], solutionArr[i+1]) + x; else solutionArr[i] = solutionArr[i-1] + x; } else { if(i+2 < n) solutionArr[i] = Math.max(solutionArr[i+1], solutionArr[i+2]) + x; else if(i+1 < n) solutionArr[i] = solutionArr[i+1] + x; else solutionArr[i] = x; } } count++; } minR = minR+1; } System.out.println("Rating\tHike"); for(i=0;i<n;i++) System.out.println(ratingArr[i] +"\t" +solutionArr[i]); } catch(IOException e) { e.printStackTrace(); } } }