Directi Placements

There were two algorithmic coding rounds of 90 Minutes each for placements at Directi.

1st Coding Round. 2 Problems . Qualified all students who were able to solve atleast one question. Mostly DFS, Dynamic Programming questions.  Easy category problems.

2nd Coding Round 3 Problems . Interviews were taken based on the rank obtained by candidates in the coding rounds.

Problem 1 : There are two arrays A and B of size N each. You can take 1st element from either 1st array or 2nd array , 2nd element from 1st array A or array B and so on. You have to select in such a way that the total cost of all the N products is minimized.

Hint : Dynamic Programming

Problem 2 : You are given a rooted Tree of N ( 10^5 nodes ). There would be M updates (10^5) to the tree which are of the form

Add x y – Add y to node x .

AddUp x y – Add y to x , parent of x , parent of parent of x  uptill Root.

After that there will be Q queries ( 10^5) queries where you will either be asked to give the value of a node or the sum of subtree rooted at that node.

Hint : Lazy Update as queries have no update value query.

Problem 3 : You are given a series of words. Let us say k words. You can map characters { A…..Z } to characters { A…..Z } in such a way that the words after encoding with the given mapping gives new words which are anagrams of the original words. Now what was asked is to find out the number of different ways in which the mapping can be done. It was also given that the total characters in all the words are always less than 16.

Eg. —  work hard

The number of different mappings are 3! * 3! .

As character r is present in both the words along with the rest of the characters distinct with the same character count, it can only map to itself. Rest all characters i.e. w, o and k in first word and h, a, and d can map to each other as they have the same word count. So permuting them will give an anagram of the given word. So answer is 3! * 3! .

Hint : BitMask

Solution ( Difficulty – Medium )

First of all we have to create a Bipartite graph with the first partite showing the characters which are to be mapped and the second partite showing the encoding of the characters. The edges in this bipartite graph is constructed by first looping on each of the given word and making an edge if the characters are present in a word ( as encoded word should be an anagram of the original word ) and have the same count. If the character pair are not present in a single word then there will never be any edge between the character pairs.

Now the problem simply reduces to finding the number of maximum matching in the given bipartite graph which can be solved using BitMask.  You can read the BitMask basics from my previous post ( Link ) .

Interview – 1 ( Skype Interview )

Problem 1 : You are given k words and their respective positions in the paragraphs as shown below :

W1 : 1 , 10 ,  18  , 21 , 25

W2 : 3 , 11 , 20

W3 : 10 , 22 , 30 , 45

W4 : 15 , 23 , 40

You have to give the minimum sized window which contains all the words i.e. W1 , W2 , W3 and W4.

Solution 1 : Create a combined data structure of the word id and its position and sort it by the position. Now, you can keep a separate array of size k where you keep the latest position of the words in the array. Now loop on all the sorted array and whenever all the words latest position is known then you can find the different of the largest and the smallest value and return the minimum value thus obtained. Complexity : O ( N * log (N) )  + O ( N * k ) 

Solution 2 : In the previous solution instead of checking the whole k sized array to find the minimum and maximum and then giving the minimum window size we can keep a separate Set ( AVL Tree ) to find the minimum and maximum in O ( log k ) time.

Solution 3 : Further improvement can be made by keeping a linked list implemented in an array based on the position of the words. In this method the factor of O ( N * log ( k ) ) reduces to O ( N ) as the operation of finding the maximum and minimum can now be done in O ( 1 ) .

Problem 2 : You are given a complete Rooted Binary Tree in which each edge has some weight. A term Sum ( X ) is defined as the sum of all path lengths from node X to all the other nodes of the nodes. Now what is asked is to find the total sum for all the values of Sum ( X ). ( Hint : A simple DFS gives the result as each edge is counted the product of number of times of the nodes on either side of the edge. ) What was asked is to complete the recursive equations in terms of the child and parent nodes i.e.

count ( X ) : Number of nodes in the subtree rooted at X.

// Simply adding the children values and 1 for itself gives the result .

childSum ( X ) : The factor of Sum ( X ) which will be coming from its children nodes.

// childSum ( 2 * X ) and child ( 2 * X + 1) plus the number of times the edge from node X to (2 * X) will be added and similarly edge from node X to (2 * X + 1) will be added.

