Facebook Interview Question Software Engineer / Developers
@Dan, what ever it is, but it got some strategy to solve
I recommend two data structures, one is to maintain a array of pointers to lists,each pointer is pointing to list of reachable locns from locn, in non decreasing order of their probabilities
-----
addr1| ->locn3(0.4,4 sec)->locn4(0.1,45 sec)->null
-----
addr2|->null
-----
addr3|->locn2(0.2,34 sec)->locn1(0.2, 76 sec)->null
-----
other is a map<locn,bool> set to all false on start, which on reaching is set to true
typdef struct
{
prob;
duration;
locn;
List* next;
}List;
typdef struct
{
locn;
bt * next;
}bt;
Bt *bt;
int locate(vector<List*> list ,map<locn> m)
{
int i=0;
double total_duration;
List temp = list[i];
bool found = false;
int total_locn = m.size();//total entries
int total_visited =1;
do
{
if( total_locn == total_visited)
{
print(total_duration);
return 0;
}
while(temp || m(temp)) temp=temp->next;
if(!temp) // no more movements
{
print("NO SoLUTION");
return 1;
}
else
{
m(temp) = true;
total_duration += temp->duration;
add_traversal_path(bt,temp->locn);
temp = set_vector_index(temp);// sets temp with list pointer of current locn
total_visited++;
add_traversal_path(bt,temp);// for tracking path
}
}(while(!found))
return 0;
}
Well, I agree with Dan. This type of puzzle is not good suit to be posted here. Thousands of puzzle are on Wu Riddle forum. Or, you could better post on stackoverflow. I'm not saying there is no point to solve a puzzle, but as Dan pointed few reasons already.
On the other hand, it could be possible to narrate the original problem concisely. That way, more people would be encouraged to get the problem, and try to solve it.
Not a puzzle at all. A graph w/ double weighting: both time & probability. Any help/hint from a graph expert please?
I have the whole solution to this puzzle, simply because I solved it before. It is ranked at the hardest level of facebook puzzles, though much easier than another one: FACEBULL based on my experience, as well as many others'. This problem is non-trivial, there is no polynomial solution (for sure) to it. All we can do is how to search efficiently. I used a lot of heuristic methods and pruning methods to exponentially speedup my search. Though it passes test cases in several milliseconds, but it is still possible (I guess) to make a counter-example that make all my pruning and heuristic fail and result in a very long running time. I tried to make such one to refine my algorithm, but it turned out it is even more difficult than FINDSOPHIE itself to design such a special counter-example...
completely agree with fentoyal, this is an NPC problem.
prove:
1. Hamiltonian path is NPC
2. because of 1, the problem "given an undirected graph G, given a specific vertex v in G, whether there exists a Hamiltonian path starting from v in G" is NPC
3. because of 2, given an undirected graph G, given a specific vertex v in G, if we are going to try to find whether there exists a Hamiltonian path starting from v in G, we will surely expect an NPC algorithm. Good. Let's do it this way: define all vertex of possibility 1/V, where V is the # of vertices in G; define all edges of length 1, now we ask: is there such a route s.t. we visit all vertices and the expected traveling distance is exactly ???, where ??? is the traveling distance assuming no vertex is visited twice. If we can solve this in linear time, then the problem in 2 is not NPC. Thus, this problem is NPC.
4, because of 3, same assumption as 3, if we can solve the problem, "finding the minimal" in linear time, we can surely answer the "whether a special ???? length route exists" because we simply compare ???? with the "minimal". Thus this problem is NPC.
If I were to answer this question, as much as I hate it, I would use a naive brute-force scan of all permutations of the position, and then visit them in that order to all permutations, and select the minimal.
If the interviewer is not happy about that, I'll tell him, if two solutions are both exponential, they are equally disappointingly slow to me and thus make no difference and you can go **** yourself.
Well...I might have gone too far...
Would someone please delete this Facebook puzzle as:
- Dan June 29, 20111. It is not a real interview question.
2. It clutters the list of questions.
3. Solution requires several steps and it is pointless to publish it in its entirety.