Google Interview Question for Software Engineers

Country: India
Interview Type: In-Person

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

Bit Manipulation problem (c#)

``````public bool IsMetaString(char[] A, char[] B)
{
count = 0;
var bitsA = 0;
var bitsB = 0;

for (int i = 0; i < A.Length; i++)
{
var valA = A[i] - 'a';
var valB = B[i] - 'a';
bitsA |= (1 << valA);
bitsB |= (1 << valB);
var xOr = (1 << valA) ^ (1 << valB);
if (xOr > 0)
count++;
}

return (bitsA ^ bitsB) == 0 && count == 2;
}``````

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

Implementation in Java. (I've assumed that 'aba' and 'aba' are meta words, but 'abc' and 'abc' are not)

``````static boolean isMetaWords(String firstWord, String secondWord) {
if (firstWord.length() != secondWord.length()) {
return false;
}
int firstDiff = -1, secondDiff = -1;
Map<Character, Integer> wordStatistic = new HashMap<>();
for (int i = 0; i < firstWord.length(); i++) {
char symbol = firstWord.charAt(i);
wordStatistic.put(symbol, wordStatistic.getOrDefault(symbol, 0) + 1);
if (symbol != secondWord.charAt(i)) {
if (firstDiff == -1) {
firstDiff = i;
} else if (secondDiff == -1) {
secondDiff = i;
} else {
return false;
}
}
}
if (firstDiff == -1 && secondDiff == -1) {
// both strings are the same, just check that the string has repeatable symbols
for (int v : wordStatistic.values()) {
if (v > 1) {
return true;
}
}
return false;
}
if (secondDiff == -1) {
return false;
}
return firstWord.charAt(firstDiff) == secondWord.charAt(secondDiff)
&& firstWord.charAt(secondDiff) == secondWord.charAt(firstDiff);
}``````

Subset of tests is:

``````{"Converse", "Conserve", true},
{"test", "test", true},
{"false", "true", false},
{"test", "text", false},
{"change", "cgahne", false},
{"change", "cganhe", true},
{"abcd", "abcd", false},
{"abcda", "abcda", true},``````

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

``````def checkMeta(s1, s2):
if len(s1) != len(s2):
return False
diff_values = {x1 for x1, x2 in zip(s1, s2) if x1 != x2}
if len(diff_values) != 2:
return False
d1, d2 = diff_values
swapped_s1 = ''.join(d2 if v == d1 else d1 if v == d2 else v for v in s1)
return swapped_s1 == s2

assert not checkMeta('abcd', 'abcd')
assert not checkMeta('abcx', 'abcd')``````

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

Simple python solution

``````def checkMeta(s1, s2):
if len(s1) != len(s2):
return False
diff_values = {x1 for x1, x2 in zip(s1, s2) if x1 != x2}
if len(diff_values) != 2:
return False
d1, d2 = diff_values
swapped_s1 = ''.join(d2 if v == d1 else d1 if v == d2 else v for v in s1)
return swapped_s1 == s2

assert checkMeta('Converse', 'Conserve')
assert not checkMeta('abcd', 'abcd')
assert not checkMeta('abcx', 'abcd')``````

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

``````public boolean conserve(){
String str1 = "Converse";
String str2 = "Conserve";

int[] map = new int[2];
int mapIndex=0;
if(str1.length()!=str2.length()) return false;
for (int i = 0; i<str1.length() ; i++) {
if (str1.charAt(i) != str2.charAt(i)) {
if (mapIndex == 2) return false;
map[mapIndex] = i;
mapIndex++;
}
}

char temp = str1.charAt(map[0]);
str1 = str1.substring(0,map[0])+str1.charAt(map[1])+str1.substring(map[0]+1,map[1])+temp+str1.substring(map[1]+1,str1.length());
return  (str1.equals(str2));

}``````

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

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

import java.io.IOException;

import org.apache.commons.lang3.text.StrTokenizer;

public class CheckMetaString {

public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub

String x = "converse";
String y = "conserve";
int stratIndex = 0;
int lastIndex = 0;
boolean isflag = true;
if(x.length() != y.length())
throw new IOException("Strings are not meta Strings");
for (int i = 0; i < x.length(); i++) {
int value = x.charAt(i);
int value1 = y.charAt(i);
if(value != value1){
if(isflag){
stratIndex = x.indexOf(x.charAt(i));
isflag = false;
}
else {
lastIndex = x.indexOf(x.charAt(i));
}

}
}
char xx = x.charAt(stratIndex);
char yy = x.charAt(lastIndex);
char[] c = x.toCharArray();
c[stratIndex] = yy;
c[lastIndex] = xx;
String xxx = new String(c);
System.out.println(xxx);
if(xxx.equalsIgnoreCase(y)){
System.out.println("Strings are meta String");
}

}

}

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

``````public class MetaStrings {
/**
* The idea is that the strings must be different maximum with two characters
* ANd for the positions that are different should be equal in crossing order
*/
public boolean areMetaStrings(final String str1, final String str2) {
if (str1.length() != str2.length()) {
return false;
}
int len = str1.length();
int firstDiffIndex = -1, secondDiffIndex = -1;
for (int i = 0; i < len; ++i) {
if (str1.charAt(i) != str2.charAt(i)) {
if (firstDiffIndex == -1) {
firstDiffIndex = i;
} else if (secondDiffIndex == -1) {
secondDiffIndex = i;
} else {
return false;
}
}
}

return (firstDiffIndex != -1 && secondDiffIndex != -1)
&& (str1.charAt(firstDiffIndex) == str2.charAt(secondDiffIndex)
&& str1.charAt(secondDiffIndex) == str2.charAt(firstDiffIndex));
}``````

}

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

``````public static bool isMeta(string first, string second)
{
if (first == null || second == null || first.Length != second.Length) return false;
Mode metaMode = Mode.BeforeMeta;
int indexOfMismatch = -1;
for (int i = 0; i < first.Length; i++)
{
if (first[i] != second[i])
{
switch (metaMode)
{
case Mode.BeforeMeta:
indexOfMismatch = i;
metaMode = Mode.Meta;
break;
case Mode.AfterMeta:
return false;
case Mode.Meta:
if (first[i] == second[indexOfMismatch]
&& first[indexOfMismatch] == second[i])
{
metaMode = Mode.AfterMeta;
}
else
{
return false;
}
break;
}
}
}
return metaMode == Mode.AfterMeta;
}

public enum Mode {
BeforeMeta, Meta, AfterMeta``````

}

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

``````#include <iostream>
#include <string>

using namespace std;

bool AreMetaString(string a, string b)
{
char diff_in_a;
char diff_in_b;
bool diff = false;
bool found = false;

if (a.length() != b.length())
return false;

for (int i = 0; i < a.length(); ++i)
{
if (a[i] != b[i])
{
if (found == true)
return false;

if (diff == true)
{
if (a[i] == diff_in_b && b[i] == diff_in_a)
found = true;
else
return false;
}
else
{
diff = true;
diff_in_a = a[i];
diff_in_b = b[i];
}
}
}
return true;
}

void main_meta_strings(void)
{
string s1 = "Conversa";
string s2 = "Consarve";

cout << AreMetaString(s1, s2);
}``````

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

change @Dhruva.Bharadwaj's codes to makes sure it is correct!

``````private static boolean IsMetaString(String string1, String string2) {
String s1 = string1.toLowerCase();
String s2 = string2.toLowerCase();
int diff = 0;
int diffIndex = 0;
if (s1.length() != s2.length() || s1.length() == 0) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(i)) {
continue;
}
diff++;
if (diff > 2) {
return false;
} else if (diff == 1) {
diffIndex = i;
}else{
if (s2.charAt(i) == s1.charAt(diffIndex) && s2.charAt(diffIndex)==s1.charAt(i)) {
continue;
}else{
return false;
}
}
}

return diff==2;
}``````

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

``````int isMeta(char *str1, char *str2)
{
int nr_diff = 0;
int diff[2];

for (int i = 0; str1[i] && str2[i]; i++)
if (str1[i] != str2[i]) {
if (nr_diff == 2)
return 0;
diff[nr_diff++] = i;
}

if (nr_diff != 2)
return 0;

if (str1[diff[0]] != str2[diff[1]] || str1[diff[1]] != str2[diff[0]])
return 0;

return 1;
}``````

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

``````package google;

public class MetaString {
public static void main(String args[]) {
String s1 = "Converse";
String s2 = "Conserve";

System.out.println(isMetaString(s1, s2));
}

private static boolean isMetaString(String string1, String string2) {
String s1 = string1.toLowerCase();
String s2 = string2.toLowerCase();
int diff = 0;
int diffIndex = 0;
if (s1.length() != s2.length() || s1.length() == 0) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(i)) {
continue;
}
diff++;
if (diff > 2) {
break;
} else if (diff == 1) {
diffIndex = i;
} else {
if (s2.charAt(i) == s1.charAt(diffIndex)) {
continue;
} else {
diff++;
break;
}
}
}

if (diff > 2) {
return false;
}
return true;
}
}``````

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.