## Free Facebook Placement Papers / Aptitude Tests Online

Indiahires.in helps you to get all the latest Facebook interview questions. Check for the latest Facebook placement questions regularly from indiahires and prepare well for your Facebook interview.

- Facebook interview Questions for Software Engineer
Facebook latest placement papers of December are listed in Indiahires.in. Get your latest Facebook placement questions from Indiahires.

Q1. There is a building with 100 floors. You are given 2 identical eggs. How do you use 2 eggs to find the threshold floor, where the egg will break from any floor above floor N, including floor N itself? Data Scientist candidate

Q2. If you were going to redesign an ATM, how would you do it? Product Designer candidate

Q3. How many birthday posts occur on Facebook on a given day? Data Scientist candidate

Q4. Do you think that Facebook should be available in China? User Operations Analyst candidate

Q5. How much do you charge to wash every window in Seattle? Online Sales operations candidate

Q6. Describe how the website works. (That’s the whole question, with no context.) Technical Project Manager candidate

Q7. How much money is spent on the Internet? Account Manager candidate

Q8. How would you design a simpler TV remote control? Product Designer candidate

Q9. How do you deal with communicating less than favorable information? Training candidate

Q10. You’re at a casino with two dice, if you roll a 5 you win, and get paid $10. What is your expected payout? If you play until you win (however long that takes) and then stop, what is your expected payout? Data Scientist candidate

Q11. You have two light bulbs and a 100-story building. You want to find the floor at which the bulbs will break when dropped. Find the floor using the least number of drops. Software Engineer candidate

Q12. How would you set up an interview in this room? Content Producer candidate

Q13. How many vacuums are there in the U.S.A.? Risk Analyst candidate

Q14. What options do you have, nefarious or otherwise, to stop people on a wireless network you are also on (but have no admin rights to) from hogging bandwidth by streaming videos? Production Engineer candidate

Q15. How many Big Macs does Mcdonald’s sell each year in the U.S.? Data Scientist candidate

Q16. How would you build Facebook for blind people? Product Manager candidate

Q17. Tell me your plan of action if you saw that photo uploads suddenly dropped by 50% Operations Associate User Intelligence Candidate

Q18. A Russian gangster kidnaps you. He puts two bullets in consecutive order in an empty six-round revolver, spins it, points it at your head, and shoots. Click You’re still alive. He then asks you, do you want me to spin it again and fire or pull the trigger again? For each option, what is the probability that you’ll be shot? Internet Marketing Analyst candidate

Q19. Should Facebook continue to add features or rely on third-party apps? – Product Designer candidate

Q20. If you were an animal what kind would you be and why? – User Operations Analyst candidate

Q21. I was asked what I was least proud of on my resume. – Media Solutions Specialist candidate

Q22. Given access to all the data Facebook collects, what would you do with it? – Product Analytics candidate

Q23. Pre-IPO, they asked me to write a paper on the valuation of Facebook. They also asked me what I thought the greatest technological advancement was in the past 20 years. – Software Engineer candidate

Q24. If you have 100 credit card numbers (and all info) how would you make as much money as possible in 24 hours using only online transactions? (Many follow-up questions of how to get around certain fraud deterrents.) – Ads Risk Associate candidate

Q25. You are trying to rob houses on a street. Each house has some amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjacent to that house. – Software Engineer candidate

Q26. The most difficult question was the 8-hour test, which involved deriving a novel and fairly-involved algorithm, significant CSS/HTML/JS coding, and plenty of opportunities to get something subtly wrong. – User Interface Engineer candidate

Q27. 25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. – Software Engineering Summer Intern candidate

Q28. What is the process you would go about in spotting a fake profile? – User Operations Analyst candidate

Q29. You are about to get on a plane to Seattle. You want to know if you should bring an umbrella. You call 3 random friends of yours who live there and ask each independently if it’s raining. Each of your friends has a 2/3 chance of telling you the truth and a 1/3 chance of messing with you by lying. All 3 friends tell you that Yes it is raining. What is the probability that it’s raining in Seattle? – Data Scientist candidate

- Facebook Interview Questions Set 1
Facebook’s latest placement papers of December are listed in Indiahires.in. Get your latest Facebook placement questions from Indiahires.

**Q1. 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

**Q2. Given an array and a number, add it in such a way where the array is [0,0,1] and the number is 4 output will be [0,0,5]****Example 2 :****the**array is [1] and the**number is 9 output will be [1,0]****Q3. Given 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 a 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****x1+x2=a{k1} x2+x3 = a{k2}, …., x{n-1} + x{n} = a{k{n-1}, x{n} + x1 = a{k{n}}****Q4. Given a string where in each word letters were randomly shuffled and then words were written without spaces (let’s 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 the dictionary****Q5. Given two arrays/Lists (choose whatever you want to) with sorted and nonintersecting intervals. Merge them to get a new sorted nonintersecting array/list.****Eg:****Given:****Arr1 = [3-11, 17-25, 58-73];****Arr2 = [6-18, 40-47];****Wanted**:Arr3 = [3-25, 40-47, 58-73];

**Q6. Task schedule: given a sequence of tasks like A B C(means 3 different tasks), and a cold time, which means you need to wait for that much time to start the next [same] task. Now—-****Input: string, n****Output**: the best task-finishing sequence.eg. input: AAA BBB, 2

Output: AB_AB_AB

( “_” represents do nothing and wait)

**Q7. Given a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.****#!/usr/bin/env python3****assert solution(-15) == 110001****assert solution(2) == 110****assert solution(13) == 11101****Q8. Given 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.****Try to do this in O(log(n)) time and O(1) space.****Q9. Given an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.****Q10. Given integer k and a subset S of set {0, 1, 2, …, 2^k – 1}****Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)****& here is bit-wise and.****Do it faster than O((2^k)^2), assume k <= 16****Example:****0b111****0b101****0b010****Answer**: 20b110

0b011

0b101

**Answer**: 0**Q11. Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T.****example:****S=adobecodebanc****T=abc****Answer**: banc**Q12. Given a set of ranges:****(e.g. S = {(1, 4), (30, 40), (20, 91),(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}.****And given a target range R (e.g. R = (3, 13) – meaning the range going from 3 to 13). Write an algorithm to find the smallest set of ranges that covers your target range. All of the ranges in the set must overlap in order to be considered as spanning the entire target range. (In this example, the answer would be {(3, 9), (9, 12), (11, 14)}.****Q13. Given an array of positive integers (excluding zero) and a target number. Detect whether there is a set of consecutive elements in the array that add up to the target.****Example: a = {1, 3, 5, 7, 9}****target = 8****output = true ({3, 5})****or target = 15****output = true : {3, 5, 8}****but if target = 6, the output would be false. since 1 and 5 are not next to each other.****Q14. Given an array of integers. Modify the array by moving all the zeros to the end (right side). The order of the other elements doesn’t matter.****Q15. Given a dictionary containing a list of words, a starting word, and an ending word, return the minimum number of steps to transform the starting word into the ending.****A step involves changing one letter at a time to a valid word that is present in the dictionary.****Return null if it is impossible to transform the starting word into the ending word using the dictionary.****Example**:Starting word: cat

Ending word: dog

cat -> cot -> cog -> dog (cot and cog are in the dictionary)

return 3

**Q16. Given predicted stock prices for the next n days for a stock e.g: 10, 30, 42, 15, 20, 50, 10, 25 find the maximum profit that can be made with a single buy-sell transaction. Suppose no profit can be made return 0. In the example buying at 15 and selling at 50 gives maximum profit. Note that the two prices are neither minimum nor maximum in the array.****Q17. We have an array of objects A and an array of indexes B. Reorder objects in array A with given indexes in array B. Do not change array As length.**example:

var A = [C, D, E, F, G];

var B = [3, 0, 4, 1, 2];

sort(A, B);

// A is now [D, F, G, C, E];

**Q18. You are given a set of points on the x-axis (consumers)****Also, you are given a set of points on a plane (producer)****For every consumer print the nearest producer.****Wanted something better than O(n^2) time.**Example:

consumers: 1 5 7

producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100)

**Answer**:for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2)

Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?

**Q19. Given n, return 1 ^ 2 ^ 3 ^ … ^ n****Where ^ is binary xor.****Note: n is a 64-bit number, and 1<<63 is a valid n for this problem.****Examples**:>>> reduce(lambda a,b:a^b, [1,2,3])

0

>>> reduce(lambda a,b:a^b, [1,2,3,4])

4

>>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7])

0

>>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7,8,9])

1

**Q20. Given an array of positive, unique, increasingly sorted numbers A, e.g. A = [1, 2, 3, 5, 6, 8, 9, 11, 12, 13]. Given a positive value K, e.g. K = 3. Output all pairs in A that differ exactly by K.**e.g. 2, 5

3, 6

5, 8

6, 9

8, 11

9, 12

**What is the run time for your code?****Q21. You are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};****Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, kth order statistic on slice [a:b] of arr.****E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it – get [0,1,5] and take kth element, that is – 5.****Implement the**request(a, b, k) function. You can pre-process**input data, that is, assume there will be only one array and many request() calls.****Q22. Design Live comments. If your facebook.com homepage is open with a bunch of feeds and if someone comments on those feeds, the comments should automatically show up on the facebook.com home page without refreshing the page. Feeds could be a simple status update by a friend, a post in a group, a post by a person you’re following, a post on a page you’ve liked, etc.**Few things that they are looking for –

1. How do you solve it initially and how do you scale it?

2. How do you scale the push model in-case if you choose the PUSH model to solve it?

3. If push cannot scale how do you solve it?

4. How pull model solves it?

5. When will you use push vs pull?