ancestor ( X ) : The factor in Sum ( X ) which is coming from its ancestor nodes.

// ancestor ( X ) includes all the nodes other than the nodes in the subtree rooted at node X. Hence the contribution of the sibling also has to be taken into consideration.

Interview – 2 ( Skype Interview )

Question 1 : You are two arrays of size N each. The first array contains only 1’s and 0’s. The second array contains values in the integer range. You can only flip the adjacent values in the first array from (0,1) -> (1,0) and vice versa ( and nothing else ) . You can apply this operation as many number of times as possible. Now what was asked to do is do this operation on the first array as many times such that the final sum of values in the second array corresponding to the 1’s in the first array should be maximum .

Hint : All possible arrangements of 1’s and 0’s are possible. If the number of set bits are k then take maximum k values from the second array.

Question 2 : You are given two strings A and B which are anagram of each other. You can perform only one type of operation on the first string i.e. choose any character and bring it to the first index thus shifting all characters in between one step right. Example : String A : abcdefgh and doing the operation on e gives us the new string as eabcdfgh. Now what was asked to do is to transform String A to String B in minimum number of steps possible.

Input :

abcd

cbad

Output :

2

Explanation : abcd -> bacd -> cbad

Hint : Check what happens to the characters that remain unmoved.

Question 3 :  You are given a Simple graph with two people located at nodes P and Q of the graph. Now P wants to go to node P1 and Q wants to go to node Q1. In each time unit either person at P can move to its neighboring nodes or Q can move to any of its neighboring nodes but not both. You have to tell there is a path in the movement from P to P1 and Q to Q1 where the minimum distance between nodes is always greater than a fixed value D at any point of time in the path.

Hint : Think in terms of BFS on the pair of initial nodes.

Interview – 3 ( Telephonic Interview – No Coding )

First there was a general questionnaire about my previous Internship Projects for about 7-8 minutes.

Then there was a general discussion about my personal projects apart from academics( 5-6 minutes ).

Question – 1 : You are given a large array which can consist of only three numbers (1 , 2 and 3). How will you sort them ?

Question – 2 : Now you are given an array of objects. And each object has a field called num  which can only take 3 values ( 1, 2 and 3 ) . How will you sort the array of objects ?

Question – 3 :  You are given a log csv file. It has the following format for one entry :

10.3.100.1 , 11.4.50.3 , USA

The first entry represent the starting IP address ,the second entry represents the ending IP address and the third entry represents the area in which the range of IP addresses lies. Now given an IP address how will you find the area which the IP address lies ?

Question – 4 : Given a large array of numbers. The operations possible are push a value to the array, delete a value from the array, and search for a value to the array. Which data structure would you choose for performing the operations ?

Question – 5 : Instead now you have only one operation Search which data structure would you prefer ?

Question – 6 : In Java, between HashMap and TreeMap which data structures would you prefer for ideal search and why ?

Question – 7 : Instead of search for a single number now you wish to search a range of numbers which data structure would you prefer ?

Question – 8 : What is a B-Tree ? Which data structure would you prefer B-Tree or BST ?

Question – 9 : Instead of search you can now add or delete a value . Which data structure would you prefer ?

BitMask

Bitmask is a very important Dynamic Programming technique used in competitive programming.

Target Problems : This technique applies to those type of problems where in the worst case you have to check all the permutations and report the best one i.e. if you have an array of size N then check all N! permutations and report your answer.

Dynamic Programming bit-masking technique reduces the complexity to exponential ((2^N)*N) or ((2^N)*(N^2)) (here 2^N represents 2 power N) depending upon the problem, which is way less than the brute force method of N! . This technique works in cases where the Size of N is 15-20 ( at max ). The small size of N provides hints to us this technique.

Let us take a very simple problem.

Example : You are given N players and N different Cricket T-Shirts. Each player prefers to wear only some selected types of T-Shirts based on his choice. i.e Player-1 prefers to weak T-Shirts 1, 3, 5  , Player-2 prefers to wear T-Shirts 4, 5, and 6 and so on.  So now what we need to do is find the total number of distinct ways in which all N-Players gets to wear a T-Shirt from his choice list.

Solution : A brute force solution to the above problem is to find out all permutations of the T-Shirts ( A is the array of T-shirts ) and then check whether Ai T-Shirt is there in the choice list of player i.

For Example let us take N as 5. So one of the permutations of 1,2,3,4 and 5 is

3 1 2 5 4

Now what we can do is check whether 3 lies in the preference list of Player-1, 1 lies in the preference list of Player-2, 2 lies in the preference list of Player-3, 5 lies and the preference list of Player-4 and 4 lies in the preference list of Player-5. If all the above conditions gets satisfied then the above permutation is a valid assignment of the T-Shirts. We can do the same for all the permutations to count the number of valid assignments of T-Shirts. Complexity : O( N! * N ) N is for checking the validity of the permutation and there are in total N! permutations.

Now let us get to the solution of the above problem by using the concept of BitMask.

What if we know the count of proper assignments of N-1 T-Shirts to the first N-1 Players. Then if the last remaining T-Shirt is present in the preference list of the Nth Player, it would give us the count of all proper assignments of the T-Shirts in which the Nth player has the given left over T-Shirt. If the same process is repeated for all the T-Shirts as being the last remaining T-Shirt then we have got the solution of the problem.

As this technique work only for a small value of N ( max 20 as 2^N is 10^6 ) we can represent all the T-Shirts by using N bits.

Bit-1 for T-Shirt:1

Bit-2 for T-Shirt:2

……..

……..

Bit-N for T-Shirt:N

We require a Dynamic Programming array of size 2^N let us name it dp[2^N]. The bit representation of all values from 0 to 2^N contains all possible bit combinations of n bits. So now, what does our array dp contain? The index i has a bitwise pattern let us take it as “000111010” . Now dp[i] stores the count of all proper assignments of T-Shirts 4,5,6 and 8 to the first 4 Players.

How to get this value ?? Dynamic programming technique remembers the past. So we know the count of all proper assignments of the T-Shirts represented by the set bits in 000011010 , 000101010 , 000110010 and 000111000 (one set bit from the number i has been unset) to the first 3 players and automatically the unset bit from i representing T-Shirt goes to the 4th player.

Similarly we go on calculating the values for dp[i] i from 0 to 2^N-1. Finally in dp[111111… 1] (N 1s) we have the count of proper assignments of all the N T-Shirts to the N-Players.

The Base case for the above problem is when the index of the dynamic programming array has 0 Set bits. So the number of ways of assigning 0 T-Shirts to 0 Players in 1.

Exact problem :   http://www.spoj.com/problems/ASSIGN/

Solution : http://pastebin.com/hd3Q1Ab8

 

Similar problem : http://www.codechef.com/AUG14/problems/TSHIRTS/

Explanation : The problem says that there are N people and M T-Shirts and we have to find the number of proper assignments of M T-Shirts to N people.

In the previous problem the number of T-Shirts were exactly equal to the number of Players so the number of set bits were sufficient enough to carry the information of the number of players who would be assigned the T-Shirt.

But, here N is at max 10 and M is at max 100. So in this problem we would require a 2D Dynamic Programming array. Let us name it dp[2^N][M]. Here the dp[i][j] would contain the following information,  the set bits in the bit pattern of i will contain the people who will be provided T-Shirts upto index j. How to calculate this ?? If we make a set bit in the bit pattern of i unset and assign T-Shirt number j to it (in case it is valid) and all other people get T-Shirts upto index j and further doing it for all the set bits we would get the solution which we require.

Solution : http://pastebin.com/QCYFA5r2

 

Similar Problem : http://www.spoj.com/problems/HIST2/

Solution : http://pastebin.com/0NLnmEF6

Happy Coding :):)

Google Summer Internship : Interview Questions

Google Summer Internship selection takes place through two Technical Interviews entirely based on Algorithms. The main aim of the interview is not how many questions does an interviewer solves neither how fast he gives the answers. It is in order to know the thinking process used by the student at the time of Interview in order to solve the problem asked.

The interview questions are given below :

1.      You are given a number in the formed of a linked list as given below :

                          eg.        1 -> 2 -> 3 -> 4       represents the number          1234

          You have to increment the number by 1 i.e. you have to change the number in the linked list to               1235. The number in the list can be arbitrarily large.

