Googol

GCJ 2011 - Magicka

noreply@blogger.com (Babji Prashanth, Chetty) — Sun, 08 May 2011 22:17:00 +0000

Below is the description of a problem called 'Magicka', from 'Google Code Jam - 2011':

Problem
-------
Introduction

Magicka™ is an action-adventure game developed by Arrowhead Game Studios. In Magicka you play a wizard, invoking and combining elements to create Magicks. This problem has a similar idea, but it does not assume that you have played Magicka.

Note: "invoke" means "call on." For this problem, it is a technical term and you don't need to know its normal English meaning.

Problem

As a wizard, you can invoke eight elements, which are the "base" elements. Each base element is a single character from {Q, W, E, R, A, S, D, F}. When you invoke an element, it gets appended to your element list. For example: if you invoke W and then invoke A, (we'll call that "invoking WA" for short) then your element list will be [W, A].

We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters). For example, Q and F might combine to form T. If the two elements from a pair appear at the end of the element list, then both elements of the pair will be immediately removed, and they will be replaced by the element they form. In the example above, if the element list looks like [A, Q, F] or [A, F, Q] at any point, it will become [A, T].

We will specify pairs of base elements that are opposed to each other. After you invoke an element, if it isn't immediately combined to form another element, and it is opposed to something in your element list, then your whole element list will be cleared.

For example, suppose Q and F combine to make T. R and F are opposed to each other. Then invoking the following things (in order, from left to right) will have the following results:

