## Facebook Interview Questions

- 1of 1 vote
Given a binary tree that complies to the following rule:

The parent node value is always the the result of the AND operator of its children values.

You modify one of the LEAF nodes value (e.g. if it was 1 it is now 0). Write a function that fixes the tree

so it complies with the above rule.`// // 0 1 // / \ / \ // 1 0 =====> 1 1 // / \ / \ / \ / \ // 1 1 0 1 1 1 1 1 // // The parent node value is always children value's LOGICAL AND // & //`

- 0of 0 votes
Given an array of integers, return the index of the max value in this array.

Note:

If the max value appears more than once, the function should return one the indexes, but make it so that the next call will return different index.

Important: you are not allowed to store state between calls

Example: given this input array`// 0 -1 6 4 5 6 6 // | | | // 2,1/3 5,1/3 6,1/3`

Function signature:

`int getIndex(const std::vector<int>& numbers);`

Example output:

`2 5 6 5 2`

Extension:

What if you knew how many times the max value appears in the array, can you improve the function performance?

So using the given example array, the function signature is now:`int getIndex(const std::vector<int>& numbers, int maxCount);`

- 0of 0 votes
`Given an array of n * m matrix, and a moving matrix window (size k * k), move the window from top left to bottom right at each iteration, find the median number inside the window at each moving Can you do it better than brutal force method? void getMedian(int[][] matrix, int k){ print median } For matrix [ [1, 5, 3], [3, 2, 1], [4, 1, 9], ] The moving window size k = 2. At first the window is at the start of the array like this [ [|1, 5|, 3], [|3, 2|, 1], [4, 1, 9], ] ,get the median (2 + 3) / 2 = 2.5; then the window move one step forward. [ [1, |5, 3|], [3, |2, 1|], [4, 1, 9], ] ,get the median (2 + 3) / 2 = 2.5 then the window move one step forward again. [ [1, 5, 3], [|3, 2|, 1], [|4, 1|, 9], ] ,get the median (2 + 3) / 2 = 2.5 then the window move one step forward again. [ [1, 5, 3], [3, |2, 1|], [4, |1, 9|], ] ,get the median (1 + 2) / 2 = 1.5`

- 1of 1 vote
We are planning an orienteering game.

The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.

However, the players have to pass all the checkpoints (@) on the map.

An orienteering map is to be given in the following format.

########

#@....G#

##.##@##

#..@..S#

#@.....#

########

In this problem, an orienteering map is to be given.

Calculate the minimum distance from the start to the goal with passing all the checkpoints.

Specification

* A map consists of 5 characters as following.

You can assume that the map does not contain any invalid characters and

the map has exactly one start symbol 'S' and exactly one goal symbol 'G'.

* 'S' means the orienteering start.

* 'G' means the orienteering goal.

* '@' means an orienteering checkpoint.

* '.' means an opened-block that players can pass.

* '#' means a closed-block that players cannot pass.

* It is allowed to move only by one step vertically or horizontally (up, down, left, or right) to the

next block.

Other types of movements, such as moving diagonally (left up, right up, left down and right down)

and skipping one or more blocks, are NOT permitted.

* You MUST NOT get out of the map.

* Distance is to be defined as the number of movements to the different blocks.

* You CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary.

* You can assume that parameters satisfy following conditions.

* 1 <= width <= 100

* 1 <= height <= 100

* The maximum number of checkpoints is 18.

- 0of 0 votes
convert prefix to postfix expression

public String convert2postfix(String prefix){

}

- 1of 1 vote
Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array

can you do it without extra space

- 1of 1 vote
I get a chance to talk to Facebook software engineer during my android engineer interview. He asked me couple of question about native android like diff between views and fragment, mutable and immutable string, diff between string builder and string and a programming question convert int into words.

- 2of 2 votes
There is a maze of size m*n. You are sitting at (0,0). Another person is sitting in another cell. There are some cheeses placed in different cells with a cell value of 2. Some cells are blocked with a value of 1, thus you cannot pass it, while some cells are filled with 0, thus you can pass it.

You can move to left, right, up, down at each step. You have to collect all the pieces of cheese and then reach to Another Person cell. You need to return the minimum no. of steps required to do so.

Public int getShortest(int[][] maze, int[] anotherPersonCell){

}

- 1of 1 vote
We start with a list of Integers. We can remove a group of integers from the list if the all but one equals the remaining number. This removal operation can be performed in the remaining number of list until no more operations can be performed.

Write a function which can accept an array of integers, and return the minimal number of remaining integers from performing this operation.

Example [1, 3, 5, 6] -> remove 1, 5, 6 , because 1 + 5 = 6, thus only [3] left, so return 1

[48, 20, 1, 3, 4, 6, 9, 24] -> remove 3, 6, 9 , because 3 + 6 = 9, and remove 4, 20, 24, 48, because 4 + 20 + 24 + 48, thus only [1] left, so return 1

int left(int[] nums){

}

- 0of 0 votes
The numbers on a telephone keypad are arranged thus:

`1 2 3 4 5 6 7 8 9 0`

Starting from any digit, and choosing successive digits as a knight moves in chess, determine how many different paths can be formed of length n. There is no need to make a list of the paths, only to count them.

