CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Interview Question


Country: United States
Interview Type: In-Person



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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class FindInterval {

	public static List retrieveCombinations(String[] set, int n) {		
		
		LinkedList<String> combinations = new LinkedList<String>();
		for (int i = 0; i < (1 << n); i++) {
			String str = "";
			for (int j = 0; j < n; j++) {

				if ((i & (1 << j)) > 0)
					str += set[j] + "-";
			}

			if (str.length() > 0)
				str = str.substring(0, str.length() - 1);

			if (str.contains("-")) {
				combinations.add(str);
			}
		}
		return combinations;
	}

	public static List<Interval> retrieveFreeTime(LinkedList<Interval> intervals) {

		if (intervals.size() == 0 || intervals.size() == 1)
			return intervals;
		else {
				intervals.addFirst(new Interval(0, 0));
			if (intervals.getLast().getEnd() != 24)
				intervals.addLast(new Interval(24, 0));
		}

		Interval first = intervals.get(0);
		double start = first.getStart();

		ArrayList<Interval> output = new ArrayList<Interval>();
		for (int i = 1; i < intervals.size(); i++) {
			Interval current = intervals.get(i);

			if (start < current.getStart()) {
				output.add(new Interval(start, current.getStart()));
				start = current.getEnd();
			} else {
				start = current.getEnd();
			}
		}

		return output;
	}

	public static LinkedList<Interval> mergeBusyTime(LinkedList<Interval> intervals) {

		if (intervals.size() == 0 || intervals.size() == 1)
			return intervals;

		Collections.sort(intervals, new IntervalComparator());

		Interval first = intervals.get(0);
		double start = first.getStart();
		double end = first.getEnd();

		LinkedList<Interval> result = new LinkedList<Interval>();

		for (int i = 1; i < intervals.size(); i++) {
			Interval current = intervals.get(i);
			if (current.getStart() < end) {
				end = Math.max(current.getEnd(), end);
			} else {
				result.add(new Interval(start, end));
				start = current.getStart();
				end = current.getEnd();
			}
		}

		result.add(new Interval(start, end));
		return result;
	}

	public static void main(String[] args) throws java.lang.Exception {

		HashMap<String, List<Interval>> inputData = new HashMap<String, List<Interval>>();
		inputData.put("Alice", Arrays.asList(new Interval(13.5, 14), new Interval(15.75, 17)));
		inputData.put("Bob", Arrays.asList(new Interval(9, 12), new Interval(13, 14), new Interval(14, 16)));
		inputData.put("Eve", Arrays.asList(new Interval(9, 11), new Interval(12.5, 13.5), new Interval(14, 15),	new Interval(16, 18)));
		inputData.put("Mallory", Arrays.asList(new Interval(0, 9), new Interval(12, 24)));

		String set[] = { "Alice", "Bob", "Eve", "Mallory" };
		int n = set.length;
		
		for (String getCombinations : (List<String>) retrieveCombinations(set, n)) {
			String[] splitByHyphen = getCombinations.split("-");
			LinkedList<Interval> addIntervals = new LinkedList<Interval>();
			for (String str : splitByHyphen) {
				for (Interval intrval : inputData.get(str)) {
					addIntervals.add(intrval);
				}
			}

			LinkedList<Interval> x = mergeBusyTime(addIntervals);

			System.out.println(getCombinations + " Busy Time=============================");
			for (Interval i : x) {
				System.out.println(i.getStart() + " " + i.getEnd());
			}
			System.out.println(getCombinations + " Free Time=============================");

			List<Interval> opt = retrieveFreeTime(x);

			for (Interval i : opt) {
				System.out.println(i.getStart() + " " + i.getEnd());
			}

			System.out.println("****************************************************");
		}

	}

}

class Interval {
	private double start;
	private double end;

	Interval() {
		start = 0;
		end = 0;
	}

	Interval(double s, double e) {
		start = s;
		end = e;
	}

	public double getStart() {
		return start;
	}