(Hint : Take two pointers to mark the last non-nine digit and the second one for traversal of the array)

2.       What is a Binary Search Tree ? Given a binary Search Tree and a value as N. You have to find                out the number in the BST nearest to this number N i.e. with the minimum modulus of difference            value.

(Hint : Just traverse in the tree in order to find the value. In this process keep track of the modulus value of difference)

3.       You are given a Binary Search Tree and a sum value S. You have to find out the pair of numbers             in the binary search Tree whose sum is equal to S .

(Hint : It is done by first converting the BST to circularly sorted doubly linked list in O(N) time and then finding the sum equal to S in again O(N) time )

4.       You are given an array of numbers

                                      a1 , a2, a3, a4, a5,…….

          you have to sort the array in the following form.

                                     a1 <=a2 >= a3 <= a4 >= a5.

(Hint : Just sort the array according to the rule given. If it is not satisfied then just swap the elements)
Justify your solution once given an O(N) time solution.

Binary Indexed Trees

Binary Indexed Trees data structure is one of the most simple Data Structure to implement but hard to understand. The code of Binary Indexed Trees could be directly used anywhere.

The basic Data Structure of BIT is used for problems have Range Queries and point updates.

The implements is much more simple as compared to Segment Trees and it takes only N amount of space whereas in Segment Trees its 2*N.

The implementation of the Data Structure is done using two important methods called as the Get method and Set method. The Set method is used to set value at the specified location of the binary indexed trees. The Get method is used to get the cumulative sum up to the index supplied to the method. The complexity of both the operations are  O(log(N)).  Point to be noted here is that the indexes should start from 1 to the maximum value i.e. maximum size of the array.

The Get method looks like this :

public long get(int A[],int idx)
	{
		long sum=0;
		while(idx>0)
		{
			sum+= A[idx];
			idx -= idx&-idx;
		}
		return sum;
	}

The Set method looks like this :

public void set(long A[],int idx,long val)
	{
		while(idx<=max)
		{
			A[idx] +=val;
			idx += idx&(-idx);
		}
	}

In the similar way the 2-D Binary Indexed Trees could be designed. In the 2-D binary indexed trees both the row number and the column number would be supplied to you. Then for each column you need to update all the row and vise-versa. Leave comments in case of doubts.

Jarvis March Algorithm for finding the Convex Hull

Jarvis March also called as the gift wrapping algorithm is commonly used to find the Convex Hull for a given set of points.

The time complexity for finding the convex hull is  O(N*H)

Here,

  N  -> Total Number of input points
  H  -> Total Number of points present on the Convex Hull

#include<stdio.h>
#include<string.h>
#include<math.h>

#define max 10000000
#define min -10000000

typedef struct node
{
       double x;
       double y;
}node;

double orientation(node p, node q,node r);

int main()
{
       long long int n;
       node points[10000];
       double x,y;
       scanf("%lld",&n);
       int i;

       for(i=0;i<n;i++)
       {
              scanf("%lf",&x);
              scanf("%lf",&y);
              points[i].x = x;
              points[i].y = y;
       }

       int  p = 0;
       int  l;
       for(i=1;i<n;i++)
       {
              if(points[p].x > points[i].x)
              {
                     p = i;
              }
              else if(points[p].x==points[i].x && points[p].y > points[i].y)
              {
                     p = i;
              }
       }
       l =p;
       int  q = (p+1)%n;

       node result[10001];
       int  count =0;
       if(n<3)
       {
              for(i=0;i<n-1;i++)
              {
                     printf("%lf %lf\n",points[i].x,points[i].y);
                     result[count]=points[i];
                     count++;
              }
       }
       else
       {
              do
              {
                     printf("%lf %lf\n",points[p].x,points[p].y);
                     result[count]=points[p];
                     count++;
                     for(i=0;i<n;i++)
                     {
                            if(orientation(points[p],points[i],points[q])==2)
                            {
                                   q = i;
                            }
                     }
                     p = q;
                     q = (p+1) % n;
              }while(p!=l);
       }

       return 0;
}

double orientation(node p, node q,node r)
{
    double val = (q.y - p.y) * (r.x - q.x)-(q.x - p.x) * (r.y - q.y);
    if (val == 0)
       return 0;
    if(val>0)
       return 1;
    else
       return 2;
}


					

Lazy Propagation using Segment Tree Data Structure

Lazy Propagation is a very useful method while dealing with problems of the type Range Update and Range Queries. It is handled using the Data Structure of Segment Trees.

Initially you will be given an array of n elements then you would be asked to update/ query the array numerous times in the following ways :

1. Add or multiply a fixed value to all elements in an array from index i to index j.(or Anything similar to this)

2. Give the sum of elements from index i to index j in the array.

So this type of questions are solved using the concept of Lazy Propagation using Segment Trees Data Structure.

The concept goes like this :

1. First of all we need to make is a binary tree which contains the data of all the nodes in the arrays. The construction of the tree is done using the method of Construct-Tree method which looks something like this :

The Construct-Tree method initialized all the nodes of the segment tree data structure with the values of the array elements.



public static void construct_tree(int present,int start, int last) 
 {
    int mid;
    if(start==last)
    {
       lazy[present]=0; // Lazy nodes to store information about the update of its children
       information[present]=0; // Information specific to nodes
       return ;
    }
    mid = (start + last)/2;
    construct_tree(2*present,start,mid);
    construct_tree(2*present+1,mid+1,last);
    lazy[present] = lazy[2*present]+lazy[2*present+1];
    information[present] = information[2*present]+information[2*present+1];
    return;
 }

2. We have to construct a method which would update the ranges in case of range update queries. So the concept is that there would be nodes in the tree which would contain the information specific to ranges. We have to find all those nodes which contains the information of the range asked for in the queries. The method is called as update method and is written something as given below.

public static void update_tree(int present,int begin,int end,int i,int j)
 {
     if(begin > j || end < i)
     {
           // Unnecessary node as it doesn't contain the required information so just propagate the 
           // information to its children.
     }
     if(begin >=i && end <=j)
     {
          // store the update data in this required node.
     }
 }
 int mid = (begin + end)/2;
 /*
    First propagate the information and then look for subtrees.
 */
 update_tree(2*present,begin,mid,i,j);
 update_tree(2*present+1,mid+1,end,i,j);
 // Recalculate the nodes information
 return;
}

3. The third method that needs to be constructed is the query method which gives the result of the range queries in demand. The method is called as the query method which looks something like this :

public void query(int present,int start,int end, int i, int j)
 {
     if(start>j || end <i)
     {
          //Unnecessary node so just carry forward the lazy information stored in the node.
     }
     if(start>=i && end<=j)
     {
          // Node which is of importance to us hence collect the information and propagate it to the          // children nodes.
     }      
    // When the node may not be entirely useful
    int mid = (start+end)/2;
    // Find the mid propagate the information to its children. 
    query(2*present,start,mid,i,j);
    query(2*present+1,mid+1,end,i,j);
    //recalculate the nodes information from its updated children.
}

Some of the questions that you could practice are given below :

1. FLIPCOIN http://www.codechef.com/problems/FLIPCOIN

2. DQUERY  http://www.spoj.com/problems/DQUERY/

3. LITE http://www.spoj.com/problems/LITE

4. KGSS http://www.spoj.com/problems/KGSS

5. MLCHEF www.codechef.com/problems/MLCHEF

As a sample code I have given the working code of FLIPCOIN problem in Java.

public static void main(String[] args) throws IOException
{
  int n = in.readInt();  // Using Fast I/O in Java
  int q = in.readInt();
  flip = new int[8*n+1];
  heads = new int[8*n+1];
  construct_tree(1,0,n-1);
  for(i=0;i<q;i++)
  {
      str = br.readLine();
      int spIndex = str.indexOf(" ");
      int query = in.readInt();
      int start = in.readInt();
      int end = in.readInt();
      if(query ==0)
      {
               update_tree(1,0,n-1,start,end);
      }
      else
      {
               head_count=0;
               get_result(1,0,n-1,start,end);
               System.out.println(head_count);
      }
    }
 }
