## Facebook Interview Questions

- 0of 4 votes

AnswersGiven two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves.

- wtcupup2017 November 27, 2016 in United States

Follow Up: If they are general binary trees instead of BSTs, could you solve it? give out your reason.

For the first question, I was thinking to construct two BSTs from pre-order traversal then do a leaf-level comparison. Any better solutions are welcome.| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 3of 3 votes

AnswersFinding biggest plus sign "+" in a sparse matrix(matrix with elements 0 and 1)

- wtcupup2017 November 19, 2016 in United States

For example, the biggest plus sign for following matrix is located at (2,2), with length 1 for each edge(Yes, each edge should have same length)

0 0 1 0 0 1 0

1 0 1 0 1 0 1

1 1 1 1 1 1 1

0 0 1 0 0 0 0

0 0 0 0 0 0 0

Hint: use DFS/BFS| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 3of 3 votes

AnswersDefine amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.

- wtcupup2017 November 13, 2016 in United States

Example 1: 0, 1, 2, 3

Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.

Example 2: 1, 0 , 0

Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.

If there are multiple positions, return the smallest one.

should get a solution with time complexity less than O(N^2)| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 1of 1 vote

AnswersUsing that data structure, devise an algorithm to compute the dot product between two sparse matrices.

- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 0of 0 votes

AnswersWhat data structure would you use to store the entries of a sparse matrix?

- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer Data Structures - 1of 1 vote

Answers/*

- cheeyim October 28, 2016 in Singapore

# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.

# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:

# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.

# For example:

# input = [(1,4), (2,3)]

# > 3

# input = [(4,6), (1,2)]

# > 3

# input = [(1,4), (6,8), (2,4), (7,9), (10, 15)]

# > 11

*/| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 1of 1 vote

AnswersGiven two (binary) trees, return the first pair of non-matching leaves

- bobshanely October 03, 2016 in United States

Tree 1: A, B, C, D, E, null, null

Tree 2: A, D, B

Output: (E,B)| Report Duplicate | Flag | PURGE

Facebook Intern Trees and Graphs - 3of 3 votes

AnswersGiven: sorted array of integers

- 123georgedavid September 21, 2016 in United States

Return: sorted array of squares of those integers

Ex: [1,3,5] -> [1,9,25]

Integers can be negative.| Report Duplicate | Flag | PURGE

Facebook Software Engineer - 0of 0 votes

AnswersDesign a HTTP response service that will allow sync and async download. What classes would you create and the methods used with paramerters and return types.

- MM September 10, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Software Developer Object Oriented Design - 2of 2 votes

AnswersConvert a number to English representation.

- coder145 August 09, 2016 in United States

Ex: Input : 100

Output : One Hundred.| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 1of 1 vote

AnswersHow do I find the longest possible route in a matrix?

- axaysd July 30, 2016 in United States

There are some hurdles in the path.

Details in image : https://s31.postimg.org/7nwp4gmzv/hurdle1.jpg| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

AnswersGiven Nodes such as

`M-> N-> T-> D-> E | | | | C X Y L | | A Z`

-> right pointer

- Raj July 14, 2016 in United States

| down pointer

Output should be

M->C->A->N->X->Z->T->Y->D-L>E

Write this to flatten

flatten(Node head) {

}

Node {

Node right;

Node down;

char a;

}| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 1of 1 vote

AnswersYou have an array of unique integer numbers and only one operation: MoveToFront(x) that moves given number to the beginning of the array.

- emb July 02, 2016 in United States

Write a program to sort the array using the minimum possible number of MoveToFront() calls.| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 2of 2 votes

AnswersGiven an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X

- falkon June 29, 2016 in United States

[1, 3, 5, 18] X = 8 Output: True

X = 9 Output: True

X = 10 Output: False

X = 40 Output :False| Report Duplicate | Flag | PURGE

Facebook - 2of 2 votes

AnswersA museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.

- fire May 17, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Android Engineer Algorithm - 1of 1 vote

AnswersYou are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123".

- sachin323 May 16, 2016 in United States

For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).

for string "1234" we have following possible combinations, I might be missing some of them but you get the idea

{12, 3, 4}

{1, 23, 4}

{1, 2, 3, 4}| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 0of 0 votes

Answers// Reverse the words. Given a String that contains words separated by single space, reverse the words in the String. You can assume that no leading or trailing spaces are there.

// For example: "Man bites dog" => "dog bites Man”

- almunayer May 10, 2016 in United States`String reverseWords(String value) { // Insert implementation }`

| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 1of 1 vote

AnswersSelect Kth largest value in the array. Given an unsorted array of size n, and a value k. Select the kth largest value from the array.

For example:

Array is [5, 3, 9, 1], n is 4

k = 0 => 9

k = 1 => 5

k = 3 => 1

- almunayer May 10, 2016 in United States`public int kthLargest(int array[], int k) { // ..... }`

| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 2of 2 votes

AnswersGiven two sorted linked lists of integers write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order. You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.

- vkoolkatz April 28, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer Data Structures - 0of 0 votes

AnswersThere are N coins with coordinates (x, y) where x >0 and y >0

