## Facebook Interview Questions

- 0of 0 votes
download all urls from 1000 hosts. Imagine all the urls are graph.

Requirement: Each host has bad internet connection among each other, Has to download url exacly once.

- 2of 2 votes
FB on-site two weeks ago last round of coding . (This problem is also in the internal question bank of G.)

There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.

You have a remote that could walk the robot into any of the four directions - up, left, down or right.

Here is the move method: boolean move(int direction), direction: 0, 1, 2, 3. If the robot hits the wall, the method returns false.

Otherwise returns true and the robot moves on to the direction given.

Find out the area of the room.

e.g.

X

XXX X

XXXXX 'X' marks the floor plan of the room.

A room like such has an area of 10.

- 0of 0 votes
Give you a robot and a room where you do not know where the robot is in the room and you do not know the size of the room, you have a remote control that allows the robot to walk around four directions. Here you give a move method: boolean move (int direction), direction: 0,1,2,3 that four directions. If it can move in that direction, return true, and if it cannot move in that direction, return false. Ask you determine how big this room is. the shape of the room can be any shape, so you cannot assume it is rectangle or square.

- 0of 0 votes
Given a 2D character array of size NxN. Find if there is a path from the cell 'R' to the cell 'T'. You can go left, right, up, down from a cell and you cannot pass through any cell marked with 'X'.

Example input:

X__R_X

X_XXX_

______

_XX_XX

XT__X_

Output: true

- 0of 0 votes
Print all permutations of a given string.

- 0of 0 votes
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You can begin the journey with an empty tank at one of the gas stations.

Return ALL the starting gas station's index where you can travel around the circuit once

public List<Integer> canCompleteCircuit(int[] gas, int[] cost) {

}

- 1of 1 vote
You have a array with integers:

`[ 1, -2, 0, 6, 2, -4, 6, 6 ]`

You need to write a function which will evenly return indexes of a max value in the array.

In the example below max value is 6, and its positions are 3, 6 and 7. So each run function should return random index from the set.

Try to implement with O(n) for computation and memory.

Try to reduce memory complexity to O(1).

- 0of 0 votes
You have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:

`0 / \ 0 1 / \ / \ 0 1 1 1`

You need to write a code, which will invert given LEAF and put tree in a correct state.

- 0of 0 votes
Given n1, n2 is the number after removing one digit from n1. Example, n1 = 123, then n2 can be 12, 13 or 23.

If we know the sum of n1 + n2, and find the possible values of n1 and n2.

public List<List<Integer>> getNumber(int sum){

}

- 0of 0 votes
Design copy-on-write string class

e.g. stringclass s("abc");

stringclass s1 = s; // no copy

s = "bcd"; // copy

- 0of 0 votes
Design and implement an algorithm to assign an unlimited M number of messages evenly among N number of servers (N will not change).

Input to the algorithm

A message contains a message identifier and a text string. The algorithm will be fed one message at a time.

There are N numbers of servers (N will not change), each can be identified by a unique id.

Output of the algorithm

When the algorithm is called to process a message, it should output the id of the server that the message is assigned to.

- 0of 0 votes
Given an ODD number, print diamond pattern of stars recursively.

`n = 5, Diamond shape is as follows: * *** ***** *** *`

void print(int n){

}

- 0of 0 votes
/From the input array, output a subset array with numbers part of a Fibonacci series.

// input: [4,2,8,5,20,1,40,13,23]

// output: [2,5,1,8,13]

public static List<Integer> getFibNumbers(int[] nums){}

- 0of 0 votes
The number of valid combinations of a strings for given input array a[], where a=>1, z => 26, and 0 <= a[i] <= 9

{1,1,1} => {aaa, ak, ka} => 3

{1,1,0} => {aj} => 1

- 0of 0 votes
Can multiple threads improve the time complexity to merge k sorted arrays? If so, how?

- 0of 0 votes
Gives an array of unsorted int (may have negative number),

rearrange the array such that the

num at the odd index is greater than the num at the even index.

example

giving 5, 2, 3, 4, 1, one of the expected result is 1,4,2,5,3,

please solve it in o(n) time, where n is the length of the array

public void rearrange(int[] nums){

}

- 0of 0 votes
`Given a string, find all possible combinations of the upper and lower case of each Alphabet char, keep the none Alphabet char as it is. example1 s = "ab", return: "Ab", "ab", "aB", "AB" example2 s = "a1b", return: "A1b", "a1b", "a1B", "A1B" public List<String> getPermutation(String s){ }`

- 0of 0 votes
Given a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)

Node restore(List<Integer> list)

Example Tree:

5

/ \

3 2

/ / \

1 6 1

- 0of 0 votes
For a given array, find the subarray (containing at least k number) which has the largest sum.

Example:

// [-4, -2, 1, -3], k = 2, return -1, and the subarray is [-2, 1]

