Facebook Interview Questions
- 0of 0 votes
AnswersGiven an unsorted array of integers, find a 3-element subset that sums to zero
- newtonrealman January 15, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook - 0of 0 votes
AnswersGiven a set of points (x,y) in a 2-d plane, which are guesses of a particular unknown point (x',y'), how do find the best estimate of (x',y') using the set of points given.
- nanjundi_kalyana January 15, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is a concatenation of each word in L exactly once and without any intervening characters. This substring will occur exactly once in S..
- topcoder99 January 06, 2012 in United States
.
Example:.
L: "fooo", "barr", "wing", "ding", "wing".
S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".
fooowingdingbarrwing.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou have a room-full of balances and weights. Each balance weighs ten pounds and is
- sanjeevmehtaubi December 26, 2011 in India
considered perfectly balanced when the sum of weights on its left and right sides are
exactly the same. You have placed some weights on some of the balances, and you have placed
some of the balances on other balances. Given a description of how the balances are arranged
and how much additional weight is on each balance, determine how to add weight to the balances
so that they are all perfectly balanced.
There may be more than one way to balance everything, but always choose the way that places additional weight on the lowest balances.
The input file will begin with a single integer, N, specifying how many balances there are.
Balance 0 is specified by lines 1 and 2, balance 1 is specified by lines 3 and 4, etc...
Each pair of lines is formatted as follows:
WL <balances>
WR <balances>
WL and WR indicate the weight added to the left and right sides, respectively.
<balances> is a space-delimited list of the other balance that are on that side of this balance.
<balances> may contain zero or more elements.
Consider the following input:
4
0 1
0 2
0
0 3
3
0
0
0
Balance 0 has balance 1 on its left side and balance 2 on its right side
Balance 1 has balance 3 on its right side
Balance 2 has three pounds on its left side
Balance 3 has nothing on it
Since balance 3 has nothing on it it is already perfectly balanced, and weighs a total of 10 pounds.
Balance 2 has no other balance on it, so all we need to do is balance it by putting three pounds on its right side. Now it weighs a total of 16 pounds.
Balance 1 has balance three on its right side, which weighs 10 pounds, so we just put 10 pounds on its left side. Balance 1 weighs a total of 30 pounds.
Balance 0 has balance 1 on its left side (30 pounds), and balance 2 on its right side (16 pounds), we can balance it by adding 14 pounds to the right side.
The output should be N lines long, with the nth line listing the weight added to the nth balance, formatted as follows:
<index>: <weight added to left side> <weight added to right side>
So the output for this problem would be:
0: 0 14
1: 10 0
2: 0 3
3: 0 0| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersYou are given a list of points in the plane, write a program that
- topcoder99 December 25, 2011 in United States
outputs each point along with the three other points that are closest
to it. These three points ordered by distance.
The order is less then O(n^2) .
For example, given a set of points where each line is of the form: ID
x-coordinate y-coordinate
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
Your program should output:
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
Answershow would you detect mouth in a picture
- prabhat0189 September 10, 2011 in -| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Graphics - 0of 0 votes
Answerswrite iterative version of seed fill algorithm
- prabhat0189 September 10, 2011 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
Answersthree points are randomly chosen on a circle.what the probability that
- David August 02, 2011
1.triangle formed is right angled triangle.
2.triangle formed is acute angled triangle.
3.triangle formed is obtuse angled triangle.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Math & Computation - 1of 1 vote
Answersthere is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on..
- anonymous July 14, 2011 in United States
It looks something like this
1
2 3
4 5 6
every cup has capacity C. you pour L liters of water from top . when cup 1 gets filled , it overflows to cup 2,3 equally, and when they get filled , Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both the cups and so on.
Now given C and M .Find the amount of water in ith cup.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Dynamic Programming - -2of 2 votes
AnswersRead in a list of words.Create a 20x20 grid.Put the first word at 0,0 across Each of the following words in the list should be placed so that they intersect at as many letters as possible (the input words will always have at least one letter of overlap.)
- reva July 11, 2011
If there is one more than one spot with the same number of intersected letters, place the word at all positions. (if some positions cause others to be invalid, choose the positions that allow the most words to be placed.)
Words can read across, backwards (right to left), down, and up.
A word is two or more characters in a row.
Positions are not valid if they cause non-words to appear in the grid.
If a word could fit in either direction (across/backwards) (up/down) choose across or down.
the question
example input:
alley
zebra
bole
bolero
wares
forgetmenot
carbonate
aardvarks
trombone
arts
example output:
alley c
r l s f aardvarks
b orelob r
elob r r b s
z r a g enobmort
seraw e t n r
l t a aardvarks
forgetmenot
b t e o e
a n b
n o r
enobmort aardvarks
b c
r
aardvarks
c| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - -2of 2 votes
AnswersFind Sophie
- daxingqiao June 29, 2011
After a long day of coding, you love to head home and relax with a loved one. Since that whole relationship thing hasn't been working out for you recently, that loved one will have to be your cat, Sophie. Unfortunately you find yourself spending considerable time after you arrive home just trying to find her. Being a perfectionist and unable to let anything suboptimal be a part of your daily life, you decide to devise the most efficient possible method for finding Sophie.
Luckily for you, Sophie is a creature of habit. You know where all of her hiding places are, as well as the probability of her hiding in each one. You also know how long it takes you to walk from hiding place to hiding place. Write a program to determine the minimum expected time it will take to find Sophie in your apartment. It is sufficient to simply visit a location to check if Sophie is hiding there; no time must be spent looking for her at a location. Sophie is hiding when you enter your apartment, and then will not leave that hiding place until you find her. Your program must take the name of an input file as an argument on the command line.
Input Specifications
The input file starts with a single number, m, followed by a newline. m is the number of locations available for Sophie to hide in your apartment. This line is followed by m lines, each containing information for a single location of the form (brackets for clarity):
<location name> <probability>probability is the probability that Sophie is hiding in the location indicated. The sum of all the probabilities is always 1. The contents of these lines are separated by whitespace. Names will only contain alphanumeric characters and underscores ('_'), and there will be no duplicate names. All input is guaranteed to be well-formed. Your starting point is the first location to be listed, and in effect it costs you no time to check if Sophie is there.
The file continues with a single number, c, followed by a newline. c is the number of connections that exist between the various locations. This line is followed by c lines, each of the form:
<location name> <location name> <seconds> The first two entries are the names of locations and seconds is the number of seconds it takes you to walk between the them. Again these lines are whitespace-delimited. Note that the locations are unordered; you can walk between them in either direction and it will take the same amount of time. No duplicate pairs will be included in the input file, and all location names will match one described earlier in the file.
Example input file:
4
front_door .2
in_cabinet .3
under_bed .4
behind_blinds .1
5
front_door under_bed 5
under_bed behind_blinds 9
front_door behind_blinds 5
front_door in_cabinet 2
in_cabinet behind_blinds 6
Output Specifications
Your output must consist of a single number followed by a newline, printed to standard out. The number is the minimum expected time in seconds it takes to find Sophie, rounded to the nearest hundredth. Make sure that the number printed has exactly two digits after the decimal point (even if they are zeroes). If it is impossible to guarantee that you will find Sophie, print "-1.00" followed by a newline instead.
Example output:
6.00| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 1of 1 vote
AnswersGattaca
- daxingqiao June 29, 2011
You have a DNA string that you wish to analyze. Of particular interest is which intervals of the string represent individual genes. You have a number of "gene predictions", each of which assigns a score to an interval within the DNA string, and you want to find the subset of predictions such that the total score is maximized while avoiding overlaps. A gene prediction is a triple of the form (start, stop, score). start is the zero-based index of the first character in the DNA string contained in the gene. stop is the index of the last character contained in the gene. score is the score for the gene.
Input Specification
Your program will be passed the name of an input file on the command line. The contents of that file are as follows.
The first line of the input contains only n, the length of the DNA string you will be given.
The next ceiling(n / 80) lines each contain string of length 80 (or n % 80 for the last line) containing only the characters 'A', 'C', 'G', and 'T'. Concatenate these lines to get the entire DNA strand.
The next line contains only g, the number of gene predictions you will be given.
The next g lines each contain a whitespace-delimited triple of integers of the form
<start> <stop> <score> representing a single gene prediction. No gene predictions will exceed the bounds of the DNA string or be malformed (start is non-negative and no more than stop, stop never exceeds n - 1).
Example Input:
100
GAACTATCGCCCGTGCGCATCGCCCGTCCGACCGGCCGTAAGTCTATCTCCCGAGCGGGCGCCCGATCTCAAGTGCACCT
CACGGCCTCACGACCGTGAG
8
43 70 27
3 18 24
65 99 45
20 39 26
45 74 26
10 28 20
78 97 23
0 9 22
Output Specification
Print to standard out the score of the best possible subset of the gene predictions you are given such that no single index in the DNA string is contained in more than one gene prediction, followed by a newline. The total score is simply the sum of the scores of the gene predictions included in your final result.
When constructing your output, you may only consider genes exactly as they are described in the input. If you find the contents of a gene replicated elsewhere in the DNA string, you are not allowed to treat the second copy as a viable gene. Your solution must be fast and efficient to be considered correct by the robot.
Example Output:
100| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersIt's A Small World
- daxingqiao June 29, 2011
As a popular engineer, you know many people in your home city. While traveling around town, visiting your friends, you realize it would be really handy to have a program that tells you which of your friends are closest based upon which friend you are currently visiting.
Being an engineer who is interested in writing software that is useful to everyone, you decide to write a general solution to your quandary. Each of your friends lives at a unique latitude and longitude. For the purposes of this program, the world is flat, and the latitude and longitude are for all intents and purposes Cartesian coordinates on a flat plane. For example, in our flat world, lat 45, long -179 is not as close to lat 45, long 179 when compared to lat 45, long 170.
Write a program that takes a single argument on the command line. This argument must be a file name which contains the input data. Your program should output the nearest three other friends for each friend in the list. You are virtually a celebrity and your friend list can be astoundingly huge. Your program must exhibit better than quadratic asymptotic growth in runtime as a function of the size of your friend list, and be robust and resource efficient.
Input specifications
The input file consists of multiple lines, all of which follow the same format. Each line has three values separated by an amount of white space. The first value is the unique id number of that friend, expressed as an integer. The second value is the latitude of that friend, expressed as a rational number. The third and last value is the longitude of that friend, expressed as a rational number. Every friend lives at a unique combination of latitude and longitude (e.g. no two friends will ever share the exact same values). Each line ends with a single new line, except for the last line of the file, which may or may not have a terminating new line.
Example input file:
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99 You are guaranteed that your program will run against an input file that is well formed, and has at least four lines. You are also guaranteed that your list of friends have unique distances between one another; no two distinct pairs of friends will have the same distance between them.
Output specifications
In the order presented in the input file, output the nearest three friends for each friend. Each line of output should start with the integer id of the friend followed by a single space character, and then the list of three nearest other friend ids followed by a single new line. Even the last line of the output should terminate in a new line. This list should be comma-delimited, with no spaces. The list must be in order of proximity, with the closest of the three being first, and the farthest of the three being last.
Example output:
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersGiven a node in a graph that is reachable, how do you find all the nodes that are reachable ? How would you enable parallel computation of this information ? Given a number of cores, how many threads would you choose ?
- anon June 22, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersQuestion: Design a component that implements the following functionality..
- ss June 01, 2011
1) Record an Event (For the sake of simplicity, treat the Event as an integer code)
2) Return the number of Events recorded in the last one minute.
3) Return the number of Events recorded in the last one hour.
i.e implement the following interface
- Design the interface first
- Give the implementation detail.
<<>>
Open ended question:
What if there isn't enough storage available to store each individual event ?| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDesign a system to calculate the number of unique words in a file..
- ss June 01, 2011
1) What if the file is huge ? (i.e cannot fit in the main memory)
2) Assuming that you have more than one computers available, how can you distribute the problem ?| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Data Structures - 1of 1 vote
AnswersReally like the linear solution of this problem. You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.
- Martin May 27, 2011
Example
pos = 0 1 2 3 4 5 6 7 8
0 1 0 0 1 1 1 1 0
One interval is (0, 1) because there the number of 0 and 1 are equal. There are many other intervals, find all of them in linear time.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - -1of 1 vote
AnswersA tree is serialized in such a way that all the leaves are market with L and all the other nodes with N. The tree is serialized keeping the order derived by a pre-order traversal. Write an algorithm for reconstructing the tree. Also, suggest a methodology for improving the serialization.
- Martin May 27, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind top log(n) or top sqt(n) values in an array of integers in less than linear time.
- Martin May 27, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are:
- Martin May 27, 2011
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSort 1TB file on machine with 1GB RAM.
- deveffort May 10, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersImplement function to find needle from a haystack. Interviewer was looking for coding skills.
- deveffort May 10, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersWhat is the time and space complexity of Fibonacci series recursive function.
- April 15, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersImplement strstr function without using any library functions.
- April 15, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersCount words in a sentence. Words can be separated by more than one space.
- April 15, 2011| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer