Interview Question


Country: United States




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

It's just like the activity arrangement problem. Greedy algorithm will work.
(1)divide customers into several groups in which members have the same favourite room. customers in different groups are unrelated with each other.
(2)sort each group according to ending time.
(3)for each group, always add the next customer whose ending time is the earliest and whose starting time is not earlier than last one's ending time into the room's schedule.

- uuuouou January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you tell me the data structure to be used if value of k and n is too lage

- shivam sharma January 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This question looks like it is from running online coding competition: codechef.com/JAN14/problems/FGFS

- Anonymous January 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. The question is not clear.
maximum no of customers can get the rooms
By the example, it seems that is "maximum no of customers can get the favorite rooms".
2. If it is just the favorite rooms, it becomes to just arrange by every room and sum all rooms. All below discussion based on this assumption.
3. For every room, "uuuouou" 's answer seems reasonable.

- JIE January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Your problem is a mixture of "Bin Packing" (assign different objects with volumes to different bins with finite capacity) and "Agent Matching" (assignment based on preference) and hence,
NP-complete. So in general, any solution might be as good as others, i.e., worst time exponential.

What I suggest, is a backtracking algorithm (aka Branch and Bound). This is just to have a first crack at the problem. The idea behind branch and bound is very simple:
A- Browse all (worst case) possibilities (through recursion, for instance)
B- Before each assignment check if we bound
Bounding: Cleverly deducing whether or not we need to delve in deeper. For example, you have already found a solution to serve 3 customers. Now you are checking customer 3/4 and you have assigned only one yet. Obviously, the best you can do is to assign only one more customer which brings you to "2" and this is a worst solution than what you already have. So just don't bother!

The code is in Java.


Main Algorithm:

// Assign customer with ID = c_id
    public void RunAssignment(int c_id) {
        // Here goes nothing... (worst time exponential)
        // Trying to assign customer id = c_id
	/// HERE IS THE BOUNDING PART (a very simplistic one indeed)
        int customers_left = customers.length - c_id;   // How many more customers left to assign
        if (curr_customers_in + customers_left < max_customers_assigned) // There is no way to find a better assignment since we already have a better solution
            return;
        
        // Check all rooms that this customer likes
        for (int room_index : customers[c_id].preferred_rooms) {
            // Can we check this customer in? (Here you resolve the clashes)
            if (rooms[room_index].CheckIn(customers[c_id])) { 
                // YES!
                // Count one more
                curr_customers_in++;
                
                // Is it a better or equally good as our best one so far?
                if (curr_customers_in >= max_customers_assigned) {
                    // YES!
                    max_customers_assigned = curr_customers_in;
                    // Print it!
                    AnnounceSolution();
                }    
                // Do we have anybody left?
                if (c_id < customers.length - 1) {
                    // Assign next!
                    RunAssignment(c_id + 1);
                    // To brows other options, check this customer out.
                    rooms[room_index].CheckOut(customers[c_id]);
                    // Count one out
                    curr_customers_in--;
                    // Try to assign next (this time, our current customer is not assigned anymore!)
                    RunAssignment(c_id + 1);
                }                                              
                else {
                    // No? Just check out to try next room (not necessary at this point, but just to make sure we have all possible solutions)
                    curr_customers_in--;
                    rooms[room_index].CheckOut(customers[c_id]);
                }
            }            
        }         
    }

I am using two types of Objects: Customer and Room

First Room:

public class Room {
    public static int MaxHour = 300;
    public ArrayList<Customer> customers;
    int ID;
    boolean[] hours;
    // Sets the room ID 
    public Room(int ID) {
        customers = new ArrayList<Customer>();
        hours = new boolean[Room.MaxHour];
        this.ID = ID;
    }
    
    /**
     * 
     * @param c Customer (object)
     * @return  True if "c" can be checked in. If so, the corresponding hours of occupancy are marked off. Otherwise, just say false.
     */
    public boolean CheckIn(Customer c) {
        for (int i = c.hour_in; i < c.hour_out; i++)
            if (hours[i])
                return false;
        for (int i = c.hour_in; i < c.hour_out; i ++)
            hours[i] = true;
        customers.add(c);
        return true;           
    }       
    /**
     * Release the hours assigned to a customer.
     * @param c Check out this customer.
     */
    public void CheckOut(Customer c) {
        for (int i = c.hour_in; i < c.hour_out; i++) 
            hours[i] = false;
        customers.remove(c);
    }
       
       // For printing solution
       @Override
       public String toString() {
            String msg= "Room " + Integer.toString(ID) + " serves ";
            if (customers.isEmpty())
                msg = msg + " no one!";
            else
                for (Customer c : customers)
                    msg = msg + "[" + c.toString() + "]";
            return msg;
        }       
}

And now the Customer class (nothing to it)

public class Customer {    
    // Set the corresponding info.
        public Customer(int ID, int hours_in, int hours_out, int[] rooms) {
           this.ID = ID;
           this.hour_in = hours_in - 1;
           this.hour_out = hours_out - 1;
           this.preferred_rooms = rooms;
        }
        int ID, hour_in, hour_out;
        public int[] preferred_rooms;
        
        @Override
        public String toString() {
            return "Customer " + Integer.toString(ID);
        }
}

- Ehsan January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Group customers according to their favorite room's number:
1) Map<Integer, List<Customer>>
2) Sort each customer's list according to arrival time (you can also use Queue instead of list and write custom comparator. it might be more realistic :) )
3) for each room iterate over its queue
- first customer get access
- counter++;
- set variable departureTime = customer.endingTime
if(nextCustomer.startTime > departureTime){
departureTime = nextCustomer.endingTime
counter++
}

- thelineofcode January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

will it provide maximum count?or sorting on basis of end time will provide maximum?

- justhack4fun688 January 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Yes, it provides max count. Each time a new customer is assigned to the room increment counter. Just like in the example. At the end you will have max.

- thelineofcode January 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perhaps a piece of code might be helpful.Their are some sort of ambiguties

- justhack4fun688 January 03, 2014 | Flag


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