- emb April 02, 2016 in United States

You start at (0, 0) and you can only do steps of form (dx, dy) where dx >0 and dy > 0

Print the maximum number of coins that you can collect.

Clarification: you can do as many moves as you wish, the point is to collect maximum number of coins. If you are located at position (a, b) you may jump to position (a+dx, b+dy) for all dx > 0 and dy > 0

@krbchd: Your algorithm may output incorrect values. Suppose there are points (5, 7), (5, 8), (5, 9) for y coordinates LIS will output 7, 8, 9, however since these points are on the same x axis, you can choose only one of them.| Report Duplicate | Flag | PURGE

Facebook Software Developer Algorithm - 2of 2 votes

AnswersGIven a string "str" and pair of "N" swapping indices, generate a lexicographically largest string. Swapping indices can be reused any number times.

- uvm March 15, 2016 in United States

Eg 1)

String = "abdc"

Indices:

(1,4)

(3,4)

Answer:

cdba, cbad, dbac,dbca

you should print only "dbca" which is lexicographically largest.| Report Duplicate | Flag | PURGE

Facebook SDE-2 Algorithm - 4of 4 votes

AnswersGiven the root of a binary tree containing integers, print the columns of the tree in order with the nodes in each column printed top-to-bottom.

- takepwn February 26, 2016 in United States`Input: 6 / \ 3 4 / \ \ 5 1 0 / \ / 9 2 8 \ 7 Output: 9 5 3 2 6 1 7 4 8 0 Input: 1 / \ 2 3 / \ / \ 4 5 6 7 When two nodes share the same position (e.g. 5 and 6), they may be printed in either order: Output: 4 2 1 5 6 3 7 or: 4 2 1 6 5 3 7`

| Report Duplicate | Flag | PURGE

Facebook Software Engineer Intern Trees and Graphs - 0of 0 votes

AnswersGiven an array and a number, add it in such a way where array is [0,0,1] and number is 4 output will be [0,0,5]

- Ipalibo February 25, 2016 in United Kingdom

Example 2 :

array is [1] and number is 9 output will be [1,0]| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 0of 0 votes

AnswersGiven a set of numbers {x1, x2, x3, x4, ..., xN} (N>=3) a set of its pairwise sums is {x1+x2, x1+x3, x1+x4, x2+x3,x2+x4,x3+x4, ...,}. (That is s_k = x_i + x_j where i != j)

Restore a set of numbers given a set of its pairwise sums.

Note: you don't know given some k, to which i and j it refers, (i.e. input is given in undefined order)

EDIT: couldn't comment, so here is clarification

Example:`S = {1, 5, 10, 100} (n elements) P = {6, 11, 101, 15, 105, 110} (n * (n - 1) / 2 elements)`

Given P you have to restore S.

Note here means that if you knew which element in P corresponded to which pair of indices in S, you could just solve a simple linear equation

- emb February 22, 2016 in United States`x1+x2=a{k1} x2+x3 = a{k2}, ...., x{n-1} + x{n} = a{k{n-1}, x{n} + x1 = a{k{n}}`

| Report Duplicate | Flag | PURGE

Facebook Intern - 1of 1 vote

AnswersGiven a string where in each word letters were randomly shuffled and after that words were written without spaces (lets call it X). Also you have a dictionary. The task is to return all possible strings S that can be transformed into the string X and all words in S are from dictionary.

- golyjivan February 19, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 2of 2 votes

AnswersGiven two arrays/Lists (choose whatever you want to) with sorted and non intersecting intervals. Merge them to get a new sorted non intersecting array/list.

- HumbleLearner February 12, 2016 in United States

Eg:

Given:

Arr1 = [3-11, 17-25, 58-73];

Arr2 = [6-18, 40-47];

Wanted:

Arr3 = [3-25, 40-47, 58-73];| Report Duplicate | Flag | PURGE

Facebook Software Engineer Intern Algorithm - 3of 3 votes

AnswersTask schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now----

- songty11 January 27, 2016 in United States

Input: string, n

Output: the best task-finishing sequence.

eg. input: AAABBB, 2

Output: AB_AB_AB

( "_" represents do nothing and wait)| Report Duplicate | Flag | PURGE

Facebook Software Engineer Intern Algorithm - 1of 1 vote

AnswersGiven a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.

- JP Ventura January 09, 2016 in United States`#!/usr/bin/env python3 assert solution(-15) == '110001' assert solution(2) == '110' assert solution(13) == '11101'`

| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer Algorithm - 3of 3 votes

AnswersGiven a forest of balanced binary trees and two nodes, n1 and n2, find the closest common parent of n1 and n2. Nodes have parameters "parent", "left" and "right", and you cannot access the values of the nodes. If n1 and n2 are not on the same tree, return NULL.

- Matt Cooper December 26, 2015 in United States for Software Engineering

Try to do this in O(log(n)) time and O(1) space.| Report Duplicate | Flag | PURGE

Facebook Intern Trees and Graphs - 2of 2 votes

AnswersGiven an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.

- neer.1304 December 25, 2015 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window