Facebook Interview Question
Country: United States
I though of this one solution and at some point I felt it was too much memory.
But that is the trade off.
to get all the combinations of 'x' and strings:
#include <stdio.h>
char tar[100];
void foo(char *s, int i, int size)
{
if (i >= size)
return;
if (i == size-1) {
tar[i] = '\0';
printf("%s\n", tar);
return;
}
if(s[i] >= 'a' && s[i] <= 'z') {
tar[i] = 'x';
foo(s, i+1, size);
tar[i] = s[i];
foo(s, i+1, size);
}
}
int main()
{
char s[] = {"abc"};
foo(s, 0, sizeof(s)/sizeof(s[0]));
return 0;
}
private HashSet<String> computePermutations(String input) {
HashSet<String> returns = new HashSet<String>();
int len = input.length();
for(int i = len; i>0; i--) {
for(int j=0; j<len; j++) {
int start=j;
StringBuilder sb = new StringBuilder(input);
for(int star = i; star>0; star--) {
sb.setCharAt(start, '*');
start = (++start%len);
}
returns.add(sb.toString());
}
}
return returns;
}
iterative method. how does this look?
Here is the iterative solution, I wrote. How does it look? This works. Can anyone take a look at it?
private HashSet<String> computePermutations(String input) {
HashSet<String> returns = new HashSet<String>();
int len = input.length();
for(int i = len; i>0; i--) {
for(int j=0; j<len; j++) {
int start=j;
StringBuilder sb = new StringBuilder(input);
for(int star = i; star>0; star--) {
sb.setCharAt(start, '*');
start = (++start%len);
}
returns.add(sb.toString());
}
}
return returns;
}
@Eric - The solution using regex varies depending on language, but in general, to form the regular expression you would just replace the asterisk (*) with a period (.) because a period matches any single character. However, the regex solution would not meet the O(1) lookup requirement, so it's kind of a moot point.
The O(1) requirement is a very important element to the problem, as it tests your ability to make tradeoffs of memory for speed (or in some cases, speed for memory). With a company like Facebook, a lot of problems they would want to solve would require very fast computation/lookups with large data sets, and would very much be worth storing extra data in order to speed things up.
import java.util.Arrays;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Searcher {
private final String data;
public Searcher(String[] data) {
if(data == null || data.length == 0) {
throw new IllegalArgumentException("bad data");
}
StringBuilder builder = new StringBuilder();
for(String part : data) {
builder.append(part).append("\n");
}
this.data = builder.toString();
}
public String checkValuePresent(String value) {
boolean result = search(value);
return result ? "YES" : "NO";
}
public boolean search(String input) {
if(input == null) {
throw new IllegalArgumentException("input should not be NULL");
}
String patternSource = input.replace('*', '.');
Pattern pattern = Pattern.compile("^"+patternSource+"$", Pattern.MULTILINE);
Matcher matcher = pattern.matcher(data);
boolean result = matcher.find();
return result;
}
public static void main(String [] args) {
String [] data = {"hazem", "ahmed", "moustafa", "fizo"};
Searcher searcher = new Searcher(data);
System.out.println("data = " + Arrays.toString(data));
String result = null;
String input = "ahmed";
result = searcher.checkValuePresent(input);
System.out.println(input + ": " + result);
input = "m**stafa";
result = searcher.checkValuePresent(input);
System.out.println(input + ": " + result);
input = "fizzo";
result = searcher.checkValuePresent(input);
System.out.println(input + ": " + result);
input = "fizd";
result = searcher.checkValuePresent(input);
System.out.println(input + ": " + result);
input = "*****";
result = searcher.checkValuePresent(input);
System.out.println(input + ": " + result);
input = "****";
result = searcher.checkValuePresent(input);
System.out.println(input + ": " + result);
input = "**";
result = searcher.checkValuePresent(input);
System.out.println(input + ": " + result);
}
}
dict = {}
words = ['ahmed', 'hazem', 'moustafa', 'fizo']
def addToDict(original, final):
# Take first letter in original, recursively call
# function with that letter in one call and * in another
if len(original) == 0:
dict[final] = 1
else:
addToDict(original[1:], final + original[0])
addToDict(original[1:], final + '*')
def checkWord(word):
if word in dict:
print '{} : YES'.format(word)
else:
print '{} : NO'.format(word)
for word in words:
addToDict(word, "")
checkWord('ahmed')
checkWord('m**stafa')
checkWord('fizoo')
checkWord('fizd')
checkWord('*****')
checkWord('****')
checkWord('**')
Generate all possible string and put them in a set. and search from there O(1), it is not horrible in terms of space complexity... :P.
public static void main(String args[])
{
String[] words = {"hazem", "ahmed", "moustafa", "fizo", "hazhaz"};
Set<String> pool = BuildPool(words);
List<String> list = new ArrayList<>();
list.addAll(Arrays.asList("ahmed", "m**stafa", "fizoo", "fizd", "*****", "****", "**"));
for(String word : list)
{
System.out.print(pool.contains(word)+" ");
System.out.println(word);
}
}
public static Set<String> BuildPool(String[] words)
{
Set<String> pool = new HashSet<>();
for(String word : words)
{
pool.add(word);
char[] buf = word.toCharArray();
for(int i = 0; i < word.length(); i++)
{
for(int j = i; j < word.length(); j++)
{
for(int k = i; k <= j; k++)
{
buf[k] = '*';
pool.add(new String(buf));
}
for(int k = i; k < j; k++)
buf[k] = word.charAt(k);
}
}
}
return pool;
}
package com.superdecoder.questions;
import java.util.HashSet;
public class PlaceHolderLookup {
public static void main(String[] args) {
String[] words = new String[] { "hazem", "ahmed", "moustafa", "fizo" };
HashSet<String> hs = new HashSet<String>();
for(String w : words) {
hs.add(w);
permute(w, hs, 0);
}
System.out.println(search("ahmed", hs));
System.out.println(search("m**stafa", hs));
System.out.println(search("fizoo", hs));
System.out.println(search("fizd", hs));
System.out.println(search("*****", hs));
System.out.println(search("****", hs));
System.out.println(search("**", hs));
}
public static void permute(String w, HashSet<String> hs, int numWC) {
if(numWC == w.length()) return;
for(int i=0; i<w.length(); i++) {
if(w.charAt(i) == '*') continue;
StringBuilder sb = new StringBuilder(w.length())
.append(w.substring(0, i))
.append("*")
.append(w.substring(i+1, w.length()));
hs.add(sb.toString());
//System.out.println(sb.toString());
permute(sb.toString(), hs, numWC+1);
}
}
public static boolean search(String w, HashSet<String> hs) {
return hs.contains(w);
}
}
Since the requirement is O(1) look up only, we can use a hash table to store all possible combination for each string. For each string, insert all possible combination as follow
void addString(string& str, unordered_map<string,int>& m)
{
//cout << str << endl;
m.insert(pair(str, 1));
int len = str.length();
for (int i = 0; i < len; ++i)
{
char c = str[i];
str[i] = '*';
//cout << str << endl;
m.insert(pair(str, 1));
str[i] = c;
}
for (int i = 2; i <= len; ++i)
{
for (int j = 0; j < len-(i-1); ++j)
{
string tmp = str;
for (int k = j; k < j+i-1; ++k)
{
tmp[k] = '*';
}
for (int k = j+i-1; k < len; ++k)
{
char c = tmp[k];
tmp[k] = '*';
//cout << tmp << endl;
m.insert(pair(tmp, 1));
tmp[k] = c;
}
}
}
}
std::unordered_set<std::string> dictionary;
void PopulateDictionary(const std::vector<std::string> &words) {
for (size_t i = 0; i < words.size(); ++i) {
PopulateWord(words[i], 0, '');
}
}
void PopulateWord(const std::string &word, int position, const std::string &str) {
if(position == word.size() - 1) {
dictionary.insert(str);
return;
}
PopulateWord(word, position + 1, str + '*');
PopulateWord(word, position + 1, str + word[position]);
}
std::string Search(const std::string &word) {
if (dictionary.find(word) == dictionary.end()) {
return 'NO';
} else {
return 'YES';
}
}
Sorry, made a mistake.
New code as below:
std::unordered_set<std::string> dictionary;
void PopulateDictionary(const std::vector<std::string> &words) {
for (size_t i = 0; i < words.size(); ++i) {
PopulateWord(words[i], 0, '');
}
}
void PopulateWord(const std::string &word, int position, const std::string &str) {
if(position == word.size()) {
dictionary.insert(str);
return;
}
PopulateWord(word, position + 1, str + '*');
PopulateWord(word, position + 1, str + word[position]);
}
std::string Search(const std::string &word) {
if (dictionary.find(word) == dictionary.end()) {
return 'NO';
} else {
return 'YES';
}
}
I can propose to precalculate all possible combinations and insert those in hashset and just check if given query in hashset. There are not to many combinations
hazem - 2 ^ 5 = 32
ahmed - 2 ^ 5 = 32
fizo - 2 ^ 4 = 16
moustafa = 2 ^ 8 = 256
So in total set will contain less that 336 combinations, we can check for existence in O(1)
#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<string, int> myMap;
bool isChar(const char& input) {
if ( input >= 'a' && input <= 'z')
return true;
if (input >= 'A' && input <= 'Z')
return true;
return false;
}
void fill(vector<string>& dict, int vecIndex, int subIndex) {
// Out of words to insert.
if ( vecIndex == dict.size())
return;
// Word is fully formed, insert to map.
if ( dict[vecIndex].length() == subIndex ) {
myMap[dict[vecIndex]] = 1;
}
for (int i = subIndex; i < dict[vecIndex].length(); i++ ) {
if ( isChar(dict[vecIndex][i]) ) {
char holder = dict[vecIndex][i];
dict[vecIndex][i] = '*';
// Insert one with this *
fill(dict, vecIndex, dict[vecIndex].length() + 1);
// Continue the recursion for thi sparticular item.
fill(dict, vecIndex, i + 1);
// restore previous state.
dict[vecIndex][i] = holder;
} // end if
} // end for
myMap[dict[vecIndex]] = 1;
fill(dict, vecIndex + 1, 0);
}
string isThere(string query) {
cout << query << " : ";
map<string, int>::iterator it = myMap.find(query);
if (it == myMap.end())
return "NO\n";
return "YES\n" ;
}
int main() {
vector<string> dict;
dict.push_back("ahmed");
dict.push_back("moustafa");
dict.push_back("hazem");
dict.push_back("fizo");
fill (dict, 0, 0);
cout << isThere("ahmed");
cout << isThere("m**stafa");
cout << isThere("fizoo");
cout << isThere("fizd");
cout << isThere("*****");
cout << isThere("****");
cout << isThere("**");
/*
map<string, int>::iterator it;
for (it = myMap.begin(); it != myMap.end(); it++)
cout << it->first << endl;
*/
return 0;
}
public class PlaceHolderDictionnary {
Set<String> dictionnary;
public PlaceHolderDictionnary(List<String> words) {
this.dictionnary = new HashSet<String>();
for (String word : words) {
add(word);
}
}
private void add(String word) {
this.dictionnary.add(word);
int stars = 1;
while (stars <= word.length()) {
for (int i = 0; i + stars <= word.length(); i++) {
char[] strToChars = word.toCharArray();
Arrays.fill(strToChars, i, i + stars, '*');
this.dictionnary.add(new String(strToChars));
}
stars++;
}
}
public String answer(String word) {
return dictionnary.contains(word) ? "YES" : "NO";
}
public static void main(String[] args) {
PlaceHolderDictionnary placeHolderDictionnary = new PlaceHolderDictionnary(Arrays.asList("hazem", "ahmed", "moustafa", "fizo"));
System.out.println(placeHolderDictionnary.answer("ahmed"));
System.out.println(placeHolderDictionnary.answer("m**stafa"));
System.out.println(placeHolderDictionnary.answer("fizoo"));
System.out.println(placeHolderDictionnary.answer("fizd"));
System.out.println(placeHolderDictionnary.answer("*****"));
System.out.println(placeHolderDictionnary.answer("****"));
System.out.println(placeHolderDictionnary.answer("**"));
}
}
To achieve the O(1) search time regardless of data strings, it is necessary to create the permutation of data strings with '*' in advance and store in hashtable, which gives O(1) search time.
The following is the C++ version of solution.
#include<iostream>
#include<string>
#include<map>
using namespace std;
void permutate(string prev, string s, int pos, map<string, int> &m)
{
if (m.find(prev)==m.end())
{
m[prev] = 1;
}
if (pos >= s.length())
return;
for (int i = pos; i < s.length(); i++)
{
prev.replace(i, 1, 1, '*');
permutate(prev, s, pos+1, m);
prev.replace(i, 1, 1, s[i]);
}
}
void initialize(string* input, int len, map<string, int> &m)
{
for (int i = 0; i < len; i++)
permutate(input[i], input[i], 0, m);
}
So I assume O(max length of word) O(1)
python2
TERMINATOR = object()
def add_to_trie(trie, word):
for c in word:
trie = trie.setdefault(c, {})
trie[TERMINATOR] = {}
def query(trie, mask):
tries = [trie]
for c in list(mask) + [TERMINATOR]:
new_tries = []
for t in tries:
if c == '*':
new_tries.extend(t.values())
else:
if c in t:
new_tries.append(t[c])
tries = new_tries
return bool(new_tries)
def main():
words = ['hazem', 'ahmed', 'moustafa', 'fizo', 'hazhaz']
trie = {}
for word in words:
add_to_trie(trie, word)
assert not query(trie, '**')
assert query(trie, 'ahmed')
assert query(trie, '*hmed')
assert query(trie, 'm**stafa')
assert query(trie, '*****')
assert query(trie, '****')
assert not query(trie, '***')
assert not query(trie, 'fizoo')
assert query(trie, 'fizo')
assert not query(trie, '')
if __name__ == '__main__':
main()
- Adding different combinations of string in cache and then check it out. Cache is taken as Set so the search operation should ideally be in O(1). Well the dummy string length should be more than the length of longest string in the input.
import java.util.HashSet;
import java.util.Set;
public class QuerySearch {
static Set<String> dataCache = new HashSet<>();
static String dummy = "***********************************";
public static void main(final String a[]) {
addToMemory("fizo");
addToMemory("hazem");
addToMemory("ahmed");
addToMemory("moustafa");
System.out.println(checkQuery("ahmed"));
System.out.println(checkQuery("m**stafa"));
System.out.println(checkQuery("fizoo"));
System.out.println(checkQuery("fizd"));
System.out.println(checkQuery("*****"));
System.out.println(checkQuery("****"));
System.out.println(checkQuery("**"));
}
//Adding different combinations of string in cache
public static void addToMemory(final String data) {
dataCache.add(data);
for (int i = 0; i < data.length(); i++) {
final String prefix = data.substring(0, i);
for (int j = i + 1; j <= data.length(); j++) {
dataCache.add(prefix + dummy.substring(i, j) + data.substring(j));
//System.out.println(prefix + dummy.substring(i, j) + data.substring(j));
}
}
}
//checking in Set
public static String checkQuery(final String str) {
return dataCache.contains(str) ? "YES" : "NO";
}
}
Won't this miss some combinations? Your solution would put f*zo into the cache, but it wouldn't put f*z* into the cache.
This is my solution.
I create a set containing all the names which will be sought. Then I parse a string request. If it doesn't have any asterisk placeholders, I'll just call contains(request) on the set with the names.
If the request contains asterisk(s), I'll replace them with a, b, c, etc. and call contains(request) every time after replacing.
So if the input data is has**, the following strings will be checked:
- hasaa,
- hasab,
- hasac
...
- hasem is in the map. We're done.
package careepcup.fb;
import java.util.HashSet;
import java.util.Set;
public class Main {
/*
* This class offers constant time performance for the basic operations (add, remove, contains
* and size), assuming the hash function disperses the elements properly among the buckets.
*/
private static final Set<String> NAMES = new HashSet<String>();
private static final String YES = "YES";
private static final String NO = "NO";
static {
NAMES.add("hasad");
NAMES.add("ahmed");
NAMES.add("moustafa");
NAMES.add("fizo");
}
public static void main(String[] args) {
System.out.println(hasName("has**"));
}
static boolean generate(String query, int length, String prefix) {
for (char letter = 'a'; letter <= 'z'; letter++) {
if (length > 1) {
boolean result = generate(query, length - 1, prefix + letter);
if (result) {
return true;
}
}
else {
char[] generated = (prefix + letter).toCharArray();
char[] queryAsArray = query.toCharArray();
for (int i = 0, j = 0; i < queryAsArray.length; i++) {
if (queryAsArray[i] == '*') {
queryAsArray[i] = generated[j];
j++;
}
}
if (NAMES.contains(new String(queryAsArray))) {
return true;
}
}
}
return false;
}
static String hasName(String query) {
int fromIndex = 0;
int asteriskCount = 0;
while ((fromIndex = query.indexOf("*", fromIndex)) != -1) {
asteriskCount++;
fromIndex++;
}
if (asteriskCount == 0) {
return NAMES.contains(query) ? YES : NO;
} else {
return generate(query, asteriskCount, "") ? YES : NO;
}
}
}
If we assume we can't use regex. (Since that would somewhat trivialize this problem)
You could populate the hashtable by recursively running through all the strings and replacing * in the strings to make all combinations of letters and *.
If the length of the longest string is k, then the population of the hashtable runs in O(n * 2 ^k), but then lookup is just O(1).
You can populate the hashtable with something like the following code called on every string s with the following function call:
Example:
- Skor February 25, 2015populateHashTable(HashTable h, String original, String edited, int currentCharIndex) { if (currentCharIndex >= s.length) { h.add(edited, true); return; } populateHashTable(h, original, edited + original.charAt(currentCharIndex), currentCharIndex + 1); populateHashTable(h, original, edited + "*", currentCharIndex + 1); }