	public double getEnd() {
		return end;
	}
}

class IntervalComparator implements Comparator<Interval> {
	public int compare(Interval i1, Interval i2) {
		return Double.compare(i1.getStart(), i2.getStart());
	}
}

- Gerald Amalraj October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindInterval {

	public static List retrieveCombinations(String[] set, int n) {		
		
		LinkedList<String> combinations = new LinkedList<String>();
		for (int i = 0; i < (1 << n); i++) {
			String str = "";
			for (int j = 0; j < n; j++) {

				if ((i & (1 << j)) > 0)
					str += set[j] + "-";
			}

			if (str.length() > 0)
				str = str.substring(0, str.length() - 1);

			if (str.contains("-")) {
				combinations.add(str);
			}
		}
		return combinations;
	}

	public static List<Interval> retrieveFreeTime(LinkedList<Interval> intervals) {

		if (intervals.size() == 0 || intervals.size() == 1)
			return intervals;
		else {
				intervals.addFirst(new Interval(0, 0));
			if (intervals.getLast().getEnd() != 24)
				intervals.addLast(new Interval(24, 0));
		}

		Interval first = intervals.get(0);
		double start = first.getStart();

		ArrayList<Interval> output = new ArrayList<Interval>();
		for (int i = 1; i < intervals.size(); i++) {
			Interval current = intervals.get(i);

			if (start < current.getStart()) {
				output.add(new Interval(start, current.getStart()));
				start = current.getEnd();
			} else {
				start = current.getEnd();
			}
		}

		return output;
	}

	public static LinkedList<Interval> mergeBusyTime(LinkedList<Interval> intervals) {

		if (intervals.size() == 0 || intervals.size() == 1)
			return intervals;

		Collections.sort(intervals, new IntervalComparator());

		Interval first = intervals.get(0);
		double start = first.getStart();
		double end = first.getEnd();

		LinkedList<Interval> result = new LinkedList<Interval>();

		for (int i = 1; i < intervals.size(); i++) {
			Interval current = intervals.get(i);
			if (current.getStart() < end) {
				end = Math.max(current.getEnd(), end);
			} else {
				result.add(new Interval(start, end));
				start = current.getStart();
				end = current.getEnd();
			}
		}

		result.add(new Interval(start, end));
		return result;
	}

	public static void main(String[] args) throws java.lang.Exception {

		HashMap<String, List<Interval>> inputData = new HashMap<String, List<Interval>>();
		inputData.put("Alice", Arrays.asList(new Interval(13.5, 14), new Interval(15.75, 17)));
		inputData.put("Bob", Arrays.asList(new Interval(9, 12), new Interval(13, 14), new Interval(14, 16)));
		inputData.put("Eve", Arrays.asList(new Interval(9, 11), new Interval(12.5, 13.5), new Interval(14, 15),	new Interval(16, 18)));
		inputData.put("Mallory", Arrays.asList(new Interval(0, 9), new Interval(12, 24)));

		String set[] = { "Alice", "Bob", "Eve", "Mallory" };
		int n = set.length;
		
		for (String getCombinations : (List<String>) retrieveCombinations(set, n)) {
			String[] splitByHyphen = getCombinations.split("-");
			LinkedList<Interval> addIntervals = new LinkedList<Interval>();
			for (String str : splitByHyphen) {
				for (Interval intrval : inputData.get(str)) {
					addIntervals.add(intrval);
				}
			}

			LinkedList<Interval> x = mergeBusyTime(addIntervals);

			System.out.println(getCombinations + " Busy Time=============================");
			for (Interval i : x) {
				System.out.println(i.getStart() + " " + i.getEnd());
			}
			System.out.println(getCombinations + " Free Time=============================");

			List<Interval> opt = retrieveFreeTime(x);

			for (Interval i : opt) {
				System.out.println(i.getStart() + " " + i.getEnd());
			}

			System.out.println("****************************************************");
		}

	}

}

class Interval {
	private double start;
	private double end;

