Category Archives: Data Structures

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 🙂