Consecutive character removal algorithm

Recently I came across a question in one of the coding practices quiz – Remove consecutive characters from a string and they say it as String Bomber Algorithm. I was given half an hour of time to complete the task. Looks simple at first but while writing I came across certain scenarios which proved me that the algorithm requires more thinking than anticipated. However, I  managed to complete the task in which a few test cases passed while one failed. Let us take some examples.

Examples:

Input Output
abbcd acd
abbcccd ad
abbcccad d
abbcccadag dag

Still looks simple , huh ? 🙂

The difficulty of the problem lies in re eliminating the characters which become consecutive in the output if all the characters in between them has been dropped.

Say, in example above exmple ‘abbcccad’ input should give the output as ‘d’.

Input : abbcccad

Pass 1: acccad ==> bb is consecutive so elliminated

Pass 2: aad ==> ccc is consecutive so eliminated

Pass 3: d ==> aa is consecutive so eliminated.

Hence output is ‘d’.

I wrote an algorithm which would do the above task:

package com.ds;

/**
 * Created by devashish on 2/13/2017.
 */
public class StringBomber {
    public static void main(String args[])
    {
        String input  = "abbcccadag";
        String output = "";
        char prevchar = input.charAt(0);
        for(int i  = 0 ; i < input.length()   ; )
        {

            char outputlastchar = ' ';
            if(output.length() > 0)
            {
             outputlastchar =  output.charAt(output.length()-1);
            }

            if( i == input.length() -1 )
            {
                if(outputlastchar != input.charAt(i))
                {
                    output +=input.charAt(i);
                }
                else
                {
                    if(output.length() > 0)
                    {
                        output = output.substring(0,output.length()-1);
                    }
                }
                break;
            }

            if((input.charAt(i) == input.charAt(i+1)) )
            {
                int j = i;

                while(j< input.length() && input.charAt(j) == input.charAt(i))
                {
                    j++;
                }
                i=j;
                prevchar = input.charAt(j-1);
            }
            else if(   input.charAt(i) == outputlastchar )
            {

                if(output.length() > 0)
                {
                     output = output.substring(0,output.length()-1);
                }

                prevchar = input.charAt(i);
                i++;
               
            }
            else
            {
                output +=input.charAt(i);
                prevchar = input.charAt(i);
                i++;

            }

        }

        System.out.println("output:"+output);
    }
}

 

Complexity of the above problem is O(n).

Try it and comment in case you see any issues with the algorithm.

Stay well and happy coding 🙂

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Insertion Sort

Insertion sort : Pick an element in the array and position it in its appropriate place in the natural ordering.

e.g. Array 5,4,3,2,1

Pass 1:

Input : 5,4,3,2,1

4 is lesser than 5, so re-position 4.

Output: 4,5,3,2,1

Pass 2:

Input :4,5,3,2,1

3 is lesser than 4, so re-position 3.

Output: 3,4,5,2,1

 

Pass 3:

Input :3,4,5,2,1

2 is lesser than 3, so re-position 3.

Output: 2,3,4,5,1

 

Pass 4:

Input :2,3,4,5,1

1 is lesser than 2, so re-position 2.

Output: 1,2,3,4,5

Array is now sorted.

So, the complexity of the sorting lies in re positioning the array elements.

  • Worst case: O(n^2).
  • Best case: O(n).
  • Average case for a random array: O(n^2).

I have written a small program to compare the elements using insertion sort algorithm.

 

public class InsertionSort 
{
 public static void main(String[] args) 
 {
 int arr[] = {28,26,1,7,13,12,9,-1,6,6,6,6,5,6,4,3,2,1};
 
 for(int i = 1 ; i < arr.length ; i++)
 {
 if(arr[i] < arr[i-1])
 {
 boolean shift = false;
 int temp = -100;
 for(int j = 0 ; j <= i ; j++)
 {
 
 if(shift)
 {
 int temp1 = arr[j];
 arr[j] = temp;
 temp = temp1;
 continue;
 }
 
 if(arr[j] > arr[i])
 {
 temp = arr[j];
 arr[j] = arr[i];
 shift = true;
 }
 }
 }
 }
 
 for(int i : arr)
 {
 System.out.println(i);
 }
 }
}


 