	Interval() {
		start = 0;
		end = 0;
	}

	Interval(double s, double e) {
		start = s;
		end = e;
	}

	public double getStart() {
		return start;
	}

	public double getEnd() {
		return end;
	}
}

class IntervalComparator implements Comparator<Interval> {
	public int compare(Interval i1, Interval i2) {
		return Double.compare(i1.getStart(), i2.getStart());
	}
}

- Anonymous October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindInterval {

	public static List retrieveCombinations(String[] set, int n) {		
		
		LinkedList<String> combinations = new LinkedList<String>();
		for (int i = 0; i < (1 << n); i++) {
			String str = "";
			for (int j = 0; j < n; j++) {

				if ((i & (1 << j)) > 0)
					str += set[j] + "-";
			}

			if (str.length() > 0)
				str = str.substring(0, str.length() - 1);

			if (str.contains("-")) {
				combinations.add(str);
			}
		}
		return combinations;
	}

	public static List<Interval> retrieveFreeTime(LinkedList<Interval> intervals) {

		if (intervals.size() == 0 || intervals.size() == 1)
			return intervals;
		else {
				intervals.addFirst(new Interval(0, 0));
			if (intervals.getLast().getEnd() != 24)
				intervals.addLast(new Interval(24, 0));
		}

		Interval first = intervals.get(0);
		double start = first.getStart();

		ArrayList<Interval> output = new ArrayList<Interval>();
		for (int i = 1; i < intervals.size(); i++) {
			Interval current = intervals.get(i);

			if (start < current.getStart()) {
				output.add(new Interval(start, current.getStart()));
				start = current.getEnd();
			} else {
				start = current.getEnd();
			}
		}

		return output;
	}

	public static LinkedList<Interval> mergeBusyTime(LinkedList<Interval> intervals) {

		if (intervals.size() == 0 || intervals.size() == 1)
			return intervals;

		Collections.sort(intervals, new IntervalComparator());

		Interval first = intervals.get(0);
		double start = first.getStart();
		double end = first.getEnd();

		LinkedList<Interval> result = new LinkedList<Interval>();

		for (int i = 1; i < intervals.size(); i++) {
			Interval current = intervals.get(i);
			if (current.getStart() < end) {
				end = Math.max(current.getEnd(), end);
			} else {
				result.add(new Interval(start, end));
				start = current.getStart();
				end = current.getEnd();
			}
		}

		result.add(new Interval(start, end));
		return result;
	}

	public static void main(String[] args) throws java.lang.Exception {

		HashMap<String, List<Interval>> inputData = new HashMap<String, List<Interval>>();
		inputData.put("Alice", Arrays.asList(new Interval(13.5, 14), new Interval(15.75, 17)));
		inputData.put("Bob", Arrays.asList(new Interval(9, 12), new Interval(13, 14), new Interval(14, 16)));
		inputData.put("Eve", Arrays.asList(new Interval(9, 11), new Interval(12.5, 13.5), new Interval(14, 15),	new Interval(16, 18)));
		inputData.put("Mallory", Arrays.asList(new Interval(0, 9), new Interval(12, 24)));

		String set[] = { "Alice", "Bob", "Eve", "Mallory" };
		int n = set.length;
		
		for (String getCombinations : (List<String>) retrieveCombinations(set, n)) {
			String[] splitByHyphen = getCombinations.split("-");
			LinkedList<Interval> addIntervals = new LinkedList<Interval>();
			for (String str : splitByHyphen) {
				for (Interval intrval : inputData.get(str)) {
					addIntervals.add(intrval);
				}
			}

			LinkedList<Interval> x = mergeBusyTime(addIntervals);

			System.out.println(getCombinations + " Busy Time=============================");
			for (Interval i : x) {
				System.out.println(i.getStart() + " " + i.getEnd());
			}
			System.out.println(getCombinations + " Free Time=============================");

			List<Interval> opt = retrieveFreeTime(x);

			for (Interval i : opt) {
				System.out.println(i.getStart() + " " + i.getEnd());
			}

			System.out.println("****************************************************");
		}

	}

}

class Interval {
	private double start;
	private double end;

	Interval() {
		start = 0;
		end = 0;
	}

	Interval(double s, double e) {
		start = s;
		end = e;
	}

	public double getStart() {
		return start;
	}

	public double getEnd() {
		return end;
	}
}

class IntervalComparator implements Comparator<Interval> {
	public int compare(Interval i1, Interval i2) {
		return Double.compare(i1.getStart(), i2.getStart());
	}
}

- gerald.amalraj October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

* Not a bug free, this is the very basic implementation to show my approach to the problem, you have to modify the source when additional cases are added.

* Typecasting the input value to float is not decent to the eyes o_O so please do improve them if you want to use it.

The approach can be breakdown by the following:
* collect the busy schedule/s
* calculate the "available schedule" based on the given busy schedule.
* find the available time intervals between each person using the "available schedules" data.

import java.util.List;
import java.util.ArrayList;

class Time {
    float start_time = 0.0f;
    float end_time = 0.0f;
    
    Time (float start, float end) {
        start_time = start;
        end_time = end;
    }
}

class Schedule {
    String name;
    List<Time> busySchedule;
    List<Time> freeSchedule;
    
    Schedule(String name) {
        this.name = name;
        busySchedule = new ArrayList<Time>();
        freeSchedule = new ArrayList<Time>();
    }

    void add(float start, float end) {
        Time time = new Time(start,end);
        busySchedule.add(time);
        addFreeSchedule(time);
    }

    private void addFreeSchedule(Time busy) {
        int size = freeSchedule.size();

        if (size > 0) {
            Time lastSched = freeSchedule.get(size - 1);
            if (lastSched.start_time == busy.start_time) {
                lastSched.start_time = busy.end_time;
            } else {
                lastSched.end_time = busy.start_time;
                if (busy.end_time < 24.0f) {
                    freeSchedule.add(new Time(busy.end_time, 24.0f));
                }
            }
        } else {
            if (busy.start_time > 0.0f) {
                freeSchedule.add(new Time(0.0f, busy.start_time));
            }
            if (busy.end_time < 24.0f) {
                freeSchedule.add(new Time(busy.end_time, 24.0f));
            }
        }
    }

    private boolean freeSchedAvailable(Time timeOne, Time timeTwo) {
        if (timeOne.start_time > timeTwo.start_time
            && timeOne.start_time < timeTwo.end_time) {
            return true;
        } else if (timeOne.end_time > timeTwo.start_time
            && timeOne.start_time < timeTwo.end_time) {
            return true;
        }
        return false;
    }

    List<Time> getAvailableSchedule(List<Time> other) {
        List<Time> availableSchedule = new ArrayList<Time>();

        for (Time time : freeSchedule) {
            for (Time yourTime : other) {
                if (!freeSchedAvailable(time, yourTime)) {
                    continue;
                }

                float start;
                float end;
                if (time.start_time >= yourTime.start_time) {
                    start = time.start_time;
                } else {
                    start = yourTime.start_time;
                }

                if (time.end_time <= yourTime.end_time) {
                    end = time.end_time;
                } else {
                    end = yourTime.end_time;
                }
                
                availableSchedule.add(new Time(start,end));
            }
        }

        return availableSchedule;
    }
}

