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?

- mike March 25, 2022 | Flag Reply
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)
                    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

- Try this November 26, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Would return True for below

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

- Sumit January 15, 2023 | Flag
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;
}

- Aleks November 27, 2021 | Flag Reply
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;
}

- Aleks November 27, 2021 | Flag Reply
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;
}

- Aleks November 27, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- dfsdfdsfd December 05, 2021 | Flag Reply
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?

- mike March 25, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 01, 2023 | Flag
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.

- Riks June 03, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 08, 2022 | Flag
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
            }
            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
}

- Grzegorz.Poreba.73 July 30, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Code is written in kotlin

- Grzegorz.Poreba.73 July 30, 2022 | Flag
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;
}
}}

- Peter Akwa November 08, 2022 | Flag Reply
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;
}
}}

- Peter Akwa November 08, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def has_one_difference_pair(words):
seen = set()
for word in words:
for i in range(len(word)):
# Generate variants of the word with one character difference
variant = word[:i] + '_' + word[i+1:]
if variant in seen:
return True
seen.add(variant)
return False

- Dmitry October 25, 2023 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Map. Key- character, value- index.

For each key insert in map with index and check if already seen index.

You need to run loop over the list of the given string and compare 2 strings by above logic.

To optimize more, in case of running loops Use divide and conquer to compare 2 strings.

- Anonymous December 22, 2023 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Map(character, index) everytime before check if index same or not.

Assuming it's list of strings, so run loop and compare 2 strings by above logic.

Optimize, in case of loop use divide and conquer to compare 2 strings.

- Tridib December 22, 2023 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More