Facebook Interview Question
SDE1sCountry: United States
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<>());
}
movieTimings.get(timing).add(entry.getKey());
}
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;
}
}
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) ✗
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 } } });
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;
}
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
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.
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.
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
- kredible July 16, 2017