Stay well and happy coding 🙂

Arranging scores in a Game Board.

Problem Statement: Let us say a scenario where player’s scores are displayed in a Game Board. As and when the player scores, it should be inserted in the proper position in the Game Board.

Assumptions:

  1. We assume maximum number of scorecards to be inserted in the Game Board to be fifty.
  2. The player names must be unique in a Game Board.

Solution: A simple approach is:

  1. When we get a scorecard, we iterate through the existing Game Board as insert it in the proper position.
  2. When we have inserted it in the proper position, all the next scorecards has to be shifted right and score card length will be incremented by 1.
  3. If we want to remove a score card from the Game Board, we search it by name and remove it. Also, we shift the array left by one position.

Code:

 

public class GameBoard {
 ScoreCard[] scorecards;
 static int scorecardlength;

public GameBoard() {
 this.scorecards = new ScoreCard[50] ;
 scorecardlength = 0;
 }

public GameBoard(ScoreCard[] scorecards) 
 {
 this.scorecards = scorecards ;
 }

public int insertScoreCard(ScoreCard myscorecard)
 {
 int i = 0;
 try {
 do
 {
 
 if(i == scorecardlength)
 {
 scorecards[i] = myscorecard;
 scorecardlength++;
 break;
 }
 
 if(scorecards[i].playerName.equals(myscorecard.playerName))
 {
 System.out.println("Player "+myscorecard.playerName+" already mentioned in GameBoard. This will be skipped. ");
 break;
 }
 
 if(scorecardlength > 0)
 {
 if(myscorecard.score > scorecards[i].score)
 {
 scorecardlength++;
 ScoreCard temp = scorecards[i];
 scorecards[i] = myscorecard;

int iterator = i+1;
 while(iterator <= scorecardlength)
 {
 ScoreCard tempnext = scorecards[iterator];
 scorecards[iterator] = temp;
 temp = tempnext;
 iterator++;
 }
 break;
 } 
 }
 else
 {
 scorecards[i] = myscorecard;
 scorecardlength++;
 break;
 }

i++;
 }
 while( i <= scorecardlength);
 } catch (Exception e) {
 e.printStackTrace();
 }
 return scorecardlength;

}
 
 
 public void removeScoreCard(String playerName)
 {
 for(int i=0; i <scorecardlength ; i++)
 {
 if(scorecards[i].playerName.equals(playerName))
 {
 int iterator = i;
 while(iterator < scorecardlength-1 )
 {
 scorecards[iterator] = scorecards[iterator+1];
 iterator++;
 }
 scorecardlength--; 
 break;
 }
 }
 }
 
 public int getScoreCards()
 {
 return scorecardlength;
 }
 public void displayGameBoard()
 {
 for(int i=0;i<scorecardlength;i++)
 {
 if(scorecardlength >0 )
 {
 System.out.println("Player "+scorecards[i].playerName+" scored "+scorecards[i].score+" score. You are on "+(i+1)+" position.");
 }
 else
 {
 System.out.println("No scorecards in the Game Board.");
 }
 }
 }
 
 
 public static void main(String[] args) {
 GameBoard gameboard = new GameBoard();
 
 
 gameboard.insertScoreCard(new ScoreCard("player1", 10));
 gameboard.insertScoreCard(new ScoreCard("player2", 20));
 gameboard.insertScoreCard(new ScoreCard("player3", 5));
 gameboard.insertScoreCard(new ScoreCard("player4", 10));
 gameboard.insertScoreCard(new ScoreCard("player5", 10));
 gameboard.insertScoreCard(new ScoreCard("player6", 10));
 gameboard.insertScoreCard(new ScoreCard("player7", 10));
 gameboard.insertScoreCard(new ScoreCard("player8", 10));
 gameboard.insertScoreCard(new ScoreCard("player1", 10));
 gameboard.insertScoreCard(new ScoreCard("player2", 20));
 gameboard.insertScoreCard(new ScoreCard("player3", 5));
 gameboard.insertScoreCard(new ScoreCard("player4", 10));
 gameboard.insertScoreCard(new ScoreCard("player5", 10));
 gameboard.insertScoreCard(new ScoreCard("player6", 10));
 gameboard.insertScoreCard(new ScoreCard("player7", 10));
 gameboard.insertScoreCard(new ScoreCard("player8", 10));
 
 gameboard.displayGameBoard();
 }
}

