Google Interview Question Software Developers
Country: United States
Interview Type: In-Person
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));
}
}
}
//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());
}
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",
"crumpet", "croissant", "cookie",
}
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
}
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");
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);
}
}
I think that it works.
{
{
{
package test;
public class GoogleLexicography {
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;
}
}
}
}
}
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?
- EPavlova April 07, 2016