QF → [T] (Q and F combine to form T)
QEF → [Q, E, F] (Q and F can't combine because they were never at the end of the element list together)
RFE → [E] (F and R are opposed, so the list is cleared; then E is invoked)
REF → [] (F and R are opposed, so the list is cleared)
RQF → [R, T] (QF combine to make T, so the list is not cleared)
RFQ → [Q] (F and R are opposed, so the list is cleared)
Given a list of elements to invoke, what will be in the element list when you're done?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line, containing the following space-separated elements in order:

First an integer C, followed by C strings, each containing three characters: two base elements followed by a non-base element. This indicates that the two base elements combine to form the non-base element. Next will come an integer D, followed by D strings, each containing two characters: two base elements that are opposed to each other. Finally there will be an integer N, followed by a single string containing N characters: the series of base elements you are to invoke. You will invoke them in the order they appear in the string (leftmost character first, and so on), one at a time.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a list in the format "[e0, e1, ...]" where ei is the ith element of the final element list. Please see the sample output for examples.

Limits

1 ≤ T ≤ 100.
Each pair of base elements may only appear together in one combination, though they may appear in a combination and also be opposed to each other.
No base element may be opposed to itself.
Unlike in the computer game Magicka, there is no limit to the length of the element list.

Small dataset
-------------
0 ≤ C ≤ 1.
0 ≤ D ≤ 1.
1 ≤ N ≤ 10.

Large dataset
-------------
0 ≤ C ≤ 36.
0 ≤ D ≤ 28.
1 ≤ N ≤ 100.

Sample Input
------------
5
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QW

Output
------
Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []

This problem can be easily coded, if you can use some efficient data structures to look up, which elements when invoked merge and which elements oppose each other. The problem requirements should also be carefully read and implemented, for example: "After you invoke an element, if it isn't IMMEDIATELY combined to form another element, and it is opposed to something in your element list, then your whole element list will be cleared."

First off, when parsing the input, I'm using Java's HashMap data structures to build a convenient data structure to look up, which elements oppose and which elements combine to form an other element. The code to build these data structures, is as below:

String[] splitString = line.split(" ");
int index = 0;
int num1 = Integer.parseInt(splitString[index]);
HashMap<String, String> mergeMap = new HashMap<String, String>();
          
for(int i=0;i<num1;i++) {
  index++;
  String str = splitString[index];
  String sub1 = str.substring(0,2);
  String sub2 = str.substring(2);

  mergeMap.put(sub1, sub2);
  mergeMap.put(sub1.charAt(1) + "" + sub1.charAt(0), sub2);
}
          
index++;
int num2 = Integer.parseInt(splitString[index]);
HashMap<String, ArrayList<String>> opposingMap = new HashMap<String, ArrayList<String>>();
          
for(int i=0;i<num2;i++) {
  index++;
  String str = splitString[index];
  String sub1 = "" + str.charAt(0);
  String sub2 = "" + str.charAt(1);
            
  if(opposingMap.containsKey(sub1)) {
     opposingMap.get(sub1).add(sub2);
  } else {
     ArrayList<String> keyList = new ArrayList<String>();
     keyList.add(sub2);

     opposingMap.put(sub1, keyList);
  }

  if(opposingMap.containsKey(sub2)) {
     opposingMap.get(sub2).add(sub1);
  } else {
     ArrayList<String> keyList = new ArrayList<String>();
     keyList.add(sub1);

     opposingMap.put(sub2, keyList);
  }
}

index++;
int invokeStringLength = Integer.parseInt(splitString[index]); 
          
index++;
String invokeString = splitString[index];

And...with the above input, I'm using the below code, for solving the problem:

import java.util.*;
import java.io.*;

public class Magicka {
 public String castAspell(HashMap<String, String> mergeMap, HashMap<String, ArrayList<String>> opposingMap, String invokeString,         int invokeStringLength) {
  StringBuilder sbOutput = new StringBuilder("" + invokeString.charAt(0));

  for(int i=1;i<invokeStringLength;i++) {
   int len = sbOutput.length();
   if(len > 0) {
    int pos = sbOutput.length() - 1;
    String str1 = "" + sbOutput.charAt(pos);
    String str2 = "" + invokeString.charAt(i);

    if(mergeMap.containsKey(str1+str2) || mergeMap.containsKey(str2+str1)) {     
     sbOutput.deleteCharAt(pos);
     sbOutput.append(mergeMap.get(str1+str2));
     continue;
    } else {
     String tempStr = sbOutput.toString();
     Iterator iter = opposingMap.entrySet().iterator();
     boolean flag = false;

     while (iter.hasNext()) {
      Map.Entry pair = (Map.Entry) iter.next();
      String key = (String) pair.getKey();
      ArrayList<String> keyList = (ArrayList<String>) pair.getValue();
      
      if(tempStr.indexOf(key) >= 0) {
       for(String value: keyList) {
        if(str2.indexOf(value) >= 0) {
         sbOutput.delete(0, len);
         flag = true;
        }
       }
      }

      if(flag) {
       break;
      }
     }
     
     if(!flag) {
      sbOutput.append(", " + invokeString.charAt(i));
     }
    }
   } else {
    sbOutput.append(invokeString.charAt(i));
   }
  }

  return "[" + sbOutput.toString() + "]";
 }
}

GCJ 2011 - Bot Trust

noreply@blogger.com (Babji Prashanth, Chetty) — Sun, 08 May 2011 21:46:00 +0000

Below is the description of a problem called 'Bot Trust', from 'Google Code Jam - 2011':

Problem
-------

Blue and Orange are friendly robots. An evil computer mastermind has locked them up in separate hallways to test them, and then possibly give them cake.

Each hallway contains 100 buttons labeled with the positive integers {1, 2, ..., 100}. Button k is always k meters from the start of the hallway, and the robots both begin at button 1. Over the period of one second, a robot can walk one meter in either direction, or it can press the button at its position once, or it can stay at its position and not press the button. To complete the test, the robots need to push a certain sequence of buttons in a certain order. Both robots know the full sequence in advance. How fast can they complete it?

For example, let's consider the following button sequence:

O 2, B 1, B 2, O 4

Here, O 2 means button 2 in Orange's hallway, B 1 means button 1 in Blue's hallway, and so on. The robots can push this sequence of buttons in 6 seconds using the strategy shown below:

Time | Orange | Blue
-----+------------------+-----------------
1 | Move to button 2 | Stay at button 1
2 | Push button 2 | Stay at button 1
3 | Move to button 3 | Push button 1
4 | Move to button 4 | Move to button 2
5 | Stay at button 4 | Push button 2
6 | Push button 4 | Stay at button 2
Note that Blue has to wait until Orange has completely finished pushing O 2 before it can start pushing B 1.
Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case consists of a single line beginning with a positive integer N, representing the number of buttons that need to be pressed. This is followed by N terms of the form "Ri Pi" where Ri is a robot color (always 'O' or 'B'), and Pi is a button position.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of seconds required for the robots to push the given buttons, in order.

Limits

1 ≤ Pi ≤ 100 for all i.

Small dataset

1 ≤ T ≤ 20.
1 ≤ N ≤ 10.

Large dataset

1 ≤ T ≤ 100.
1 ≤ N ≤ 100.

Sample Input
------------
3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1

Output
------
Case #1: 6
Case #2: 100
Case #3: 4

The solution to the problem can be easily coded, after understanding the fact that the robot (which was not scheduled to press the switch) can freely move to it's destination (next switch), so as to make the time required to solve the problem, as minimal as possible. Both the robots start at 1. So, for example, if one robot has to press the switch at 10 (first move), it takes 9 seconds (10 - 1) to move and 1 to press the switch...So, it takes a total of 10 seconds...In these 10 seconds, the other robot can move as long as possible and stay-put there, waiting for its turn. I used Java datastructures 'Queue' and 'Deque' to solve the problem. Below is my solution:

import java.util.*;
import java.io.*;

public class BotTrust {
 private int findMin(String inputLine) {
  int index = 0;
  String[] splitString = inputLine.split(" ");
  int n = Integer.parseInt(splitString[index++]);
  Queue<String> orderQueue = new LinkedList<String>();
  Deque<Integer> orangeQueue =  new ArrayDeque<Integer>();
  Deque<Integer> blueQueue = new ArrayDeque<Integer>();

  for(int i=0;i<n;i++) {
   String robot = splitString[index++];
   orderQueue.add(robot);

   if(robot.equals("O")) {
    orangeQueue.add(Integer.parseInt(splitString[index++]));
   } else {
    blueQueue.add(Integer.parseInt(splitString[index++]));
   }      
  }

  int res = 0;
  int orangePos = 1;
  int bluePos = 1;
  
  while(true) {
   if(orderQueue.isEmpty()) {
    break;
   }
   String robot = (String) orderQueue.remove();   
   
   if(robot.equals("O")) {
    int orangeSwitch = (Integer) orangeQueue.removeFirst();
    int orangeTimeRequired = Math.abs(orangeSwitch - orangePos) + 1;
    res += orangeTimeRequired;
    orangePos = orangeSwitch;    
    
    if(!blueQueue.isEmpty()) {
     int blueSwitch = blueQueue.removeFirst();
     blueQueue.addFirst(blueSwitch);
     int blueTimeRequired = Math.abs(blueSwitch - bluePos);
     if(blueTimeRequired >= orangeTimeRequired) {
      bluePos = (blueSwitch > bluePos) ? (bluePos + orangeTimeRequired) : (bluePos - orangeTimeRequired);
     } else {
      bluePos = blueSwitch;
     }
    }    
   } else {
    int blueSwitch = (Integer) blueQueue.removeFirst();
    int blueTimeRequired = Math.abs(blueSwitch - bluePos) + 1;
    res += blueTimeRequired;
    bluePos = blueSwitch;
    
    if(!orangeQueue.isEmpty()) {
     int orangeSwitch = orangeQueue.removeFirst();
     orangeQueue.addFirst(orangeSwitch);
     int orangeTimeRequired = Math.abs(orangeSwitch - orangePos);
     if(orangeTimeRequired >= blueTimeRequired) {
      orangePos = (orangeSwitch > orangePos) ? (orangePos + blueTimeRequired) : (orangePos - blueTimeRequired);
     } else {
      orangePos = orangeSwitch;
     }
    }    
   }
  }

  return res;
 }
}

GCJ 2010 - Fair Warning

noreply@blogger.com (Babji Prashanth, Chetty) — Mon, 10 May 2010 23:52:00 +0000

Below is the description of a problem called 'Fair Warning', from 'Google Code Jam - 2010':

Problem
-------
On our planet, Jamcode IX, three Great Events occurred. They happened 26000, 11000 and 6000 slarboseconds ago. In 4000 slarboseconds, the amount of time since all of those events will be multiples of 5000 slarboseconds, the largest possible amount... and the apocalypse will come.

Luckily for you, you live on Jamcode X! The apocalypse came on Jamcode IX less than a year ago. But Jamcode X has a worrying prophecy: "After the moment of reckoning, on the first optimum anniversary of the N Great Events, the apocalypse will come. 64 bits will not save you. You have been warned."

The people of Jamcode X are very concerned by this prophecy. All of the Great Events have already happened, and their times have been measured to the nearest slarbosecond; but nobody knows when their optimum anniversary will occur. After studying the diary of a scientist from Jamcode IX, scientists working on the problem have come up with a theory:

The moment of reckoning is now, the moment you solve this problem. At some time y ≥ 0 slarboseconds from now, the number of slarboseconds since each of the Great Events will be divisible by some maximum number T. If you can find the smallest value of y that gives this largest possible T, that will give you the optimum anniversary when the apocalypse will come.

On Jamcode IX, for example, there were 3 Great Events and they happened 26000, 11000 and 6000 slarboseconds before the moment of reckoning. 4000 slarboseconds later, the amount of time since each event was a multiple of T=5000 slarboseconds, and the apocalypse came.

Your job is to compute the amount of time until the apocalypse comes. But remember the prophecy: even though the people of Jamcode X have been solving problems for two years, and 64-bit integers have always been enough, they might not always be enough now or in the future.

Input
-----
The first line of the input gives the number of test cases, C. C lines follow. Each starts with a single integer N, which is followed by a space and then N space-separated integers ti, the number of slarboseconds since Great Event i occurred.

Output
------
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of slarboseconds until ti + y is a multiple of the largest possible integer factor T for all i.

Limits
------
1 ≤ C ≤ 100.
ti ≠ tj for some i, j.

Small dataset
-------------
2 ≤ N ≤ 3.
1 ≤ ti ≤ 108.

Large dataset
-------------
2 ≤ N ≤ 1000.
1 ≤ ti ≤ 1050.

Sample Input
------------
3
3 26000000 11000000 6000000
3 1 10 11
2 800000000000000000001 900000000000000000001

Output
------
Case #1: 4000000
Case #2: 0
Case #3: 99999999999999999999

Below is my java solution:

import java.util.*;
import java.math.BigInteger;

public class FairWarning {
public BigInteger nextApocalypseParty(int n, ArrayList<biginteger> numberList) {
Collections.sort(numberList);
BigInteger smallest = numberList.get(0);
BigInteger gcdBigInt = new BigInteger("0");  

for(int i=1;i<n;i++) { 
   gcdBigInt = gcdBigInt.gcd(numberList.get(i).subtract(numberList.get(i-1)));
   if(gcdBigInt.equals(BigInteger.ONE)) return BigInteger.ZERO;
  }

  return ((((smallest.add(gcdBigInt)).subtract(BigInteger.ONE)).divide(gcdBigInt)).multiply(gcdBigInt)).subtract(smallest);
 }
}

GCJ 2010 - Snapper Chain

noreply@blogger.com (Babji Prashanth, Chetty) — Sun, 09 May 2010 16:28:00 +0000

Below is the description of a problem called 'Snapper Chain', from the 'Google Code Jam - 2010':

Problem

The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.

When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers -- making a clicking sound -- any Snapper receiving power at the time of the snap toggles between the ON and OFF states.

In hopes of destroying the universe by means of a singularity, I have purchased N Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper.

Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.

I keep doing this for hours. Will the light be on or off after I have snapped my fingers K times? The light is on if and only if it's receiving power from the Snapper it's plugged into.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each one contains two integers, N and K.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "ON" or "OFF", indicating the state of the light bulb.

Limits

1 ≤ T ≤ 10,000.

Small dataset

1 ≤ N ≤ 10;
0 ≤ K ≤ 100;

Large dataset

1 ≤ N ≤ 30;
0 ≤ K ≤ 108;

Sample Input
------------
4
1 0
1 1
4 0
4 47

Sample Output
-------------
Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON

The description of the problem might be a bit confusing, but if you spend some time and clearly understand about what it really wants, then its really easy to code the solution for that. In my case, I wrote it down on paper and looked at the pattern of the snappers, for different values of n (number of snapper devices)....After looking at the different patterns, it was easy for me to figure out that the number of minimum snaps required to power the end device is equal to "(2 power n) - 1". Ok, this is just the minimum number of snaps! After the minimum number of snaps, it takes 1 snap to totally power off all the snappers...and it again takes "minimum number of snaps', to power the end device. So, after the 'minimum number of snaps', it takes (2 power n) to power the end device. Below is the solution, that I coded in Java:

public class Snapper {
 private String findDeviceStatus(double numOfSnappers, double numOfSnaps) {
  if(numOfSnaps == 0) return "OFF";
  double minRequiredSnaps = Math.pow(2, numOfSnappers) - 1;
  if(numOfSnaps < minRequiredSnaps) return "OFF";

  return (minRequiredSnaps == numOfSnaps || ((numOfSnaps % (minRequiredSnaps + 1)) == minRequiredSnaps)) ? "ON" : "OFF";
 }
}

The solution for this problem can be coded in different ways...In the 'Content Analysis' section of Code Jam site, there is another interesting solution of using XOR operation of bits.

Odd Man Out - GCJ 2010 (Africa)

noreply@blogger.com (Babji Prashanth, Chetty) — Sat, 10 Apr 2010 21:21:00 +0000

Below is the problem statement of 'Odd Man Out' problem, from 'Google Code Jam 2010 (Africa)':

Problem
-------
You are hosting a party with G guests and notice that there is an odd number of guests! When planning the party you deliberately invited only couples and gave each couple a unique number C on their invitation. You would like to single out whoever came alone by asking all of the guests for their invitation numbers.

Input
-----
The first line of input gives the number of cases, N.
N test cases follow. For each test case there will be:

One line containing the value G the number of guests.
One line containing a space-separated list of G integers. Each integer C indicates the invitation code of a guest.

Output
------
For each test case, output one line containing "Case #x: " followed by the number C of the guest who is alone.

Limits
------
1 ≤ N ≤ 50
0 < C ≤ 2147483647 Small dataset ------------- 3 ≤ G < 100 Large dataset ------------- 3 ≤ G < 1000 Sample Input ------------ 3 3 1 2147483647 2147483647 5 3 4 7 4 3 5 2 10 2 10 5 Output ------ Case #1: 1 Case #2: 7 Case #3: 5

Below is the solution coded by me in Java:

import java.util.*;
import java.io.*;

public class OddManOut {
public String getTheOddOneOut(String lineWithNumbers, int numberCount) {
String[] numberArr = lineWithNumbers.split("[ ]");
Arrays.sort(numberArr);
ArrayList<string> list1 = new ArrayList<string>();

for(int index=0;index<numberCount;index++) {
   String strNumber = numberArr[index];
      
   if((index%2) == 0 && index != (numberCount - 1)) {    
    list1.add(strNumber);
   } else if(!list1.contains(strNumber)) {    
    if(index == (numberCount - 1) || !strNumber.equals(numberArr[index + 1])) {
     return strNumber;
    } else {
     return list1.get(list1.size() - 1);
    }    
   }
  }

  return null;
 }
}

Store Credit - GCJ 2010 (Africa)

noreply@blogger.com (Babji Prashanth, Chetty) — Thu, 25 Mar 2010 20:37:00 +0000

Below is the 'Store Credit' problem statement from the qualification round of Google Code Jam 2010 - Africa:

Problem
-------
You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

Input
-----
The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:

One line containing the value C, the amount of credit you have at the store.
One line containing the value I, the number of items in the store.
One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
Each test case will have exactly one solution.

Output
------
For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.

Limits
------
5 ≤ C ≤ 1000
1 ≤ P ≤ 1000

Small dataset
-------------
N = 10
3 ≤ I ≤ 100

Large dataset
-------------
N = 50
3 ≤ I ≤ 2000

Sample Input
------------
3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3

Output
------
Case #1: 2 3
Case #2: 1 4
Case #3: 4 5

This is one of the easiest problems, I've ever seen in a programming competition. Below is the solution in Java:

public class StoreCredit { 
public String buyTwo(int price, int numOfItems, int[] itemPrices) { 
for(int i=0;i<numOfItems;i++) {
for(int j=0;j<numOfItems;j++) {
if(i != j) { 
if(itemPrices[i] + itemPrices[j] == price) { 
return ((i + 1) + " " + (j + 1)); 
} 
} 
} 
} 

return ""; 
} 
}

T9Spelling - GCJ 2010 (Africa)

noreply@blogger.com (Babji Prashanth, Chetty) — Tue, 23 Mar 2010 19:48:00 +0000

Below is a problem from the qualification round of 'Google Code Jam 2010 - Africa':

T9Spelling

Problem
-------
The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ' ' should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.

Input
-----
The first line of input gives the number of cases, N. N test cases follow. Each case is a line of text formatted as:

desired_message

Each message will consist of only lowercase characters a-z and space characters ' '. Pressing zero emits a space.

Output
------
For each test case, output one line containing "Case #x: " followed by the message translated into the sequence of keypresses.

Limits
------
1 ≤ N ≤ 100.

Small dataset
-------------
1 ≤ length of message in characters ≤ 15.

Large dataset
-------------
1 ≤ length of message in characters ≤ 1000.

Sample Input
------------
4
hi
yes
foo bar
hello world

Output
------
Case #1: 44 444
Case #2: 999337777
Case #3: 333666 6660 022 2777
Case #4: 4433555 555666096667775553

There's also a pictorial representation of the problem statement, which I didn't attach to this post. If you want, you can check the link: GCJ 2010 - T9Spelling

The solution for the above problem is pretty easy. Below is my Java solution:

import java.util.*; 
import java.io.*; 

public class T9Spelling {  
public String translate(String phrase) { 
HashMap alphaMap = getKeypadDictionary(); 

StringBuilder sbTranslatedMessage = new StringBuilder(); 
for(int i=0;i<phrase.length();i++) {
if(i != 0) { 
String str1 = alphaMap.get("" + phrase.charAt(i-1)); 
String str2 = alphaMap.get("" + phrase.charAt(i)); 

sbTranslatedMessage.append((str1.charAt(0) == str2.charAt(0)) ? " " + alphaMap.get("" + phrase.charAt(i)) : 
alphaMap.get("" + phrase.charAt(i))); 
} else { 
sbTranslatedMessage.append(alphaMap.get("" + phrase.charAt(i))); 
} 
} 

return sbTranslatedMessage.toString(); 
} 

private HashMap getKeypadDictionary() { 
HashMap<String, String> alphaMap = new HashMap<String, String>(); 

alphaMap.put(" ", "0"); 

alphaMap.put("a", "2"); 
alphaMap.put("b", "22"); 
alphaMap.put("c", "222"); 
alphaMap.put("d", "3"); 
alphaMap.put("e", "33"); 
alphaMap.put("f", "333"); 
alphaMap.put("g", "4"); 
alphaMap.put("h", "44"); 
alphaMap.put("i", "444"); 
alphaMap.put("j", "5"); 
alphaMap.put("k", "55"); 
alphaMap.put("l", "555"); 
alphaMap.put("m", "6"); 
alphaMap.put("n", "66"); 
alphaMap.put("o", "666"); 
alphaMap.put("p", "7"); 
alphaMap.put("q", "77"); 
alphaMap.put("r", "777"); 
alphaMap.put("s", "7777"); 
alphaMap.put("t", "8"); 
alphaMap.put("u", "88"); 
alphaMap.put("v", "888"); 
alphaMap.put("w", "9"); 
alphaMap.put("x", "99"); 
alphaMap.put("y", "999"); 
alphaMap.put("z", "9999"); 

return alphaMap; 
} 
}

The solution for the above problem can be coded in a couple of other creative ways, but the above solution is fast and works good enough, although it has a trade-off in memory complexity (in the form of HashMap).

Reverse Words - GCJ 2010 (Africa)

noreply@blogger.com (Babji Prashanth, Chetty) — Tue, 23 Mar 2010 19:23:00 +0000

Below is a problem statement from the 'Google African Code Jam' (which is happening, at the moment):

Reverse Words

Problem
-------
Given a list of space separated words, reverse the order of the words. Each line of text contains L letters and W words. A line will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words.

Input
-----
The first line of input gives the number of cases, N.
N test cases follow. For each test case there will a line of letters and space characters indicating a list of space separated words. Spaces will not appear at the start or end of a line.

Output
------
For each test case, output one line containing "Case #x: " followed by the list of words in reverse order.

Limits
------
Small dataset
-------------
N = 5
1 ≤ L ≤ 25

Large dataset
-------------
N = 100
1 ≤ L ≤ 1000

Sample Input
------------
3
this is a test
foobar
all your base

Output
------
Case #1: test a is this
Case #2: foobar
Case #3: base your all

The solution for the above problem is pretty easy. Below is my solution:

import java.util.*;
import java.io.*;

public class ReverseWords {
public String reverseWords(String phrase) {
List<string> wordList = Arrays.asList(phrase.split("[ ]"));
Collections.reverse(wordList);

StringBuilder sbReverseString = new StringBuilder();
for(String word: wordList) {
sbReverseString.append(word + " ");
}

return sbReverseString.substring(0, sbReverseString.length() - 1);
}
}

All Your Base - GCJ 2009

noreply@blogger.com (Babji Prashanth, Chetty) — Sun, 13 Sep 2009 14:36:00 +0000

First off, Welcome...and AYBABTU...I mean "All Your Base Are Belong To Us" :)