**Q23. Write a Program for String Permutations using the most efficient algorithm. Can you solve the problem in O(n) time?****Q24. Conflict resolution in Multi-Master systems.****Q25. Design a URL shortener service****Q26. Check a binary tree is a binary search tree****Q27. Write a function to check if a string matches a regex pattern. Note that you only have to deal with patterns containing “*”. Also, note that the pattern can’t start with “*”.**Some examples:

isMatch(â€œaaâ€,â€aâ€) â†’ false

isMatch(â€œaaâ€,â€aaâ€) â†’ true

isMatch(â€œaaaâ€,â€aaâ€) â†’ false

isMatch(â€œaaâ€, â€œa*â€) â†’ true

isMatch(â€œaaâ€, â€œ*â€) â†’ true

isMatch(â€œabâ€, â€œ*â€) â†’ true

isMatch(â€œabâ€, â€œ*â€) â†’ true

isMatch(â€œb*aâ€, â€œaâ€) â†’ true

isMatch(â€œa*aâ€, â€œaâ€) â†’ true

isMatch(â€œaabâ€, â€œc*a*bâ€) â†’ true

**Q28. Given an array of integers, find the maximum drop between two array elements, given that the second element comes after the first one.****Q29. On a given array with N numbers, find a subset of size M (exactly M elements) that is equal to SUM.****Q30. Find the in-order successor of a node in BST** - Facebook Interview Questions Set 2
Facebook latest placement papers of December are listed in Indiahires.in. Get your latest Facebook placement questions from Indiahires.

