HackerRank: Circular Array Rotation

Problem

John Watson performs an operation called a right circular rotation on an array of integers, [a(0),a(1).a(2)...a(n-2),a(n-1)]. After performing one right circular rotation operation, the array is transformed from

[a(0),a(1).a(2)...a(n-2),a(n-1)]

to

[a(n-1),a(0),a(1).a(2)...a(n-2)].

Watson performs this operation k times. To test Sherlock’s ability to identify the current element at a particular position in the rotated array, Watson asks q queries, where each query consists of a single integer, m, for which you must print the element at index in the rotated array (i.e., the value of a(m)).

Input Format

The first line contains space-separated integers, n, k, and q, respectively.
The second line contains space-separated integers, where each integer i describes array element a(i)(where 0 <= i <= n).
Each of the q subsequent lines contains a single integer denoting m.

Constraints

  • 0 <= i <= 10^5
  • 0 <= a(i) <= 10^5
  • 0 <= k <= 10^5
  • 0 <= q <= 500
  • 0 <= m <= N-1

Output Format

For each query, print the value of the element at index m of the rotated array on a new line.

Sample Input
3 2 3
1 2 3
0
1
2
Sample Output
2
3
1

Explanation

After the first rotation, the array becomes [3,1,2].
After the second (and final) rotation, the array becomes [2,3,1].

Let’s refer to the array’s final state as array b. For each query, we just have to print the value of b(m) on a new line:

  • m=0 , so we print 2 on a new line.
  • m=1 , so we print 3 on a new line.
  • m=2 , so we print 1 on a new line.

Soluton

HackerEarth: Battle Of Bots 6: Draughts

Problem:

Sample Game

Draughts is a two player board game which is played on a 8X8 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Red ( First Player ) or White ( Second Player ) being conventional. Players take turns involving diagonal moves of uniform game pieces in the forward direction only and mandatory captures by jumping over opponent pieces.

Rules:

  • Player can only move diagonally to the adjacent cell and in forward direction, if the diagonally adjacent cell is vacant.
  • A player may not move an opponent’s piece.
  • If the diagonally adjacent cell contains an opponent’s piece, and the cell immediately beyond it is vacant, the opponent’s piece may be captured (and removed from the game) by jumping over it in the forward direction only.
  • If a player made a jump, then its mandatory to keep on jumping as long as the jump is possible.
  • Player cannot move to the diagonally adjacent cell once the player made a jump.

The game will end when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an 8X8 grid. The top left of the grid is [0,0] and the bottom right is [7,7].

Input:
The input will be a 8X8 matrix consisting only of 0o2. Then another line will follow which will contain a number –  1 or 2 which is your player id. In the given matrix, top-left is [0,0] and bottom-right is [7,7]. The x-coordinate increases from left to right, and y-coordinate increases from top to bottom.

The cell marked 0 means it doesn’t contain any stones. The cell marked 1 means it contains first player’s stone which is Red in color. The cell marked 2 means it contains second player’s stone which is white in color.

Output:
In the first line print the coordinates of the cell separated by space, the piece he / she wants to move.
In second line print an integer N, number of steps or jumps the piece will make in one move.
In the next N lines print the coordinates of the cells in which the piece will make jump.
You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if [1,1] in diagonal to the piece in which is going to jump, but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

Starting state
The starting state of the game is the state of the board before the game starts.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0

First Input
This is the input give to the first player at the start of the game.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0
1
SAMPLE INPUT
0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0
0 0 0 2 0 0 0 2
2 0 2 0 2 0 2 0
1
SAMPLE OUTPUT
2 5
2
4 3
6 1

Explanation

This is player 1’s turn, and the player will move the piece at [2,5] and will make two jumps. First jump will be at [4,3and second jump will be at [6,1]

After his/her move the state of game becomes:

0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 2 0 2 0 2
2 0 2 0 2 0 2 0

This state will be fed as input to program of player 2.

Other valid move for the first player is

2 5
1
3 6

But the following are invalid moves.
Case 1:

2 5
1
4 3

Because after making a jump its possible to jump again and its mandatory to jump as long as its possible to jump.

Case 2:

2 5
2
4 3
5 4

Because after making a jump its invalid to move to diagonally adjacent cell.

Here is the code of the Random Bot.

Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

Solution

This is the solution submitted by me

GCD algorithm in Java

Given 2 non negative integers m and n, find gcd(m, n)

GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n.
Both m and n fit in a 32 bit signed integer.

Example

m : 6
n : 9

GCD(m, n) : 3

NOTE : DO NOT USE LIBRARY FUNCTIONS

How to put a time restriction on a method in java?

I have a specific requirement where in I am calling a method and I want to get the response within a specific duration.
For example, I am trying to fetch the contents of a web-page.

If within 3 seconds, I get the response, its good, otherwise, I want to give a message to the user that internet is too slow.

Now, how do I do this?

You could make use of the ExecutorService and its timeout facilities. The idea is to execute the method you want to call in a different thread, and let the ExecutorService cancel it after a specific time. Here is a simple example, using two fixed threads. You’d have to adapt this to your needs.

Make a class MyTask implements Callable

package testapp;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;

class MyTask implements Callable {

private String name;
private long sleepTime;

public MyTask(String name, long sleepTime) {
this.name = name;
this.sleepTime = sleepTime;
}

public Void call() throws Exception {
System.out.println("Starting task " + name);
Thread.sleep(sleepTime);
System.out.println("Finished task " + name);
return null;
}
}

Use this as is done here

public class ExecutorServiceTest {

public static void main(String[] args) throws InterruptedException {
ExecutorService service = Executors.newFixedThreadPool(2);
Collection<Callable> tasks = new ArrayList<Callable>();
tasks.add(new MyTask("Task1", 10000));
tasks.add(new MyTask("Task2", 2000));
System.out.println(new java.util.Date());
List<Future> taskFutures = service.invokeAll(tasks, 2L, TimeUnit.SECONDS);
for (Future future : taskFutures) {
System.out.println("Done: " + future.isDone());
System.out.println("Cancelled: " + future.isCancelled());
}
System.out.println(new java.util.Date());

System.out.println("END");

}
}

Comparable vs Comparator

There are many articles available on internet for this. But still I would write something about it.

What when and why?

A Comparable class is a class, which can be compared with the objects of its own type. Let us take an example of a book.

public class Book implements Comparable {
    String title;
    int    isbn;

    Book(String title, int isbn) {
        this.title = title;
        this.isbn  = isbn;
    }
    /* This method will be the default method used 
       to sort Book objects in a list or Array */
    public int compareTo(Object object) {
    // It should throw NullPointerException if object passed is null
    if (object==null)
    {
        throw new NullPointerException("compareTo: Argument passed is null");
    }
        Book other = (Book) object;
        if (this.title.equals(other.title)) {
            return this.isbn - other.isbn;
        }
        return this.title.compareTo(other.title);
    }
}

The moment your class implements Comparable, you can then use

List list = new LinkedList();
        list.add(new Book("Patterns", 12345));
        list.add(new Book("Apples", 34567));
        list.add(new Book("Examples", 23456));

        Collections.sort(list);


Using this you can sort your list.

But what if now, you want to add or use another sorting criteria defined in Book class… Here comes the need of Comparator.
There are two ways listed here to use the Comparator class.

First method

We create a anonymous class that implements Comparator and overrides compare method.

Collections.sort(list, new Comparator() {
            public int compare(Object obj1, Object obj2) {
                if(obj1 == null || obj2 == null){
                    throw new NullPointerException("compareTo: Argument passed is null");
                }
                Book book1 = (Book) obj1;
                Book book2 = (Book) obj2;
                return book1.isbn - book2.isbn;
            }
        });

 

Second Method

You define a class that implements Comparator like as below.

class BookComparator implements Comparator{
   
    public int compare(Object book1, Object book2){
   
        int b1= ((Book)book1).isbn;        
        int b2= ((Book)book2).isbn;
       
        if(b1> b2)
            return 1;
        else if(b1< b2)
            return -1;
        else
            return 0;    
    }
   
}

And use this newly defined comparator class as an argument to Collections.sort.

Arrays.sort(list, new BookComparator ());

Good reasons to use Comparator interface

  • I do not have permissions to edit the Book class.
  • Book class already implements Comparable interface, but I want to sort the objects using a different criteria
  • I want to have more than 1 criterias to sort the objects in different orders.

Reasons to implement Comparable interface

  • I want my class to have a default sorting criteria that can be used by the users of my class
  • Usually, one would like to sort the objects based on primary key

Few good links on this topic are here http://www.javadeveloper.co.in/java-example/java-comparator-example.htmlhttp://grdurand.com/static/presentation_four/comparable.htmlhttp://javarevisited.blogspot.com/2011/06/comparator-and-comparable-in-java.html

Best practices in JDBC Connection

JDBC Connection Scope

How should your application manage the life cycle of JDBC connections? Asked another way, this question really asks – what is the scope of the JDBC connection object within your application? Let’s consider a servlet that performs JDBC access. One possibility is to define the connection with servlet scope as follows.

import java.sql.*;

public class JDBCServlet extends HttpServlet {

    private Connection connection;

    public void init(ServletConfig c) throws ServletException {
      //Open the connection here
    }

    public void destroy() {
     //Close the connection here
    }

    public void doGet (HttpServletRequest req, HttpServletResponse res) throws ServletException { 
      //Use the connection here
      Statement stmt = connection.createStatement();
      //do JDBC work.
  }
}

Using this approach the servlet creates a JDBC connection when it is loaded and destroys it when it is unloaded. The doGet() method has immediate access to the connection since it has servlet scope. However the database connection is kept open for the entire lifetime of the servlet and that the database will have to retain an open connection for every user that is connected to your application. If your application supports a large number of concurrent users its scalability will be severely limited!

Method Scope Connections


To avoid the long life time of the JDBC connection in the above example we can change the connection to have method scope as follows.

public class JDBCServlet extends HttpServlet {

  private Connection getConnection() throws SQLException {
    // create a JDBC connection
  }

  public void doGet (HttpServletRequest req, HttpServletResponse res) throws ServletException { 
    try {
      Connection connection = getConnection();
      //..
      connection.close();
    }
    catch (SQLException sqlException) {
      sqlException.printStackTrace();
    }
  }
}


This approach represents a significant improvement over our first example because now the connection’s life time is reduced to the time it takes to execute doGet(). The number of connections to the back end database at any instant is reduced to the number of users who are concurrently executing doGet(). However this example will create and destroy a lot more connections than the first example and this could easily become a performance problem.

In order to retain the advantages of a method scoped connection but reduce the performance hit of creating and destroying a large number of connections we now utilize connection pooling to arrive at our finished example that illustrates the best practices of connecting pool usage.

import java.sql.*;
import javax.sql.*;

public class JDBCServlet extends HttpServlet {

  private DataSource datasource;

  public void init(ServletConfig config) throws ServletException {
    try {
      // Look up the JNDI data source only once at init time
      Context envCtx = (Context) new InitialContext().lookup("java:comp/env");
      datasource = (DataSource) envCtx.lookup("jdbc/MyDataSource");
    }
    catch (NamingException e) {
      e.printStackTrace();
    }
  }

  private Connection getConnection() throws SQLException {
    return datasource.getConnection();
  }

  public void doGet (HttpServletRequest req, HttpServletResponse res) throws ServletException {
    Connection connection=null;
    try {
      connection = getConnection();
      ....
    } 
    catch (SQLException sqlException) {
      sqlException.printStackTrace();
    }
    finally {
      if (connection != null) 
        try {connection.close();} catch (SQLException e) {}
      }
    }
  }
}


This approach uses the connection only for the minimum time the servlet requires it and also avoids creating and destroying a large number of physical database connections. The connection best practices that we have used are:

A JNDI datasource is used as a factory for connections. The JNDI datasource is instantiated only once in init() since JNDI lookup can also be slow. JNDI should be configured so that the bound datasource implements connecting pooling. Connections issued from the pooling datasource will be returned to the pool when closed.

We have moved the connection.close() into a finally block to ensure that the connection is closed even if an exception occurs during the doGet() JDBC processing. This practice is essential when using a connection pool. If a connection is not closed it will never be returned to the connection pool and become available for reuse. A finally block can also guarantee the closure of resources attached to JDBC statements and result sets when unexpected exceptions occur. Just call close() on these objects also.

For More details :
http://www.javaranch.com/journal/200601/JDBCConnectionPooling.html