class SchedulerDemo {
    public static void main(String[] args) {
        // Alice: [(13.5, 14), (15.75, 17)],
        Schedule aliceSched = new Schedule("Alice");
        aliceSched.add((float)13.5, (float)14);
        aliceSched.add((float)15.75, (float)17);

        // Bob: [(9, 12), (13, 14), (14, 16)], 
        Schedule bobSched = new Schedule("Bob");
        bobSched.add((float)9, (float)12);
        bobSched.add((float)13, (float)14);
        bobSched.add((float)14, (float)16);

        // Eve: [(9, 11), (12.5, 13.5), (14, 15), (16, 18)] 
        Schedule eveSched = new Schedule("Eve");
        eveSched.add((float)9, (float)11);
        eveSched.add((float)12.5, (float)13.5);
        eveSched.add((float)14, (float)15);
        eveSched.add((float)16, (float)18);

        // Mallory: [(0, 9), (12, 24)] 
        Schedule mallorySched = new Schedule("Mallory");
        mallorySched.add((float)0, (float)9);
        mallorySched.add((float)12, (float)24);

        List<Time> aliceBobFreeSched = aliceSched.getAvailableSchedule(bobSched.freeSchedule);
        System.out.print("Alice, Bob => [");
        for (Time time : aliceBobFreeSched) {
            System.out.print("(" + time.start_time + ", "  + time.end_time + "), ");
        }
        System.out.print("]\n");

        List<Time> bobMalloryFreeSched = bobSched.getAvailableSchedule(mallorySched.freeSchedule);
        System.out.print("Bob, Mallory => [");
        for (Time time : bobMalloryFreeSched) {
            System.out.print("(" + time.start_time + ", "  + time.end_time + "), ");
        }
        System.out.print("]\n");

        List<Time> aliceBobEveFreeSched = eveSched.getAvailableSchedule(aliceBobFreeSched);
        System.out.print("Alice, Bob, Eve=> [");
        for (Time time : aliceBobEveFreeSched) {
            System.out.print("(" + time.start_time + ", "  + time.end_time + "), ");
        }
        System.out.print("]\n");
    }
}

Output:
Alice, Bob => [(0.0, 9.0), (12.0, 13.0), (17.0, 24.0), ]
Bob, Mallory => []
Alice, Bob, Eve=> [(0.0, 9.0), (12.0, 12.5), (18.0, 24.0), ]

- jan.michael.gardose October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python:

def trace(txt):
    traceOn = False
    if traceOn:
        print(txt)

class Scheduler:
    def __init__(self):
        self._s = {}

    def addPerson(self, name, *schedule):
        self._s[name] = schedule
        
    def getFreeTime(self, *names):
        freeTime = set(range(0,24*100)) # in minutes
        
        for name in names:
            busyTime = set()
            for start, end in self._s[name]:
                busyTime |= set(range(int(start*100), int(end*100)))
            trace("%s BUSY -> %s"%(name, busyTime))
            freeTime = freeTime - busyTime
        trace("%s FREE -> %s"%(name, freeTime))
        
        startFree = None
        prev = None
        res = []
        for min in sorted([*freeTime]):
            if startFree == None:
                startFree  = min
                continue
            if prev is not None and min-prev > 1:
                res.append((startFree/100,(prev+1)/100))
                prev = min
                startFree = min
            prev = min
        if prev is not None:
            res.append((startFree/100,(prev+1)/100))
        print("free time: %-20s \t%s"%(names,res))

s = Scheduler()
s.addPerson('Alice', (13.5, 14), (15.75, 17))
s.addPerson('Bob', (9, 12), (13, 14), (14, 16))
s.addPerson('Eve', (9, 11), (12.5, 13.5), (14, 15), (16, 18))
s.addPerson('Mallory', (0, 9), (12, 24))
                
s.getFreeTime('Alice')
s.getFreeTime('Alice', 'Bob')
s.getFreeTime('Bob', 'Mallory')
s.getFreeTime('Alice', 'Bob', 'Eve')

Output:

free time: ('Alice',)           	[(0.0, 13.5), (14.0, 15.75), (17.0, 24.0)]
free time: ('Alice', 'Bob')     	[(0.0, 9.0), (12.0, 13.0), (17.0, 24.0)]
free time: ('Bob', 'Mallory')   	[]
free time: ('Alice', 'Bob', 'Eve') 	[(0.0, 9.0), (12.0, 12.5), (18.0, 24.0)]

- Diana.Savvatina November 06, 2018 | 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