crossrefme

Tuesday, July 03, 2007

Facebook quiz solution

A couple of months ago I stumbled upon this puzzle on the facebook jobs page. I thought I might take a crack at it, based on my interpretation of the problem. If anyone has a better solution please leave me a comment. I call it the "Brute Force LCM method."

Using the example given I figured out which key belongs to which.

key['a'] = 'l'; key['b'] = 'c'; key['c'] = 'z';
key['d'] = 'f'; key['e'] = 't'; key['f'] = 'm';
key['g'] = 'i'; key['h'] = 'w'; key['i'] = 'o';
key['j'] = 'k'; key['k'] = 'd'; key['l'] = 'g';
key['m'] = 'j'; key['n'] = 'n'; key['o'] = 'a';
key['p'] = 's'; key['q'] = 'e'; key['r'] = 'b';
key['s'] = 'u'; key['t'] = 'h'; key['u'] = 'v';
key['v'] = 'y'; key['w'] = 'q'; key['x'] = 'r';
key['y'] = 'p'; key['z'] = 'x';

Notice that with the exception of 'n' it takes 5 step to get from a character back to its original. i.e a to l, l to g, g to i, i to o, o to a. So every character has a 5 step shortest path except for n which has a path of 1 step. So if you have a string made of any of these characters you'll take 5 steps to
return back to the original string. If however, you have a string made up of n's the you'll
have only have 1 step to get back. If your string has a mixture of characters and an 'n'
then it still takes 5 steps.

Jodt Dabn
Kafh Flcn
Dlmw Mgzn
Fgjq Jixn
Mike Korn

That is, although to n loops once, the other characters loops 5 times so the n has to loop 5 times to catch up with the other characters. If n had a path of
2 instead then it would have had to loop 10 times for all the characters to catch up. If you do
this manually you'll see this. If you notice, 10 is the Lowest Common Multiple(LCM) of 5 and 2. So going back to our example, the LCM of 5 and 1 is 5. Therefore, given and string, the maximum number of loops it goes through before getting back to it's original state is the LCM of all the cycles which is 5.

So the algorithm is as follows,

We find the shortest path each character takes to get back to it's original character.
(Hence the term Brute Force)

//iterate through each letter and cycle through them until we get back to the orig character.
//we count the lenght of the cycle
for (var j=0; j<size; j++){
var current = nme.charAt(j);
var start = current;
var next = key[current];

while (next != start &&amp;amp;amp;amp;amp; current !== null){
current = key[current];
next = key[current];
count++;
}
a = lcm(count,a); //the LCM of all the cycles is the answer
count = 1;
}
return a;

We then find the LCM of all the paths using Euclid's algorithm.

function lcm(a,b){
return a * b / gcd(a,b);
}

function gcd(a,b){
if (b==0)
return a;
else
return gcd(b, a%b);
}

I have attached full code listing below;

<html>
<head></head>
<body>
<script language = 'JavaScript'>
<!--
//@author: AL SAM
//@date: 21 June 2006
//@description: Possible solution to the facebook Korn Shell puzzle using "Brute Force LCM method"
//  http://www.facebook.com/jobs_puzzles/?puzzle_id=7

var key= new Array();
key['a'] = 'l';
key['b'] = 'c';
key['c'] = 'z';
key['d'] = 'f';
key['e'] = 't';
key['f'] = 'm';
key['g'] = 'i';
key['h'] = 'w';
key['i'] = 'o';
key['j'] = 'k';
key['k'] = 'd';
key['l'] = 'g';
key['m'] = 'j';
key['n'] = 'n';
key['o'] = 'a';
key['p'] = 's';//
key['q'] = 'e';
key['r'] = 'b';
key['s'] = 'u';//
key['t'] = 'h';
key['u'] = 'v';//
key['v'] = 'y';//
key['w'] = 'q';
key['x'] = 'r';
key['y'] = 'p';//
key['z'] = 'x';


function korn(fname, lname){
var fn = fname.toLowerCase();
var ln = lname.toLowerCase();
var nme = fn + ln;
var size = nme.length;
var count = 1;
var a = 1;

//iterate through each letter and cycle through them until we get back to the orig character.
//we count the lenght of the cycle
for (var j=0; j> 2;
document.write(ans2 + "
");
//-->
</script>

<form name="korn_form">
<input type="text" id="fname" value="firstname"/> <input type="text" id="lname" value="lastname"/> <input type="button" value="go" onclick="suger();"/>
</form>
<div id="ans"/>

<script language = 'JavaScript'>
<!--
function suger(){
var fn = document.getElementById('fname').value;
var ln = document.getElementById('lname').value;
var ans = korn(fn,ln);
document.getElementById('ans').innerHTML = " ans = " + ans;
}
//-->
</script>
</body>
</html>

Friday, June 01, 2007

I love the NYTimes.com design

Designing the website for a major news organization is not the easiest thing to do but it seems that Khoi Vinh, Design Director for the NYTimes.com, has pulled it off. I love reading the New York Times newspaper/print because it's so well laid out and they've got great pictures. Vinh has managed to translate this onto the website as well. The typography is very readable, the content is well laid out, the pictures still look great and you can feel the New York Times brand all over the site. Technorati lists them as the most authoritative media site on the internet -- so I guess that they're doing something right. Major kudos to Khoi Vinh.

Tuesday, April 17, 2007

Facebook IPO?

All indications are that Zuckerberg is taking Facebook all the way to Wall Street. I'd love to see a Facebook IPO.
froosh is hedging his bets that Facebook will file for an IPO in 08. He also mentions that Facebook has essentially priced itself out of the Mergers and Aquisitions market by leaving $1 billion on the table during their Yahoo negotiations.

Facebook clearly sees itself as/wants to be a Google. They want to be refered to as a tech companany as oppossed to a media
company. This all point to the fact that Zucs might make the company a publicly traded company just like Google.

"The companywide focus is on innovation and engineering, and the commitment to optimizing the user experience. The goal is
not to create a media company." - Mark Zuckerberg http://www.fastcompany.com/magazine/115/open_features-hacker-dropout-ceo_3.html

They're posting wierd programming puzzles on their web site in an effort to attract "smart" employees, much akin to Google.

Finally, their financial backers would love for them to go all the way.

"Certainly most of our companies go through liquidity in the public markets ...Public markets seem to want to pay more than
acquirers these days."- Meritech founder, Paul Madera. http://www.fastcompany.com/magazine/115/open_features-hacker-dropout-ceo_3.html

Bofore they file for an IPO howerver, they need to find an experienced CEO (unless Zucks is crazy enough to do it himself), and make over $100M in revenue, just like Google.

A successful Facebook IPO might just herald a new era of Internet startup IPOs.

Monday, February 20, 2006

crossrefme is now live!

crossrefme is now live! It's still in Alpha so your comments will be greatly appreciated. Check it out at http://www.crossrefme.net

Saturday, February 11, 2006

Announcing crossrefme!

We are currently creating a FREE service that determines the originality of documents. This service scours the millions of pages on the internet to determine if the contents of user submitted documents have already been published on the internet. This service could be used to ;

determine whether a given text has been correctly referenced
determine how original a given text is.
determine if someone has used your text without properly attributing it to you. etc

crossrefme is still in the prototype stage. I should begin rolling out a Beta version very soon.