And now...lets get serious:

The problem listed below, is from the 'Round 1C' of Google Code Jam - 2009:

Problem

In A.D. 2100, aliens came to Earth. They wrote a message in a cryptic language, and next to it they wrote a series of symbols. We've come to the conclusion that the symbols indicate a number: the number of seconds before war begins!

Unfortunately we have no idea what each symbol means. We've decided that each symbol indicates one digit, but we aren't sure what each digit means or what base the aliens are using. For example, if they wrote "ab2ac999", they could have meant "31536000" in base 10 -- exactly one year -- or they could have meant "12314555" in base 6 -- 398951 seconds, or about four and a half days. We are sure of three things: the number is positive; like us, the aliens will never start a number with a zero; and they aren't using unary (base 1).

Your job is to determine the minimum possible number of seconds before war begins.

Input

The first line of input contains a single integer, T. T test cases follow. Each test case is a string on a line by itself. The line will contain only characters in the 'a' to 'z' and '0' to '9' ranges (with no spaces and no punctuation), representing the message the aliens left us. The test cases are independent, and can be in different bases with the symbols meaning different things.

Output

For each test case, output a line in the following format:

Case #X: V
Where X is the case number (starting from 1) and V is the minimum number of seconds before war begins.

Limits

1 ≤ T ≤ 100
The answer will never exceed 1018
Small dataset

1 ≤ the length of each line < 10 Large dataset 1 ≤ the length of each line < 61 Sample Input ------------ 3 11001001 cats zig Output ------- Case #1: 201 Case #2: 75 Case #3: 11

Coding the solution for the above problem, might sound easy, but its more trickier than what you first think. That is probably because you might understand it differently, than what the problem really wants.

The above problem statement, requires the output to be the minimum possible number. The first step is to understand that the number would be smaller if you take the smallest possible 'Base System' for the number. To find the base system that you want, you would have to find the number of unique symbols in the input string. If there are 2 'Unique' symbols in the string, take it as 'Base 2' system. If there are 10 unique symbols, take it as 'Base 10 (Decimal)' system.....and so on. Since the 'Unary System' is not used, ignore that.

After that, we need to find how we can make the sum, as minimal as possible. Since we don't know which digit stands for what, we have to make a decision for each symbol, so as to make the number, as small as possible. Since the left most digit carries more weight, this digit should be multiplied by the smallest digit. But since the left-most digit can't be zero (0), make it '1'. Use the Zero (0) for the second left-most digit (if there is 2nd digit in the number). Then use '2' for the third left most digit (if it is unique), '3' for the 4th left most digit (if it is unique)..and so on, unitl the end of the string with symbols. Here's the solution, that I coded in Java:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.math.BigInteger;
import java.io.*;