**Q1. Design a data structure that supports a**kind of full-text**search but in numbers.****We are given a**file with a lot of 10-digit**numbers, for example:****1234 567 890****4124 123 123****3123 123 322****On a given number X we should return all numbers that contain X.****For example, if the number 123 was given, we should return all numbers (from the list above) because 123 is in all of them.****If the number 41 was given we should return only the middle number – because the number 41 is only in it.****Q2. Design Facebook Messenger backend****[[ 0, 2, 3], [1]] (0,2,3 are the same person and 1 is another one)****Q3. Search in a sorted rotated array.****Q4. Merge K sorted singly linked list****Q5. paint a list of N houses and M colors, each combination has a cost, minimizing the total cost without color in a row.****Q6. Given array A of size N, using function Random(returns a random number between 0 and 1) implement function that will return an array of size N with randomly shuffled elements of the array A.****You should give only algo.****Q7. We know a string is Palindrome if it is the same reading from both sides. Now we define the following string also Palindrome:****A man, a plan, a canal, Panama!****Write a code that returns if a string is a palindrome and it should return true for the above input. (Without directly saying, I should conclude that I have to only consider alphanumerical characters in a string). In addition, we assume the string is very long and we can not keep a copy of this string or even a copy of the preprocessed version of this string. Therefore the result should be returned with the first sweep of the string.****Q8. Given a singly linked list, swap the list items in pairs (reconnect the pointers, not simply swap the values). For example:****Before: A->B->C->D****After: B->A->D->C****Q9. you have an interface called Op and a Filter interface****interface Op {****public boolean hasNext();****public boolean next();****}****interface Filter {****public boolean filter(T1 t1, T2 t2);****}****design a MutualOp that has the below API, MutualOp should return the ops that combine op1 and op2, also should meet with the filter****class MutualOp implements Op{****public MutualOp(Op left, Op right, Filter filter) {****this.left = left;****this.right = right;****this.filter = filter;****}****public boolean hasNext {****……****}****public T next {****……****}****}****Q10. Calculate the minimum h-index for a sorted integer array(http://en.wikipedia.org/wiki/H-index)****Q11. Given a machine, you can try to guess the word, and the machine will return how many characters have been matched by your guess. Design a system to crack the word.****Q12. Permutate a list of string****this question is supposed to permutate the characters instead of who string,****as input example {“red”, “fox”, “super” }, the expected output is****rfs****rfu****rfp****rfe****rfr****ros****rou****rop****roe****ror****rxs****rxu****rxp****rxe****rxr****efs****efu****efp****efe****efr****eos****eou****eop****eoe****eor****exs****exu****exp****exe****exr****dfs****dfu****dfp****dfe****dfr****dos****dou****dop****doe****dor****dxs****dxu****dxp****dxe****dxr****Q13. A 2D array filled with an integer defines a flow from one point to its neighbor only if the value of the current point is not less than its neighbor’s value. Consider the up edge and left edge as the east coast, the bottom edge and right edge as the west coast, and find all positions that it can flow to the east coast and west coast both****Q14. Sort an integer array with three functions: findMin(), findMedium(), findMax().****Q15. /******Find if the given list of recurring weekly intervals covers the****entire time. Times are given up to a second.****You can take the input intervals in the number of seconds since****the beginning of the week or any other format you prefer.****—Example 1—****Input:****Tuesday 9AM – Sunday 9AM****Sunday 8:00:20AM – Wednesday 3AM****Output**:true

—Example 2—

Input:

Tuesday 9AM – Sunday 9AM

Sunday 8:00:20PM – Tuesday 8AM

**Output**:false

/

**Q16. /*****For each node in a binary tree find the next right node on the same depth. Write a function that takes the root node and populates “next” with the answer for each node.****A****/****B -> C****/ /****D -> F-> G****/****H -> I****class Node {****Node left;****Node right;****Node next; // <– answer should be stored here****};****B.next = C****D.next = F****F.next = G****H.next = I****{A, C, G, I}.next = null*****/****Q17. Pangram****Q18. In-place Palindrome Check****Q19. Dutch national flag w/ get rank followup****Q20. Given an array (list) of integers return true(boolean function) if two of the numbers add to 12.****Q21. N queen problem.****In NXN chess board, you have to arrange N queens such that they do not interfere with each other. Following is how you define interference of queens.****1. Two queens cannot be on the same diagonal****2. Two queens cannot be in the same horizontal or vertical line****3. Queen can jump like a knight. So, two queens cannot be in a position where they can jump two and a half steps like a knight and reach the other queen.****You should return the possible ways to arrange N queens on a chess board.****This was a tech screen, but since I was local, they called me into their office rather than a phone interview.****Q22. I needed to develop the next system:****We have a lot of servers. Every server generates logs. Every log has two data types: the first is numeric metrics. These numeric metrics are integers. The second is strings. We need to collect logs from all servers on another server (storage). Then we have to execute queries and get some data from storage. In our queries, we have to use numeric metrics and strings as well. For numerics metrics, we have to be able to get aggregation data as well.****Develop Storage server and database. Describe how will you scale this system, what database will you use, how will you save data and how will you execute these queries.****Q23. Given an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one more condition that the min or max should be non-edge elements of the array****Example: 1 2 3 4 5 4 3 2 1 -> Local max is 5****1 2 3 4 5 -> No local max or min exists****5 4 3 2 1 -> No local max or min exists****Q24. Write a function that calculates the minimum number of meeting rooms that can accommodate given schedules****input: same****Output**: # of roomsAlso back to back events are allowed e.g. {2,5} {5,9} correct o/p:1

**Q25. Write a function that detects conflicts in given meeting schedules****input: a list of intervals, [(s1, e1), (s2, e2), ]****output: return True if there’s any conflict, False otherwise****Q26. Given a tokenized PHP file, give me a map from class to a list of functions****Q27. There are 3 rooms in which the party is going on let’s say room A, B, C. Guests are coming one by one and you have to tell the guest****which room to enter. At any point in time, each room has to maintain a percentage Let’s say the percentage that each room has to maintain is****A- 20%, B-30%, C- 50%. You can maintain a total count of each room and keep on adding the count to the respective room as the new guest enters each room.****How would you go about it? What formula would you use?****Give a general formula so that it works if no. of rooms increases.****Q28. You are given a 2nd rectangular array of positive integers representing the height map of a continent. The “Pacific ocean” touches the left and top edges of the array and the “Atlantic ocean” touches the right and bottom edges.****– Find the “continental divide”. That is the list of grid points where water can flow either to the Pacific or the Atlantic.****Water can only flow from one cell to another one with a height equal to or lower.****Example:****Pacific ~ ~ ~ ~ ~ |__****~ 1 2 2 3 (5) ~****~ 3 2 3 (4)(4) ~****~ 2 4 (5) 3 1 ~****~ (6)(7) 1 4 5 ~****__ (5) 1 1 2 4 ~****|~ ~ ~ ~ ~ Atlantic****The answer would be the list containing the coordinates of all circled cells:****[(4,0), (3,1), (4,1), (2,2), (0,3), (1,3), (0,4)]****Q29. Implement stairs(N) that (collect the solutions in a list) print all the ways to climb up an N-step-stairs****where one can either take a single step or a double step.****Well use 1 to represent a single step, and 2 to represent a double step.****stairs(3)****111****12****21** - Facebook Interview Questions Set 3
Facebook latest placement papers of December are listed in Indiahires.in. Get your latest Facebook placement questions from Indiahires.

**Q1. A robot has to move in a grid which is in the form of a matrix. It can go to****1.) A(i,j)–> A(i+j,j) (Down)****2.) A(i,j)–> A(i,i+j) (Right)****Given it starts at (1,1) and it has to go to A(m,n), find the minimum number of STEPS it has to take to get to (m,n) and write****public static int minSteps(int m,int n)****For instance to go from (1,1) to m=3 and n=2 it has to take (1, 1) -> (1, 2) -> (3, 2) i.e. 2 steps****Q2. Given an m x n matrix where each row element is sorted, but the columns do not appear in sorted order, write a function to print each matrix element in sorted order.**Example matrix:

matrix = [

[20, 40, 80],

[5, 60, 90],

[45, 50, 55]

]

Your function should print 5, 20, 40, 45, 50, 55, 60, 80, and 90.

Add on: Assume that we are space-constrained such that we can only hold one row in memory at a time. Optimize your function to work under such constraints as efficiently as possible.

