## Google Interview Question for Software Developers

• -1
of 1 vote

Country: United States
Interview Type: In-Person

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

Can you clarify, please what should be when we compare digraph "ch" with character '"c", or with other digraph, or digraph "ch" with character '"a". How do we know which pairs are digraphs?

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

Here is a possible solution with the stipulation that I assume that it is given a set of digraphs in advance and each digraph has a its own place in the alphabet, for example we have a, b, c, ch,cz,d,e,f ...z n. Ofcourse I don't pretend that algorithm is correct when I don't know concrete details of the problem, just try to solve the problem with my own assumptions.
Time complexity O(n)

``````Set<String> digraphs = new HashSet<>();
boolean isDigraph(String word) {
if (word.length() < 2)
return false;
return digraphs.contains(word.substring(0,2));
}
int compare(String a, String b) {
if(a.length() == 0 && b.length() == 0)
return 0;
else if(a.length() == 0){
return -1;
} if(b.length() == 0){
return 1;
}
else {
if (a.charAt(0) != b.charAt(0))
return a.charAt(0) < b.charAt(0)? -1 : 1;
else {
if (isDigraph(a) && isDigraph(b)) {
if(a.charAt(1) != b.charAt(1))
return a.charAt(1) < b.charAt(1)? -1 : 1;
else
return compare(a.substring(2), b.substring(2));
}
else if(isDigraph(a)) {
return 1;
}
else if(isDigraph(b)) {
return -1;
}
else
return compare(a.substring(1), b.substring(1));
}
}

}``````

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

``````//Assumptions: A dictionary in the form of HashMap is given where the keys are the different languages of the characters and the values tell us their lexicographic value.
//Time complexity:O(Min(n,m)) where n and m are the sizes of the strings.Why Min??Because, if one of the strings is smaller then the other we will not assess the excess characters
of the larger string.
public int compare(String s1, String s2, HashMap<String,Integer> mp)throws NullPointerException
{
if(s1==null||s2==null)
{
throw new NullPointerException();
}

int i=1;
int j=1;
while(i<s1.length() && j<s2.length())
{
String str1=s1.substring(i-1,i);
String str2=s2.substring(j-1,j);

if(mp.containsKey(str1) && mp.containsKey(str2))
{
int v=mp.get(str1).intValue();
int w=mp.get(str2).intValue();
if(v==w)
{
i++;
j++;
}else
{
return v-w;
}
}
else if (!mp.containsKey(str1) && !mp.containsKey(str2))
{
str1+=s1.substring(i,i+1);
str2+=s2.substring(j,j+1);
if(!mp.containsKey(str1)||!mp.containsKey(str2))
{
throw new Exception("Invalid character");
}
int v=mp.get(str1).intValue();
int w=mp.get(str2).intValue();
if(v==w)
{
i+=2;
j+=2;
}else{
return v-w;
}

}
else if (!mp.containsKey(str1))
{
str1+=s1.substring(i,i+1);
if(!mp.containsKey(str1))
{
throw new Excepton("invalid character");
}
int v=mp.get(str1);
int w=mp.get(str2);
return  v-w;

}else{
str2+=s2.substring(j,j+1);
if(!mp.containsKey(str2))
{
throw new Exception("Invalid character");

}
int v=mp.get(str1);
int w=mp.get(str2);
return v-w;

}
}
//If we get out of the loop and both strings are of different lengths
if(s1.length()!=s2.length())
{
return s1.length()-s2.length();
}
//If we get out of the loop because the last character is not part of a pair (ie i=s1.length() && j==s2.length())
String str1=s1.substring(i-1);
String str2=s2.substring(j-1);
if(!mp.containsKey(str1)||!mp.containsKey(str2))
{
throw new Exception("invalid character");
}
return(mp.get(str1).intValue()-mp.get(str2).intValue());
}``````

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

``````package main

import (
"fmt"
"sort"
)

