## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

why "abcd" and "abdd" is false? they only have one difference right?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)
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``````

Comment hidden because of low score. Click to expand.
0

Would return True for below

``words = ["abc", "cab", "cbd"]``

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

leetcode.com/problems/longest-string-chain link to leetcode

Comment hidden because of low score. Click to expand.
0
of 0 vote

why "abcd" and "abdd" returns false. There is only one difference right?

Comment hidden because of low score. Click to expand.
0

abcd -> abd (without third character 'c')
abdd -> abd (without third character 'd')
abdd -> abd (without forth character 'd')

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Questions is not about the last character. It could be anywhere. @jllangston probably just give an example.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}
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]) {
return false
}
}
return true
}``````

Comment hidden because of low score. Click to expand.
0

Code is written in kotlin

Comment hidden because of low score. Click to expand.
0
of 0 vote

{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;
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{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;
}
}}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.