// [1, 1, 1, 1, 1, 1], k = 3, return 6, and the subarray is [1, 1, 1, 1, 1, 1]

try to do it in O(n) time

Followup, if input is stream, how to solve it

public int maxSubArray(int[] nums, int k) {}

- 0of 0 votes
find maximum contiguous subarray sum with size (the number of the element in the subarray) <= k

a brute force method is very simple, can you do it better?

public int maxSum(int[] nums, int k){

}

- 0of 0 votes
I want to learn some big words so people think I'm smart.

I opened up a dictionary to a page in the middle and started flipping through, looking for words I didn't know. I put each word I didn't know at increasing indices in a huge array I created in memory. When I reached the end of the dictionary, I started from the beginning and did the same thing until I reached the page I started at.

Now I have an array of words that are mostly alphabetical, except they start somewhere in the middle of the alphabet, reach the end, and then start from the beginning of the alphabet. In other words, this is an alphabetically ordered array that has been "rotated." For example:

String[] words = new String[]{

"ptolemaic",

"retrograde",

"supplant",

"undulate",

"xenoepist",

"asymptote", // <-- rotates here!

"babka",

"banoffee",

"engender",

"karpatka",

"othellolagkage",

};

Write a function for finding the index of the "rotation point," which is where I started working from the beginning of the dictionary. This array is huge (there are lots of words I don't know) so we want to be efficient here.

- 0of 0 votes
// Read4K - Given a function which reads from a file or

// network stream up to 4k at a time, give a function which

// which can satisfy requests for arbitrary amounts of data

private int read4K(char[] buf) {

// GIVEN

}

// IMPLEMENT:

public int read(char[] buf, int toRead) { }

Due to network latency, if the read4K method return a value < 4k, it does not necessarily mean that we reach the End of File (EOF), in this case, you should continue to read the file until you reach toRead or EOF.

- 0of 0 votes
given a graph: example -> A company holds 10% of B company’s share,

B company holds 5% of C company’s share, A company holds 2% of C company’s share,

what percent of C company’s share does A company hold?

- 0of 0 votes
`// Design and implement key value system // // string -> string // Insert a key-value pair or modify a value void put(string key, string value); // Delete a key-value pair void delete(string key); // Gets a value given a snapshot string get(string key, Snapshot snap); // Take a snapshot Snapshot takeSnapshot(); // Delete a snapshot void deleteSnapshot(Snapshot snap); // put(k1,v1) // put(k2,v2) // put(k3,v3) // takeSnapshot -> snap1 { k1 -> v1, k2 -> v2, k3 -> v3 } // get(k1,snap1) -> v1 // put(k1,v4) // delete(k3) // takeSnapshot -> snap2 { k1 -> v4, k2 -> v2 } // get(k1,snap2) -> v4 // get(k1,snap1) -> v1 // get(k3,snap2) -> XX // deleteSnapshot(snap1) // get(k1,snap1) -> XX // Space efficient is more important than time efficient, thus please use as small space as possible.`

- 0of 0 votes
Insert node with a given value in a circular sorted linked list.

- 0of 0 votes
Given list of N points find the K closest points to origin i.e((0,0)).

- 0of 0 votes
Given a mapping from digits to list of letters and a string of digits of arbitrary length determine all possible ways to replace the digits with letters.

Input Mapping = {

'1' → ['A', 'B', 'C'],

'2' → ['D', 'E', 'F'],

...

}

Avg length of map values - N

Input String = “12” - K

Expected Output = [“AD”, “AE”, “AF”, “BD”, “BE”, “BF”, “CD”, “CE”, “CF”]

- 0of 0 votes
Given a task sequence tasks such as ABBABBC, and an integer k, which is the cool down time between two same tasks. Assume the execution for each individual task is 1 unit.

rearrange the task sequence such that the execution time is minimal.

Example:

S = AAABBBCCC, K = 3

Result: ABCABCABC (all 'A's are 3 distance apart, similarly with B's and C's), thus return 9

S = AAABC, K=2

Result: ABCA_ _A, thus return 7

S = AAADBBCC, K = 2:

Result: ABCABCDA, thus return 8

public int rearrangeTasks(String tasks, int cooldown){

}

- 0of 0 votes
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

Try to do it in one pass

example

[4, 2, 0, 5, 2, 0, 1] return: 0, 2

[1, 2, 3, 0, 0, 1, 3, 6, 6,6] return 0, 1, 3, 6

public List<Integer> findRepeat(int nums[]){

}

- 0of 0 votes
`convert a ternary expression into a Binary tree structure. a?b:c a / \ b c a?b?c:d:e a / \ b e / \ c d class TreeNode{ char val; TreeNode left; TreeNode right; public TreeNode(char val){ this.val = val; } } public TreeNode build(String s){}`

try to do it in o(n) time complexity, n is the size of the string