Saturday, May 29, 2010

Lets Ruby!

I have been working mostly in Java for the past 4 years and my new work demands me to learn Ruby. So I've started looking into it for the past week and thought I would share my learning process so that it would be useful for someone out there. And thats the objective of this series of posts for someone having a Java background and wanting to learn Ruby.


Lets get into business. I am really excited to see the way Ruby language syntax is and I am eager to learn this mouth-watering scripting language of coolest nature. During my initial analysis, I learnt that Ruby is,
  1. Implemented in many other high level languages such as C, Java, .Net etc.,
  2. Is relatively slower.
  3. Ruby is a high level language made of a high level language.
  4. Not suitable for large applications.
  5. Completely open source and is in a budding state.
  6. Has a framework called Rails which is good for Agile development
  7. Community out there is getting better day by day and finding help immediately should not be a problem as time goes by.
  8. Has significant changes between releases which many developers wont welcome right away.
  9. Running time cannot be easily estimated since the language has several underlying implementation in several languages. But there are various profilers available to test them.
  10. Books are always outdated by the time when you finish them.
Now that the premise being established on what Ruby is, we shall learn it and have a comparison/understanding on how it relates to Java.

Cheers,
Bragaadeesh.

Friday, May 28, 2010

How to exploit Google docs

Now that google has removed the restriction on its documents, it is time for us to start exploiting it.

No need to upload your pictures in some free image webhosting websites where you wont be having the 100% surity of whether it might come up all time or you'l see a "bandwidth exceeded" message. Upload it to your own google account and with some tweak, we can link it directly in the webpage. You can do the same with Picasa, but you will have to create an album every time and it becomes kind of annoying to maintain it.

Same goes with the flash presentations as well. No need to host it to any unreliable free websites. Upload it to your own google document. Plus if you want any referring files you can very well upload it to Google Docs. Yes, there is a limit on the size per account but still 7+ GB will become handy for small and medium bloggers.

Ok, the steps are very very simple.
1. Login to http://docs.google.com. Sign in with your google id and password.
2. Click on upload from the left top and select "any" file type you want only restriction is it cannot exceed 100 MB. Do not forget to uncheck "Convert documents, presentations, and spreadsheets to the corresponding Google Docs formats" if you feel you dont want Google mess up your documents.
3. After you upload the file, select the file and click on Share and select "Get the link to share". You should be getting a link in a text bar as shown below
4. To append the file in your page all you got to do is add this to the url &export=open&type=.swf

This way you can directly embed your flash or jpg or png directly in your pages (the type=.xxx will vary depending on the file you've uploaded). If you want to give a direct download link append this command at the end &export=download&confirm=no_antivirus

The last one &confirm=no_antivirus can be given to files of .exe and .zip extensions.

Hope this helped. A sample flash file embedded from google doc can be found here.

Cheers!!
Bragaadeesh.

Tuesday, May 11, 2010

Print Matrix in a circular path (Interview question)

Hi friends,

This is one of the interview questions I faced recently and thought I would share it.

Question:
Given a matrix print all its value in a circular fashion like shown in the image below.



Solution:
To attack this problem we definitely want to have a left-right, top-bottom, right-left and bottom-top spans. For attaining this, we obviously want to have 4 loops. The C++ code is given below.

//============================================================================
// Name        : circular_matrix_read.cpp
// Author      : c++
// Description : output given matrix elements circularly
//============================================================================

#include <iostream>
using namespace std;

#define HEIGHT 6
#define WIDTH  3

int main()
{
 //int array[HEIGHT][WIDTH] = {{1,2,3,4,5},{16,17,18,19,6},{15,24,25,20,7},{14,23,22,21,8},{13,12,11,10,9}};
 //int array[HEIGHT][WIDTH] = {{1,2,3,4,5,6},{14,15,16,17,18,7},{13,12,11,10,9,8}};
 int array[HEIGHT][WIDTH] = {{1,2,3},{14,15,4},{13,16,5},{12,17,6},{11,18,7},{10,9,8}};
 int maxh = HEIGHT-1, maxw = WIDTH-1;
 int minh = 0, minw = 0;
 while(1)
 {
  if(minh > maxh || minw > maxw)
   break;

  //top-left to top-right
  for(int i=minh,j=minw;j<=maxw;j++)
   cout << array[i][j] << endl;
  minh++;

  if(minh > maxh || minw > maxw)
   break;

  //top-right to bottom-right
  for(int i=minh,j=maxw;i<=maxh;i++)
   cout << array[i][j] << endl;
  maxw--;

  if(minh > maxh || minw > maxw)
   break;

  //bottom-right to bottom-left
  for(int i=maxh,j=maxw;j>=minw;j--)
   cout << array[i][j] << endl;
  maxh--;

  if(minh > maxh || minw > maxw)
   break;

  //bottom-left to top-left
  for(int i=maxh,j=minw;i>=minh;i--)
   cout << array[i][j] << endl;
  minw++;
 }
 return 0;
}
//1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Cheers!
Bragaadeesh.

Sunday, May 9, 2010

Google CodeJam 2010 : Theme Park with Solution

Guys,

This is one of the three problems asked in the 2010 Edition of Google Codejam Qualification Round. The question is quite interesting and simple to solve and I did solve. But the problem here is the running time. If not a proper strategy is followed, then the running time of the algorithm will be more and eventually you cannot submit the answer in time for large data set. Lets look at the problem.


Problem

Roller coasters are so much fun! It seems like everybody who visits the theme park wants to ride the roller coaster. Some people go alone; other people go in groups, and don't want to board the roller coaster unless they can all go together. And everyone who rides the roller coaster wants to ride again. A ride costs 1 Euro per person; your job is to figure out how much money the roller coaster will make today.
The roller coaster can hold k people at once. People queue for it in groups. Groups board the roller coaster, one at a time, until there are no more groups left or there is no room for the next group; then the roller coaster goes, whether it's full or not. Once the ride is over, all of its passengers re-queue in the same order. The roller coaster will run R times in a day.
For example, suppose R=4, k=6, and there are four groups of people with sizes: 1, 4, 2, 1. The first time the roller coaster goes, the first two groups [1, 4] will ride, leaving an empty seat (the group of 2 won't fit, and the group of 1 can't go ahead of them). Then they'll go to the back of the queue, which now looks like 2, 1, 1, 4. The second time, the coaster will hold 4 people: [2, 1, 1]. Now the queue looks like 4, 2, 1, 1. The third time, it will hold 6 people: [4, 2]. Now the queue looks like [1, 1, 4, 2]. Finally, it will hold 6 people: [1, 1, 4]. The roller coaster has made a total of 21 Euros!

 

Input

The first line of the input gives the number of test cases, T. T test cases follow, with each test case consisting of two lines. The first line contains three space-separated integers: R, k and N. The second line contains N space-separated integers gi, each of which is the size of a group that wants to ride. g0 is the size of the first group, g1 is the size of the second group, etc.

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 number of Euros made by the roller coaster.

Limits

1 ≤ T ≤ 50.
gik.

Small dataset

1 ≤ R ≤ 1000.
1 ≤ k ≤ 100.
1 ≤ N ≤ 10.
1 ≤ gi ≤ 10.

Large dataset

1 ≤ R ≤ 108.
1 ≤ k ≤ 109.
1 ≤ N ≤ 1000.
1 ≤ gi ≤ 107.

Sample


Input
 

Output
 
3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3
Case #1: 21
Case #2: 100
Case #3: 20

Solution

The solution for this problem may look simple and if we follow the problem as is, its pretty straight-forward. So, here is the solution that I initially arrived at,
private int solve(int R, int k, int[] groups){
  
  int moneyMade = 0;
  LinkedList<Integer> groupsQueue = new LinkedList<Integer>();
  
  for(int i=0;i<groups.length;i++){
   groupsQueue.add(groups[i]);
  }
  
  while(R>0){
   //calculate the people that can fit in
   int eachSum = 0;
   int i;
   for(i=0;i<groups.length;i++){
    eachSum+=groupsQueue.get(i);
    if(eachSum>k){
     eachSum-=groupsQueue.get(i);
     break;
    }
   }
   moneyMade+=eachSum;
   //alterQueue
   for(int j=0;j<i;j++){
    groupsQueue.add(groupsQueue.poll());
   }
   R--;
  }
  
  return moneyMade;
 }

If you look at the above solution, I have followed the problem by the word. But turned out this cannot take the large data input set simply because of the amount of time it takes to run. The mole in the above solution is that I calculate the eachSum everytime for all R iterations. The large dataset is having R upto 10^8 and Group to be 10^7. So the runtime in worst case will be 10^16 which even the fastest computers invented these days struggle to solve in small time.

So, I had to attack my problem in a different manner. All Google CodeJam problems dont have any space criterion, so its wise to make use of it. So, what would be ideal here is to precalculate the sum and extent for each group before hand. This would take a max of 10^3 * 10^3 = 10^6 iterations. The results are stored in a separate array for faster recovery.

Then iterate through the entire R once and finish the problem in constant time. The matured code is given below.

private long solve(long R, long k, long[] groups){
  int len = groups.length;
  long[] sums = new long[len];
  int[] span = new int[len];
  //irrespective of R, calculate and keep the extent and sum in separate arrays
  for(int x=0;x<len;x++){//Maximum 1000 runs
   int sum = 0; int extent=0;
   for(int y=x;;y++){
    if(sum+groups[y%len]>k || len==extent){
     break;
    }
    extent++;
    sum+=groups[y%len];
   }
   sums[x] = sum;
   span[x] = extent;
  }
  long totalSum = 0;
  int i = 0;
  for(int r=0;r<R;r++){
   totalSum += sums[i];
   i+=span[i];
   i=i%len;
  }
  return totalSum;
 }

Files you may need.
1. Input file - Small dataset
2. Input file - Large dataset
3. Output file - Small dataset
4. Output file - Large dataset
5. Complete Source code in Java

Cheers!,
Bragaadeesh.

Tuesday, May 4, 2010

Google CodeJam : Alien Language Problem with Solution

This is the problem asked in 2009 Google Codejam's qualification round. Lets get into business straightaway.

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 for this problem is relatively simple compared to the other codejam problems that we are going to solve in the future. The solution is implemented in Perl language. It uses the regex pattern matching method.

#!/usr/local/bin/perl

use strict;
use warnings;

print "Enter file name :: ";
my $infile = <STDIN>;

open(INP,"<$infile") or die "can not open file for reading";

my $line_num = 0;
my $num_of_words = 0;
my $num_of_testcases = 0;
my @words_array;
my @testcases_array;

while(<INP>)
{
 if($line_num == 0)
 {
  my @tmp = split(/\s/,$_);
  $num_of_words = $tmp[1];
  $num_of_testcases = $tmp[2];
 }
 elsif($line_num >= 1 and $line_num < ($num_of_words + 1))
 {
  s/[\s\t\n]//;
  $words_array[$line_num - 1] = $_;
 }
 elsif($line_num >= ($num_of_words + 1) && $line_num < ($num_of_words + $num_of_testcases + 1))
 {
  s/[\s\t\n]//;
  s/\(/[/g;
  s/\)/]/g;
  $testcases_array[$line_num - 1 - $num_of_words] = $_;
 }
 $line_num++;
}

my $words_passed = 0;
my $testcase_num = 1;
foreach my $pattern (@testcases_array)
{
 foreach my $word (@words_array)
 {
  if($word =~ m/$pattern/)
  {
   $words_passed++;
  }
 }
 print "Case #$testcase_num: $words_passed\n";
 $words_passed = 0;
 $testcase_num++;
}

close(INP);

Input file of large dataset : Download
Output file of large dataset : Download

Cheers!
Bragaadeesh

Monday, May 3, 2010

Find three numbers in an array which forms a maximum product (for signed integers)

This is a problem that we had already seen. But it gives more kick if the input has negative elements and zero!!!

Question:
Given an array of integers (signed integers), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].

