## Facebook Interview Questions

- 0of 0 votes
find LCA in directed acyclic graph

class Node {

int label;

List<Node> neighbors;

Node(int x) {

label = x;

neighbors = new ArrayList<>();

}

}

public List<Node> findLCAINDAG(Node, graph, Node n1, Node n2)

- 0of 0 votes
Say you have an array for which the ith element is the price of a given stock on day i, you can buy stock at any day, but can only buy once a day, but if you sell the stock, you must sell all of them at once.

Seeking maximum profit

public int maxProfit(int[] prices) {

- 0of 0 votes
Given a binary tree, print the path that has the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. the node val may be negative one`For example: Given the below binary tree, 1 / \ 2 3 Return 2-1-3. -1 / \ -2 3 \ -1 Return 3. public List<Integer> findMaxPath(TreeNode root){ } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */`

- 0of 0 votes
find the longest substring with at most k repeating characters,

to make it more clear, at most k repeating characters means in the substring, the max count(frequency) of one or more chars is k

- 0of 0 votes
Robot walked from the upper left to the lower right, can only go down and to the right, the number of each grid is height,

If the next cell height is higher than the current, we must pay the difference cost, otherwise no cost,

Find the minimum cost to reach the lower right corner,

Follow up 1, print the minimum cost path;

- 0of 0 votes
Expression evolution

expr :: = int | '(' op expr + ')'

op :: = '+' | '*'

Cite a few examples:

"3" -> 3

"(+ 1 2)" -> 3

"(+ 3 4 5)" -> 12

"(+7 (* 8 12) (* 2 (+ 9 4) 7) 3)" -> ...

Public int getValue(String s){

}

- 0of 0 votes
`Insert a number into an array of sorted intervals. For example, [1,4], [6,8], after insert 5, return [1,8]. class Interval{ int start; int end; public Interval(int start, int end){ this.start = start; this.end = end; } } class Solution{ public List<Interval> insert(List<Interval> list, int val){ } }`

- 0of 0 votes
determine whether a number is the sum of two squares, such as 17 = 16 +1

- 0of 0 votes
`Give a matrix, for example 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 Find if there is a rectangle in the matrix, all four corners are 1 For the example, there is only one rectangle, that is 1 0 1 0 1 0 1 0 1`

- 0of 0 votes
class DirectedGraphNode {

int label;

List<DirectedGraphNode> neighbors;

DirectedGraphNode(int x) {

label = x;

neighbors = new ArrayList<>();

}

}

check if there is a cycle in a directed graph, if there is a cycle, remove all the cycles

- 0of 0 votes
given a string and a segmentation length k

For example:

"This is a good day" k = 10

Cut into:

"This (1/4)"

"is a (2/4)"

"good (3/4)"

"day (4/4)"

Each line followed by a suffix in the form of (i/n) has 10 chars including space (except for the last line), return the minimum cut required, for the example, just return 4.

- 0of 0 votes
trie search, Search Return all words that match the wildcard *

such as

add ("car")

add ("caw")

add ("cauw")

search ("c*w") returns "caw" and "cauw".

- 0of 0 votes
given a target node in a directed graph, find the shortest cycle including this node, return the whole path.

- 0of 0 votes
Implement a trie tree which can add and search word, an extra "*" sign will also be considered, similar to Leetcode 211 but with "*"

'*' means any sequence of characters (including the empty sequence).

- 0of 0 votes
Given a Map (representing an old phone key number and possible letters present there) and a sequence of keys return all possible combinations of strings that are possible to produce.

`Map<String, String[]> map = new HashMap<String, String[]>(); map.put("1", new String[] { "a", "b", "c" }); map.put("2", new String[] { "c", "d", "e" }); map.put("3", new String[] { "f", "g", "h" }); String in = "12"; List<String> mix(String in, Map<String, String[]> map)`

The result for "1,2" should be [ac, bc, cc, ad, bd, cd, ae, be, ce]

- 0of 0 votes
`given a binary array, you can flip 0 -> 1 or 1 -> 0 to make all the 1 are in the left part and all the 0 to the right part, return the minimun flip required example 1 1011000 -> 1111000 only need one flip 0 -> 1 example 2 00001 -> 10000 require 2 flips public int findMiniFlip(int[] nums) { } }`

- 0of 0 votes
Given a string s, break s such that every substring of the partition can be found in the dictionary.

Return the minimum break needed.

Example

Given a String CatMat

Given a dictionary ["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]

return 1

we can break the sentences in three ways, as follows:

CatMat = Cat Mat break 1

CatMat = Ca tM at break 2

CatMat = C at Mat break 2

but the first way has the minimum break, thus return 1

public int wordBreak(String s, Set<String> dict) {

// Write your code here

}

- 0of 0 votes
Given a 2d grid map of '1's (land) and '0's (water), find the perimeter of each island. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

- 0of 0 votes
To determine if two graphs have isomorphism or not

- 0of 0 votes
Give an array A, find the (i, j) pairs that satisfy the condition.

Condition 1: A [j] = A [i] + 1, Condition 2: j - i is as large as possible

Followup condition 1 is changed to A [j]> A [i]

- 0of 0 votes
find a shortest string to cover all of a list of string,

For example, [aab, aabb, bc], should return aabbc,

because aab, aabb, bc are all the substring of aabbc

- 0of 0 votes
Given a linked list with next and random pointer, deepcopy the linked list and return new head.

Node {

char val,

Node next,

Node random }

A {

val: ’a’

next: D

random: G}

D {

val: ’d’

next: G

random: A}

G {

val: ’g’

next: null

random: D}

-----------

| |

| V

A -> D -> G -> null

-------------

| |

| V

A' -> D' -> G' -> null

- 0of 0 votes
Explain in detail about your favourite android api.

- 0of 0 votes
given 2 list of interval representing users online offline timestamp e.g (already sorted), find all intervals that both of users are online.

e.g A= [(3, 5), (7, 11)] B=[(2, 4), (9, 10)] --> [(3, 4), (9, 10)].

- 2of 2 votes
Facebook

-Phone: LC304 & longest arithmetic sequence. Return the sequence.

- 0of 0 votes
Given an array of integers and k, find the difference between the number of the strictly increasing number of subarrays (of size more than one) and the number of the strictly decreasing subarray in the window of size k. your method should be time and space efficent

example

int[] nums = {188930, 194123, 201345, 154243, 154243};

int k = 3;

Output

3, 0, -1

Explanation

For the first window of [188930, 194123, 201345], there are 3 increasing subranges ([188930, 194123, 201345], [188930, 194123], and [194123, 201345]) and 0 decreasing, so the answer is 3. For the second window of [194123, 201345, 154243], there is 1 increasing subrange and 1 decreasing, so the answer is 0. For the third window of [201345, 154243, 154243], there is 1 decreasing subrange and 0 increasing, so the answer is -1.

public int[] getdiff(int[] nums, int l){

}

- 0of 0 votes
`There is an unordered interval stream, write a method, returns the total length that all intervals cover by now class Interval{ int start; int end; } public List<Integer> countCoverLength(Iterator<Interval> stream){ }`

- 0of 0 votes
‘.’Matches any single character,' * 'Matches any sequence of characters (including the empty sequence).

There are two input, one is string pattern, and the other is dictionary like dict = ["cat", "cats", "and", "sand", "dog"].

return a boolean: whether to find a dictionary in the pattern match the word

eg: dict = ["cat", "cats", "and", "sand", "dog"].

pattern = "* t", -> true (can match cat)

pattern = ".a *" -> true (can match cat, cats, can also match sand, because * can also express empty sequence)

- 0of 0 votes
How would you store and retrieve values in Memcache if the values are larger than the individual value size allowed by Memcache?

- 2of 2 votes
node {

node * left, * right;

}

Given a list of node to determine whether the node in the list can form a valid binary tree. several points of judgment

1. need to ensure that all left, right pointer point to the node inside list

2. no cycle

3. All node must be connected

Boolean isValidTree(List<Node> list){}