mabid.mahmood
BAN USER- 5of 15 votes
AnswersGiven a function
- mabid.mahmood in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 3 votes
AnswersGive a function
- mabid.mahmood in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm
I think this should be solved using BFS, it will take care of the cycles if there are any. Simply build an adjacency list out of the given individual steps list may look something like this
for example, notice there can be multiple paths from one city to another and there can be cycles too, this list can be build in O(N). all you need to do is iterate over the given steps and keep putting them in the appropriate list.
A -> [B,D]
C -> [F, D]
F - > [G]
B -> [C,D,A]
D -> [C,A]
Q => [F]
After this all you have to do is BFS and record which node was reached from which node( to be used in the end to reconstruct the actual path found )
Here is how the code would roughly look like in c++. Note that this can be easily modified to use the said API of Node.
- mabid.mahmood July 06, 2014