Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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.
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[3];
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"));
}
}
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)
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.
# 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)
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).
- Mike P November 05, 2014It 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?