Google Interview Question for Software Engineer in Tests


Country: United States




Comment hidden because of low score. Click to expand.
14
of 16 vote

1)For all characters in the left hand set add weight = 2.
2) 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.

- king August 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A really smart solution..

- Anon August 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

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.

- horizon August 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- algo_guy August 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Will it be possible to save a long right sided word? it'll be out of the range of int..

- alex August 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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.

- LinhHA05 August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about overflow?
why not just keep true if all matched and then keep track of so far max/min length.

- pankaj September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kalyan2s2 November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why to compute the hash in case you need to access every letter to count it's hash and by that time you already can distinguish if this word is left/right. I will write my solution proposal

- mbriskar May 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
	}
}

- Elliott Mantock August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jordan Smith August 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
	
	
}

- Elliott Mantock August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- liuguohua.friend August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Anand October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- abhish December 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Peerakit Somsuk May 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- mbriskar May 09, 2015 | 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