Citrix System Inc Interview Question for Software Engineer / Developers


Country: United States




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

This can be solved using Greedy Algorithms Method.
Suppose 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.

- Ankit November 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

	}

- artak.a.petrosyan November 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kyduke November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- harry November 30, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More