public static void get_result(int present,int start,int end, int i, int j)
{
   if(start>j || end <i)
   {
      if(flip[present]%2==0)
      {
          flip[present]=0;
      }
      else
      {
          heads[present]= end - start +1 - heads[present];
          flip[2*present] += flip[present];
          flip[2*present+1] += flip[present];
          flip[present]=0;
      }
      return;
    }
    if(start>=i && end<=j)
    {
        if(flip[present]%2!=0)
        {
            head_count = head_count + end - start +1 - heads[present];
            flip[2*present] += flip[present];
            flip[2*present+1] += flip[present];
            flip[present]=0;
            heads[present] = end - start +1 - heads[present];
         }
         else
         {
              head_count = head_count + heads[present];
              flip[present]=0;
         }
         return;
     }
     int mid = (start+end)/2;
     flip[2*present] += flip[present];
     flip[2*present+1]+=flip[present];
     flip[present]=0;
     get_result(2*present,start,mid,i,j);
     get_result(2*present+1,mid+1,end,i,j);
     heads[present] = heads[2*present]+heads[2*present+1];
 }
public static void update_tree(int present,int begin,int end,int i,int j)
 {
      if(begin > j || end < i)
      {
           if(flip[present]%2==0)
           {
              flip[present]=0;
           }
           else
           {
              heads[present]= end - begin +1 - heads[present];
              flip[2*present] += flip[present];
              flip[2*present+1] += flip[present];
              flip[present]=0;
           }
           return;
        }
        if(begin >=i && end <=j)
        {
           flip[present] = flip[present]+1;
           if(flip[present]%2!=0)
           {
               heads[present]= end - begin +1 -heads[present];
               flip[2*present] += flip[present];
               flip[2*present+1] += flip[present];
               flip[present]=0;
           }
           else
           {
               flip[present]=0;
           }
           return;
       }
       int mid = (begin + end)/2;
       flip[2*present]+= flip[present];
       flip[2*present+1] += flip[present];
       flip[present]=0;
       update_tree(2*present,begin,mid,i,j);
       update_tree(2*present+1,mid+1,end,i,j);
       heads[present] = heads[2*present]+heads[2*present+1];
       return;
 }
 public static void construct_tree(int present,int start, int last)
 {
     int mid;
     if(start==last)
     {
         flip[present]=0;
         heads[present]=0;
         return ;
     }
     mid = (start + last)/2;
     construct_tree(2*present,start,mid);
     construct_tree(2*present+1,mid+1,last);
     flip[present] = flip[2*present]+flip[2*present+1];
     heads[present] = heads[2*present]+heads[2*present+1];
     return;
 }

Ford-Fulkerson Algorithm for finding Maximum Flow in Java.

Aim : Find Maximum Flow from Source to Destination

Other Applications : Finding Maximum Matching

Code :

<pre>class mysolver
 {
     public void solve(InputReader in,OutputWriter out)
     {
         int n=6;
         int graph[][]={{0, 16, 13, 0, 0, 0},
         {0, 0, 10, 12, 0, 0},
         {0, 4, 0, 0, 14, 0},
         {0, 0, 9, 0, 0, 20},
         {0, 0, 0, 7, 0, 4},
         {0, 0, 0, 0, 0, 0}};
         System.out.println("The maximum Flow from source to destination is : "+fordfulkerson(graph,0,5));
     }
     public int fordfulkerson(int graph[][],int s,int t)
     {
         int parent[] = new int[6];
         Arrays.fill(parent,-1);
         int maxflow=0;
         while(bfs(graph,s,t,parent))
         {
             int min= 2147483647;
             int val = t;
             while(val!=s)
             {
                 int u = parent[val];
                 if(graph[u][val]<min)
                 {
                      min = graph[u][val];
                 }
                 val = parent[val];
             }
             val = t;
             maxflow += min;
             while(val!=s)
             {
                 int u = parent[val];
                 graph[u][val] -= min;
                 graph[val][u] += min;
                 val = parent[val];
             }
        }
       return maxflow;
    }
    public boolean bfs(int[][] graph,int s,int t,int[] parent)
    {
         boolean visited[] = new boolean[6];
         Arrays.fill(visited,false);
         visited[s]=true;
         Queue<Integer> queue = new LinkedList<Integer>();
         queue.add(s);
         while(!queue.isEmpty())
         {
              int val = queue.remove();
              for(int i=0;i<6;i++)
              {
                   if(graph[val][i]!=0 && visited[i]==false)
                   {
                         parent[i] = val;
                         visited[i] = true;
                         queue.add(i);
                   }
              }
         }
         if(visited[t]==true)
              return true;
         else
              return false;
     }
}

