Citrix System Inc Interview Question
Software Engineer / DevelopersCountry: United States
I believe there is a typo in the description.
Second row explanation for input
1 5
should be:
... stall 1 has 1 ticket, stall 2 has 5.
Also the number of stalls is redundant input unless we need to validate second row input.
import java.util.HashMap;
public class TicketsValue {
public static long calculateMaxAmount(int totalSold, int[] initialNumbers) {
long value = 0;
HashMap<Integer, Integer> initialNumbersCounter = new HashMap<>();
int maxPrice = 0;
for (int i = 0; i < initialNumbers.length; i++) {
if (initialNumbers[i] > maxPrice)
maxPrice = initialNumbers[i];
int counter = 0;
if (initialNumbersCounter.containsKey(initialNumbers[i])) {
counter = initialNumbersCounter.get(initialNumbers[i]);
}
counter++;
initialNumbersCounter.put(initialNumbers[i], counter);
}
int count = 0;
int rem = totalSold;
for (int price = maxPrice; price > 0; price--) {
if (initialNumbersCounter.containsKey(price)) {
count = initialNumbersCounter.get(price);
}
if (count < rem) {
rem -= count;
} else {
count = rem;
rem = 0;
}
value += count * price;
if (rem == 0)
return value;
}
if (rem > 0)
throw new IllegalArgumentException(
"Total number of sold tickets is greater then sum of the tickets which stalls had initially.");
return value;
}
public static void main(String[] args) {
//int numOfStalls = 2;
int totalSold = 4;
int[] remainings = { 1, 5 };
System.out.println("Maximum Amount: $" + calculateMaxAmount(totalSold, remainings));
}
c++, implementation
int maxPrice(vector<int> s, vector<int> p) {
int length, ret, i, price, count;
length = (int)min(s.size(), p.size());
ret = 0;
for (i = 0; i < length; i++) {
count = min(s[i], p[i]);
if (count <= 0) continue;
price = (p[i] + p[i] - count + 1) * count / 2;
ret = max(ret, price);
}
return ret;
}
A simple Brute-force approach to solve this problem and the complexity of this solution is O(n*m)
public class Stalls {
public static void main(String[] args) throws IOException {
//1. Take input from console
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//2. Get row1 and row2
String row1 = br.readLine();
String row2 = br.readLine();
//3. Validation of input rows
if(row1 == null || row1=="" || row2==null || row2==""){
System.out.println("Exiting as invalid inputs");
System.exit(0);
}
//4. Split the row1 elements with space and validate
String[] tokens1 = row1.split(" ");
if(tokens1==null || tokens1.length!=2){
System.out.println("Exiting as invalid input for row1");
System.exit(0);
}
//5. Capture the number of stalls and number of Tickets to be sold in two variables.
int numOfStalls = Integer.parseInt(tokens1[0]);
int numOfTickets = Integer.parseInt(tokens1[1]);
//6. Split the second row and validate against the number of stalls given in first row.
String[] tokens2 = row2.split(" ");
if(tokens2==null || tokens2.length!=numOfStalls){
System.out.println("Exiting as invalid input for row2");
System.exit(0);
}
//7. Find the maximum sum
findMaximum(numOfStalls, numOfTickets, tokens2);
//8. With Sorting
findMaximumMinComplexity(numOfStalls, numOfTickets, tokens2);
}
/**
* Find the maximum sum from different stalls.Complexity is O(n*m)
* @param numOfStalls
* @param numOfTickets
* @param tokens
*/
private static void findMaximum(int numOfStalls, int numOfTickets, String[] tokens) {
//1. Get the initial number of tickets in each stall in an ArrayList and initialize the values list and stall list.
List<String> ticketsInEachStall = new ArrayList<String>(Arrays.asList(tokens));
List<Integer> valueList = new ArrayList<Integer>();
List<Integer> stallList = new ArrayList<Integer>();
//2. Variable to capture the maximum sum.
int sum = 0;
//3. Variable to capture which stall ticket number has to be decreased.
int indexToDecrease = 0;
//4. For the number of tickets to be sold, loop and find the max value.
for(int ticketIndex=1;ticketIndex<=numOfTickets; ticketIndex++){
int maxValue = 0;
for(int stallIndex=0; stallIndex<ticketsInEachStall.size(); stallIndex++){
int ticketValueOfStall = Integer.parseInt(ticketsInEachStall.get(stallIndex));
if(ticketValueOfStall > maxValue){
indexToDecrease=stallIndex;
maxValue = ticketValueOfStall;
}
}
valueList.add(maxValue);
sum+=maxValue;
stallList.add(indexToDecrease+1);
int existingval = Integer.parseInt(ticketsInEachStall.get(indexToDecrease));
existingval--;
ticketsInEachStall.remove(indexToDecrease);
ticketsInEachStall.add(indexToDecrease, String.valueOf(existingval));
}
System.out.println("The maximum profit is $"+ sum);
System.out.println("Values list: "+ valueList);
System.out.println("------------------");
System.out.println("Stall number from which ticket has to be sold in order is : "+ stallList);
}
This can be solved using Greedy Algorithms Method.
- Ankit November 13, 2015Suppose the input from second line is stored in an array.
At each step select the maximum number from the array and add that number to sum.
Decrease that number by 1 and number of tickets remaining by 1.
Repeat until number if tickets remaining is 0.