type withDigraph []string

func (v withDigraph) Len() int {
return len(v)
}

func (v withDigraph) Less(i, j int) bool {
return compare(v[i], v[j])
}

func (v withDigraph) Swap(i, j int) {
v[i], v[j] = v[j], v[i]
}

var digraphs map[string]int = map[string]int{
"ch": 256,
"cz": 257,
}

func main() {
strings := []string{
"cheese", "cracker", "casserole",
}
sort.Sort(withDigraph(strings))
fmt.Println(strings)
}

func compare(a, b string) bool {
if len(a) == 0 && len(b) == 0 {
return true
}
if len(b) == 0 {
return false
}
i, j, wa, wb := 0, 0, 0, 0
for wa == wb && i < len(a) && j < len(b) {
if w, ok := isDigraph(a[i:]); ok {
wa += w
i += 2
} else {
wa += int(a[i])
i++
}
if w, ok := isDigraph(b[j:]); ok {
wb += w
j += 2
} else {
j += int(b[j])
j++
}
}
return wa <= wb
}

func isDigraph(s string) (int, bool) {
if len(s) < 2 {
return 0, false
}
if w, ok := digraphs[s[:2]]; ok {
return w, true
}
return 0, false
}``````

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

In this case, does "Question" equals "Pregunta"... and "Text" equals "Texto", based of above algorithms?

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

``````map<string, size_t> order = { { "a", 0 },{ "b", 1 },{ "c", 2 },{ "ch", 3 },{ "cz", 4 },{ "d", 5 },{ "e", 6 },{ "f", 7 },{ "g", 8 },{ "h", 9 },{ "i", 10 },{ "j", 11 },{ "k", 12 },{ "l", 13 },{ "m", 14 },{ "n", 15 },{ "o", 16 },{ "p", 17 },{ "q", 18 },{ "r", 18 },{ "s", 19 },{ "t", 20 },{ "u", 21 },{ "v", 22 },{ "w", 23 },{ "x", 24 },{ "y", 24 },{ "z", 25 } };

bool LexicographicSort(string s1, string s2)
{
size_t i, j;
map<string, size_t>::iterator s1It = order.end(), s2It = order.end();
std::transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
std::transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
for (i = 0, j = 0; i < s1.size(), j < s2.size(); ) {
if (i < s1.size() - 1) {
s1It = order.find(s1.substr(i, 2));
if (s1It != order.end())
i += 2;
}
if (s1It == order.end())
s1It = order.find(s1.substr(i++, 1));
if (j < s2.size() - 1) {
s2It = order.find(s2.substr(j, 2));
if (s2It != order.end())
j += 2;
}
if (s2It == order.end())
s2It = order.find(s2.substr(j++, 1));
if (s1It->second == s2It->second) {
s1It = order.end();
s2It = order.end();
} else
return s1It->second < s2It->second;
}
return (s1.size() - i) < (s2.size() - j);
}
vector<string> strings;
strings.push_back("abcczch");
strings.push_back("abcchcz");
strings.push_back("abcde");
strings.push_back("ABCCZCH");
strings.push_back("ABCCHCZ");
strings.push_back("ABCDE");
sort(strings.begin(), strings.end(), LexicographicSort);
assert(strings[0] == "abcchcz");
assert(strings[1] == "ABCCHCZ");
assert(strings[2] == "abcczch");
assert(strings[3] == "ABCCZCH");
assert(strings[4] == "abcde");
assert(strings[5] == "ABCDE");``````

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

A solution to use Trie to take the character table and a hash map to take its value has been implemented here: cpluspluslearning-petert.blogspot.co.uk/2016/05/compare-exotic-string.html.

Test

