Google Interview Question
Software Engineer in TestsCountry: United States
To check whether a work is left-hand-only or right-hand-only, we can probably use just boolean variables. Just use this -
if the first letter is left-hand-only, check whether the rest is left-hand-only
else otherwise.
To check a work is left-hand-only, just go over each letter and quit once you find something right-hand.
The above problem might run in integer overflow.
What is meant by largest? Does position of letters matter("as" has same values as "sa"? If the problem statement consider them different, this algo won't work.
If largest simply goes by number of letters you are correct.
It sounds smart but this approach has several problems as horizon and alex mentioned, actually the solution by horizon is a better one, why do we need to compute (check) to the end of the string while we know the condition is violated already and we also suffer the chance to overflow.
what about overflow?
why not just keep true if all matched and then keep track of so far max/min length.
near to perfect ! but 1 thing - 5 & 2 share many common multiples - 10, 20, 30. any word with that count will be false in both conditions
I realized I forgot to comment my code, so I am resubmitting it with comments now.
Tell me what you think!
public class OneHandWords {
// Strings containing all of the left and right characters
// of a qwerty keyboard including space
public static String left = "qwerasdfzxcvtgb ";
public static String right = "uiopjklmnhy ";
/****************************************************/
/**** Given a list of strings, ********/
/**** these methods find the largest ********/
/**** and smallest words in a list that can ********/
/**** be typed with one hand. ********/
/****************************************************/
public static String largestLeft(String[] words) {
String ret = "";
for (String s : words) {
if (isLeft(s.toLowerCase()) && s.length() > ret.length()) {
ret = s;
}
}
return ret;
}
public static String smallestLeft(String[] words) {
String ret = "";
for (String s : words) {
if (isLeft(s.toLowerCase())) {
if (ret.length() > s.length())
ret = s;
else if (ret.equals(""))
ret = s;
}
}
return ret;
}
public static String largestRight(String[] words) {
String ret = "";
for (String s : words) {
if (isRight(s.toLowerCase()) && s.length() > ret.length()) {
ret = s;
}
}
return ret;
}
public static String smallestRight(String[] words) {
String ret = "";
for (String s : words) {
if (isRight(s.toLowerCase())) {
if (ret.length() > s.length())
ret = s;
else if (ret.equals(""))
ret = s;
}
}
return ret;
}
public static String largestOneHandWord(String[] words) {
String right = largestRight(words);
String left = largestLeft(words);
if (right.length() >= left.length())
return right;
else
return left;
}
public static String smallestOneHandWord(String[] words) {
String right = smallestRight(words);
String left = smallestLeft(words);
if (left.length() < right.length())
return left;
else
return right;
}
// Recursive call that determines if a string is on the left
// hand side of a keyboard
private static boolean isLeft(String s) {
boolean isGood = left.contains(s.subSequence(0, 1));
if (s.length() < 2 && isGood) {
return true;
}
else if (isGood) {
return isLeft(s.substring(1));
}
else
return false;
}
// Recursive call that determines if a string is on the right
// hand side of a keyboard
private static boolean isRight(String s) {
boolean isGood = right.contains(s.subSequence(0, 1));
if (s.length() < 2 && isGood) {
return true;
}
else if (isGood) {
return isRight(s.substring(1));
}
else
return false;
}
}
Really good solution but would it not be better to first check if the string you are comparing to your (smallest or biggest) sting is smaller or bigger before going into the recursive function?
Bad phrasing ok so what I mean is... both your smallest/largest left/right you should first see if the string is larger or smaller than your current largest or smallest string. This could save time and resources by not entering the recursive isRight/isLeft function. If the string isn't larger or smaller, throw it out and move to the next.
I was also thinking that instead of writing two functions for each hand, you could add a parameter detailing which hand you would like to compare then you only have to write one function for each. You could specify which hand in the LargestOneHandWord() function. This could save you actual physical time and make the solution a bit shorter.
public class OneHandWords {
public static String left = "qwerasdfzxcvtgb ";
public static String right = "uiopjklmnhy ";
public static String largestLeft(String[] words) {
String ret = "";
for (String s : words) {
if (isLeft(s.toLowerCase()) && s.length() > ret.length()) {
ret = s;
}
}
return ret;
}
public static String smallestLeft(String[] words) {
String ret = "";
for (String s : words) {
if (isLeft(s.toLowerCase())) {
if (ret.length() > s.length())
ret = s;
else if (ret.equals(""))
ret = s;
}
}
return ret;
}
public static String largestRight(String[] words) {
String ret = "";
for (String s : words) {
if (isRight(s.toLowerCase()) && s.length() > ret.length()) {
ret = s;
}
}
return ret;
}
public static String smallestRight(String[] words) {
String ret = "";
for (String s : words) {
if (isRight(s.toLowerCase())) {
if (ret.length() > s.length())
ret = s;
else if (ret.equals(""))
ret = s;
}
}
return ret;
}
public static String largestOneHandWord(String[] words) {
String right = largestRight(words);
String left = largestLeft(words);
if (right.length() >= left.length())
return right;
else
return left;
}
public static String smallestOneHandWord(String[] words) {
String right = smallestRight(words);
String left = smallestLeft(words);
if (left.length() < right.length())
return left;
else
return right;
}
private static boolean isLeft(String s) {
boolean isGood = left.contains(s.subSequence(0, 1));
if (s.length() < 2 && isGood) {
return true;
}
else if (isGood) {
return isLeft(s.substring(1));
}
else
return false;
}
private static boolean isRight(String s) {
boolean isGood = right.contains(s.subSequence(0, 1));
if (s.length() < 2 && isGood) {
return true;
}
else if (isGood) {
return isRight(s.substring(1));
}
else
return false;
}
}
Simple comparisons seem work to me. Does the following solution miss any key points?
To find the largest right-hand-word:
1. max = the first right-hand-word; // initialization
2. For each word{
3. if the word is a right-hand-word{
4. max = word > max? word : max;
5. }
6. }
7. Output max;
The comparison in 4 is defined, since the order of words must be given in the question (by the interviewer).
public static void wrodProcessor(String [] words) {
int weight[] = {2,2,5,5,................};
String lmax = "";
String lmin = "";
Stirng rmax = "";
String rmin = "";
int lMaxVal = Integer.MAX_VALUE;
int rMaxVal = Integer.MAX_VALUE;
int lMinVal = Integer.MIN_VALUE;
int rMinVal = Integer.MIN_VALUE;
int i;
int n = words.length;
for(i = 0; i< n; i++) {
String word = words[i];
int j;
int n1 = word.length();
int w = 1;
for (j = 0; j < n1; j++) {
char ch = word.charAt(j);
w = w * weight[ ch - 'a'];
}
if(w % 2 == 0 && w % 5 != 0) {
if(lMinVal > w ) {
lMinVal = w;
lmin = word;
}
if( lMaxVal < w ) {
lMaxVal = w;
lmax = word;
}
} else if(w % 2 != 0 && w % 5 == 0) {
if(rMinVal > w ) {
rMinVal = w;
rmin = word;
}
if( rMaxVal < w ) {
rMaxVal = w;
rmax = word;
}
}
}
System.out.println(lmin + " " + lmax + " " + rmin + " " + rmax);
}
I believe instead of doing multiplication. We can maintain an integer byte. Lets say one for left hand words and other for right hand words. Which is one time process.
Now for each character in each word, it is possible to find whether it is left hand word or right hand. ( bit flipping)
And yes it good idea to check if word length is greater than or less than current maximum and minimum. But my point in that in this case either we must know length of each word before hand or we ourselves need to determine. And if we ourselves determine that it will be bad since we are traversing the whole word.
1. left_array = [a,s,d,f...]
2. right_array = [j,k,l...]
3. weight_array = [ 1 for i in string.alphabet else -1 ]
4. cumm_val = weight_array[c] + weight_array[a] + weigh_array[t] = which is -3 == len('cat')
5. for right hand, we use positive number, and sum by weight
6. iterate and keep the highest sum, and lowest sum, along with the words.
In the most voted answers you have to compute hash of each word (by that time you could already tell that the word is left/right) or there is quite complicated algorithm
My proposal is just to do this:
a) prepare set of left letter and right letters
a2) prepare String max, String min
b) scan every word
b1) for every single letter, prepare/initialize boolean isLeft =true; isRight=true;
b2) if the letter is from right, set isLeft=false, the same for the left
b3) after scanning the whole word, if isLeft || isRight is true, then check if it's length is bigger than max or smaller than min and in such case, set it there.
After getting through all of the words,you are done.
1)For all characters in the left hand set add weight = 2.
- king August 09, 20132) For all characters in the right hand set add weight = 5.
lefthand set is "qwerasdfzxcvtgb "
righthand set is "uiopjklmnhy "
weight[] = {2 or 5 for all of 26 chars};
Foreach word w in dictionary:
1) computer cummulative weight as :
cum_weight = product of weight of all chars in the word.
Eg: cum_weight(cat) = weight[c]*weight[a]*weight[t] = 2*2*2 = 8
2) If (cum_weight % 2 ==0) and (cum_weight %5 !=0)
the word consists of ONLY LEFT HAND set chars.
If (cum_weight %5 ==0) and (cum_weight %2 != 0)
the word consists of ONLY RIGHT HAND set chars.
3) Now u can use max variable to keep track of longest word. Longest word is essentially maximum value in each category.