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;
    }
}

- RajK July 16, 2017 | Flag Reply
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<>());
                }
                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;
    }
}

- VigilDBest July 19, 2017 | Flag Reply
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) ✗

- NoOne July 16, 2017 | Flag Reply
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 } } });

- PenChief September 11, 2017 | Flag Reply
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.

- ab asudeh July 15, 2017 | Flag Reply
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.

- Ab. Asudeh July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.


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