## Facebook Interview Questions

- 0of 0 votes
Given an array of integers, design an algorithm that moves all non-zero integers to the end of the array. Minimize the number of writes or swaps.

- 0of 0 votes
Generate square of numbers in an array example [1,3,5] should come out as [1,9,25].

- 0of 0 votes
Given an Array of N elements and Integer K, write a function that returns true if the sum of any 2 elements of Array is K, false otherwise.

- 0of 0 votes
Write code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".

My solution is as follows.`public class StringDecoder { public static void main(String[] args){ String s = "3[a2[bd]g4[ef]h]"; System.out.println(decode(s)); } public static String decode(String s){ if(s == null || s.length()==0) return s; int indexOfFirstNumber = findIndexOfFirstNumber(s); int indexOfFirstBracket = findIndexOfFirstBracket(s); int indexOfClosingBracket = findIndexOfClosingBracket(s, indexOfFirstBracket); if(indexOfFirstNumber == -1) return s; String subStr1 = s.substring(0, indexOfFirstNumber); String subStr2 = decode(s.substring(indexOfFirstBracket+1, indexOfClosingBracket)); String subStr3 = decode(s.substring(indexOfClosingBracket+1, s.length())); int duplicates = Integer.parseInt(s.substring(indexOfFirstNumber, indexOfFirstBracket)); StringBuilder sb = new StringBuilder(); sb.append(subStr1); while(duplicates>0){ sb.append(subStr2); duplicates--; } sb.append(subStr3); return sb.toString(); } public static int findIndexOfFirstNumber(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c>=47 && c<=58){ index = i; break; } } return index; } public static int findIndexOfFirstBracket(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c=='['){ index = i; break; } } return index; } public static int findIndexOfClosingBracket(String s, int indexOfBracket){ int index = -1; int numberOfBracket = 1; for(int i=indexOfBracket+1; i<s.length(); i++){ char c = s.charAt(i); if(c == '[') numberOfBracket++; if(c==']'){ numberOfBracket--; if(numberOfBracket==0){ index = i; break; } } } return index; } }`

- 0of 0 votes
Print first pair of mis-matching leaves (first pair as in in-order) given two pre-order traversal arrays of BSTs.

e.g.`For 5 4 8 2 4 6 9 Pre-order Sequence as [5,4,2,4,8,6,9] & 5 3 8 2 4 7 9 Pre-order Sequence2 as [5,3,2,4,8,7,9] Print “4, 3”.`

- 1of 1 vote
Interview Question: essentially given a bunch of sets in an array, print out the cross product of all of those sets

- 3of 3 votes
Given a singly linked list: 1->2->3->4->5

Change it to 1->5->2->4->3 using O(1) space

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

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.

- 3of 3 votes
Finding biggest plus sign "+" in a sparse matrix(matrix with elements 0 and 1)

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

- 2of 2 votes
Define 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.

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)

- 1of 1 vote
Using that data structure, devise an algorithm to compute the dot product between two sparse matrices.

- 0of 0 votes
What data structure would you use to store the entries of a sparse matrix?

- 1of 1 vote
/*

# 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

*/

- 1of 1 vote
Given two (binary) trees, return the first pair of non-matching leaves

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

Tree 2: A, D, B

Output: (E,B)

- 3of 3 votes
Given: sorted array of integers

Return: sorted array of squares of those integers

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

Integers can be negative.

- 0of 0 votes
Design 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.

- 2of 2 votes
Convert a number to English representation.

Ex: Input : 100

Output : One Hundred.

- 0of 0 votes
How do I find the longest possible route in a matrix?

There are some hurdles in the path.

Details in image : https://s31.postimg.org/7nwp4gmzv/hurdle1.jpg

- 0of 0 votes
Given Nodes such as

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

-> right pointer

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

}

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

Write a program to sort the array using the minimum possible number of MoveToFront() calls.

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

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

X = 9 Output: True

X = 10 Output: False

X = 40 Output :False

- 2of 2 votes
A 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.

- 1of 1 vote
You 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".

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}

- 0of 0 votes
// 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”`String reverseWords(String value) { // Insert implementation }`

- 1of 1 vote
Select 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`public int kthLargest(int array[], int k) { // ..... }`

- 2of 2 votes
Given 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.

- 0of 0 votes
There are N coins with coordinates (x, y) where x >0 and y >0

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.

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

Eg 1)

String = "abdc"

Indices:

(1,4)

(3,4)

Answer:

cdba, cbad, dbac,dbca

you should print only "dbca" which is lexicographically largest.

- 4of 4 votes
Given 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.

`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`

- 0of 0 votes
Given 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]

Example 2 :

array is [1] and number is 9 output will be [1,0]