**Q3. Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T****Example****[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20****[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8****[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7****Q4. Given a string containing letters, digits, and other characters, write a function to check palindrome for only letters and digits. The implementation needs to be in place, no extra memory is allowed to create another string or array.****For example:****“ABA” is a palindrome****“A!#A” is a palindrome****“A man, a plan, a canal, Panama!” is a palindrome****Q5. Write a program that answers YES/NO search queries containing * placeholders. Example: if the data you have is (Hazem, Ahmed, Moustafa, or fizo), then you should answer as follows:****â€¨ahmed: YES****â€¨m**stafa: YES****â€¨fizoo: NO****â€¨fizd: NO****: YES****â€¨: YESâ€¨****NO****â€¨Your program should be able to answer each search query in O(1).****Q6. Input: A string equation that contains numbers, + and *****Output: Result as int.****For example:****Input: 3*5+8 (as String)****Output: 23 (as int)****Q7. Given a class Range****class Range {****public int begin;****public int end;****public Range(int begin, int end) {****this.begin = begin;****this.end = end;****}****}****The problem:****Input:****1) list of Ranges that don’t overlap (not sorted)****2) new range that might overlap.****Output:****list of merged Ranges****For example:**Input: [1..5] [9..13] [17..22]

new Range: [4..10]

Output: [1..13] [17..22]

**Q8. Convert a binary tree into an In Order traversal circular list re-purposing the node’s pointers Left & Right as Previous and Next respectively.**Hint: A single node Left & Right points to itself.

Note: This is not a binary search tree.

**Q9. You are given a set of unique characters and a string.****Find the smallest sub-string of the string containing all the characters in the set.****ex:****Set : [a, b, c]****String: “abbcbcba”****Result: “cba”****Q10. First, they did ask to find a pattern for this****this is a test sentence => [t, h, i, s, i, s, a, t, e, s, t, s, e, n, t, e, n, c, e]****thiis iss a teest seentennce => [i, s, e, e, n]****thiiis iss aa teeest seentennnce => [i, e, n]****thiiiis iss a teeest seeentennncccce => [i, c]****after I**have to do the body of the**function****getLongestConsecutiveChar****Q11. Completely blew it on this question today.****1.) Given an array, find the maximum difference between two array elements given the second element comes after the first.****For example.****array = [1,2,3,4,5,6,7]****We can take the difference between 2 and 1 (2-1), but not the different between 1 and 2 (1-2).****Q12. It started with simple behavioral questions like, why facebook, cultural fit questions,**etc. They asked a**simple question.****You are at the latest version of the committed code. assume one branch of code. The Code version is in sorted order. It is corrupted by the bug. You have fun isBug(VerNumber) which returns True or False. Find the version in which the bug was introduced. This can be solved by linearly checking each version or modified binary search. The person asked to write test cases? This is where I struggled. how do you write a test case for this question? Do you guys use framework syntax or something else?****Q13. Place reverse a sentence****You are given a sentence of English words and spaces between them.****Nothing crazy:****1) no double spaces****2) no empty words****3) no spaces at the ends of a sentence****void inplace_reverse(char* arr, int length) {****// your solution****}****Example:****input “I wish you a merry Christmas”****output “Christmas merry you wish I”****Constrains: O(1) additional memory****Q14. The closest common ancestor in a tree forest.****class Node {****Node* parent; // == null for root of tree****Node* left;****Node* right;****}****Node* tree_forest[]; // array of pointers which points to roots of each tree respectively****Node* closest_common_ancestor(Node* n1, Node* n2) {****// your solution****}****Example:****| a | j****| / | /****| b c | h****| / / |****|d e f |****for e and d CCA is a****for e and f CCA is c****for e and c, CCA is c****for h and d CCA is null****Constraints: O(1) additional memory****Q15. Design a URL system.****He even wanted to know what kind of algorithm to use, and improve the speed, availability, etc.****Q16. Given a 4 X 4 game slot that has random alphabets in all the slots****Write a function that takes the keyboard and the word as input and returns true if the word can be formed****False otherwise.**A word can be formed on the board by connecting alphabets adjacent to each other (horizontal, vertical, and diagonally)

The same alphabet should not be reused.

**Q17. Given a set of n people, find the celebrity.****Celebrity is a person who:****1. Knows only himself and no one else****2. Everyone else knows this person****You are given the following helper function:****bool knows(i, j);****Returns:****True: If I know j****False: otherwise**I proposed the O(n2) algorithm at first but he wanted me to improve on it. He wanted an O(n) algorithm

**Q18. You have a list of words with ranking.****Now you need to create a function that will take this list as input and provide a way so that a T9 keyboard can provide three top results of probable words based on rankings for the numbers punched in.****Q19. Tree to List: convert a binary tree to a circular doubly-linked list****Q20. Roll two dice, what is the probability of rolling no sixes?****Q21. Given an array of integers, return true if 3 numbers are adding up to zero (repetitions are allowed)****{10, -2, -1, 3} -> true****{10, -2, 1} -> true -2 + 1 +1 =0****Q22. Find the maximum number of non-intersecting events in a calendar.****Q23. Write a function to print the rows of a binary tree, terminating each row with a carriage return****Q24. Given a Tree:****A****/****B C****/ /****D E F G****Write a function that prints:****A****BC****DEFG****Q25. Given an array of ages (integers) sorted lowest to highest, output the number of occurrences for each age.****For instance:****[8,8,8,9,9,11,15,16,16,16]****should output something like:****8: 3****9: 2****11: 1****15: 1****16: 3****This should be done in less than O(n).****Q26. Print a BST such that it looks like a tree (with new lines and indentation, the way we see it in algorithms books).****Q27. Write a function that takes the following inputs and gives the following outputs.****Input: A list of points in 2-dimensional space, and an integer k****Output: The k input points closest to (5, 5), using Euclidean distance****Example:****Input: {(-2, -4), (0, 0), (10, 15), (5, 6), (7, 8), (-10, -30)}, k = 2****Output: {(5, 6), (7, 8)}****Q28. An efficient way to sort patient files in an array of just 3 types High-importance, Mid-importance, and Low-importance which are in an arbitrary order (unsorted).****The output preference should start with the highest.****1. High-importance****2. Mid-importance****3. Low-importance****[high,**low, low, med, high,**low]****Q29. There is a list of rectangles and a list of points in a 2d space. Note that the edge of each rectangle is aligned to the XY axis. question is how to find rectangles with points or points inside****– rush December 15, 2014, in the United States | Report Duplicate | Fl** - Facebook Interview Questions Set 4
**Q1. Create the data structure for a component that will receive a series of numbers over time and, when asked, returns the median of all received elements.****(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is****2, 7, 4, 9, 1, 5, 8, 3, 6****then the median is 5.)****Model the data structure for a component that would have these two methods:****@interface SampleHandler {****– (void)and number:(NSNumber*)number;****– (NSNumber*)median;****}****Q2. You want to create a staff to use in your martial arts training, and it has to meet some specific requirements.****1. You want it to be composed of two smaller staves of equal length so that you can either use it as a single staff or as two smaller ones.****2. You want the full-sized staff’s center of gravity to be exactly in the middle of the staff.****You have a very, very long branch from which you can cut the pieces for your staff. The mass of the branch varies significantly throughout it, so you use just any two pieces of the same length. Given a description of the mass throughout the branch, determine the longest staff you can make, then return three integers on a single line, the first two indicating the first index of each half-staff, and the third indicating the length of each half-staff.****The input will be given on a single line as a string of digits [1-9], each digit representing the mass of a section of the branch. All sections are the same size and the maximum length of the string is 500. Here is an example:****41111921111119****11119 11119****If the indicated sections are cut from the branch they will satisfy your requirements. They are both the same length, and they can be put together as either 9111111119 or 1111991111, both of which have a center of gravity exactly in the center of the staff.****The Center of gravity can be determined by taking a weighted average of the mass of each section of the staff. Given the following distances and masses:****Distance: 12345678****Mass: 22241211****Some of the mass of each section: 2 + 2 + 2 + 4 + 1 + 2 + 1 + 1 = 15****The weighted sum of the masses:****2*1 + 2*2 + 2*3 + 4*4 + 1*5 + 2*6 + 1*7 + 1*8 = 60****Weighted sum / regular sum = 60 / 15 = 4****This means that the center of mass is in section 4 of the staff. If we wanted to use this stuff the center of gravity would need to be (8+1)/2 = 4.5.****Here is an example problem:****131251141231****—- —-**If we take the sections indicated we get 1312 and 1231. By reversing the first one and putting them together we get 21311231

Some of the mass of each section: 2 + 1 + 3 + 1 + 1 + 2 + 3 + 1 = 14

Weight sum of the masses:

2*1 + 1*2 + 3*3 + 1*4 + 1*5 + 2*6 + 3*7 + 1*8 = 63

Weighted sum / regular sum = 63 / 14 = 4.5

This puts the center of mass exactly in the center of the staff, for a perfectly balanced staff. There isn’t a long staff that can be made from this, so the answer to this problem is

0 8 4

Because the half-staves begin at indices 0 and 8 (in that order) and each is of length 4.

**Q3. /******* Implement a function OneEditApart with the following signature:***** bool OneEditApart(string s1, string s2)********** OneEditApart(“cat”, “dog”) = false***** OneEditApart(“cat”, “cats”) = true***** OneEditApart(“cat”, “cut”) = true***** OneEditApart(“cat”, “cast”) = true***** OneEditApart(“cat”, “at”) = true***** OneEditApart(“cat”, “acts”) = false***** Edit is: insertion, removal, replacement*****/****Q4. Given an array of words, write a method that determines whether there are any words in this array that are anagrams of each other.****Sample #1: @[@”bag”, @”bat”, @”tab”]; // output TRUE****Sample #2: @[@”gab”, @”bat”, @”law”]; // output FALSE****Q5. An UIView A2 is subclassed from the same parent as an UIView A1.****Given inputs of A1, A2, and an UIView that is in the tree of UIViews of A1 somewhere, return the exact UIView that mirrors this in A2.****Example setup:****A1————****| |****UIView UIView****|****UIView <– Given this****A2————****| |****UIView UIView****|****UIView <– Find/return this****Q6. Given a list of n sorted lists of numbers, write a method that returns one giant list of all the numbers in order.****Example input:****NSArray* input = @[****@[@2, @5, @10],****@[@25, @100, @105],****@[@7, @56, @42],****…….****];****Q7. Given the following hashmap for numeric to alpha translation of a telephone keypad:****NSDictionary* dict = @{@2: @[@”A”, @”B”, @”C”],****@3: @[@”D”, @”E”, @”F”],****@4: @[@”G”, @”H”, @”I”],****@5: @[@”J”, @”K”, @”L”],****@6: @[@”M”, @”N”, @”O”],****@7: @[@”P”, @”Q”, @”R”, @”S”],****@8: @[@”T”, @”U”, @”V”],****@9: @[@”W”, @”X”, @”Y”, @”Z”]};****Write a method that takes a phone number as input and returns all possible letter combinations for that phone number.****Q8. Print all paths of a binary tree from root to leaf.****Later, extend the solution to work with graphs, with careful attention to cycles which you should print as paths as well (without printing visited nodes twice).****Q9. Given two extremely large numbers – each number is stored in a Singly Linked list, with the MSB at the head. You are not allowed to reverse the Linked lists. Write a program to multiply them in optimum space and time.****Q10. input [2,3,1,4]****output [12,8,24,6]****Multiply all fields except their position.****Restrictions:****1. no use of division****2. complexity in O(n)****Q11. Given a matrix with 1s and 0s, a rectangle can be made with 1s. What is the maximum area of the rectangle?****00010****11100****11110****11000****11010 In this test case the result needs to be 8.****How:****00010 00010****11100 11 100****11110 11 110****11000 11 000****11010 11 010****If you see above the 11s are used from the first two columns and last four rows making the area or count of 1s to be 8.****Q12. Imagine x is an operand and * is a binary operator. We say a string of x and * follows Reverse Polish notation if it is a postfix notation.****For example strings, xx*, x, and xx*xx** follow Reverse Polish notation.****Given a string of x and *, how many insert, delete, and replace operations are needed to make the string follow the RPN.****For example, xx* needs 0 operations to follow RPN since it already follows RPN.****x*x needs two operations to become xx* which follows RPN.*****xx* needs one operation to become xx* which follows RPN.****Your algorithm should work for a string of size up to 100.****Q13. WAP to modify the array such that arr[I] = arr[arr[I]].****Do this in place i.e. without using additional memory.****example : if a = {2,3,1,0}****o/p = a = {1,0,3,2}**Note: The array contains 0 to n-1 integers.

**Q14. Given a linked list where apart from the next pointer, every node also has a pointer named random which can point to any other node in the linked list. Make a copy of the linked list.****Q15. Microsoft Excel numbers cells as 1…26 and after that AA, AB… AAA, AAB…ZZZ and so on.****Given a number, convert it to that format and vice versa.****Q16. Design question: Say you have hacked into a network and can deploy your bot on thousands of machines, how would you design your bot so that all the machines work together to download a website, says Wikipedia? There should be load balancing and a page should be queryable given its URL.****Q17. Given a matrix of letters and a word, check if the word is present in the matrix. E,g., suppose the matrix is:****a b c d e f****z n a b c f****f g f a b c****and the given word is fnz, it is present. However, and is not since you would be repeating g twice.****You can move in all 8 directions around an element.****Q18. Given a matrix consisting of 0s and 1s, find the largest connected component consisting of 1s.****Q19. Given two arrays of sorted integers, merge them keeping in mind that there might be common elements in the arrays and that common elements must only appear once in the merged array.****Q20. Given a normal binary tree, write a function to serialize the tree into a string representation (returning the string), and also a function to deserialize a serialized string into the original binary tree.****Q21. Given a normal binary tree, write a function to serialize it into a string representation (returning a string), and also a function to deserialize the string into the original binary tree****Q22. A professor wants to see if two students have cheated when writing a paper. Design a function: has cheated (String s1, String s2, int N) that evaluates to true if two strings have a common substring of length N. Additional question after implementation. Assume you don’t have the possibility of using String. contains() and String. substring(). How would you implement this?****Q23. Given a list of 4 billion integers, find an integer not in the list using 4MB of memory. (the interview was in Java)****Q24. Write in Java, which converts a string representation of a float (like “342.18E-10”) to an actual float without using any built-in parsing functions.****Q25. Given a Binary Tree (balanced or not) write a method that transforms the tree into a degenerate tree (basically a data structure like a sorted linked list where each node has the left child null) and returns the new root. This must be made in place, no external memory usage is allowed.****Q26. What are the screen dimensions of various iPhone models?** - Facebook Interview Questions Set 5
**Q1. Convert a binary tree to a doubly circular linked list.****Q2. The only difficulty u will Facebook to get into Facebook is 1st round itself because u r supposed to code 3 questions in 90 minutes.****Q3. Cant point my finger at any one of them.****Q4. Given a binary tree, write a function that prints all of the paths from the root node to the leaf nodes. What are the functions’ run time and space requirements?****Q5. Given a linked list, where the value of each node can itself be a linked list (a recursive linked list), write a function that flattens it.****Q6. Basic data structure-based coding problem. Had to solve the problem and discuss run time and optimizations using another data structure.****Q7. What feature do you want to add to Facebook?****Q8. You are given a bunch of dominoes. Write a function that determines if any two of those dominoes add up to [6, 6] (e.g. [1,4] + [5, 2]).****Q9. Create a linked list with 3 chars (A, B, C) in it and print the list in reverse.****Q10. Given two BST, return true if they have the same variable, and false if not.****Q11. Design an API for a news feed****Q12. Find the shortest subtree that consists of all the deepest nodes. The tree is not binary.****Q13. Given an array of positive ints and a target, check to see if any consecutive sum in the array can add up to the target****Q14. Asked me how to reverse a Linked List. Recursive Solution, Non-Recursive Solution, edge cases.****Q15. Given a matrix of 1s and 0s, find the shortest route between two points in the matrix while considering 1s as walls and 0s as traversable paths.****Q16. Given an unsorted string, determine if it can be presented as a palindrome. MMO-True, DOOR-False****Q17. You have a 4 x 4 board with words. For example:**A B G H

O L L E

E R T Y

G E F Y

**You need to write a function that finds if a certain word exists on the board. The rules are as followed:****1. Each character needs to be close to one other (neighbor cell). For example, The function will return false for the word HERE but true for the word.****Q18. Give the count and the number following in the series.**for e.g 1122344

first line output: 21221324

next line: 12112211121214 and so on.

**Q19. Given an array of integers, return the length of the longest increasing subarray.****Q20. Difference between a file and an inode?****Q21. With a tree write a program to double the value of each node.****Q22. Write a function to find how many valid letters are in a string of digits give the mapping:**a -> 1

b -> 2

…

z – > 26

ex) 123 =>1, 12, 23 => a, l, w

