Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Well, may be if you do hige amount of runs and compare amount of aab vs baa occurence, you will know b position, provided perfect random distribution
Total combination of unique triplets is total=n!/6(n-3)!.
From them starting from the first charachter of string is (n-1)(n-2)/2, second (n-2)(n-3)/2 and so on
So, we know the percintile of triplets that has to have first string character as first triplet char, second, and so on, it is getting less and less.
For ever character of the alphabet, count how many times it was first in the triplet on many calls. Take most frequent. It will be the first char. Substract percentile based on the postion by the above formula for this char. Repeat untill build half a string. The other half build in similar way going backwords and counting last tripplet char.
If the string can contain duplicate letters, as @CT replies, we can never deduct the original string by random triplet.
Considering string S = "aaaabaaa", the triplet will always be one of the four types: "aab", "aba", "baa", "aaa".
With these four type of triplets we cannot know the real position of 'b' in S, so S will never be deducted.
If there is an extra condition that S does not contain duplicate letters. We can solve it with graph, for a triplet "abc", add a->b, b->c, a->c into the graph.
(Assume the length of S is N)
During constructing the graph, the node whose out-degree first reaches N-1 is the first letter of S, then find the node whose out-degree reaches N-2 first to find the second letter, etc..
Consider for every string returned , each character as a node of the graph.
Then on final output, perform Topological Sort
to give the original string
This code works for most strings. If in the secret string there is not too much duplicating then this algo will work fine and in most cases it will be able to recover secret string as it is.
import java.util.*;
public class Main {
/*
* Input:
* SecretString length precisenessLevel
*
* ex: hello 5 10
*
* Note: In some cases you should provide higher precisenessLevel such as 1000. But it may be so slow.
* */
private final String alphabet = "a b c d e f g h i j k l m n o p q r s t u v w x y z";
private String secretString;
private int secretStringLength;
private Map<String, Integer> occurrenceCountsMap;
private int precisenessLevel; //Higher is better but slower.
private String myGuess;
public void init(){
Scanner sc = new Scanner(System.in);
secretString = sc.next();
secretStringLength = sc.nextInt();
precisenessLevel = sc.nextInt();
sc.close();
secretStringLength = secretString.length();
occurrenceCountsMap = new HashMap<String,Integer>();
}
public String getRandomTriplet(){
Random rn = new Random();
int firstIndex = rn.nextInt(secretStringLength -2);
int secondIndex = rn.nextInt(secretStringLength - 1 - firstIndex - 1) + firstIndex + 1;
int thirdIndex = rn.nextInt(secretStringLength - secondIndex - 1) + secondIndex + 1;
return secretString.substring(firstIndex,firstIndex+1) +
secretString.substring(secondIndex,secondIndex+1) +
secretString.substring(thirdIndex,thirdIndex+1);
}
/*
* Given suffix "uv" and notThisOne = m + "uv" we want to find a triplet
* that is of form a + "uv" and occurence of a + "uv" is strictly less than occurence of m + "uv".
* */
public String findBestTriplet(String suffix, String notThisOne){
int countOfNotThisOne = Integer.MAX_VALUE;
if(notThisOne != null) countOfNotThisOne = occurrenceCountsMap.get(notThisOne);
Scanner sn = new Scanner(alphabet);
String result = null;
int maxOccurrence = -1;
while(sn.hasNext()){
String nextLetter = sn.next();
String tripletToLookFor = nextLetter + suffix;
if(occurrenceCountsMap.get(tripletToLookFor) != null
&& occurrenceCountsMap.get(tripletToLookFor) < countOfNotThisOne
&& maxOccurrence < occurrenceCountsMap.get(tripletToLookFor))
{
maxOccurrence = occurrenceCountsMap.get(tripletToLookFor);
result = tripletToLookFor;
}
}
// System.out.println("current myGuess : " + myGuess + "\t next prev : " + result);
return result;
}
public void process(){
long selectableTripletCount = secretStringLength * (secretStringLength - 1) * (secretStringLength - 2) / 6;
// System.out.println("secretStringLength : " + secretStringLength + ", triplet count : " + selectableTripletCount);
long iterationCount = selectableTripletCount * precisenessLevel;
for(int i = 0 ; i < iterationCount; i++) {
String nextRandomTriplet = getRandomTriplet();
if(occurrenceCountsMap.get(nextRandomTriplet) == null){
occurrenceCountsMap.put(nextRandomTriplet, 1);
} else {
int prevCount = occurrenceCountsMap.get(nextRandomTriplet);
occurrenceCountsMap.put(nextRandomTriplet, prevCount+1);
}
}
/*
* If secret string is abclkqwxyz then abc will have lowest frequency and xyz highest.
* In addition, the more you are close to the end the more frequency you have. This is not
* always true but in most cases this is true. Here, find the triplet with highest frequency
* and guess it is the last 3 chars of the secret string.
* */
Set<String> triplets = occurrenceCountsMap.keySet();
Iterator<String> it = triplets.iterator();
String tripletWithHighestFrequency = "";
int itsFrequency = -1;
while(it.hasNext()){
String next = it.next();
if(itsFrequency < occurrenceCountsMap.get(next)){
tripletWithHighestFrequency = next;
itsFrequency = occurrenceCountsMap.get(next);
}
}
// print();
/*We will build our guess on the last 3 chars.*/
myGuess = tripletWithHighestFrequency;
while(myGuess.length() < secretStringLength){
String prev = findBestTriplet(myGuess.substring(0, 2), null);
/*If such best triplet was not found then at some point we made wrong guess.
* So roll back and try with another triplet that has smaller frequency than what we guessed.*/
while(prev == null){
/*If precisenessLevel is not high enough then we might face some trouble.*/
if(myGuess.length() < 3){
System.out.println("Please increase precisenessLevel. Stopping the program...");
System.exit(0);
}
String notThisOne = myGuess.substring(0,3);
myGuess = myGuess.substring(1);
prev = findBestTriplet(myGuess.substring(0, 2), notThisOne);
}
myGuess = prev.substring(0,1) + myGuess;
}
}
public void print(){
// System.out.println("Unique triplet count : " + occurrenceCountsMap.size());
System.out.println("guessed : " + myGuess);
// System.out.println(occurrenceCountsMap.toString());
}
public void run(){
init();
process();
print();
}
public static void main(String[] args) {
new Main().run();
}
}
My idea is to call getTripplet() many times and for each tripplet, represent it as a directed path in a graph. Say for string "abcd", we could have abc, abd, acd, bcd. So we create a graph based on all those tripplets. If a path already exists, just ignore it (in this case, b->c->d path already exists before reach this tripplet).
After the graph is constructed, find a full path that visits all the nodes.
The tricky part is how many times you should call getTripplet(). My random guess is until you have called it 10 times and you found all the paths already exist.
My solution. This returns correct guess in most cases. But there might be a set whose element generate exact same set of triplets, in which case the guessed string might not be the same to the secret string but still a correct guess.
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <memory>
using namespace std;
template <typename R>
function<R(int, int)> memoize(function<R(int, int)> f) {
shared_ptr<unordered_map<int, R>> m = make_shared<unordered_map<int, R>>();
return [=](int k1, int k2) {
auto key = k1 * 1000 + k2;
if (m->find(key) != m->end()) {
return (*m)[key];
}
return (*m)[key] = f(k1, k2);
};
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& data) {
for (auto d : data) {
os << d << " ";
}
return os;
}
string guess_string(int nstr, const function<string()>& get_random_triplet) {
function<int(int)> comb = [&](int x) {
auto r = 1;
for (int i = 0; i < 3; ++i) {
r *= x;
--x;
}
r /= 6;
return r;
};
auto ncandidates = comb(nstr);
string guessed;
while (guessed.size() != nstr) {
unordered_map<char, int> char_freq_map;
unordered_map<char, int> char_pos_map;
for (int i = 0; i < ncandidates; ++i) {
auto triplet = get_random_triplet();
for (int j = 0; j < triplet.size(); ++j) {
++char_freq_map[triplet[j]];
char_pos_map[triplet[j]] += j;
}
}
struct GuessedChar {
char c;
double pos;
};
vector<GuessedChar> gchars;
for (auto p : char_freq_map) {
auto freq = lround((double)p.second / (3.0*ncandidates / nstr));
auto rel_pos = lround(((double)char_pos_map[p.first] / p.second) * nstr / 3.0);
for (int i = 0; i < freq; ++i) {
gchars.emplace_back(GuessedChar{ p.first, rel_pos });
}
}
sort(gchars.begin(), gchars.end(), [](const GuessedChar& c1, const GuessedChar& c2) {
return c1.pos < c2.pos;
});
for (auto gc : gchars) {
guessed.push_back(gc.c);
}
}
auto lcs_len = [&](const string& s1, const string& s2) {
function<int(int, int)> lcs_len_impl = memoize<int>([&](int i, int j) {
if (i < 0 || j < 0) {
return 0;
}
if (s1[i] == s2[j]) {
return 1 + lcs_len_impl(i - 1, j - 1);
}
return max(lcs_len_impl(i - 1, j), lcs_len_impl(i, j - 1));
});
return lcs_len_impl(s1.size() - 1, s2.size() - 1);
};
cout << "guessed = " << guessed << endl;
auto char_positions = [](const string& guessed) {
unordered_map<char, vector<int>> char_pos_map;
for (int i = 0; i < guessed.size(); ++i) {
char_pos_map[guessed[i]].push_back(i);
}
return char_pos_map;
};
auto char_pos_map = char_positions(guessed);
int no_successive_pass = 0;
int no_try = 0;
while (no_try++ < 100 * ncandidates && no_successive_pass < ncandidates) {
auto triplet = get_random_triplet();
if (lcs_len(guessed, triplet) < 3) {
no_successive_pass = 0;
cout << "conflicted: " << triplet << endl;
cout << "positions of " << triplet[0] << ": " << char_pos_map[triplet[0]] << endl;
cout << "positions of " << triplet[1] << ": " << char_pos_map[triplet[1]] << endl;
cout << "positions of " << triplet[2] << ": " << char_pos_map[triplet[2]] << endl;
auto first_pos = char_pos_map[triplet[0]][0];
auto second_pos = char_pos_map[triplet[1]][char_pos_map[triplet[1]].size() - 1];
if (first_pos > second_pos) {
guessed.insert(first_pos + 1, 1, triplet[1]);
guessed.erase(second_pos, 1);
}
first_pos = char_pos_map[triplet[1]][char_pos_map[triplet[1]].size() - 1];
second_pos = char_pos_map[triplet[2]][char_pos_map[triplet[2]].size() - 1];
if (first_pos > second_pos) {
guessed.insert(first_pos + 1, 1, triplet[2]);
guessed.erase(second_pos, 1);
}
cout << "guessed changed = " << guessed << endl;
char_pos_map = char_positions(guessed);
}
else {
++no_successive_pass;
}
}
return guessed;
}
int main() {
string str = "Iloveyou";
auto subsets = [](const string& str) {
vector<string> sets;
string set;
function<void(int, int)> impl = [&](int i, int n) {
if (i + n <= str.size() && n == 0) {
sets.push_back(set);
return;
}
else if (i + n > str.size()) {
return;
}
impl(i + 1, n);
set.push_back(str[i]);
impl(i + 1, n - 1);
set.pop_back();
};
impl(0, 3);
return sets;
};
auto candidates = subsets(str);
auto ncandidates = candidates.size();
auto get_random_triplet = [&]() {
return candidates[rand() % candidates.size()];
};
srand(time(nullptr));
cout << guess_string(str.size(), get_random_triplet) << endl;
str = "helloworld";
candidates = subsets(str);
cout << guess_string(str.size(), get_random_triplet) << endl;
return 0;
}
1.As each triplet is unique we should run the function till we get n!/6(n-3)! to get all possible triplets
2.As we receive we start building a directed graph with no node repeating, so after all the triplets are processed we have the entire directed graph to process.
3.From this we can understand the node with no inputs is the head and node with no outputs is the tail. to understand this we need to maintain the graph as an adjacency list for better performance.
4.The length of the string is also given. In case of "helloworld" the length is 10 so we start from "h" and process the graph using back tracking algorithms until we find "d" in the 10th place if we dont find d in the 10 th position we backtrack one step back and proceed with the other adjacent node.
5. Finally the word formed starting from h and ending with d in the 10th location is our word "helloworld".
This is the only possible solution i could come up with.
Here is the outline I can come up with, start with atleast n/3 samples and get new sample triplet if cannot fit yet
1) If the character c appears k times and k>=3, p(ccc) = kC3/nC3, else if there are only triplets with 2 c's k = 2, else k=1
2) If k = 1, and position of c is m then p(c**) = (n-m)C2/nC3
3) If c repeats say at positions m1, m2 , ... mk, p(c**) = Sum from 1 to k of (n-ml)C2/nC3
4) Determine positions of characters with lowest k first and reduce the problem to a smaller size by dropping all triplets containing them
Looking at pair constraints like say c1 appears at i1<i2,...ik and c2 appears at j1<j2<...jl on p(c1c2*) would reduce #samples needed
Not sure what the expectation is for this question, watching for additional solutions
public class Test{
public String getWord(int length){
Map<Character, GraphNode> nodes = new HashSet<Character, GrapNode>();
do{
char[] triplet = Util.getTriplets();
for(int i=0; i<3; ++i){
char from = triplet[i];
for(int j=i+1; j<3; ++j){
char to = triplet[j];
if(nodes.containsKey(from)){
nodes.get(from).goingOut.add(to);
}else{
nodes.put(from, new GraphNode(from));
nodes.get(from).goingOut.add(to);
}
if(nodes.containsKey(to)){
nodes.get(to).comingIn.add(from);
}else{
nodes.put(to, new GraphNode(to));
nodes.get(to).goincomingInOut.add(from);
}
}
}
}while(nodes.size() < length && isMoreThanOneNodeHavingNoIncoming(nodes))
}
private boolean isMoreThanOneNodeHavingNoIncoming(nodes){
int noIncomingCount = 0;
for(char c : nodes.keySet()){
if(nodes.get(c).incoming.size() == 0)
noIncoming++;
if(noIncoming > 1)
return true;
}
}
}
class GraphNode{
Set<GraphNode> comingIn, goingOut;//Also, Initialize them
char value;
//Make sure you override equals and hashCode for value;
}
Here is my first try:
/**
* 2014-07-15: Shao Miller
* gcc -ansi -pedantic -Wall -Wextra -Werror
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define NON_CHAR '*'
static char secret[] = "helloworld";
static int find_pair(const char * s, int l, int r);
static int getRandomTripplet(char * buf);
static int is_consistent(const char * clue, const char * guess);
static int try_clue(const char * clue, char * guess);
static int unambiguous(const char * s, int l, int r);
int main(void) {
char buf[3] = "";
unsigned int sz;
unsigned int puzzled;
unsigned int guess_len;
int learned;
char * guess;
/* Allocate for the guess */
sz = getRandomTripplet(buf);
guess = malloc(sz * 2 + 4);
if (!guess) {
printf("Out of memory\n");
return EXIT_FAILURE;
}
/* Clear the guess */
memset(guess, NON_CHAR, sz * 2 + 3);
guess[sz * 2 + 3] = '\0';
/* Inject the first clue */
memcpy(guess + sz, buf, 3);
printf("*** %s Start\n", guess);
guess_len = 3;
for (puzzled = 0; puzzled < 65535;) {
getRandomTripplet(buf);
learned = try_clue(buf, guess);
if (learned) {
guess_len++;
if (guess_len == sz) {
printf("That's my final guess!\n");
free(guess);
return EXIT_SUCCESS;
}
puzzled = 0;
} else {
puzzled++;
}
}
printf("I've been puzzled for too long. I give up.\n");
free(guess);
return EXIT_FAILURE;
}
static int getRandomTripplet(char * buf) {
unsigned char positions[sizeof secret - 1] = "";
unsigned int pos;
double d;
int i;
if (buf) {
/* Pick three random positions */
i = 0;
while (1) {
d = rand();
d /= RAND_MAX;
d *= sizeof secret - 1;
pos = d;
if (positions[pos])
continue;
positions[pos] = 1;
++i;
if (i == 3)
break;
}
/* Populate the buffer from those positions */
i = 0;
for (pos = 0; pos < sizeof positions; ++pos) {
if (positions[pos])
buf[i++] = secret[pos];
}
}
/* Consistent with strlen */
return sizeof secret - 1;
}
/* Find a left and right character somewhere in a string */
static int find_pair(const char * s, int l, int r) {
char * lpos;
char * rpos;
/* Check for invalid argument */
if (!s)
return -1;
/* Find the left character */
lpos = strchr(s, l);
/* Found? */
if (!lpos)
return -1;
/* Find the right character somewhere after the left */
rpos = strchr(lpos + 1, r);
/* Found? */
if (!rpos)
return -1;
/* Return the offset to the left character */
return lpos - s;
}
/*
* Find out if a left and right character match multiple locations
* in a string
*/
static int unambiguous(const char * s, int l, int r) {
int pos1;
int pos2;
/* Check for invalid argument */
if (!s)
return -1;
/* Find the pair */
pos1 = find_pair(s, l, r);
/* Found? */
if (pos1 < 0)
return -1;
/*
* Try to find the pair again, somewhere after where the first
* was found
*/
pos2 = find_pair(s + pos1 + 1, l, r);
/* Found? If so, it's ambiguous */
if (pos2 >= 0)
return -1;
/* Return the offset to the left character */
return pos1;
}
/* Check if a clue is already consistent with a guess */
static int is_consistent(const char * clue, const char * guess) {
int pos;
pos = find_pair(guess, clue[0], clue[1]);
if (pos < 0)
return 0;
pos = find_pair(guess + pos + 1, clue[1], clue[2]);
if (pos < 0)
return 0;
return 1;
}
/* Try to learn from a clue */
static int try_clue(const char * clue, char * guess) {
int pos;
char * rpos;
/* Check if the clue is too confusing */
if (clue[0] == clue[1] || clue[1] == clue[2] || clue[0] == clue[2])
return 0;
/* Check if the guess is already consistent with the clue */
if(is_consistent(clue, guess)) {
/* Nothing to learn */
return 0;
}
/* Check for an insertion */
pos = unambiguous(guess, clue[0], clue[2]);
if (pos >= 0 && guess[pos + 1] == clue[2]) {
/* An insertion is possible! */
memmove(guess, guess + 1, pos);
guess[pos] = clue[1];
printf("%s %s Insertion\n", clue, guess);
return 1;
}
/* Check for a prepend */
pos = unambiguous(guess, clue[1], clue[2]);
if (pos >= 0 && guess[pos - 1] == NON_CHAR) {
/* Prepending is possible! */
guess[pos - 1] = clue[0];
printf("%s %s Prepend\n", clue, guess);
return 1;
}
/* Check for an append */
pos = unambiguous(guess, clue[0], clue[1]);
if (pos < 0)
return 0;
/* Find out if the right character is at the edge */
rpos = strchr(guess + pos + 1, clue[1]);
/* We assert that rpos is non-null */
if (rpos[1] == NON_CHAR) {
/* An append is possible! */
rpos[1] = clue[2];
printf("%s %s Append\n", clue, guess);
return 1;
}
/* Nothing learned */
return 0;
}
import java.util.Random;
public class RandomTripplet {
private static Random random = new Random();
private static int randomInteger(int min, int max) {
return min + random.nextInt((max - min) + 1);
}
public static String getRandomTripplet(String str) {
if (str.length()<=3)
return str;
char[] array = str.toCharArray();
int lastIndex = str.length() - 1;
int firstIndex = randomInteger(0, lastIndex - 2);
int secondIndex = randomInteger(firstIndex+1, lastIndex - 1);
int thirdIndex = randomInteger(secondIndex+1, lastIndex);
return String.valueOf(array[firstIndex]) + String.valueOf(array[secondIndex]) + String.valueOf(array[thirdIndex]);
}
public static void main(String[] args) {
for (int i=0; i<5; i++)
System.out.println(getRandomTripplet("helloworld"));
}
}
Let's assume the length of the given string as N. Therefore, index range for each character in the string is: [0,N-1]
Lets's assume the desired random triplet is represented as XYZ. Also, let's assume Ix,Iy, and Iz denote randomly chosen indices for characters X, Y, and Z respectively. As per the given condition:
Ix = [0, N-3]
Iy = [ Ix+1, N-2]
Iz = [ Iy+1, N-1]
The psuedo code is:
int rand_in_range(int a, int b)
{
return (a + rand() % (b - a + 1));
}
char* getRandomTripplet(char* str)
{
int N = strlen(str);
char result[3];
int Ix, Iy, Iz;
// boundary condition
if(N < 3)
{
return NULL; // error
}
Ix = rand_in_range(0,N-3);
Iy = rand_in_range(Ix+1,N-2);
Iz = rand_in_range(Iy+1,N-1);
result[0] = str[Ix];
result[1] = str[Iy];
result[2] = str[Iz];
return result;
}
public static void printRandomTripplet(char[] a, char[] branch, int idx, int startId, int k) {
if (idx == k) {
System.out.println(new String(branch));
return;
}
for (int i = startId; i < a.length; i ++) {
branch[idx++] = a[i];
printRandomTripplet(a, branch, idx, i + 1, k);
idx --;
}
}
public static void main(String[] args) {
System.out.println("====Ramdon Tripplet====");
int k = 3;
char[] branch = new char[k];
printRandomTripplet("abcd".toCharArray(), branch, 0, 0, k);
}
var getRandomTripplet = (function() {
var getTripplet = function(str) {
var i, m, n;
var length = str.length;
var resultObj = {};
var resultAry = [];
var firstChar = '';
var secondChar = '';
var thirdChar = '';
for (i = 0; i < length; i++) {
firstChar = str[i];
resultObj[firstChar] = true;
for (m = i + 1; m < length; m++) {
secondChar = str[m];
resultObj[firstChar + secondChar] = true;
for (n = m; n < length; n++) {
thirdChar = str[n];
resultObj[firstChar + secondChar + thirdChar] = true;
}
}
}
for (var foundStr in resultObj) {
if (foundStr.length === 3) {
resultAry.push(foundStr)
}
}
return resultAry;
};
return function(str) {
return getTripplet(str);
};
})();
console.log(getRandomTripplet('helloworld'));
It works, but with O(N3);
This question needs a tedius program. So I just list the steps for solving it.
1. Maintain a list of possible strings at all time. If the list has only one string with the required length, that is the answer.
2. If list has multiple strings, call getRandomTriplet() again. Combine the triplet with each of the strings in the list. If length overflow, delete it. A new list is formed.
3. In combining two strings (one from the list, one is a triplet). We could simply merge the two. Say 'abc' and 'def'. It can generate 'abcdef', 'dabcef', 'dabecf', 'dabefc', 'adbcef', 'adbecf', 'adbefc', 'deabcf', 'deabfc', 'deafbc', 'abdcef', 'abdecf', 'abdefc', 'daebcf', 'daebfc', 'daefbc', 'adecef', 'adefbc', 'defabc'.
If the two strings share some letters, we could use shared letters and generate shorter strings. Say 'abc' and 'dbf', we could generate 5 letter strings, 'adbcf', 'dabcf', 'adbfc', 'dabfc'.
// this is a working code in JAVA for Nplets, that is duplex, triplex, quadruplets etc are provided by the function argument
package pkg;
import java.util.Random;
public class RandomNplet {
public static int randInt(int min, int max) {
Random rand = new Random();
// nextInt is normally exclusive of the top value, so add 1 to make it inclusive
int randomNum = rand.nextInt((max - min) + 1) + min;
return randomNum;
}
// second argument of this function dertermines duplex, tripplets, quadrupplets etc.
public static String getRandomNlets(int length, int nPlate) {
String index = "";
int current_num = -1;
for (int i = nPlate; i > 0; i--) {
current_num = randInt(current_num + 1, length - i);
index = index + current_num;
}
return index;
}
public static void main(String[] args) {
String input = "Helloworld";
String index = getRandomNlets(input.length(), 3);
// System.out.println(index);
String result = "";
for (int i = 0; i < index.length(); i++) {
String char_index = String.valueOf(index.charAt(i));
result = result + input.charAt(Integer.valueOf(char_index));
}
System.out.println(result);
}
}
1. Generate a random string
2. Generate 3 random numbers, the first between 0 and string length, the second between 1st number and string length and 3rd between 2nd number and string length.
3. Concatenate string indices to get the random triplet.
s = (0...10).map { ('a'..'z').to_a[rand(26)] }.join
i = rand(s.length-1)
j = rand(i..s.length-1)
k = rand(j..s.length-1)
random_triplet = s[i]+s[j]+s[k]
You have the length of the string. After a certain number of attempts all coming up "aaa", you really could conclude that, with high probability, the string is "aaaaaaaaaaaaaaa". I'm guessing the question only requires you to return an answer that is correct with high probability, because clearly there is always some chance that you will never even learn about the existence of a character. That chance can become vanishingly small with enough uses of the random triplet method, however.
It is missing some condition, for example consists of english words. Because:
- CT July 18, 2014aaaaaaaaaaabaaaa
will not tell what position b is located in any of the aba, aab, baa return.