public class AllYourBase {  
public BigInteger convert(String str) {
BigInteger res = new BigInteger("0");

int base = 0;
int len = str.length();

HashMap<String, Integer> hm = new HashMap<String, Integer>();

int index = 1;

for(int i=0;i<len;i++) {
if(!hm.containsKey("" + str.charAt(i))) {
if(i != 0) {
if(index == 1) {
index--;
} else if (index == 0) {
index = 2;
} else {
index++;
}
}        

hm.put("" + str.charAt(i), new Integer(index));
base++;
}
}

if(hm.size() == 1) base = 2;

System.out.println("base : " + base + " Len : " + len);

for(int i=0;i<len;i++) {
String s = str.charAt(i) + "";

res = res.add(new BigInteger("" + hm.get(s)).multiply(
new BigInteger("" + base).pow(len-i-1)));
}

return res;
}  
}

Interesting 'Google Suggestions'

noreply@blogger.com (Babji Prashanth, Chetty) — Sun, 13 Sep 2009 14:00:00 +0000

Here are some interesting 'Google Suggestions' that you find, when you type some specific phrases : (It also shows the best of stereotypes that people have, in reality) :P

From Google Suggestions

It's somehow funny, as well as serious at the same time, to see what people have on their minds. :P You can probably find many more interesting things like this, when you type some special phrases, on Google search box.

Alien Language - GCJ 2009

noreply@blogger.com (Babji Prashanth, Chetty) — Fri, 04 Sep 2009 01:26:00 +0000

...Just finished the qualification round of 'Google Code Jam - 2009', passed through and just thought of posting this simple solution to the first problem, called 'Alien Language'. Here's the problem description:

Problem

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output

For each test case, output

Case #X: K
where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits

Small dataset

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10
Large dataset

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500
Sample Input
------------
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Output
------

Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

The solution to this problem is pretty simple, if you could figure it out, that its tailor-made for regular expressions. I used Java. So, I could create a solution, with just a couple of code statements. Here's the solution:

import java.util.ArrayList;
import java.io.*;

public class AlienLanguage {
public int checkPattern(ArrayList wordsAL, String pattern) {
int res = 0;

for(int i=0;i<wordsAL.size();i++) {
if(((String) wordsAL.get(i)).matches(
pattern.replaceAll("[(]","[").replaceAll("[)]","]"))) res++;
}

return res;
}
}

Google Code Jam 2008 - Minimum Scalar Product

noreply@blogger.com (Babji Prashanth, Chetty) — Sat, 15 Aug 2009 00:36:00 +0000

Recently, I was just trying to solve some problems from GCJ - 2008 and started off with a problem, which looked pretty easy. This problem is from the 'Round 1 A' and is called 'Minimum Scalar Product'. The problem statement is as below:

Problem

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Input

The first line of the input file contains integer number T - the number of test cases. For each test case, the first line contains integer number n. The next two lines contain n integers each, giving the coordinates of v1 and v2 respectively.
Output

For each test case, output a line

Case #X: Y
where X is the test case number, starting from 1, and Y is the minimum scalar product of all permutations of the two given vectors.
Limits

Small dataset

T = 1000
1 ≤ n ≤ 8
-1000 ≤ xi, yi ≤ 1000

Large dataset

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

Sample Input
------------
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Output
------
Case #1: -25
Case #2: 6

The solution for the above problem is pretty easy, as all that you gotta do, is to multiply the largest/smallest element from X-Array to smallest/largest element in Y-Array. If you are using Java, it is probable that your solution might pass through, for small input file, but not for the large one. This is because the data in the larger input file, might cause an overflow of the 'int' value. So, care should be taken to use 'BigInteger' or 'BigDecimal', instead of primitive 'int'. Here's the bare bones Java code, for that problem:

public BigInteger findMin(String strXArr, String strYArr) {
String[] xArr = strXArr.split(" ");
String[] yArr = strYArr.split(" ");

BigInteger res = new BigInteger("0");

int len = xArr.length;    

int[] iXArr = new int[len];
int[] iYArr = new int[len];

for(int i=0;i<len;i++) {
iXArr[i] = Integer.parseInt(xArr[i]);
iYArr[i] = Integer.parseInt(yArr[i]);
}

Arrays.sort(iXArr);
Arrays.sort(iYArr);

for(int i=0;i<len;i++) {                  
res = res.add((new BigInteger("" + iXArr[i])).multiply(new BigInteger("" + iYArr[len-1-i])));      
}

return res;
}

After reading the input from the file, I pass the X-Array (v1) and Y-Array (v2), to the above method, get the result and write back to the output file. Thats it! :-)

Open Source Jam - Google Zurich

noreply@blogger.com (Babji Prashanth, Chetty) — Sun, 12 Oct 2008 00:12:00 +0000

Last Thursday (Oct 2), I happened to be there at Google office in Zurich, Switzerland for the 'Zurich Open Source Jam' event, for just a couple of hours and also got to see the office, which is said to be one of the best places to work (with all the work done and the facilities/benefits provided). Its also said to be the Google's biggest R&D centre, outside US of A.

I spent a couple of hours there, listening to the presentations given by a couple of other developers from Zurich and its surroundings. I haven't been to many events like that before and so, I planned on this event and also thought of spending the weekend, looking around Zurich and some other places in Switzerland and Liechenstein (although it was my third entry into Switzerland).

I started working early in the morning, on Thursday (Oct 2) and took off from work in the afternoon (Friday was a holiday, as it was German Re-Unification Day) and set off to Zurich, by the German ICE train. After reachin' Zurich, I went directly to the Google office, with my huge backpack. After checkin' in and signin' an NDA, I was there for a couple or hours, listening to the presentations given by a couple of developers. It was ok, nothing interesting. I just thought that it would be a nice experience and will get to know what other guys are tryin' to do and get to know the perspective and come up with my own ideas (if any) and try to do something. I'm more interested in the math, algorithms, Java, AJAX, js, scripting languages or any other creative stuff.

Most of the guys who attended were pretty young. Some are studying at ETH Univ, Zurich and some are working. After the event, I got to see the Google Zurich Office and the extra things offered there. Michael Haselmann (Zoogler - who works there) guided us through all this stuff. He's a pleasant guy, with a smile always. Good to see relaxed people like that (specially, in the German world) ;-). Apart from this, I also saw the display screen, at the reception, which shows all the 'Google Search Queries' that are fired by different people across the world. If you happen to be there, you can probably see some funny/weird/naive queries on the screen.

Taking pics inside the office is prohibited, but there are numerous sources on the internet, from where you can check how the 'Zurich Google Office' looks like. Here's one of those links:

Google Office - Zurich

If you wanna check the rest of my trip, follow the link below:

Journal Of A Nomad

Google Developer Day 2008 - Munich (Germany)

noreply@blogger.com (Babji Prashanth, Chetty) — Fri, 26 Sep 2008 20:04:00 +0000

Last month, I was searching for something on the internet and stumbled upon this news that Google is organising its 'Developer Day' event at Munich (Germany)/Munchen (Deutschland). Since I haven't attended many events like that and was interested in Google's tech stuff, I filled up the form on Google's site and got an e-invite from Google folks at Munich. Also, I thought I could meet up with a couple of famous or well-known Googler's and discuss things, personally (although I aint bigtime and just a face in the IT-Crowd) on varied topics like Java frameworks, MapReduce/Apache Hadoop, Cloud Computing and the hype around it, AJAX stuff and new Java frameworks like Richfaces, JBoss Seam, Dependency Injection (which is implemented by many, but not understood by all), et al.

The event was scheduled on Tuesday, Sep 23 2008 and the agenda/sessions for that day was known well-ahead and so, I flicked through the Google pages and went through a couple of technologies like 'Google App Engine', 'OpenSocial', 'Geo', 'Visualization API', 'GData', 'Google Web Toolkit (GWT)', 'Guice', et al. I ran a couple of examples and got an idea about how these technologies are useful and what is the strategy behind this, for Google to release those API's.

I planned my trip so that I could also spend some time in Munich and visit 'Oktoberfest', which is well-known all over the world, for being the biggest folk festival, in the world. Indeed, many people consider this 'Oktoberfest', as a binge-drinkin' event, rather than a normal folk festival, with people dressed up in colourful Lederhosen and Dirndl's (typical Bavarian dress'). Also, it offers a couple of other amusement-park stuff like the 'Free-Fall', et al. So, I went on Monday afternoon by the German ICE train (which sped to a max of 301 km/h and took me to Munich in just 1 hour, from Nuremberg/Nurnberg) and spent sometime lookin' around 'Oktoberfest' (not for binge-drinking. I'd no company, anyways. ;-)) and also checked the location of Google's event, the next day. Here's a post from my other blog, about 'Oktoberfest':

Oktoberfest 2008 - Munich, Germany

The next day, I was there in time for the Google's 'Developer Day' event and attended the keynote by Markus Muhlbauer (Google Munich's Engineering Director) and Chris DiBona (Open Source Manager for Google, who previously worked as a editor for 'Slashdot', hosted 'FLOSS weekly' event and also co-founded 'Damage Studios'). Chris DiBona has good presentation skills, which is mixed up with a bit of humour and other facts. Here are some pics:

From Google Developer Day 2008 - Munich

After the keynote, I spoke a bit to Chris DiBona and immediately rushed up to the next session (App Engine Code Labs). Since I ran those examples already, I didn't spend much time there. So, I went to the other code lab for 'Google Geo' and spent sometime there, just to get an idea . I also spoke to 2 French employees of Google. One Googler said that he's from South France and I'd a good conversation with him, talking about my 'Monte Carlo and French Riviera trip'. Indeed, I was excited to talk about that, as I like that part of France (which has good weather, sophisticated to laid-back and relaxing places, many things to do, et al).

Later, I met 'Markus Muhlbauer' at Google Lounge and talked to him, a bit about Google Munich's R&D centre, its location and what they exactly do over there. I gotta know that Google Munich's office is located at Marienplatz, Munich (which is the centre and one of the best parts of Munich) and at the moment, there are just a couple of employees working there and that the office aint so big and that they are planning to expand. Here are some pics:

From Google Developer Day 2008 - Munich

After the lunch break, I also attended 'Google Web Kit' (presented by 'Sumit Chandel') and 'Google Gears' (by 'Dion Almaer'). I was particularly interested in 'GWT' as it relates to Java stuff and also explored a bit of it, already. All the presentations were pretty basic (or 'Just Right') as they have to target all the audience. If you have gone through the Google documentation regarding these technologies, attending this event is not a big deal, but the whole experience and meeting bigtime folks, gives you a perspective (if you are a budding and ambitious developer/user). Anyways, its a freebie and if you attend that, you get more presents as freebies. So, its definitely worth it. ;-) Here's a pic from the 'Google Web Kit' session:

From Google Developer Day 2008 - Munich

I also spent some time listening to 'Ian Fette',who was presenting 'Google Chrome' stuff. There was a nice Q&A session, at the end of this presentation and got to know a couple of things.

At the end of the day, there was a 'Wrap-up' session, in which 'Chris DiBona' presented some cool things on the mobile and talked a bit about 'Android'. After that, I wanted to talk to 'Peter Chanezon' about 'Cloud Computing' and other technologies, but didn't happen, as he was busy. Apart from that, I was particularly interested in talking to 'Dion Almaer', as I know him pretty well through his 'Ajaxian.com' site/blog. I couldn't speak to him at length, but had a small talk and called it a day and headed back home. Here are some more pics:

From Google Developer Day 2008 - Munich

If you need more info regarding the sessions, check the below link (which has youtube videos from those sessions on that day):

Google Developer Day 2008 - Munich

Google Hacking And Other Interesting Search Stuff

noreply@blogger.com (Babji Prashanth, Chetty) — Tue, 26 Aug 2008 20:18:00 +0000

Apart from 'plain search' stuff, Google is versatile, does good math and offers other good services like weather info, stock market quotes, et al. If you had tried the new experimental version (beta) of the 'Google Search', you would probably know that they are trying to come up with more creative/useful search stuff. Here are some of the interesting Google queries:

What Time Is It In Vanuatu?

28 C in F

1 Euro = ? $

2.728 euros per liter in dollars per gallon

987654321 to binary

1 Nautical Mile

UPS, Fedex or USPS Package Tracking

Speed Of Light In Kilometres Per Hour

Munich Weather

How Many Leagues In A Furlong?

There are many queries like this. Apart from this, some guys use Google for the sole purpose of hacking into systems or assessing security of their sites. Not many people really saw Google from this perspective (hacking), until some of the hackers did. If my memory serves right, I heard from someone (or read somewhere) that 'Google' was the kind of thing that some security/spying organisations were looking for, 10/20 years back.

There are several search queries, which any end-user can use to find a security hole on some site, which aint secured in the right way (And ofcourse, that site is already indexed by Google). Its surprising to see some of the search results and it shows that there are still many vulnerable sites in our virtual world. Mr. Johnny Long maintains a 'Google Hacking Database', which has hundreds of queries to assess the security of a system. And there are couple of 'Google Hacking' books published based on this stuff. After all this stuff, I dont mean to say that Google is helping crackers to break into systems. It just shows the 'Power Of A Good Search Technology'. Also, Google directly doesn't help you to break into systems. If you have some knowledge about hacking concepts, then you could couple that with effective Google-search and if you are probably lucky, you can find some defect (Ex: You can probably figure out how to access a restricted htpasswd/htaccess file or a file with passwords and from that, you figure out how to access the server or things like that). Here are some queries:

filetype:pdf inurl:secret

filetype:pdf inurl:confidential

If you go through Mr. Johnny's 'Google Hacking Database', you can find many search queries like this. Also, one of the well-known hacking cult groups, called 'cultdeadcow' released a security scanner for websites based on this 'Google Hacking Database', called 'Goolag Scanner'. This is a pretty simple GUI application, which just stores the 'Google Hacking Queries' in a XML file (dorks.xml) and performs test by firing a search query (from its XML database) for a particular site. For more info on 'Goolag Scanner' and other 'Google Hacking' stuff, check my other (security) blog: White Hat Stuff

GCJ 2008 - Alien Numbers

noreply@blogger.com (Babji Prashanth, Chetty) — Wed, 16 Jul 2008 18:22:00 +0000

'Alien Numbers' problem statement:

Problem

The decimal numeral system is composed of ten digits, which we represent as "0123456789" (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as "oF8", then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that's written in one alien system into a second alien system.

Input

The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as

alien_number source_language target_language

Each language will be represented by a list of its digits, ordered from lowest to highest value. No digit will be repeated in any representation, all digits in the alien number will be present in the source language, and the first digit of the alien number will not be the lowest valued digit of the source language (in other words, the alien numbers have no leading zeroes). Each digit will either be a number 0-9, an uppercase or lowercase letter, or one of the following symbols !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

Output

For each test case, output one line containing "Case #x: " followed by the alien number translated from the source language to the target language.

Limits

1 ≤ N ≤ 100.

Small dataset

1 ≤ num digits in alien_number ≤ 4,
2 ≤ num digits in source_language ≤ 16,
2 ≤ num digits in target_language ≤ 16.

Large dataset

1 ≤ alien_number (in decimal) ≤ 1000000000,
2 ≤ num digits in source_language ≤ 94,
2 ≤ num digits in target_language ≤ 94.

Sample:

Input	Output
`4 9 0123456789 oF8 Foo oF8 0123456789 13 0123456789abcdef 01 CODE O!CDE? A?JM!.`	`Case #1: Foo Case #2: 9 Case #3: 10011 Case #4: JAM!`

There are a couple of ways you can code a solution for this, but if you know (or did some research on) number systems, you can figure out the easiest solution.

My Solution:
Since the 'decimal system' is the easiest that we humans and the programming languages (Higher-Level Languages) can comprehend, I converted the 'Alien Number' (using 'Source Language' input) into a decimal number and then divided that number with the 'base of the 'Target Language' number system) . The remainder is found and if its not zero, the division has to be done repeatedly on the quotient of the previous division until the remainder is '0' and collect all the 'remainders'. Form a number from the remainders, in the reverse order....and....VOILA!

Example: (Converting '19' (decimal) to 'base 5')

19/5 = 3 ------> 4 (remainder)
3/5 = 0 - -----> 3 (remainder)

So, the decimal number 19 is equal to 34 in 'base 5'. Simple! :-)

Then I uploaded the output files and found the solution to be 'Correct'.

Here's the code for my solution:

public class AlienNumbers
{
public String convertFromOneNumberSystemToOther(String alienNum, 
String srcLang, String targetLang) {

int iSrcLangBaseNum = srcLang.trim().length();
int iTgtLangBaseNum = targetLang.trim().length();

int iAlienNumInDecSystem = 0;
int iAlienNumLen = alienNum.length();

for(int i=0;i<iAlienNumLen;i++) {
iAlienNumInDecSystem += srcLang.indexOf(alienNum.charAt(i)) *
Math.pow(iSrcLangBaseNum,(iAlienNumLen-1-i));
}

StringBuffer sbTgtLangNum = new StringBuffer();

int tempNum = iAlienNumInDecSystem;

while(true) {
sbTgtLangNum.append(strTgtLang.charAt(tempNum % iTgtLangBaseNum));
if((tempNum/iTgtLangBaseNum) == 0) {
break;
} else {
tempNum /= iTgtLangBaseNum;
}
}

return sbTgtLangNum.reverse().toString();
}
}

Calculating 'e' to 10000 Digits In Groovy

noreply@blogger.com (Babji Prashanth, Chetty) — Mon, 14 Jul 2008 23:50:00 +0000

Yesterday, I was reading a bit about scripting languages and started playing with 'Groovy', which is an alternative to 'Java'. You can say that it's a bit higher-level language than Java, as it is built on Java libraries (or classes) and provides one more abstraction layer. Groovy, which is a 'Dynamic Language' (dynamically typed) was built to provide a scripting language for the Java platform, along the lines of Python, Ruby and Perl. Below are some imp points:

1) The Groovy compiler can be used to generate 'Java Bytecode', which can be integrated with any other java module/project.

2) Most of the Java code is also a valid syntax for Groovy.

3) Groovy is dynamically typed, whereas Java is static and strongly typed. Dynamically typed languages have lesser code, but more execution time.

4) Groovy also provides special XML processing through the classes XmlParser, XmlSlurper, DOMCategory.

Apart from these, Groovy has features like 'Dynamic Typing', 'Closures' and 'builders'. Also, it's pretty useful for testing as it supports unit-testing and mocking out-of-the-box.

After doing a bit of reading and coding some basic scripts, I tried to code a Groovy solution for the Java code that I wrote for solving the "Google's Billboard Puzzle" (from other post in this blog). It's for calculating "Euler's Number (e)" , which is pretty basic and simple code. Here's the code:


BigDecimal e = new BigDecimal(1.0G)
BigDecimal temp = new BigDecimal(1.0G)

for(i in 1..100) {
   temp *= i
   e += new BigDecimal("1").divide(temp, new java.math.MathContext(10000))
}

println("e : " + e)
println("length of e calculated : " + (e+"").length())

English To 'Pig Latin'

noreply@blogger.com (Babji Prashanth, Chetty) — Sat, 12 Jul 2008 17:27:00 +0000

Yesterday, I was doing some research about 'Latin' and 'Roman Civilization' and as I was scouring the internet, I stumbled upon this slang (or 'Backslang') called 'Pig Latin', which is also a 'English Language Game'. Following are the rules to translate a 'English' word into 'Pig Latin':

1) For words that begin with 'consonant' sounds, move the initial consonant or consonant cluster to the end of the word and add "ay."

Ex: English: Zeitgeist ------ Pig Latin: eitgeistzay

2) For words that begin with vowel sounds (including silent consonants), simply add the syllable "ay" to the end of the word.

Ex: Englsih: Algorithm ------ Pig Latin: Algorithmway

This is the basic stuff for 'Pig Latin'. If you wanna know more about this, you can fire a Google query and do some research. Also, I'm not covering much of 'silent consonants' stuff in this post.

Ok..I thought its pretty simple and wrote a basic 'Java' program to translate an 'English phrase' into 'Pig Latin'. This is a pretty basic 'Java' program tested with just a couple of test cases. And ofcourse, there are a lot of other things to be added, in order to make it a perfect translator. I'm just posting the 'Java' code that I wrote in a couple of minutes, outta my own interest. Here's the code:

import java.util.Scanner;

public class EnglishToPigLatinTranslator {
public static void main(String[] args) {
System.out.println("Enter The English Phrase To Be " 
+ "Translated Into 'Pig Latin' : ");
Scanner scanner = new Scanner(System.in);

String strEngPhrase = scanner.nextLine();

if(strEngPhrase != null && !strEngPhrase.equals("")) {
System.out.println("\nPig Latin Text : \n" + 
convertEnglishToPigLatin(strEnglishPhrase));
} else {
System.out.println("No Input Specified!");
}
}

public static String convertEnglishToPigLatin(String strEnglishPhrase) {
String strVowels = "aeiou";
String[] strTokens = strEnglishPhrase.split("[ ]");
StringBuffer sbPigLatinStuff = new StringBuffer();

for(int i=0;i<strTokens.length;i++) {
if(strVowels.indexOf(strTokens[i].charAt(0)) >= 0) {
sbPigLatinStuff.append(strTokens[i] + "way ");
} else if((strTokens[i].indexOf("a") < 0) && 
(strTokens[i].indexOf("e") < 0) && 
(strTokens[i].indexOf("i") < 0) && 
(strTokens[i].indexOf("o") < 0) && 
(strTokens[i].indexOf("u") < 0)) {
sbPigLatinStuff.append(strTokens[i] + "ay ");          
} else {
for(int j=1;j<strTokens[i].length();j++) {
if(strVowels.indexOf(strTokens[i].charAt(j)) >= 0) {
sbPigLatinStuff.append(strTokens[i].substring(j) + 
strTokens[i].substring(0,j) + "ay ");
break;
}
}
}
}

return sbPigLatinStuff.toString();
}
}

The above code reads/takes 'English' phrase as input from the console and outputs a 'Pig Latin' phrase as output.

Example Input: She sells sea shells by the sea shore
Output: eShay ellssay easay ellsshay byay ethay easay oreshay

Also, the above code doesn't take care of special characters. If you want, you can customize that, accordingly. Here's an input phrase, which shows that:

Input: A skunk sat on a stump and thunk the stump stunk, but the stump thunk the skunk stunk.

Output: Aay unkskay atsay onway away umpstay andway unkthay ethay umpstay unk,stay utbay ethay umpstay unkthay ethay unkskay unk.stay

One more interesting thing is that, Google also offers its search in 'Pig Latin'. I used the link and searched using a set of keywords and found that this 'Pig Latin' search gives priority to 'Pig Latin' stuff only if you search in 'Pig Latin'. Otherwise, it is just the usual way of 'Googling'. I dont know if they cover all the cases, but here's the link:

Google Igpay Atinlay (Pig Latin)

Playing With Googol

noreply@blogger.com (Babji Prashanth, Chetty) — Sat, 12 Jul 2008 12:36:00 +0000

The only way, you can play around with 'Googol' in Java, is to use 'BigDecimal' or 'BigInteger', since the other primitives can't bear the weight of 'Googol'. Here's some code, which I used to test:

import java.math.*;

public class Googol {
public static void main(String[] args) {
long googol1 = (long) Math.pow(10,100);
System.out.println("Googol1 : " + googol1);
System.out.println("Max Value of Long : " + Long.MAX_VALUE);

BigDecimal googol2 = new BigDecimal(Math.pow(10,100) + "");
System.out.println("Googol2 : " + googol2);

BigDecimal bigDecimal = googol2.multiply(new BigDecimal(Math.PI + ""));
System.out.println("Googol Multiplied By PI : " + bigDecimal);
}
}

Here's the output of this program:

Googol1 : 9223372036854775807
Max Value of Long : 9223372036854775807
Googol2 : 1.0E+100
Googol Multiplied By PI : 3.1415926535897930E+100

Google Billboard Puzzle

noreply@blogger.com (Babji Prashanth, Chetty) — Sat, 12 Jul 2008 01:07:00 +0000

In July 2004, Google posed a complex mathematical question on a billboard on 'Highway 101' in the heart of silicon valley, to lure some of the mathematically talented guys (probably with special software skills too).

The billboard read:
{first 10-digit prime found in consecutive digits e}.com."

The answer, 7427466391.com, would lead to a Web page with yet another equation to solve, with still no sign of the firm that wanted to recruit some of the best math guys, out there. It wasn't known that it was Google, until the puzzle was cracked.

Here's a pic of that billbaord:

I happened to know about this puzzle much later and thought of giving it a try. My first approach was to calculate the 'Eulers Number (e)'. I didn't knew what precision (the number of digits in the decimal part) would be required for this, as no one knows where the 'first prime number' would occur. I decided to calculate 'e' to 10000 digits (decimal part) and loop through the 10 digit numbers from the beginning of the decimal part, incrementing by 1 digit in each and every loop. This is a very basic solution that I thought of, without any special/fast mechanism (or algorithms). "Euler's Number" can be calculated in a couple of ways, but I used the following formula:

With the above formula, we can calculate 'e' by looping through, finding factorial and adding up 1/Facorial(n), in each and every loop. I decided to give a try, although it was a bit naive, brute-force approach. Java was my programming language of choice, but calculating e to 10000 digits precision is a problem because you cant use the normal primitives like "double", "float" or whatever to contain the huge number of digits in the decimal part of a number. So, it was pretty obvious that I had to use 'BigDecimal'.

One more tricky part was to determine 'how many times should the program loop through , for the precision to be around 10000 digits'? I tried a couple of combinations and found that "100" would be good enough. Also it doesn't consume much time. If you try it for 10000 or more, it would probably take a couple of minutes or hours.

Ok....I looped through "100" times in the code, calculated 'e' to a bit more than 10000 digits, in the first step. The next step, I looped through the decimal part of 'e', taking 10 char substrings (starting from the decimal point) in each and every loop (and incrementing by 1 char in each and every loop) and figuring out whether its a prime or not. If its a prime, thats it..Voila..Puzzle solved! ;-)

Here's the Java code for finding the 'First 10 digit prime number in the consecutive digits of e':

import java.math.BigDecimal;
import java.math.MathContext;

public class EulersNumber {
public static void main(String[] args) {
BigDecimal e = BigDecimal.ONE;
BigDecimal bigDecimal = BigDecimal.ONE;

for(int i=1;i<100;i++) {
bigDecimal = bigDecimal.multiply(new BigDecimal(i*1.0 + ""));
e = e.add(new BigDecimal(1.0 + "").divide(bigDecimal,
new MathContext(10000)));
}

String strDecimalPart = (e + "").substring(2);

for(int i=0;i<strDecimalPart.length()-10;i++) {
long num = Long.parseLong(strDecimalPart.substring(i,i+10));
if(isPrime(num)) {
System.out.println("First 10 digit prime number in the " + 
"decimal part of e : " + num);
break;
}
}
}

public static boolean isPrime (long n) {
if (n<=1) return false;
if (n==2) return true;
if (n%2==0) return false;
long m = (long) Math.sqrt(n);

for (long i=3; i<=m; i+=2)
if (n%i==0)
return false;

return true;
} 
}

I ran this program and got the following output: b>First 10 digit prime number in the decimal part of e : 7427466391

So, thats the answer and the domain address would be 7427466391.com" (which is defunct now).

....and here's the "Euler's Number (e)" that I calculated using the above approach: 'e to 10000 digits'

PS: The above solution is a very basic, brute-force/trial-and-error approach that I used, but it very much solves the puzzle.

Euler's Number (e) to 10000 digits

noreply@blogger.com (Babji Prashanth, Chetty) — Fri, 11 Jul 2008 23:42:00 +0000

2.71828182845904523536028747135266249775724709369995957496696762772407663035354
759457138217852516642742746639193200305992181741359662904357290033429526059563
072731008532378052751063686487016953141865527484590824495504533928649764277413
664165964636632508736091584134397099983170353823380092116814655415374930542022
2461709321230949167763499311130703029256989342067643919136650384873578846610775
725576307921898867353790419412043377406494907073863079049248976437069836297366
862198429250767700214157406500293826954406871877954270969766247465243666295138
572019208303177269234097701656745392257779147341603684935723103304485761429026
633263529379734450400061311941647086898259755208734782937085387009434178080656
799728070459503917013351431243873005220184059659629058572148124084211850064775
039817941961218573369359733233622726060251817838892702513619492060782438693702
3374814484201715707221499854656151809995508987059685112005970217969141325866928
6602317310229797290687832208352244139159906185931458214703478815445166479832
5046262522680294449747348465327518061648320621808534750359139800448221992875
4115421760307308298093805920594877077289150276094679343039089600258059624590
1090903863567364545438437944570459218550946553360104699219626269410126910458
90340647723383513632617624742197059501772297495397551854979415896674068860108
7398443700914012801686726593427163552302821660247771908837094815869645205666
8815969321410949439503674072209706019571063864125657863462531390320535926139
8065461279426613181836499453900527608815525900579545890516959001648050702509
6403143330697134846164437723068270522333891693693343907700497785650966434405
2325996256928278405152469924949198823766952739854288105544527565986294752452
05693358119115333543019700716769864683030634526402994568932551341887981026382
2843693783432310455460084376713678585540041637300910512388440410273740721407
6089146349592070628050009074145432574228970773743592716838514050834569168569
4020069628069142977701272380383001974272807014909792386389979599361210460546
6132878158380106008513525733886057866008226873313592611944487920707602483719
175378078444093479419423995579464945674756628701559497832841333591914786214637
35603157123715972525235081340992882850434547504729694274009993485285212359739
17674488103383877169147599028815092782273697356447476531171632071581081270552
5598851856502807470004430053271066985202412593972634396001301781754281722806
99015701997418112250357373092905792348289915876331111795795255780918373793205
1269240357824595461131785114968639639991476102270714665227802289055681089509
0146736930196174130025404517196793385306069511899147940409256879369338070338
44117960210757341657750887635675554190855634632412343556830822523527371221710
5503387342646635300259679114329308264293528681728967169757966418436808935072
1853584011065482617985869437542874723693228725609077359083959083910914601426
14117072184462117369425231608550325954157093031897697899281462993247498822840
92401485466120845575841709241943040201506918613662787810741263281974371666516
330008170760884695890852048059030709279849861998603838516800211544530926982
11263222953723523749313973888100541833082146561100109711466796181542127994450
76235099916977658728501385580985438616207865146047255866541716806751679188638
59113108312166753578697511605452236122500023689152933590078679967211452212392
2290098658574120910961465211460661599806140981235585382519904891440442062925
925495112139384134252979654512252377847573748760543708287671195154844747383508
1601573510092133293063560544492520388015467416485377322694920822119530493637
1369428240434858154048599765296403148619908392124953147575475332405124625889
57121686955156360920651701645327408228490984014959122126619201970425151542106
73013640542646030186192840107095300278713215958912957724597357283841662968309
12210516806720757220478234957553878098197623884867165276206434004671154492769
7250480660380146624193025161061045950219756822986117002086519032370669831556
2314828872353526031083929446762905715191928824538549193915211069960080432370
33684427165463758461688160355511644363832742245956811161693438212701845186156
55761416101372838979107942215779375878684115441845526446284300286082840561456
5145085097678489064642723633070628029478321647090193520218183692763368807386
1858596938408033154128062810735163112651849784428507068524266997588412327010
9692644594407018059178367047739180941656620079419717122687690165757425276849
092593900829181546327673012278265309721072694711649587180103237308336037094
124718002747971763353021975270212394223029724655135470200873265326088010696
51682316957653741866561230702746577570979189592110672163958193180910193572622
40138979571594510928768813979234045832681877376433987660178768467826282141951
3568794428050748765941809093175009332292937037772747009321804115353182640653
1171780622593070127430035280400923998246278841349928607003107461709846780856
60256146171925487380730445091187515582011517793133710289833229203277586780250
9139516998337048606875794415220704398884922919940020129431383431469287267708
3681404480986230206993613730660473248727695273521560257818607833251900314636
1037460329769173708864378340410730989044302850521251156907880247563440669279
9182321051095812359725793718986048188974020453536240320581284657153065142529
12492042439476614866877083286718121151289143738010495191991475375329312502675
42902206790327004738901758137411520731783829875119152758426735040751711054714
1941923246974848693131873714706453440439743879138400949332358403482499509194
9842096735171845236053213985888923697150231999224724594151335488800213847246
91538470943183864703011070217387104702703139593543751554326649899326338571842
2582613915316926076702248679586655222978767959539102851890398902126342161697
9159330165276969103518713133047990903094329029249914628420541512490428251645
6746932746214616902647057490059256740212429170561779045681950630945431315218
4766472404736695193704209539728909985576721636243705276264090590830454379672
502679091492454257912086044133852067859002754311689904906392195537002710581
8216612975571073213954866373070339848665183771444369369480523976858199390808
6125130002701638160264500919161836188968056406647070513470493616674082416217
06481772590630197958443972272171843656472316231680270512046751129103103526136
5544408015102410339248492737018338624019133546654930438348313815488287286553
43791539697505176626178810067645315090761240203654377248976565316875366959861
3931146415608407893795807492175484372273231557705894548508328231662541302564
27171611575544774997441224243993883274759254403869584854298041515014362996853
2593601476977133327825679930040071754343452156177043925100909751088480877331
7082193696476465084182224449241071211734426403970652458158152697327028141431
5186959263778428980663510467346428841265110885224631075683457878504930178218
225174460500041466882994355935522278641033817469626394254500139506953702358
63111068710336036419928254963754755661181239993344592703865918454163813726481
523004938480329009196512667559683877825792199002609332773006030203819120544
7473075865273513891589520992388057333363975767184807782646421490529836209478
1696991729150079770978589433510054782303689081363960711565433419871905351687
34752631783851814430979644887878785718990707589067054658544435461194598811093
41473535982500945675748301178172162084714614189329196146949347030676397298772
332232445341105199525228932493624308607658460785332802038864362569780270279
2148665178441664055725072156401901023676418513333803139797562192289727683806
81261858779967914175349201748151716744913513256578568502951083358429780913639
5053727848617771983290354188250603562852158316159055091186345022334351945324
14452531774950581454159454767896926235849069644331189538317451035275870827121
298185800924354383038105151741805807889998458063104249533759109476263763294
9017938803529523129067651391537272995328629369956730072056740076487607846839
31338214106648455757216268590483893617111078110461552879534435611222664995665
9784035933910764838551152739021256100763830358119151783051993496819479915082
392479782967650501768646964257960281471100407585359604523309962347485350677
289284632970184431527197085081286106985690573223295367005888075920350341430
34360015717447329278150239175788794731286592663631604212679563569122828211951
0586536161249244064369095864500845511321589618532587572544297576556384231892
6441607600001517773056094180774786690888004129069593271289638606751911883864
4306238369851982856459515425563968332542495703882827336959908735218801381827
7514390458919247613316334001807369271619250148169382222374126875014028010303
3142186226903645789262051876342085012091447322173282103203638118464396858702
930558330391858010947310234962853502303569995878716757612530603333848540209
4782747364951007075237736181632922607373937890256246832186567543964696045242
7148754101498994468898956060485426243616680157799303275578481736989107749824
70738334470245233484311989072122254971558825789527474764575763565558605790976
9165036383994176295514220082474314305216853172774430602210206147858651829252
4335664928405241205101395006669723427516698744021233815406010137407923958491
342930373595709530010609740899961898712955216954476343410258194640698989420
3050328794275681342976086330639372160824427910284180259614219885424355337261
9756728839042776695026783656807516269448233053600297161311517954960480081510
103759243696856094894001139222873705396028826060269848058131712469307843008
61945457601943691625162492400802152241873307859151281377890962735078347713297
94749868587559773372475556238112674596550231901852686726565447277424962024757
9753164331835977166382242200301837076942301952858848502901552674537404631697
7964904657195931255912764404368321965951006839312721523813963827559536872525
9255663498774450204128408552760135665311196585057294907726531374828285017666
9079493575681332107268805108427749201049594207542083964439885861615931834645
965491121494647577006591807761793166616453673095582354711565411724127405791276
4935942066671832251736836733963627188213305106330064328648272252338925308465
30211236426964803883363073178869980611993731052155742778573936345107647011533
450683469883317339446680597758269980660569964529693684365470406533604545189
6856420175232112318731261169525302795582438878696844145909635734913232

-----------------------------------------------------------------------------------------------------

The above value of 'e' is indeed more than 10000 digits. :-)

Google Sponsors oCERT

noreply@blogger.com (Babji Prashanth, Chetty) — Tue, 06 May 2008 18:15:00 +0000

Google has joined a volunteer workforce called oCERT (Open Source Computer Emergency Response Team) to play an active role in reviewing/fixing security issues in open source applications. I think its a very good move for the software community. Its just not only useful for the open source community, but anyone who uses open source software and I dont think there's any developer in this world who's not using atleast a snippet of code which is a freebie from open source community.

