Facebook Interview Question for Software Engineer / Developers

• 1

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

Nosh and SadBoy.. the question did not ask you to create the getRandomTriplet() method - that would be trivial (although SadBoy managed to make it as complicated as possible).

It asked you to take several outputs from an existing getRandomTriplet() and determine the original word.

I'm still pretty stumped on how to do this. I know the solution depends on the fact that the triplets retain their ordering, and somehow you use this place each letter in each triplet into some larger ordering that reveals the original word somehow...

As mentioned, topological sort seems to make some sense, but how to parse the result from the graph is unclear. It seems cycles could occur easily.

- what if the word is very long and you are only given a few triplets?
- what if the word has many duplicate characters?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How did solve that?
I think that is some kind of Graph problem.

-> d
/
h --> l --> o
\ <--\
-> e -> w

Comment hidden because of low score. Click to expand.
0
of 0 vote

topological sort
Represent each letter by the vertices and occurs after relationship by an edge
Ex: h->l->o
Do a DFS ,arrange the vertices by the descending order of the departure time.

Comment hidden because of low score. Click to expand.
0

But for "helloworld", there are both "low" and "wol" at the same time. How can you tell the order?

Comment hidden because of low score. Click to expand.
0
of 0 vote

import random;

def getRandomTripplet( s ):
l  = len(s);
i1 = random.randint(0,l-3);
i2 = random.randint(i1+1,l-2);
i3 = random.randint(i2+1,l-1);
res = "" + s[i1]+ s[i2]+ s[i3];
return res;

str = "helloworld";
print getRandomTripplet(str);

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class RandomTriplet {
static String getRandomTriplet(String word)
{
int len=word.length();
int[] indices=new int[len];

for(int i=0;i < len;i++) indices[i]=i;
int[] outputIndices=new int;

for(int i=0; i < 3;i++)
{
int index=(int)(Math.random()*(len-1-i));
outputIndices[i]=index;			//Mistake2: Spelling mistake, always copy larger names

//swap index and len-i-1;
indices[index]=indices[index]^indices[len-1-i];
indices[len-1-i]=indices[index]^indices[len-1-i];
indices[index]=indices[index]^indices[len-1-i];
}

//
Arrays.sort(outputIndices);
StringBuffer sb=new StringBuffer();
for(int ind : outputIndices)
sb.append(word.charAt(ind));

return sb.toString();
}
public static void main(String[] args) {

System.out.println(getRandomTriplet("helloworld"));
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution that uses an array to store found random indexes, of which is then sorted and then called upon from the original input string.

func getTriplets(input:String) -> Array<String> {
var randomElements:[Int] = []

while randomElements.count < 3 {
var randInt:Int = Int(arc4random_uniform(UInt32(input.length())))
if (randomElements.contains(randInt)) {
continue
}
randomElements.append(randInt)
}

randomElements.sort {\$0 < \$1}

var letters:[String] = []
for element in randomElements {
letters.append(input[element])
}
return letters
}

getTriplets(stringTest)

Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is impossible if you can have as many of the same characters as possible. if you have a string "wwwwwawwwww" then the only possible outputs from the getRandomTripplet() are "www", "aww", "waw", "wwa".

If you run the random function a billion times and count how often each instance shows up, statically you can eliminate "awwwwwwwwww", "wwwwwwwwwwa", "wawwwwwwwww", and "wwwwwwwwaw", but other than that there's no way to guess the correct string.

Comment hidden because of low score. Click to expand.
0
of 0 vote

# in python
import  random

def trip(s, p = 2):
if not s: return ""
a = random.randint(0, len(s)-1)
print "s: " + s + " a: " + str(a) + " len(s)-a: " + str(len(s) - a) +" p: "+ str(p)
if len(s[a:]) < p+1:
return trip(s, p)
elif len(s[a:]) == p+1:
return s[a:]
else:
return s[a] + trip(s[a+1:], p-1)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.