## Facebook Interview Question for SDE1s

Country: United States

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

This is a *recursive* approach:
Step 1: Pick one movie at a time and fix it's schedule.
Step 2: Recurse to schedule the rest of the movies. If can't then go back to Step 1

``````public class MovieScheduler {
public static void main(String[] args) {
Map<String, List<Integer>> movies = new HashMap<>();
movies.put("Shining", Arrays.asList(14, 15, 16));
movies.put("Kill Bill", Arrays.asList(14, 15));
movies.put("Pulp Fiction", Arrays.asList(14, 15));
List<String> movieNames = new ArrayList<>(movies.keySet());
Map<Integer, String> schedule = new HashMap<>();
if (schedule(movies, movieNames, 0, schedule)) {
System.out.println("Schedule is " + schedule);
} else {
System.out.println("Unable to schedule!!");
}
}

private static boolean schedule(Map<String, List<Integer>> movies, List<String> movieNames, int index, Map<Integer, String> schedule) {
if (index == movieNames.size())
return true;

String movie = movieNames.get(index);
List<Integer> timings = movies.get(movie);
for(int timing : timings) {
if (!schedule.containsKey(timing)) {
Map<Integer, String> scheduleCopy = new HashMap<>(schedule);
scheduleCopy.put(timing, movie);
if (schedule(movies, movieNames, index+1, scheduleCopy)) {
schedule.clear();
schedule.putAll(scheduleCopy);
return true;
}
}
}
return false;
}
}``````

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

``````import java.util.*;

public class ScheduleMovies {

public static void main(String[] args) {
ScheduleMovies scheduleMovies = new ScheduleMovies();

HashMap<String, int[]> movieSchedules = new HashMap<>();

movieSchedules.put("K3G", new int[]{10, 11, 12});
movieSchedules.put("DDLJ", new int[]{9, 10});
movieSchedules.put("HAHK", new int[]{10});
movieSchedules.put("KKHH", new int[]{9, 10, 11});
movieSchedules.put("LS", new int[]{11, 12, 13});

System.out.println(scheduleMovies.getSchedule(movieSchedules));
}

public Map<String, Integer> getSchedule(HashMap<String, int[]> movieSchedules) {
Map<String, Integer> movieSchedule = new HashMap<>();

Map<String, Integer> movieOccurrence = new HashMap<>();
Map<Integer, List<String>> movieTimings = new TreeMap<>();

for (Map.Entry<String, int[]> entry : movieSchedules.entrySet()) {
int[] schedule = entry.getValue();
for (Integer timing : schedule) {
if (!movieTimings.containsKey(timing)) {
movieTimings.put(timing, new ArrayList<>());
}
}
movieOccurrence.put(entry.getKey(), entry.getValue().length);
}

for (Map.Entry<Integer, List<String>> entry : movieTimings.entrySet()) {
List<String> movies = entry.getValue();

String leastOccurrenceMovie = null;
Integer occurrence = Integer.MAX_VALUE;

for (String movie : movies) {
if (movieOccurrence.get(movie) != null && movieOccurrence.get(movie) <= occurrence) {
leastOccurrenceMovie = movie;
occurrence = movieOccurrence.get(movie);
}
if (movieOccurrence.get(movie) != null) {
movieOccurrence.put(movie, movieOccurrence.get(movie) - 1);
}
}

movieSchedule.put(leastOccurrenceMovie, entry.getKey());
movieOccurrence.remove(leastOccurrenceMovie);

}

return movieSchedule;
}
}``````

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

Cheating using ZoomBA, avoiding all of recursion... and

``````movies = { "Shining" : [14, 15, 16],
"kill bill" : [14, 15],
"Pulp fiction": [14, 15] }
args = list ( movies.entries ) as { name = \$.key ; list( \$.value ) as { [ name, \$.o ] } }
movie_size = size(movies)
all_sched = join( @ARGS = args ) where {
items = list ( \$.o )
sorta ( items ) where { \$.left[1] < \$.right[1] }
!exists ( [1:movie_size] ) where { items[\$.o][1] - items[\$.o-1][1] < 1 }
}
println(str(all_sched,'\n'))``````

And just to showcase that it did find the results, here are the results :

``````➜  wiki git:(master) ✗ zmb tmp.zm
@[ @[ Shining,16 ],@[ Pulp fiction,14 ],@[ kill bill,15 ] ]
@[ @[ Shining,16 ],@[ Pulp fiction,15 ],@[ kill bill,14 ] ]
➜  wiki git:(master) ✗``````

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

Using hash, no recursive functions:
* Store all the movies using std::map using int (movie-start-time) as the key and the value is std::unordered_set (hash-table) containing the movies that start at that time

NOTE: I used std::map because the underlying implementation is red-black tree, i.e. the items will be sorted based on the key (i.e. the start-time)

We then iterate over the map and print the possibilities (eliminating duplication as much as we can, we dont want to watch the same movie twice...)

``````void ScheduleMovies(const std::vector<std::pair<std::string, std::vector<int> > >& movies)
{
// Create a map based on the start time as key
std::map<int, std::unordered_set<std::string> > M;
std::for_each(movies.begin(), movies.end(), [&](const std::pair<std::string, std::vector<int> >& p) {
const std::string& name = p.first;
const std::vector<int>& movieHours = p.second;
for(size_t i = 0; i < movieHours.size(); ++i) {
if(M.count(movieHours[i]) == 0) {
M[movieHours[i]] = std::unordered_set<std::string>();
}
std::unordered_set<std::string>& moviesList = M[movieHours[i]];
moviesList.insert(name);
}
});

// Print the first option that has no conflict
while(true) {
std::vector<std::string> Plan;
std::unordered_set<std::string> Watched;
std::for_each(M.begin(), M.end(), [&](std::map<int, std::unordered_set<std::string> >::value_type& vt) {
// get the first movie from the list that we didn't watch yet
int movieHour = vt.first;
std::unordered_set<std::string>& possibleMovies = vt.second;
std::unordered_set<std::string>::const_iterator iter = std::find_if(possibleMovies.begin(),
possibleMovies.end(), [&](const std::string& name) { return (Watched.count(name) == 0); });
if(iter == possibleMovies.end() && !possibleMovies.empty()) {
// Could not find a match, pick the first movie
Plan.push_back(*(possibleMovies.begin()) + " " + std::to_string(movieHour));
Watched.insert(*(possibleMovies.begin()));
possibleMovies.erase(possibleMovies.begin());

} else if(iter != possibleMovies.end()) {
Plan.push_back(*(iter) + " " + std::to_string(movieHour));
Watched.insert(*iter);
possibleMovies.erase(iter); // Remove it
}
});
if(Plan.empty()) {
break;
}
std::for_each(Plan.begin(), Plan.end(), [&](const std::string& item) { std::cout << item << " "; });
std::cout << std::endl;
Plan.clear();
}
}``````

Example:

``ScheduleMovies({ { "Shining", { 14, 15, 16 } }, { "Kill Bill", { 14, 15 } }, { "Pulp Fiction", { 14, 15 } } });``

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

book the first hour of the first film (\$occ array ["hour" => "movie_name"]), and make a recursive call, with attempt to book the next movie. If failing to book, try the next hour. Do this until reaching the last movie and booking it successfully.

``````function filmsMatch(\$list, \$occ = []) {
if (empty(\$list)) return false;
if (count(\$list) == count(\$occ)) return \$occ;
\$i = count(\$occ);
if (!isset(\$list[\$i])) return false;

foreach (\$list[\$i][1] as \$hr) {
if (!isset(\$occ["hr_\$hr"])) {
\$res = filmsMatch(\$list, array_merge(\$occ, ["hr_\$hr" => \$list[\$i][0]]));
if (\$res !== false) return \$res;
}
}

return false;
}``````

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

1. Generate HM which tells at each hour, which movies could be played.
2. In a loop till no hours are left, start with the hour which has 1 movie only.
3. For that particular movie, remove it's name for all the timings it can be played.
4. continue this for next time (which has 1 inlet only : that is which can play only one movie)

O(m) space : m no. of times which can be played.
O(n) time : no. of inputs

Comment hidden because of low score. Click to expand.
-2
of 2 vote

It is a bipartite matching problem.
Consider a bipartite graph in which the left partite are the movies and the right partite are the time slots. There is an edge b/w from the node M[i] to T[j] iff movie i is shown at time j.

Now, in order to solve the bipartite matching, one can transform it to Maximum Flow, by adding a source node in the left of the left partite and a destination in the right of the right partite. All the movies are connected to the source and all time slots are connected to the destination node. Finally, all the edge weights are set to 1.

The problem can get simply solved in the order of O((n+m)^3) using the push-relabel algorithm.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

It is a bipartite matching problem.
Consider a bipartite graph in which the left partite are the movies and the right partite are the time slots. There is an edge b/w from the node M[i] to T[j] iff movie i is shown at time j.

Now, in order to solve the bipartite matching, one can transform it to Maximum Flow, by adding a source node in the left of the left partite and a destination in the right of the right partite. All the movies are connected to the source and all time slots are connected to the destination node. Finally, all the edge weights are set to 1.

The problem can get simply solved in the order of O((n+m)^3) using the push-relabel algorithm.

Comment hidden because of low score. Click to expand.

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.

### 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.