Sample Meeting Room Scheduler Design

Meeting Object

public class Meeting
{
    public long startTime;
    public long endTime;

    public Meeting(long sTime, long eTime)
    {
        startTime = sTime;
        endTime = eTime;
    }
}


Room Object

public class Room
{
    public List meetings;

    public Room()
    {
        meetings = new ArrayList();
    }
    public boolean tryScheduleMeeting(Meeting meeting)
    {
       for (Meeting scheduledMeeting : meetings) {
   if ((meeting.startTime < scheduledMeeting.endTime) && (meeting.endTime > scheduledMeeting.startTime))
                return false;
        }
     
        meetings.add(meeting);
        return true;
    }
}


Meeting Scheduler

public class Scheduler
{
    List rooms;

    public Scheduler()
    {
        rooms = new ArrayList();
    }
    public List scheduleMeetings(List meetings)
    {
       for (Meeting meeting : meetings)
        {
       
            boolean IsMeetingScheduled = false;
           for (Room room : rooms)
            {
                if (room.tryScheduleMeeting(meeting))
                {
                    IsMeetingScheduled = true;
                    break;
                }
            }

            if(!IsMeetingScheduled)
            {
                Room newRoom = new Room();
                newRoom.tryScheduleMeeting(meeting);
                rooms.add(newRoom);
            }
        }

        return rooms;
    }
 
    public static void main(String[] args)
    {
        List meetings = new ArrayList();
        Meeting m1 = new Meeting(8, 10);
        Meeting m2 = new Meeting(9, 10);
        Meeting m3 = new Meeting(10, 11);
        Meeting m4 = new Meeting(8, 12);

        meetings.add(m1);
        meetings.add(m2);
        meetings.add(m3);
        meetings.add(m4);

        Scheduler s = new Scheduler();
        List rooms = s.scheduleMeetings(meetings);
     
        System.out.println("Number of Rooms: "+ rooms.size());

        int i = 1;
        for (Room room : rooms)
        {
            System.out.println("Room: "+ i++);

            int j = 1;

            for(Meeting m : meetings)
            {
            System.out.println("Meeting: "+ j++);
            System.out.println("\tStart: "+ m.startTime);
            System.out.println("\t  End: "+ m.endTime);
           
            }
            System.out.println();
        }
    }
}

Google Java Interview - May 2013

When I was a college senior I applied for a job at Google. During the in-person interview, the interviewer asked me to find the median of an infinite series of numbers and I just stared at the board, having no idea what to do. Every idea I came up with that was reasonable for a finite series fell flat when faced with an infinite series.

After one more excruciating (but less memorable) interview, they politely showed me out.

So, I was a bit nervous this time around. However, I am pleased to report that I never was at a loss for what to do and all of the questions seemed pretty fair and reasonable. Most of the questions were basically variations on things in Cracking the Coding Interview, so I figured I’d share them. I got a few more creative questions which are not listed below (I don’t want to ruin a anyone’s “personal” question) but they weren’t any harder or easier than the others.

Note: if you’re planning to interview somewhere soon, you might want to save this, do your other prep, and then go through these questions as a mock-interview.

Here’s what I was asked:

• Given this weird tree-like thing:
  
  Find greatest sum on a path from root to leaf (that can only touch one node per level—no going up and down).
  I did a recursive solution that was about six lines long and then she asked me to come up with a way to do it iteratively.
• Consider a power series:
  a0 + a1x + a2x2 + …
  Suppose we have an interface as follows to get the coefficients: a0, a1, a2, etc:

view source

print?

1.class PowerSeries {

2.public:

3.virtual double next();

4.};

You can take the product of two power series:

(a0 + a1x + a2x2 + …) * (b0 + b1x + b2x2 + …)

Implement next() so it gives you the next coefficient in the product of two power series:

view source

print?

1.class PowerProduct : public PowerSeries {

2.public:

3.PowerProduct(PowerSeries* A, PowerSeries* B);

4.virtual double next();

5.};

• Reverse bytes in an int.
  This was in my last interview of the day, and mental fatigue had reduced me to such a state that I assumed four bits in a byte. I don’t even know where that came from, but that was really embarrassing when I realized it (well after the interview).
• Write a function to find if a set A is subset of a set B, B is a subset of A, the two sets are equal, or none of the above (you are allowed to use set operations like union and intersection).
• Part 2 of the previous question: suppose you are given a list of sets. You wish to filter out any set in the list that are a subset of another set in the list. Use your solution from above to find the smallest possible result list as efficiently as possible.
• Implement atoi (convert a string to an integer).
• Given a string, find the logest substring of only two distinct characters. For example, given “aabacccaba”, you would return “accca”.
• Design a cache.
• Suppose you are on a Cartesian coordinate system. Find all paths from (0,0) to (m,n) that only go through each point once. For example, if you were given m=2, n=2, you’d have the following:
  
  This would be one possible path:
  
  Return the number of possible paths. Then extend for negative coordinates.
• Given two integers, a and b, find the smallest square integer in the range (or return -1, if there is no such square)

Question for Sr Java Developer @ Google

Find the nearest common parent of two nodes of a binary tree?

Start with an ordinary depth-first search algorithm:

public void find(Node node, int target) {
    if(node == null || node.value == target) {
        return node;
    }
    if(node.value > target) {
        return find(node.left, target);
    } else {
        return find(node.right, target);
    }
}

Now, adapt this to take two "target" parameters, target1 and target2.

When the search for target1 takes you left, and the search for target2 takes you right, you've found the LCA.

This assumes that both targets actually do exist. If you need to assert that they do, you'll need to continue the search after finding the potential LCA.

public void findLca(Node node, int t1, int t2) {
    if(node == null) {
        return null;
    }
    if(node.value > t2 && node.value > t1) {
        // both targets are left
        return findLca(node.left, t1, t2);
    } else if (node.value < t2 && node.value < t1) {
        // both targets are right
        return findLca(node.right, t1, t2);
    } else {
        // either we are diverging or both targets are equal
        // in both cases so we've found the LCA
        // check for actual existence of targets here, if you like
        return node;
    }
}