``````void TestExoticStringComparator()
{
{
// non-exotic testing
const std::vector<ExoticChar> charTable = {
{ "a", 'a' },
{ "b", 'b' },
{ "c", 'c' },
{ "d", 'd' },
{ "e", 'e' },
{ "f", 'f' },
{ "g", 'g' },
{ "h", 'h' },
{ "i", 'i' },
{ "j", 'j' },
{ "k", 'k' },
{ "l", 'l' },
{ "m", 'm' },
{ "n", 'n' },
{ "o", 'o' },
{ "p", 'p' },
{ "q", 'q' },
{ "r", 'r' },
{ "s", 's' },
{ "t", 't' },
{ "u", 'u' },
{ "v", 'v' },
{ "w", 'w' },
{ "x", 'x' },
{ "y", 'y' },
{ "z", 'z' } };

ExoticStringComparator esc(charTable);
assert(esc.CompareExoticString("lkasdfajsd", "lkasdfajsd") == 0);
assert(esc.CompareExoticString("lkasdfajsd", "lkasdfahsd") > 0);
assert(esc.CompareExoticString("lkasdfajsd", "lkasdfaxsd") < 0);
assert(esc.CompareExoticString("lkasdfajsdz", "lkasdfajsd") > 0);
assert(esc.CompareExoticString("lkasdfajsd", "lkasdfajsdz") < 0);

}

{
// exotic testing
const std::vector<ExoticChar> charTable = {
{ "a", 'a' },
{ "b", 'b' },
{ "c", 'c' },
{ "d", 'd' },
{ "e", 'e' },
{ "f", 'f' },
{ "g", 'g' },
{ "h", 'h' },
{ "i", 'i' },
{ "j", 'j' },
{ "k", 'k' },
{ "l", 'l' },
{ "m", 'm' },
{ "n", 'n' },
{ "o", 'o' },
{ "p", 'p' },
{ "q", 'q' },
{ "r", 'r' },
{ "s", 's' },
{ "t", 't' },
{ "u", 'u' },
{ "v", 'v' },
{ "w", 'w' },
{ "x", 'x' },
{ "y", 'y' },
{ "z", 'z' },
{ "ae", 'z' + 1 },
{ "oe", 'z' + 2 },
{ "ue", 'a' - 1 },
{ "sch", 'a' - 2 }, };

ExoticStringComparator esc(charTable);
assert(esc.CompareExoticString("ae", "oe") < 0);
assert(esc.CompareExoticString("ae", "ue") > 0);
assert(esc.CompareExoticString("oe", "sch") > 0);
assert(esc.CompareExoticString("oe", "ue") > 0);
assert(esc.CompareExoticString("lkasdfaesd", "lkasdfajsdz") > 0);
assert(esc.CompareExoticString("lkasdfschaesd", "lkasdfaajsdz") < 0);
assert(esc.CompareExoticString("lkasdfschaesd", "lkasdfschoesd") < 0);

}
}``````

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

I think that it works.

{
{
{

package test;

public static void main(String[] args) {

String stringOne = "mercurio", stringTwo = "merced";

boolean change =lexicography (stringOne, stringTwo);

if (change){

String aux = stringOne;
stringOne = new String( stringTwo);
stringTwo = new String( aux);
//System.out.println("stringOne "+stringOne);
}

//System.out.println(stringOne);
//System.out.println(stringTwo);
}

public static boolean lexicography (String stringOne, String stringTwo){

boolean change = false;
boolean wasDigraph = false;

int iterations=0;

int length = stringOne.length()> stringTwo.length() ? stringOne.length() : stringTwo.length();

while (iterations>length || !change){

if (wasDigraph){

wasDigraph = false;

}else{
char charStrOne = stringOne.charAt(iterations);
char charStrTwo = stringTwo.charAt(iterations);

if (charStrOne+1>length){
wasDigraph = true;
}

if (charStrTwo < charStrOne){

change = true;

}
}

iterations ++;

}

return change;

}

}

}
}
}

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

can somebody explain to me this :- cpluspluslearning-petert.blogspot.com/2016/05/compare-exotic-string.html

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.