Current content:


Main
Jessica's Pics
Friends
Resume
Open Source
GLAT

Google Labs Aptitude Test (GLAT)

Google put out a test of mind benders and mathematics questions in an effort to recruit for their new Google Labs and also screen applicants. I found got a copy of it from inside a 'Linux Journal' magazine.

Here is the test:
Page 1
Page 2
Page 3
Page 4

I did a few of the problems for fun. Here are my answers and how I got them.

Problem 1:

Solve this cryptic equation realizing of course that the values for M and E could be interchanged. No leading zeros are allowed.
WWWDOT - GOOGLE = DOTCOM

Answer to Problem 1:
W == 7
D == 5
O == 8
T == 9
G == 1
L == 0
((E == 6) AND (M == 3)) OR ((E == 3) AND (M == 6))

Justification for Answer to Problem 1:

I assumed at first that each letter represented a variable. I assumed that each variable was a number 0 through 9, and that their positions represented the positions of digits in normal base 10 counting.

At first when I looked at the problem I thought that it meant that the value for M was equal to the value for E. After setting up a series of algebra equations to solve for the variables, it became apparent that this would produce no results. I then switched to base 8 and set up the same equations. Again, no results.

I then wrote a program to show me all the values in a given base number system that satisfied the results even if some letters had the same value. I was going to let E and M be the same variable, but then decided to let them be separate even if processing took 10 times as long. I saved a little time by not letting W or G be zero. Because this problem was a riddle I decided to brute force it rather than make assumptions to try to speed it up. I was running on a dual Xeon system with 4 gigs of RAM and I was going to lunch so I didn't care.

This was the code:
prob1.pl 

#!/usr/bin/perl

my $W;
my $D;
my $O;
my $T;
my $G;
my $L;
my $E;
my $C;
my $M;

my $GOOGLE;
my $WWWDOT;
my $DOTCOM;

my $count = 0;
my $base = 10;


for ($W = 1; $W < $base; $W++) {
for ($D = 1; $D < $base; $D++) {
for ($O = 0; $O < $base; $O++) {
for ($T = 0; $T < $base; $T++) {
for ($G = 1; $G < $base; $G++) {
for ($L = 0; $L < $base; $L++) {
for ($E = 0; $E < $base; $E++) {
for ($C = 0; $C < $base; $C++) {
for ($M = 0; $M < $base; $M++) {

#$count++;
#print "$count\n";

$GOOGLE = "$G$O$O$G$L$E";
$WWWDOT = "$W$W$W$D$O$T";
$DOTCOM = "$D$O$T$C$O$M";

if($GOOGLE + $DOTCOM == $WWWDOT) {
  print "$GOOGLE + $DOTCOM == $WWWDOT\n";
  print "W = $W\t";
  print "D = $D\t";
  print "O = $O\t";
  print "T = $T\t";
  print "G = $G\t";
  print "L = $L\t";
  print "E = $E\t";
  print "C = $C\t";
  print "M = $M\n";
}

}
}
}
}
}
}
}
}
}

I ran the code and got this output: prob1.out.base10

This was a large pool of potential answers. I then wrote a program to cut the answers down based on how many unique digits were represented by the various variables.

This was the code:
show_unique.pl
To run it I ran: "cat prob1.out.base10 | ./show_unique.pl" 

#!/usr/bin/perl


my $digits;

while(<>)
  {
    $digits = 0;
    if (/0/) { $digits++; }
    if (/1/) { $digits++; }
    if (/2/) { $digits++; }
    if (/3/) { $digits++; }
    if (/4/) { $digits++; }
    if (/5/) { $digits++; }
    if (/6/) { $digits++; }
    if (/7/) { $digits++; }
    if (/8/) { $digits++; }
    if (/9/) { $digits++; }

    if($digits > 8) {
      print $_;
    }

  }

I ran the script hoping for a single answer to pop out. What I got were two. It became clear what the trick to the problem was once I saw what the GLAT meant by "interchangable."

Here was the output:
show_unique_output 

188103 + 589486 == 777589
W = 7	D = 5	O = 8	T = 9	G = 1	L = 0	E = 3	C = 4	M = 6
188106 + 589483 == 777589
W = 7	D = 5	O = 8	T = 9	G = 1	L = 0	E = 6	C = 4	M = 3

Problem 17:

Consider a function which, for a given whole number n, returns the number ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

Answer to Problem 17:
199981

Justification for Answer to Problem 17:

This was easy in the sense that at least there was no riddle. All I had to do was write a program to churn out the answer. I again wrote in perl, because it was quick and easy and because I didn't want to have to worry about the size of the number. C would be a bunch faster, but I didn't want to have to worry about integers larger than 32 bits. I'm not using Perl's Math::BigInt, but I could have if I had needed to. The only other question is if this function had an answer at all. If it didn't, I would have had to come up with a proof to show that. If my code had run for a few days without an answer I would have had to face that possibility. Luckily it didn't.

This was the code:
prob17.pl 

#!/usr/bin/perl;

my $onecount = 0;
my $i = 0;
my $j;
my $jlen;
my $ilen;
my $findnum = 2;
my $findcount = 0;
while(true)
{
	$i++;
	$j = $i;
	$ilen = length($i);
	$j =~ s/1//g;	
	$jlen = length($j);

	$onecount += $ilen - $jlen;

	print "$i\t\t$jlen\t\t$onecount\n";
	if($i == $onecount) {
		$findcount++;
		if($findcount == $findnum){
			exit;
		}
	}
}