Google Interview Question Software Engineers
Country: United States
class Trie:
def __init__(self):
self.levels = []
def insert(self, string):
new_branches = 0
for level in range(len(string)):
c = string[level]
if (level + 1) > len(self.levels):
self.levels.append({c})
new_branches += 1
else:
level_nodes = self.levels[level]
if c not in level_nodes: # could be implemented in O(1)
level_nodes.add(c)
new_branches += 1
return new_branches
def fun(strings):
trie = Trie()
for string in strings:
new_branches = trie.insert(string)
if new_branches == 1:
return True
return False
I'd probably use something like vector<unordered_map<char, int>> structure while looping over each pair:
bool isPairMatch(vector<string>& dict) {
vector<unordered_map<char, int>> vmap;
for (string word: dict) {
unordered_map<char, int> mm;
for (char ch: word) {
mm[ch]++;
}
// checking if match
for (unordered_map<char, int> m: vmap) {
if (comp(m, mm)) return true;
}
vmap.push_back(mm);
}
}
bool comp(unordered_map<char, int> m1, unordered_map<char, int> m2) {
if (m1.size() != m2.size()) return false;
int diff = 0;
for (char ch: m1) {
diff += abs(m1[ch] - m2[ch]);
if (diff > 1) return false;
}
return true;
}
I'd probably use something like vector<unordered_map<char, int>> structure while looping over each pair:
bool isPairMatch(vector<string>& dict) {
vector<unordered_map<char, int>> vmap;
for (string word: dict) {
unordered_map<char, int> mm;
for (char ch: word) {
mm[ch]++;
}
// checking if match
for (unordered_map<char, int> m: vmap) {
if (comp(m, mm)) return true;
}
vmap.push_back(mm);
}
}
bool comp(unordered_map<char, int> m1, unordered_map<char, int> m2) {
if (m1.size() != m2.size()) return false;
int diff = 0;
for (char ch: m1) {
diff += abs(m1[ch] - m2[ch]);
if (diff > 1) return false;
}
return true;
}
I'd probably use something like vector<unordered_map<char, int>> structure while looping over each pair:
bool isPairMatch(vector<string>& dict) {
vector<unordered_map<char, int>> vmap;
for (string word: dict) {
unordered_map<char, int> mm;
for (char ch: word) {
mm[ch]++;
}
// checking if match
for (unordered_map<char, int> m: vmap) {
if (comp(m, mm)) return true;
}
vmap.push_back(mm);
}
}
bool comp(unordered_map<char, int> m1, unordered_map<char, int> m2) {
if (m1.size() != m2.size()) return false;
int diff = 0;
for (char ch: m1) {
diff += abs(m1[ch] - m2[ch]);
if (diff > 1) return false;
}
return true;
}
If only the last character counts for the difference, then we can insert the strings to be found in a hashmap(
unordered_map<string>
) and iterate through the strings.
For example, for
"abcd"
we check if
"abcb"
and
"abce"
are present in the hash map. If not we add them and proceed.
Whole idea is instead of for every string check every other string and check if they are off by one O(n^2 m) we for every string delete one character from string and remember it. If it already has been remembered, it means that there are 2 string off by one in array. This however takes O(nm^2) due to the fact that for every letter in string we create a string without that letter, and this requires us to copy every remaining letter. To combat that, we instead of creating a string, use a rolling hash. For each string we calculate a rolling hash and then for each letter in string we calculate "partlyHash" which is equal to hash minus hash part of current letter (which is 128^(m - letterIndex - 1)). Then we store this by its hash in `partlyHashToString`. There is a chance that there are collisions so we store strings and then double check if it is different by one for sure. This makes this algorithm O(n*m)
fun isPairWithDiffByOne(input: Array<String>): Boolean {
// map for storing whole strings to hash of them without one of the letters
val partlyHashToString = HashMap<Int, ArrayList<String>>()
for (string in input) {
// rolling hash for letters
var wholeHash = 0
// variable for calculating 128 ^ letters - 1, so in next loop we can easily use that in subtraction
var rolled128 = 1
for (letter in string) {
wholeHash = 128 * wholeHash + letter.code
rolled128 *= 128
}
rolled128 /= 128
for (letter in string) {
// from rolling hash we subtract rolling part of letter
val partlyHash = wholeHash - (rolled128 * letter.code)
val valuesForPartlyHash = partlyHashToString[partlyHash] ?: ArrayList()
partlyHashToString[partlyHash] = valuesForPartlyHash
// if array is not empty there is a string which without one of its letter has the same hash as our partlyHash
if (valuesForPartlyHash.isNotEmpty()) {
// to be safe if there are hash collisions we check to be sure that those strings are in fact off by one
// its highly improbable due to high rolling constant = 128, however hash value is constantly rolling over Int.MAX_VALUE
// so there might be a case when hashes collide
val isAMatch = valuesForPartlyHash.any { isByOne(it, string) }
if (isAMatch)
return true
}
valuesForPartlyHash.add(string)
rolled128 /= 128
}
}
return false
}
// failsafe for collisions
fun isByOne(first: String, second: String): Boolean {
var alreadyModified = false
for (i in first.indices) {
if (first[i] != second[i]) {
if (alreadyModified)
return false
alreadyModified = true
}
}
return true
}
{import java.util.*;
public class Pair {
public static void main(String[] args){
String[] names = {"abcd", "acdb", "abce", "acbe", "adfb"};
System.out.println(hasPair(names, 4));
}
static boolean hasPair(String[] names, int m) {
for (int i=0; i<names.length; i++) {
String name = names[i];
for (int j=0; j<names.length; j++){
if (i != j && (name.equals(names[j])
|| names[j].startsWith(name.substring(0,3)))) {
return true;
}
}
}
return false;
}
}}
{import java.util.*;
public class Pair {
public static void main(String[] args){
String[] names = {"abcd", "acdb", "abce", "acbe", "adfb"};
System.out.println(hasPair(names, 4));
}
static boolean hasPair(String[] names, int m) {
for (int i=0; i<names.length; i++) {
String name = names[i];
for (int j=0; j<names.length; j++){
if (i != j && (name.equals(names[j])
|| names[j].startsWith(name.substring(0,3)))) {
return true;
}
}
}
return false;
}
}}
why "abcd" and "abdd" is false? they only have one difference right?
- mike March 25, 2022