**Q23. Given two sorted input arrays that contain a two-element array of [key, value], write a function that multiplies the two arrays together and sums them where the “key” matches. Example: “v1 = [[1, 3], [2, 4], [99, 3]]; v2 = [[2,3],[5,9],[99,1]]” results in “15”. I first brute-forced it with O(n*m) then used two pointers which resulted in O(n+m) then he asked me to write it in O(n log m). I could not think of an algorithm at the time for O(n log m).****Q24. Take binary expansions as strings, and return the string containing their sum: add(“10010”, “101”) = “10111”.** - Facebook Tough Interview Questions
**Q1.**Given an increasingly sorted array and a number s, please find two numbers whose sum is s. If there are multiple pairs with sum s, just output any one of them.**Q2.**Given an array, please determine whether it contains three numbers whose sum equals to 0.**Q3.**Given an array and a value, how to implement a function to remove all instances of that value in place and return the new length? The order of elements can be changed. It doesn’t matter what you leave beyond the new length.**Q4.**How to implement a function to check whether there is a path for a string in a matrix of characters? It moves to left, right, up and down in a matrix, and a cell for movement. The path can start from any entry in a matrix. If a cell is occupied by a character of a string on the path, it cannot be occupied by another character again.A B C

E S F

C S A

D E E

**Q5.**Numbers are serialized increasingly into a sequence in the format of 0123456789101112131415…, in which each digit occupies a position in the sequence. For instance, the digit in position 5 is 5, in position 13 is 1, in position 19 is 4, and so on.**Q6.**How can you implement two stacks in a single array, where no stack overflows until no space is left in the entire array space?**Q7.**When some elements at the beginning of an array are moved to the end, it gets a rotation of the original array. Please implement a function to search a number in a rotation of an increasingly sorted array. Assume there are no duplicated numbers in the array.**Q8.**There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximum value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right sides. What is the maximal stolen value?**Q9.**A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string â€œabbabâ€ into palindrome substrings, such as: â€œabbaâ€|â€bâ€, â€œaâ€|â€bâ€|â€babâ€ and â€œaâ€|â€bbâ€|â€aâ€|â€bâ€.

The profile begins with a fast review of fundamental information such as where you’re from, where you went to school, and where you work—the types of conversation starters you share with new people or exchange with longtime acquaintances as you reacquaint yourselves. And, because there is frequently no better way to learn about a person than via images, the profile now contains a row of recently tagged photos of you. In my example, my profile includes photos from my engagement and wedding, two of the most recent and joyful events in my life.