class ScoreCard
{
 String playerName ; 
 int score;
 public ScoreCard() {

}

ScoreCard(String playerName, int score)
 {
 this.playerName = playerName ;
 this.score = score ;
 }

}

Keep Safe and Happy Coding 🙂

 

 

 

Train Routing Problem

Problem Statement: Say 4 trains start at the same time. They may travel via same stations. Only one train can be there at one station at once. How should we achieve this using multi threading.

Solution:  I consider  this as an example of multi threading. Say, there are four trains (Train 1, Train 2, Train 3 and Train 4) which run between stations A,B,C,D and E.

We assume the following points :

  1. The train routes are single line. So, only one train can be there at one station at once.
  2. All the trains are stopping for a fixed interval in all the stations (5 seconds).
  3. All the trains start at the same time.
  4. All the trains travel at the same speed.

Following are the train routes :

Train 1 Route = A –> B –> E
Train 2 Route =  B –> C –> D
Train 3 Route =  A –> C –> E
Train 4 Route = A –> B –> C –> D –> E


 

import java.util.HashMap;

public class TrainRoutingProblem implements Runnable{

private char myroute[];
 static HashMap<Character,Character> stations = new HashMap<Character,Character>();
 
 
 public void setRoute(char[] myroute)
 {
 this.myroute = myroute;
 }

public TrainRoutingProblem()
 {

}

public synchronized void atStation(char c) 
 {
 stations.put(c, 'O');

try 
 {
 Thread.sleep(100);

} 
 catch (InterruptedException e) {
 System.out.println("Station "+c+" is occupied by "+Thread.currentThread().getName()+". Please wait..");
 }

stations.put(c, 'V');
 System.out.println(Thread.currentThread().getName()+" has left station "+c);
 }


 public void trainRun()
 {

for(char c:myroute)
 {
 System.out.println(Thread.currentThread().getName()+" is approaching station "+c);
 
 atStation(c); 
 
 }
 }

public void notifyJourneyStarted()
 {
 System.out.println(Thread.currentThread().getName()+" has started its journey.");
 }

public void notifyJourneyFinished()
 {
 System.out.println(Thread.currentThread().getName()+" has completed its journey.");
 }

public static void reset()
 {
 stations.put('A', 'V');
 stations.put('B', 'V');
 stations.put('C', 'V');
 stations.put('D', 'V');
 stations.put('E', 'V');

}

public static void main(String[] args) 
 { 
 char route1[]={'A','B','E'};
 char route2[]={'B','C','D'};
 char route3[]={'A','C','E'};
 char route4[]={'A','B','C','D','E'};
 
 TrainRoutingProblem routeObj = new TrainRoutingProblem();
 routeObj.setRoute(route1);
 
 Thread t1 = new Thread(routeObj);
 t1.setName("Train 1 Route 1");
 
 routeObj.setRoute(route2);
 Thread t2 = new Thread(routeObj);
 t2.setName("Train 2 Route 2");

routeObj.setRoute(route3);
 Thread t3 = new Thread(routeObj);
 t3.setName("Train 3 Route 3");
 
 routeObj.setRoute(route4);
 Thread t4 = new Thread(routeObj);
 t4.setName("Train 4 Route 4");
 
 TrainRoutingProblem.reset();
 
 t1.start();
 t2.start();
 t3.start();
 t4.start();
 
 }

@Override
 public void run() {
 notifyJourneyStarted();
 trainRun(); 
 notifyJourneyFinished();
 }
}
Output:

Train 3 Route 3 has started its journey.
Train 4 Route 4 has started its journey.
Train 1 Route 1 has started its journey.
Train 1 Route 1 is approaching station A
Train 2 Route 2 has started its journey.
Train 4 Route 4 is approaching station A
Train 3 Route 3 is approaching station A
Train 2 Route 2 is approaching station A
Train 1 Route 1 has left station A
Train 1 Route 1 is approaching station B
Train 2 Route 2 has left station A
Train 2 Route 2 is approaching station B
Train 3 Route 3 has left station A
Train 3 Route 3 is approaching station B
Train 4 Route 4 has left station A
Train 4 Route 4 is approaching station B
Train 3 Route 3 has left station B
Train 3 Route 3 is approaching station C
Train 3 Route 3 has left station C
Train 3 Route 3 is approaching station D
Train 3 Route 3 has left station D
Train 3 Route 3 is approaching station E
Train 3 Route 3 has left station E
Train 3 Route 3 has completed its journey.
Train 2 Route 2 has left station B
Train 2 Route 2 is approaching station C
Train 1 Route 1 has left station B
Train 1 Route 1 is approaching station C
Train 1 Route 1 has left station C
Train 1 Route 1 is approaching station D
Train 2 Route 2 has left station C
Train 2 Route 2 is approaching station D
Train 4 Route 4 has left station B
Train 4 Route 4 is approaching station C
Train 4 Route 4 has left station C
Train 4 Route 4 is approaching station D
Train 2 Route 2 has left station D
Train 2 Route 2 is approaching station E
Train 2 Route 2 has left station E
Train 2 Route 2 has completed its journey.
Train 1 Route 1 has left station D
Train 1 Route 1 is approaching station E
Train 4 Route 4 has left station D
Train 4 Route 4 is approaching station E
Train 1 Route 1 has left station E
Train 1 Route 1 has completed its journey.
Train 4 Route 4 has left station E
Train 4 Route 4 has completed its journey.

Note: This is very basic solution and needs to be enhanced to meet more scenarios. Till I find out a better approach “Keep Safe and Happy Coding 🙂 “…

Quickly sorting using Quick Sort Algorithm

Quick sort algorithm and the tutorial is explained nicely  .

I have used the following steps for using quick sort:

  1. Select the first element as pivot.
  2. Position it properly in the array by comparing it from end of array.
  3. Reassign the pivot with the newly swapped element.
  4. Compare it with the starting of the array.
  5. Reassign the pivot with the next element from left side.
  6. Repeat steps 2-5 until the array is sorted.

public void sort(int arr[])
{
int pi = 0,
temp=0;

int leftpi = -1 ,
rightpi=arr.length-1,
count = 0;

boolean leftsorted = false,rightsorted = false;

System.out.println(“=================================”);
for(int a:arr)
{

System.out.print(a+” | “);
}

do{

pi = leftpi + 1;
System.out.println(“\n==========PASS “+(++count)+”==================”);
for(int i = arr.length -1 ; (i >=0 && i > leftpi) ; i– )
{

if(arr[pi] > arr[i])
{
temp = arr[i];
arr[i] = arr[pi];
arr[pi] = temp;

System.out.println(“Pivot=”+arr[pi]);

for(int a:arr)
{

System.out.print(a+” | “);
}

leftpi = pi;
pi = i ;
leftsorted = true;
break;
}
}

for(int j = 0; (j<arr.length || j<rightpi-1) ; j++)
{
if(arr[pi] < arr[j])
{
temp = arr[j];
arr[j] = arr[pi];
arr[pi] = temp;

System.out.println(“Pivot=”+arr[pi]);

for(int a:arr)
{

System.out.print(a+” | “);
}

rightpi = pi ;
pi = j ;
rightsorted = true;
break;
}
}

if(!leftsorted && !rightsorted)
{
System.exit(0);
}

leftsorted = false;
rightsorted = false;

}while(leftpi<=rightpi);
}

 

While this gives me the sorted array but I think there are some passes in the above iteration which can be skipped. Still trying for a better solution. Keep safe and happy coding 🙂

 

Attitude versus skill sets.. Which one is your priority ?

Hello !!
We are in an age where each one of us is very keen to learn a skill. Greater the number of skills you have better is your job prospect. So far as I am concerned, being a Software Engineer – I need to learn many technical skills and be very good at them. I am interested to work on different technologies, learn some new thing everyday and to keep my learning curve in the best possible shape.
Recently I have switched my job. Being a 2+ years experienced, I had not worked on many technologies but the basics were good ( Atleast I think so.. 🙂 )..  My interviewer told during the interview,” We need someone with exposure to J2EE , but you know only core Java.” . During interview I was very clear on what I knew and what I wanted to learn. I made it clear, ” I know I am not good at J2EE. But I need an opportunity to work on that. I want to be exposed to all kinds of technologies not just limited to basic stuffs”. Probably I had the fear that even if I am selected, I might be considered only for bug fixing, support and my chances to work on new technologies would be very limited.

Probably the new position was required to be filled very soon and my attitude to learn new things made the interviewer think me as the prospect candidate for the position. I was given the offer letter and I joined there.

3.5 months down the line – its the time for organisational half-yearly performance evaluation. By this time, I had put some effort to get aligned with the project. I am trying to learn new things. I know as and when I get chances to work on them I can learn better but trying to prepare myself. When it came to my turn, my supervisor said – “I think we have made the correct choice by choosing you. You are learning things and sharing it . That is good !! It is difficult for each one of us to learn everything. Sharing is very helpful in this field. You can learn technical skills  as you grow but the attitude cannot be learnt. It comes from the environment where you come from”. I was glad to hear that because the project I am into have people who have very good technical knowledge and vast experience. I am just a novice who is learning things and experimenting them around everyday.

So what is more important – your attitude or just the skill sets? I believe – definitely the skills are very important but your attitude makes the difference. Having a better attitude towards the things can make you grow faster. Finding an opportunity and working on improving yourself is important.

So what is your priority – attitude or skills ? 🙂

ActiveMQ – My First Example

Hello and welcome after a very long time !!

There are lots of things that I want to post but as of now, would post my first example code with active mq.

Active MQ – This is a open source message broker with full JMS implementation.

You can please read more details from : http://activemq.apache.org/

First step : Download and unzip apache-activemq-5.11.1-bin binary files to a drive.

Second step: Installation
————–
Run the ActiveMQ batch inside the win32 folder.
http://localhost:8161/
Testing the installation
————————
Active MQ default port is 61616

From cmd prompt

netstat -an|find “61616”

Monitoring ActiveMQ
——————-
The default username and password is admin/admin.
You can configure this in the conf/jetty-real.properties file.
Stopping ActiveMQ
——————
Type Ctrl-C at the cmd prompt.

Now open Eclipse and create a Message Producer, Message consumer and a main class. Complete codes are posted here. These are taken from the active mq website and can be modified accordingly.

Add activemq-all-5.4.3.jar in the class path.

HelloProducer.java

========================================================================================================================================================

package com.Active_MQ;

import java.awt.font.TextMeasurer;

import javax.jms.Connection;
import javax.jms.DeliveryMode;
import javax.jms.Destination;
import javax.jms.MessageProducer;
import javax.jms.Session;
import javax.jms.TextMessage;

import org.apache.activemq.ActiveMQConnectionFactory;