int[] MaxProduct(int[] input, int size)

The solution involves in finding three maximum and two minimum numbers. If the minimum numbers are negatives and if their product is greater than the two maximum number's product, then they have to considered for maximum product. Handling all these scenarios with comprehensive test cases, please find the code below for the problem implemented in C++

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman
// Version     : v2
// Copyright   : open
// Description : To find three signed numbers in an array with max product
//========================================================a====================

#include <iostream>
using namespace std;

#define MAX 10

int* MaxProduct(const int input[], const int size)
{
 int* output = new int[3];
 int negative = 0;
 for(int i = 0; i < 3; i++)
 {
  output[i] = -999999;
 }
 int min[2] = {0,0};

 for(int i=0;i<size;i++)
 {
  // find two smallest negative numbers
  if(input[i] <= 0)
  {
   if(input[i] < min[0])
   {
    min[1] = min[0];
    min[0] = input[i];
   }
   else if(input[i] < min[1])
   {
    min[1] = input[i];
   }
   negative++;
  }

  // find three largest positive numbers
  if(input[i] > output[0])
  {
   output[2] = output[1];
   output[1] = output[0];
   output[0] = input[i];
  }
  else if(input[i] > output[1])
  {
   output[2] = output[1];
   output[1] = input[i];
  }
  else if(input[i] > output[2])
  {
   output[2] = input[i];
  }
 }

 if(size != negative)
 {
  if((min[0] * min[1]) > (output[0] * output[1]) || (min[0] * min[1]) > (output[1] * output[2]))
  {
   output[1] = min[0];
   output[2] = min[1];
  }
 }

 return output;
}

int main()
{
 const int input[MAX] = {-6,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result = 0;
 result = MaxProduct(input,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result[i] << endl;
 }

 const int input1[MAX] = {0,-1,-2,-33,4,15,-7,-28,-9,-10};
 int* result1 = 0;
 result1 = MaxProduct(input1,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result1[i] << endl;
 }

 const int input2[MAX] = {0,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result2 = 0;
 result2 = MaxProduct(input2,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result2[i] << endl;
 }

 const int input3[MAX] = {6,1,2,33,4,15,7,28,9,10};
 int* result3 = 0;
 result3 = MaxProduct(input3,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result3[i] << endl;
 }

 return 0;
}

Cheers!
Bragaadeesh.

Given a sorted array find the pair that forms the sum in O(n) time

This problem is quite frequently asked and we had already seen a solution in O(n) time but using a hash table here. However in this posting we shall see how to attack this problem when the input data is sorted.


For example for the input,
[-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24] and the sum bein 0, the matching pair is -12 and 12

The solution for this problem relies upon the knowledge of the input data : sorted. We will be having two pointers, one from the start of the Array called as min and the other from the end of the array called as max. We always calculate the sum with the values present in the minimum and maximum indexes. If the sum is greater than what is needed, we will be decrementing the max pointer and for the other case, we will be incrementing the min pointer. This happens till min exceeds max.

Following the solution in C++

//============================================================================
// Name        : array_find_sum.cpp
// Author      : Prabhu Jayaraman
// Version     : v1
// Copyright   : Free
// Description : Find elements in the array that equals to given sum
//============================================================================

#include <iostream>
using namespace std;

#define MAX 15

int main()
{
 int array[MAX] = {-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24};
 const int find_sum = 0;
 int max_index = MAX - 1;
 int min_index = 0;
 while(min_index < max_index)
 {
  if(array[min_index] + array[max_index-min_index] == find_sum)
  {
   cout << array[min_index] << " & " << array[max_index-min_index] << " Matched" << endl;
   return 0;
  }
  if(array[min_index]+array[max_index-min_index] < find_sum)
  {
   min_index++;
   max_index++;
  }
  if(array[min_index]+array[max_index-min_index] > find_sum)
  {
   max_index--;
  }
 }
 cout << "NO MATCH" << endl;
 return 0;
}
//-12 & 12 matched

Cheers!
Bragaadeesh

Compact a given array coding problem

This problem may look very simple and indeed it is because the solution can be arrived at very easily. But to arrive at a clean and an efficient may take sometime. This question is asked to test the cleanliness and simplicity in providing solutions. Enough hype, here is the question.

Given an array of random numbers and -1 placed in-between, compact that array ie., all the -1s are to be removed and the final output should be the last valid index with the fresh array. For example.





You should not swap the values just the last valid index along with the array is enough to decipher the not -1 values.

The solution to this problem is seemingly simple and the same has been implemented in Java below.

public class CompactArray {
 public static void main(String[] args) {
  CompactArray c = new CompactArray();
  int[] sampleArray = {-1,5,3,-1,3,5,2,1,-1,6};
  System.out.print(" Input : ");printArray(sampleArray, sampleArray.length);
  int validIndex = c.compact(sampleArray);
  System.out.print("Output : ");printArray(sampleArray, validIndex);
 }
 
 private int compact(int[] arr){
  int k = 0;
  for(int i=0;i<arr.length;i++){
   if(arr[i]!=-1)
    arr[k++] = arr[i];
  }
  return k;
 }
 
 private static void printArray(int[] sampleArray, int validIndex) {
  for(int i=0;i<validIndex;i++){
   System.out.print(sampleArray[i]+" ");
  }
  System.out.println();
 }
}
/*
Input : -1 5 3 -1 3 5 2 1 -1 6 
Output : 5 3 3 5 2 1 6 
*/

Cheers!
Bragaadeesh.