A knight moves two steps either horizontally or vertically followed by one step in the perpendicular direction; thus, from the digit 1 on the keypad a knight can move to digits 6 or 8, and from the digit 4 on the keypad a knight can move to digits 3, 9 or 0. A path may visit the same digit more than once.

Your task is to write a function that determines the number of paths of length n that a knight can trace on a keyboard starting from any digit .

public int findNumberOfPaths(int digit, int step){

- 0of 0 votes
How do I design a Payment Gateway system? What are the things to consider in this design ?

- 1of 1 vote
In Docker, building an image has dependencies. An image can only be built once

its dependency is built (If the dependency is from outside, then the image can

be built immediately).

Sometimes, engineers make mistakes by forming a cycle dependency of local images.

In this case, ignore the cycle and all the images depending on this cycle.

Input is vector of pair of images (image, its dependency).

Output the order of images to be built in order.

##Example:

```

Example 1:

{{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}}

Output: master, numpy, tensorflow

Example 2:

{{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}}

Output: tensorflow

Example 3:

{{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}

Ouput: f

- 0of 0 votes
There are n servers, reboot time is S0, S1..Sn-1

There are m tasks, the completion of the time required are T0, T1… Tm-1

How to assign tasks to each server makes the total time the shortest

- 0of 0 votes
If you are given 2 infinitely large integers in the form of strings, given the length of the string, find the product of the two integers.

- 0of 0 votes
How will you multiply two infinitely large integers.

- 0of 0 votes
Given a list/array of "Assign" trees with integers, operators and variables, return the result of the requested "Result" tree expression.

Example:`"Assign" / \ "x" "+" / \ 2 3 "Assign" / \ "y" "-" / \ 5000 30 "Assign" / \ "z" "*" / \ 50 x "Return" \ "-" / \ z "*" / \ 1 y`

- 1of 1 vote
You are given logs that contain user and page visits for a given day.

u1 -> p4

u3 -> p2

u7 -> p9

...

comeup with efficient data structure that answers these queries

Which page was visited by exactly 100 users in day?

Which page was visited by only one user exactly 15 times in a day?

Which page was visited by u3 more than 20 times in a day?

- 4of 4 votes
Given a sorted array A, find how many subsets of A satisfies MIN(subset) + MAX(subset) < K.

- 0of 0 votes
Convert Json string to Map

public Map jsonToMap(String t) {

}

- 0of 0 votes
What if server is slow, how to solve

What if one server is down

- 0of 0 votes
Given a 2D matrix of 0's and 1's, where the 1's make up a rectangle, find the coordinates of the top-left corner of the rectangle and the rectangle's width and height.

- 1of 1 vote
Array has N integers，range[0...N-1]。Set S[k], 0 <= K < N as S[K] = {A[K], A[A[K]], A[A[A[K]]],....},

write a function returns the size of the largest set S[K] for this array. return 0 if empty.

ex:

A = [5, 4, 0, 3, 1, 6, 2]

return 4 because S[2] equals {0, 5, 6, 2} 4 elements

- 0of 0 votes
Given an array of integers and a target number, determine if an arithmetic expression using these integers can be evaluated to the target number, you are allowed to use '+', '-', '*', '/'. Follow-up: when evaluating the expression, take operand precedence into account,

public boolean getTarget(int[] nums, int target){

}

exponentia is ok

- 1of 1 vote
Given a list of input tasks to run, and the cooldown interval, output the minimum number of time slots required to run them.

// Tasks: 1, 1, 2, 1, 2

// Recovery interval (cooldown): 2

// Output: 8 (order is 1 _ _ 1 2 _ 1 2 )

=========

Tasks are task numbers in that order coming in for execution. Cooling time is time interval required to cool down the machine after executing a task. So it's like if CPU executed task 1 then it needs 2 cooling time intervals before executing another task 1 but meanwhile, it can execute other tasks which are not same as 1 and so on. So before executing any task, you have to check if you have executed same task number before and if yes, then if its cooling time interval is done or not.

The output is basically the number of cycles/time slots CPU took to execute these tasks in that order (including when task executed and cooling intervals).

- 0of 0 votes
find the Closest leaf to a given node in Binary Tree

can you do it in o(n) time

public TreeNode findCloestLeafNode(TreeNode root, TreeNode target){}

no parent pointer

- 0of 0 votes
validate IP in string format and return the uint32 format

‘1.2.3.4’ -> 0x01020304

- 1of 1 vote
Given a n-nery tree and its deep copy, a node in the original tree, return the corresponding node in the copy

public TreeNode getCopyNode(TreeNode root, TreeNode copy, TreeNode node)

- 0of 0 votes
Write the code to find the median of an unsorted array in average linear time.

followup the array is distributed across many machines.

- 0of 0 votes
Write a function to split a SQL query into individual statements.

give you a String which contains a separate Query with a semicolon ";" return all valid queries

Such as

"select name from courseinfo ;; select * from db1 where home = 'usa' ;"

The main thing to consider is that some special cases such as the escape symbol and the quotation marks inside the semicolon

public List<String> getQuery(String queries){

}

- 0of 0 votes
given a list of numbers, put with + - * / any two number, find the maximum value you can get.

int getMaxNumber(int[] nums){

}