public class HelloProducer implements Runnable{

@Override
public void run() {
// TODO Auto-generated method stub
try {
//Creating connection factory
ActiveMQConnectionFactory connectionFactory = new ActiveMQConnectionFactory(“tcp://localhost:61616”);

//ActiveMQConnectionFactory connectionFactory = new ActiveMQConnectionFactory(ActiveMQConnectionFactory.DEFAULT_BROKER_URL);

//Create connection
Connection connection = connectionFactory.createConnection();
connection.start();

//Create session
Session session = connection.createSession(false,Session.AUTO_ACKNOWLEDGE);

//Create destination
Destination destination = session.createQueue(“TEST.FOO”);

MessageProducer producer = session.createProducer(destination);

producer.setDeliveryMode(DeliveryMode.NON_PERSISTENT);

//Create a message

String text = “Hello world from ” + Thread.currentThread().getName()+” : ” + this.hashCode();
TextMessage message = session.createTextMessage(text);

//Tell the producer to send the message

System.out.println(“Sent message ” + message.hashCode() + ” : ” + Thread.currentThread().getName());

producer.send(message);

//Clean up

session.close();
connection.close();

} catch (Exception e) {
e.printStackTrace();
}
}

}

============================================================================
============================================================================

HelloConsumer.java

========================================================================================================================================================

package com.Active_MQ;

import javax.jms.Connection;
import javax.jms.Destination;
import javax.jms.ExceptionListener;
import javax.jms.Message;
import javax.jms.MessageConsumer;
import javax.jms.Session;
import javax.jms.TextMessage;

import org.apache.activemq.ActiveMQConnectionFactory;
public class HelloConsumer implements Runnable{
public void run()
{
try {
ActiveMQConnectionFactory connectionFactory = new ActiveMQConnectionFactory(“tcp://localhost:61616”);

Connection connection = connectionFactory.createConnection();

connection.start();
//connection.setExceptionListener((ExceptionListener) this);

Session session = connection.createSession(false,Session.AUTO_ACKNOWLEDGE);

Destination destination = session.createQueue(“TEST.FOO”);

MessageConsumer consumer = session.createConsumer(destination);

Message message = consumer.receive(1000);

if (message instanceof TextMessage) {
TextMessage textMessage = (TextMessage) message;
String text = textMessage.getText();
System.out.println(“Received “+text);

}
else
{
System.out.println(“Received “+message);
}

consumer.close();
session.close();
connection.close();

} catch (Exception e) {
e.printStackTrace();
}
}

}

========================================================================================================================================================

App.java

========================================================================================================================================================

package com.Active_MQ;

public class App {
public static void main(String[] args) {
try {
thread(new HelloProducer(),false);
thread(new HelloProducer(),false);
thread(new HelloConsumer(),false);
Thread.sleep(1000);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
Thread.sleep(1000);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
thread(new HelloConsumer(), false);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
thread(new HelloProducer(), false);
Thread.sleep(1000);
thread(new HelloProducer(), false);
thread(new HelloConsumer(), false);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
thread(new HelloConsumer(), false);
thread(new HelloConsumer(), false);
thread(new HelloProducer(), false);
} catch (Exception e) {
e.printStackTrace();
}

}

public static void thread(Runnable runnable,boolean deamon)
{
Thread brokerThread = new Thread(runnable);
brokerThread.setDaemon(deamon);
brokerThread.start();
}

}

========================================================================================================================================================

Now when we run the main class output shows as :

========================================================================================================================================================

Sent message 700549 : Thread-1
Sent message 7702079 : Thread-0
Received Hello world from Thread-0 : 10859927
Sent message 14397555 : Thread-10
Received Hello world from Thread-1 : 18709978
Sent message 12968500 : Thread-12
Received Hello world from Thread-10 : 28432383
Sent message 12606869 : Thread-20
Sent message 29596937 : Thread-24
Sent message 32819228 : Thread-25
Received Hello world from Thread-12 : 19520119
Received Hello world from Thread-20 : 17982827
Received Hello world from Thread-25 : 24829876
Sent message 10565194 : Thread-43
Sent message 32734483 : Thread-33
Received Hello world from Thread-24 : 23815485
Sent message 25663554 : Thread-40
Sent message 19368064 : Thread-46
Sent message 26051994 : Thread-36
Received Hello world from Thread-33 : 32729846
Received Hello world from Thread-46 : 3333237
Received Hello world from Thread-43 : 3117096
Received Hello world from Thread-40 : 11203640
Received Hello world from Thread-36 : 7522198

========================================================================================================================================================

When I open my web console then I can see queue TEST.FOO is created and messages are enqueued and dequeued.

I am trying to test some more examples with Active MQ and will keep posting the same.

Till then, Happy coding !! 🙂