No software version is perfect and comes with its own security risks and it specially applies for open source software as multiple developers work on a single module/API and the developers working on that might not be that adept in managing the security part or in testing each and every test-case related to security risks associated with that module/API. Also, some software products are developed without much priority/importance on the security issues. These security holes (if any) might bring down the total system/business and cause a huge loss. So, I think its a great move by Google to consider that. For more info, check the links below:

Google Security Blog

ZDNET NEWS

And here's a good article which discusses the security issues related to open source software:

Is Open Source Good For Security?

Wanna Work At Google?

noreply@blogger.com (Babji Prashanth, Chetty) — Thu, 10 Apr 2008 21:48:00 +0000

Sometime back, on a German chat forum, there was this speculation about Munich's new Google R&D centre and how to get into that. I'm just posting what I wrote there, so that it may be useful for folks who are preparing/looking forward to get into Google..Here I go:

---------------------------------------------------------------------------------------------------------------

.......yes, Google has recently opened its R&D centre in Munich, knowing the importance of that place and also because of its location (although there is one more R&D centre very close by - in Zurich).

QUOTE(plex24 @ Sep 13 2007, 3:11 am) *
i am interested too, where did you see the job advert?

There are scores of young people who are ready to work for Google, even for a small payscale. But ofcourse, they pay good and you get a lot of benefits too.

Also, lots of people who wanna work at Google, start preparing for the interviews well ahead of the interview (a couple of months before) in diverse topics like distributed systems, algorithms, networking problems, linux, information retrieval algorithms, and sundry other things. If you are into that already, it would be a bit easy. Do you think, its that easy to comprehend those intricate algorithm problems? ...It takes a while. And you know there are good number of young guys in Poland, Russia, China, India, etc countries who can solve these intricate algo problems in just a couple of minutes (which you can notice in a couple of coding competitions), which would otherwise take a while for some other guys (probably days, months or years).

And one more thing is that, it depends on what kind of position you are expecting at Google. Google Hamburg and Düsseldorf is mostly into sales and marketing. Google has many offices, but its main R&D centres in Europe are in Dublin(Ireland), Zurich (Switzerland), Munich(Germany) and Krakow (Poland).

QUOTE(rhein @ Sep 14 2007, 1:05 am) *
For others - any other tips !!! I am preparing my resume at the moment to apply.

Ofcourse, you can apply. But dont be surprised if you dont get any reply. They receive hundreds of resumes everyday. They had some kind of puzzle, reasoning test too. But I dont really know if they still have that procedure coz its grown big enough now and indeed some Google folks have quit working and joined Facebook, just because its grown big enough and they are missing the challenges of working as an entrepreneur. But still, its a great company to work at, because you learn much.

I have some more interesting facts for you folks:

1) Do you know that Google folks prepare their own super computers by stacking up low cost linux box's and connecting them?

2) Do you know that Google hired a Brain Surgeon (who was good in computers too) as the network admin and supervisor (in the beginning)?

QUOTE(berny @ Sep 13 2007, 11:56 pm) *
Google do have tech offices in munich. but the location is kept VERY secret because google dont want every weirdo extremist freak to know where their hardware is located.

QUATSCH! Why would they hide the location details of their office? If they would hide Munich's location, they would hide the mountain view HQ location too? and also Zurich location?...But did they?..NO.

But its obvious that they wouldnt reveal the information of their server farms, but not their office. They have huge server farms and they already had some problems (a couple of years back) when one server farm went down due to fire. There are different security risks associated with that. So, no one would reveal the location of that (Atleast, the exact location). Even if one server farm fails, there's an other one which acts as a substitute and makes it fail-safe. But still, its a huge loss. So, those details are kept confidential. Simple! smile.gif

PS: Working at Google also depends of one's priorities. I know of some people who are content with what they are working on and can do other things in life and maintain that poise in life. And there are some more, who are ambitious and want to do things. So, it all depends! Choose for yourself and then Google decides whether they can choose you or not! :-)

---------------------------------------------------------------------------------------------------------------

That was it..Good Luck! :-)

Introduction (To my google story)

noreply@blogger.com (Babji Prashanth, Chetty) — Wed, 19 Dec 2007 18:56:00 +0000

I'm one of those who's interested in creative and innovative things and would like to stuff a wealth of information into my mind. What prompted me to set up this blog (Google Tale) is the interest that I've taken in Google since its inception (specially because of the math and the algorithm work that they do).

I have been following the Google-path (we use 'Google' almost everyday, anyways) and thinking about how they are leading and where they are heading, from different perspectives (logical, technical, philiosophical and ..whatever). My initial interest started when I registered for Top-coder programming competitions just outta my pure passion to compete in those challenging and exciting competitions. I registered for that although I had a good, demanding job and was satisfied in my job, salary and had a cosy enough life. This is because it was interesting, challenging,exciting and the problem-set of those competitions involved a lot of algorithms(Not to forget that programmers from all over the world were part of that).Top coder was also given the privilege of managing and co-ordinating Google's 'Code Jam', once in an year.So, it was a big learning curve too. Also, I think that every one who is working in software field should keep abreast of the cutting-edge stuff and learn as much as possible, to be a better programmer.

And since then, I was hungry for more info and knowledge.. and started loafing around on the information superhighway, jumping from one link to other link for more info and kept myself updated with cutting-edge technologies. The way google is heading with its clear vision, hard work, clever and healthy strategy, mind-boggling math and algorithms impressed me. I dont deny that Microsoft lacks this. I admire microsoft too for being so stubborn, for having to fight with numerous firms and people, lawsuits, and sundry other stuff...It might be bad in some people's terms, but on the flip side when you think about the challenge of facing almost all or many of the other software giants, bear the brickbats and still keep progressing, aint that easy. But my policies strike with google, because of its open-minded strategy, policies, technology, creativity and innovation.

Finally, this is one reason why I thought that I would dedicate a blog to Google (inspite of the fact that Google is providing the free space for me on blogger..lol). I recently bought a book called 'Google Story' and was immersed in reading that after work, when I'd free time. Being a technology enthusiast, I was impressed with some of the facts and behind-the-scenes stuff that was written in that book. Thats when I decided that I should dedicate a blog and share my views to the world. Ofcourse, there are scores of blogs writing about Google and their stuff, but I just dont wanna 'copy and paste' or be stereotypical, but write something about the Google technologies with some examples.

I know that there are lot of people, who are more knowledgeable and know much more stuff than I do. So, please correct me if I go wrong rather than directing flames at me. If you still wanna do that, please direct them to dev>>null. ;-)

The Google System

noreply@blogger.com (Babji Prashanth, Chetty) — Mon, 17 Sep 2007 01:18:00 +0000

NOTE: Please read the 'Disclaimer' before reading this post. Also, this is just a naive attempt to explain the Google Architechture, in brief.

My first thought about the Google system is to compare the entire Google system to an operating system. This is because, there are many similarities in between the two. Below are some points, by which I compare Google system and an operating system:

1) Google has an 'File System' (GFS) like any other operating system.

2) Google uses 'caching' concept similar to an operating system. (Not exactly similar, but something that you can compare).

3) All the data is contained in the file system of operating system. Similarly, Google contains much of the internet (it aint everything, but Google is the top engine at the moment, which has crawled the maximum number of pages/sites) and is containing almost all the data on the internet (in its cache/Distributed File System - GFS).

4) An operating system maintains a 'page/paging' table to store the mapping between virtual addresses and physical addresses. In a similar way, Google system has a table (Big Table) which maps the domains to their respective pageRank's (and ofcourse, many other things are involved. This would probably be enchanced/modified gradually, as building software is an evolutionary process - as new ideas/requirements keep poppin' up).

Below is the schematic of the bare bones of a Google System (Note: I'm just trying to put forward my thoughts and not assuring the system architecture, as I dont work for Google.com Engineering (and I dont know any of the Google employees, in person)):

As you can see in the above pic, if a end-user sends a request (using Google.com search) to the Google server, the server receives the request, interacts with its 'File System' and looks up the 'Big Table' for pageRank of domains related to that keywords (or search terms) and responds by providing a ordered list (descending order of PageRank's) of results with domains related to that search term.

Note: This is just a simplified system architecture. Ofcourse, there's much more complexity associated with that - with things like Clusters, Distributed Computing models/frameworks like mapreduce, Distributed File System, calculating pageRank, Complex Algorithms That Run Behind The Scenes, Network Algos,...and much more.

Its obvious from the above pic and the associated text, that Google can be compared to an operating system (similar to the way, you fetch a file from the operating system). It also means something....that Google contains much data or metadata of many sources on the internet and is adding much data day-by-day (or hour-by-hour /sec-by-sec or whatever). The way it searches for new (freshly created) or middle-of-nowhere domains, by sending crawlers, indexing/caching that info in its 'Big Table'/'File System', is one more topic. And ofcourse, because of privacy policies or any other reasons, some domains might not be included. Also, any domain can exclude itself, by creating/copying robots.txt file in one of its directories, so that the Google crawlers would stop including that in search results or updating its info).

Apart from all this info, one more point that I would like to add is the strategy by which Google is attracting users to use their other technolgies like Google Maps, blogger, photo albums, Google pages, Notebook, Spreadsheets, Orkut, et al (which indirectly help Google in containing all the data on the internet).