Facebook Interview Question for Software Engineer / Developers


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?

- Mike P November 05, 2014 | Flag Reply
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.

Read each line, build a link

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

- rickytan July 15, 2014 | Flag Reply
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.

- Phoenix July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hjguyue August 10, 2014 | Flag
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);

- Nosh July 30, 2014 | Flag Reply
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[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"));
	}

}

- SadBoy October 27, 2014 | Flag Reply
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)

- voidet@nightgen.com December 06, 2014 | Flag Reply
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.

- rizhang December 11, 2014 | Flag Reply
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)

- anonymous January 01, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More