Parsing JSON in Java.

Parsing of JSON can be done using some of the opensource libraries such as Google-GSON , Serotonin , FastJSON and many more. I use a simple library named Argo, small and easy to use. It can be downloaded from http://argo.sourceforge.net/. It’s documentation is also very simple. An Example JSON file looks something like this :

{
"status" : "OK",
"data" : { 
          "train_name" : "ERNAKULAM EXP",
          "train_number" : "12677",
          "from" :  {"name" : "Bangalore City" , "code":"SBC"},
          "to" :  {"name" : "Coimbatore Jn." , "code":"CBE"},
          "alight" : {"name" : "Coimbatore Jn." , "code":"CBE"},
          "board" : {"name" : "Bangalore City" , "code":"SBC"},
          "class" : "2S",
          "travel_date" : "2-6-2011"
          "passenger" : [ { "seat_number" : "D8  , 31,GN", "status" : "CNF" },
                          { "seat_number" : "D8  , 32,GN", "status" : "CNF" } ],
          "chart_prepared" : false
         }
}

So the code snippet to get the train_name (Train Name) looks something like this.

String secondSingle = new JdomParser().parse(out).getStringValue("data","train_name");

Similarly finding other fields could be done similarly by just separating the fields by commas and then getting the values.

In case you have an array as the value instead you can also use the index number like :

<pre>
String secondSingle = new JdomParser().parse(out).getStringValue("data","train_name","some_field",1);</pre>

In this case you can get the value at first index in some_field.

In case of doubts you can refer the documentation available here :

http://argo.sourceforge.net/javadoc/

Using Video as a background of Web Pages

In order to make the User Interface of the WebSite better we could even use a video as the background of any website using HTML5. The video formats supported by HTML5 presently are mp4 ,ogv and WebM. So the code snippets you would require are as given below :

CSS of the video Tag should be something like this..

#video_tag { position: absolute; top: 0px; right: 0px; min-width: auto; min-height: auto; width: auto; height: auto; z-index: -1000; overflow: hidden; } 

The Javascript for the rotation of various videos should be something like this :

var index = 1,
 playlist = ['new.MP4', 'new.MP4', 'new.MP4'],   // The list of videos that needs to be rotated.
 video = document.getElementById('video_tag');
 video.addEventListener('ended', rotate_video, false);

function rotate_video() 
{
 video.setAttribute('src', playlist[index]);
 video.load();
 index++;
 if (index >= playlist.length) { index = 0; }
}

The HTML of the video tag should be something like this :

<video id="video_tag" preload="auto" autoplay="true" loop="loop" muted="muted" volume="0"> 
<source src="new.MP4" type="video/mp4">

Drawing Graphs using GNUPLOT in Ubuntu

GNUPLOT is a free, and commonly used program for plotting data in Ubuntu. It can be downloaded on Ubuntu using the following commands :

sudo apt-get install gnuplot

Then it would prompt you to enter your password. Entering the password correctly would install the program on your linux successfully. I will illustrate you how to draw a simple line chart using GNUPLOT if you have a data file which contains the (x, y) coordinates of the points which needs to be plotted.

Let the source file be “source.txt” be something like this:

1   2

2   3

3   4

Now what we need to do is to give this input file to GNUPLOT which will draw the graph for us.

So the commands would go like this:

Open the Terminal and give the commands :

gnuplot

Then we enter the commandline of GNUPLOT where commands specific to gnuplot are required to be entered. First what we need to do is define the title, the label of the x-axis and the label of the y-axis for the graph . So the commands for the following operations would go something like this :

set title "Title Of The Graph Goes Here"

set xlabel "X-Axis Label Goes Here"

set ylabel "Y-Axis Label Goes Here"

plot "source.txt" using 1:2 with lines// It would plot all the points then join them sequentially

OR plot "source.txt" using 1:2 // If you want to plot only the coordinates

For further details you can visit the following site.

http://people.duke.edu/~hpgavin/gnuplot.html

In case of any doubts feel free to leave a comment.