Facebook Interview Questions
- 1of 1 vote
AnswersDesign a site similar to tinyurl.com
- Steve September 12, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Distributed Computing - 2of 2 votes
Answersgiven a stream of quotes for a stock from the last trading day. Assume its already time sorted. Find the maximum amount of money you could have made on this stock by making at most N transactions. A buy and a sell is counted as one transaction. For parts N = 1, N = 2 and N = Inf and the generic solution for N = some number (open ended)
- Steve September 11, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
Answers• Write a function that finds all the different ways you can split up a word into a concatenation of two other words.
- Steve September 11, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
Answersrange sum query,array,given i,j.
- Steve September 11, 2012 in United States
get sum array[i,j]:
requirement: n^1/2 space/time complexity| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven: for every paper authored, there is a citation count vector. The h-index is a measure of researcher importance.
- Steve September 06, 2012 in United States
h-index: The largest number i such that there are i papers each with at least i citations.
1. Suppose that the citation-vector is sorted, how to efficiently compute the h-index?
2. Suppose that the citation-vector is not sorted, how to efficiencly compute the h-index? time complexity? an algorithm with time complexity n?| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDefinition w-index: The largest number i such that there are i papers, with the lowest paper having at least one citation, the next one has at least two citations and so on, ith paper has i citations.
- Steve September 06, 2012 in United States
The citation vector is sorted. How efficiently can you compute the w index? Code this| Report Duplicate | Flag | PURGE
Facebook Algorithm - 0of 0 votes
AnswersWrite a function that takes 2 arguments: a binary tree and an integer N, it should return the N-th element in the inorder traversal of the binary tree. I asked the interviewer if I could use a 3rd argument to store the result; he said okay.
- Yev August 31, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDetermine the 10 most frequent words given a terabyte of strings.
- geekofthegeeks August 27, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersA string s is said to be unique if no two characters of s are same.
- swati.2332 August 19, 2012 in India
A string s1 is producible from s2 by removing some of the characters from s2.
A string s1 is said to be more beautiful than s2 if length of s1 is more than s2 or if both have same length and s1 is lexicographically greater than s2( ex: ba is more beautiful than ab)
Input: is a string which can be of maximum 10^6 characters, you have to produce the most beautiful unique string out of the given string.| Report Duplicate | Flag | PURGE
Facebook Coding - 0of 0 votes
AnswersHow will you implement your own rand() such that it returns an integer from 0 to n-1 with equal probability?
- Aashish August 06, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.
- Aashish August 04, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
Answersinput a text and a pattern. The pattern can have *, say a*b, a**b, *ab... find whether the pattern matches the whole input text.
- jiangok2006 July 20, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Coding - 0of 0 votes
AnswersInput:
- Nikhita July 18, 2012 in India
3
3 1 2
nny
nnn
ynn
output:
2 1 3
n size of permutation P.First line of input is n.Second line is the permutation P.A Permutation X is said to be lexicographically smaller than Y if for all digits till i X[i]=Y[i] and for i+1 X[i]<=Y[i]so you can exchange the integers in the given permutation P if character j of line i+2 is 'y' then i th and j th integer in P can be exchanged .
Output:Lexicographically smallest premutation of the given P using rule| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Coding - 1of 1 vote
AnswersFind the number of substrings of a string that are palindromes.
- gats July 08, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersLet's say there is a file consists of billions of records data.
- aliciabondie23 July 05, 2012 in United States
The file cannot fit into memory, and you need to reverse each word in that huge file and then save the reversed words to another file.
How would you implement this?| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 4 votes
AnswersWrite a pseudo code. The question aims to test both your programming and analytical skills. Your implementation will be tested for both time and space efficiency.
- br312@live.co.uk July 04, 2012 in United States
The input format is strictly followed. Your program will be evaluated for correctness against multiple inputs. Some inputs will be very large (> 100,000 nodes).
Problem Statement
You are in-charge of the office jukebox. You are determined to do a very good job and make your colleagues happy. You ask them to email you a list of music bands they like. The number of bands each colleague likes is limited to 10,000.
Input
All input will be given on stdin. Your input will be of the form,
1. The first line will be an integer stating the number of lines of input.
2. The input will only contain alphanumeric characters, colon, comma, underscore and space [A-Z, a-z, 0-9, _, , ], +.
3. The first word will be the name of your colleague, followed by a colon.
4. A comma separated list of that person’s favourite bands will follow the colon.
5. Every line will be terminated by a newline character (\n).
An example input would look like:
6
Anne: Metallica, The_Doors, Black_Sabbath
John: The_Beatles, The_Doors, Metallica, Pink_Floyd
Kathy: U2, Guns_n_Roses, Led_Zeppelin
Jamie: Radiohead
Ashok: Guns_n_Roses, U2, Pink_Floyd, The_Doors
Sara: Blink_182, Iron_Maiden, The_Doors
Problem
You decide to use your data to find the people most compatible with each other. Two people are compatible if they have at least 2 bands in common. The compatibility of two people is directly proportional to the number of bands they like in common.
For each person in the list, output the most compatible person(s). If there is more than one compatible person, separate the names with a comma. If a person has nobody compatible, output nothing. For our example input, the output will be,
Anne: John
John: Anne, Ashok
Kathy: Ashok
Jamie:
Ashok: John, Kathy
Sara:| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Coding - 0of 0 votes
Answersimplement dir *
- aliciabondie23 June 05, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersQuestion 1 / 1
- dc360 May 20, 2012 in United States
There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must be maintained.
Constraints:
1<= N<=8
3<= K<=5
Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.
Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.
Sample Input #00:
2 3
1 1
2 2
Sample Output #00:
3
1 3
1 2
3 2
Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1
NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
If you are using "Java", the classname is "Solution"| Report Duplicate | Flag | PURGE
Facebook Algorithm - -1of 1 vote
Answersprint 2n+1 prime numbers if any one of them not prime then print factors for that number
- Anonymous April 21, 2012 in India| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer Arrays C Coding - -1of 1 vote
Answerswrite a program to print the given string as alphabets in order next integres fallowed by sum
- Anonymous April 21, 2012 in India
example: CAE2W3A is input and output should be
ACDEW5| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer Arrays Coding - 0of 0 votes
AnswersSuppose you have a graph G(V,E).
- ediston April 20, 2012 in United States
You are supposed to find the shortest path from a vertex 's' to vertex 'e' for 'n' different cases.
In each case one of the edges 'Ei' (any one edge) of the graph will be blocked/deleted only for that case and we have to find the shortest path in the graph with that edge removed.
Guys finding the shortest path is easy. But how can I make the algo so fast that even if I remove one of the edges my algo should still be very fast. O(n log n) or faster.
Remember we are not deleting the edges permanently. We are just temporary removing one edge per case.
In each case only one edge is removed.
Suppose we blocked one edge E in one case. We have to find the shortest path for the graph.
In next case, we will reconnect the last edge and we will block/remove a new edge. And again for this new case we have to find the shortest path.
Another way of understanding the problem is suppose there are cities connected to each other.
And every day one of the roads gets blocked because of heavy rain. what is the shortest path every day from city s to e.
Also one more important thing to note that each road can be used only once.
But there could be more than 1 direct road from city a to city b.
FInd the shortest path distance from city s to e on a day when all direct roads from city f to city h are blocked. If there is no connecting path return -1| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 2 votes
AnswersGiven a character array. Find if there exists a path from O to X. Here is an example
- jinalshah2007 April 11, 2012 in United States
. . . . . . .
. . . . . . .
w . . . . . .
w .w.w..
. . . . O . .
. . w. . . .
. . . X . . .
You have to just keep in mind that you cannot go through 'W'.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Brain Teasers Dynamic Programming - 0of 0 votes
AnswersWrite a program for Palindrome
- jinalshah2007 April 11, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersAn expression consisting of operands and binary operators can be written in Reverse Polish Notation (RPN) by writing both the operands followed by the operator. For example, 3 + (4 * 5) can be written as "3 4 5 * +".
- dprediction April 02, 2012 in United States
You are given a string consisting of x's and *'s. x represents an operand and * represents a binary operator. It is easy to see that not all such strings represent valid RPN expressions. For example, the "x*x" is not a valid RPN expression, while "xx*" and "xxx**" are valid expressions. What is the minimum number of insert, delete and replace operations needed to convert the given string into a valid RPN expression?
Input: The first line contains the number of test cases T. T test cases follow. Each case contains a string consisting only of characters x and *.
Output: Output T lines, one for each test case containing the least number of operations needed.
Constraints: 1 <= T <= 100 The length of the input string will be at most 100.
Sample Input:
5
x
xx*
xxx**
*xx
xx*xx**
Sample Output:
0
0
0
2
0
Explanation:
For the first three cases, the input expression is already a valid RPN, so the answer is 0. For the fourth case, we can perform one delete, and one insert operation: xx -> xx -> xx| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer C# - -2of 2 votes
AnswerAn expression consisting of operands and binary operators can be written in Reverse Polish Notation (RPN) by writing both the operands followed by the operator. For example, 3 + (4 * 5) can be written as "3 4 5 * +".
- dprediction April 02, 2012 in United States
You are given a string consisting of x's and *'s. x represents an operand and * represents a binary operator. It is easy to see that not all such strings represent valid RPN expressions. For example, the "x*x" is not a valid RPN expression, while "xx*" and "xxx**" are valid expressions. What is the minimum number of insert, delete and replace operations needed to convert the given string into a valid RPN expression?
Input: The first line contains the number of test cases T. T test cases follow. Each case contains a string consisting only of characters x and *.
Output: Output T lines, one for each test case containing the least number of operations needed.
Constraints: 1 <= T <= 100 The length of the input string will be at most 100.
Sample Input:
5
x
xx*
xxx**
*xx
xx*xx**
Sample Output:
0
0
0
2
0
Explanation:
For the first three cases, the input expression is already a valid RPN, so the answer is 0. For the fourth case, we can perform one delete, and one insert operation: xx -> xx -> xx| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer C# - 1of 1 vote
AnswersPush all the zero's of a given array to the end of the array. In place only. Ex 1,2,0,4,0,0,8 becomes 1,2,4,8,0,0,0
- CheckThisResume.com March 09, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Arrays C Coding - -2of 2 votes
AnswersWrite a function f(n) which computes the number of scoring sequences that add up to score n.
- asheeshv March 06, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersString Reduction
- sf engineer February 20, 2012 in United States
Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains the string you start with.
Output:
Output T lines, one for each test case containing the smallest length of the resultant string after applying the operations optimally.
Constraints:
1 <= T <= 100
The string will have at most 100 characters.
Sample Input:
3
cab
bcab
ccccc
Sample Output:
2
1
5
Explanation:
For the first case, you can either get cab -> cc or cab -> bb, resulting in a string of length 2.
For the second case, one optimal solution is: bcab -> aab -> ac -> b. No more operations can be applied and the resultant string has length 1.
For the third case, no operations can be performed and so the answer is 5.| Report Duplicate | Flag | PURGE
Facebook Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given C containers, B black balls and an unlimited number of white balls. You want to distribute balls between the containers in a way that every container contains at least one ball and the probability of selecting a white ball is greater or equal to P percent. The selection is done by randomly picking a container followed by randomly picking a ball from it.
- unknown February 16, 2012 in United States
Find the minimal required number of white balls to achieve that.
INPUT
The first line contains 1 <= T <= 10 - the number of testcases.
Each of the following T lines contain three integers C B P separated by a single space 1<= C <= 1000; 0 <= B <= 1000; 0 <= P <= 100;
OUTPUT
For each testcase output a line containing an integer - the minimal number of white balls required. (The tests will assure that it's possible with a finite number of balls)
SAMPLE INPUT
3
1 1 60
2 1 60
10 2 50
SAMPLE OUTPUT
2
2
8
EXPLANATION
In the 1st testcase if we put 2 white balls and 1 black ball in the box the probability of selecting a white one is 66.(6)% which is greater than 60%
In the 2nd testcase putting a single white ball in one box and white+black in the other gives us 0.5 * 100% + 0.5 * 50% = 75%
For the 3rd testcase remember that we want at least one ball in each of the boxes.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Probability - 0of 0 votes
AnswersPrint the binary tree level by level. Suggest methods. If one of your method is using queue and some delimiter is detect the change in levels, what is its space and time complexity. Prove your analysis. (yes, CLRS style proof is expected)
- AmzFAILFacebookFailMSFTFail January 17, 2012 in United States for Backend systems| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer