Technical

Missing Element In given AP

2014-12-26T00:19:00.001-08:00

Problem Statement :

Print the missing integer/element in a given AP (Arithmetic Progression).

Explanation :

First input K to the program will be number of elements which will be given.
second input will be K numbers/integers of an AP in order. Its just that one of the term would be jumped i.e.

An input like following is valid input

5
1, 5, 9, 17, 21

First input shows that there will be 5 elements given(Minimum 3 elements haqas to be given). Second input is the actual AP. In the AP series please note that number 13 is jumped and instead 17 has been given at its place and there after AP goes on as normal i.e. printing 21 which actually comes after 17.

Solution :-

Steps :
1) Find the d i.e. common difference : for this take the differences of second and first element and compare this with the different of third and second element. If the differences are equal then that will be the common difference. else, add the differences and divide it by 3 and result will be the common difference! (Why??? Try doing it and you may get the clue).

2) Add the given AP series to get SUM1. Calculate the Sum which should have been if the AP would have the right numbers in given series, Let this be SUM2.

we know that if we have jumped at position ith then

Sum1 - Sum2 = Sum1 + ((k-i) * (d))

solve this equation to get the equation used in the solution. Please let me know if something is not clear as I would be more than happy to help! :)

package main.HackerRank;

import java.util.Scanner;

/**
* Created by dhiraj on 26/12/14.
*/
public class Solution_MissingElementInAP {

public static void main(String[] str){
printMissingElement();
}

static void printMissingElement(){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] intArray = new int[n];
long sum = 0;
for(int t = 0; t < n; t++) {
intArray[t] = sc.nextInt();
sum += intArray[t];
}
//System.out.println(sum);

int d = intArray[1] - intArray[0];
int d2 = intArray[2] - intArray[1];
if(d != d2){
d = (d+d2)/3;
}
//System.out.println(d);

long expectedSum = n*intArray[0];
expectedSum += (((n*n) - n ) * d)/2;

int t = n - (int)((sum - expectedSum)/d);

System.out.println("Element : " + intArray[t]);
}
}

2014-05-28T08:02:00.001-07:00

Problem Statement : Write a Method in java to find the total number of 2's between o and n numbers. i.e. If we are given number 9 then total number of 2's between 0 to 9 is 1. If we are given number 100 then total number of 2's between the 0 till 100 will be 20 and so on

Solution :

Its a recursive solution.

/**
* Created by Dhiraj.Kumar on 5/28/2014.
*/
public class calculateNumberOf2s {
    public static void main(String[] str) {
        int input = 202;
        System.out.println(input + " :: " + calculateNumberOf2sRecurs(input));

    }

    private static int calculateNumberOf2sRecurs(int input) {
        //base case
        if (input == 0) {
            return 0;
        }
        //represent the variable in appropriate form
        int base = 1;
        while (input / base > 10) base *= 10;
        int a = input / base;
        int b = input % base;
        //calculate the number of twos
        int numberOf2s = (a * calculateNumberOf2sRecurs(base - 1)) + calculateNumberOf2sRecurs(b) + (a > 2 ? base : a == 2 ? (b + 1) : 0);

        return numberOf2s;
    }
}

Merge two sorted Arrays

2013-06-15T14:46:00.000-07:00

Merge two sorted Arrays where its given that the first array has got free space at the end just enough to accommodate the second array.

public class MergeTwoSortedArrays {

 public static void main(String[] args) {

  int[] a = {1, 2, 5, 9, 14, 0 ,0 ,0 ,0 , 0, 0, 0 , 0};

  int[] b = {-12, -8, 0, 3, 8, 10, 11, 12};

  int indexA   = a.length - b.length - 1;

  int indexB   = b.length - 1;

  int lastIndex  = a.length - 1;

  while(indexA >= 0 && indexB >= 0){

   if(a[indexA] > b[indexB])

    a[lastIndex--] = a[indexA--];

   else

    a[lastIndex--] = b[indexB--];

}

  while(indexB >= 0)

   a[lastIndex--] = b[indexB--];

  for(int i : a){

   System.out.print(i + " , ");

}

}

}

Print All Subset of a given Set

2013-06-15T06:52:00.001-07:00

Problem Statement : Print All The Subset Of A Given Set Of Integers.

Its O(2^n) space and time complex implementation. ***May be a bit more than that in order to print the formatted subsets.

package permutationRelatedProblems;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

import java.util.Set;

import java.util.TreeSet;

public class AllSubsetOfASet {

 public static void main(String[] args) {

  Set<Integer> input = new TreeSet<Integer>();

  input.add(1);

  input.add(2);

  input.add(3);

  input.add(4);

  input.add(5);

  Integer[] intArray = input.toArray(new Integer[0]);

  List<List<Integer>> subsetList = new ArrayList<List<Integer>>();

  subsetList = getAllSubsets(intArray, subsetList, 0);

  printTheSubsetList(subsetList);

}

 private static void printTheSubsetList(List<List<Integer>> subsetList) {

  System.out.println("Subsets Are :");

  System.out.print("{} , ");

  int count = 1;

  Iterator<List<Integer>> iterator = subsetList.iterator();

  StringBuffer stringBuffer = null;

  while(iterator.hasNext()){

   count++;

   List<Integer> subset = iterator.next();

   stringBuffer = new StringBuffer();

   stringBuffer.append("{");

   for(Integer e : subset){

    stringBuffer.append(e + ",");

}

   stringBuffer.replace(stringBuffer.length() - 1, stringBuffer.length(), "");

   System.out.print(stringBuffer.toString() + "} , ");

}

  System.out.println();

  System.out.println("Count : " + count);

}

 private static List<List<Integer>> getAllSubsets(Integer[] input,

   List<List<Integer>> subsetList, int index) {

  if(index == input.length)

   return subsetList;

  int e = input[index];

  subsetList = getAllSubsets(input, subsetList, ++index);

  List<List<Integer>> temp = new ArrayList<List<Integer>>();

  for(int i = 0 ; i < subsetList.size(); i++){

   List<Integer> subset = subsetList.get(i);

   List<Integer> tempSubset = new ArrayList<Integer>();

   tempSubset.add(e);

   tempSubset.addAll(subset);

   subset = null;

   temp.add(i, tempSubset);

}

  ArrayList<Integer> newEntry = new ArrayList<Integer>();

  newEntry.add(e);

  temp.add(newEntry);

  subsetList.addAll(temp);

  return subsetList;

}

}

Represent a given number using 1,2 and 3 only

2013-04-22T11:25:00.001-07:00

Problem Statement :-

given a number, return possible combinations of constructing that number with 1,2 and 3
e.g.
input: 12 --> output=19,

Input - 8
Output - 10
Explanation - Following are the possible combinations for team score of 8
1x8
1x6 + 2x1
1x4 + 2x2
1x2 + 2x3
2x4
1x5 + 3x1
1x3 + 2x1 + 3x1
1x1 + 2x2 + 3x1
1x2 + 3x2
2x1 + 3x2

Solution not only counts the number of combinations but also prints the combination possible in the form of 1*x + 2*y + 3*z

Solution :-

/**
*
* @author dhirajk
*
*/

public class CombinationOf123 {

    static int numberOfCombinationsPossible = 0;

    public static void main(String[] args) {
       int input = 8;
       for(int z = 0; z <= input/3; z++){
           int leftover = input - (z * 3);
           int temp = leftover;
           for(int y = 0; y <= leftover/2 ; y++){
               temp = leftover - (y * 2);
               int x = 0;
               if(temp < 0){
                   continue;
               }else if(temp > 0){
                   x = temp;
               }
               printConfiguration(x, y, z);
               numberOfCombinationsPossible++;
           }
       }
       System.out.println("Number of Possible Combinations are : " + numberOfCombinationsPossible);
    }

    private static void printConfiguration(int x, int y, int z) {
       System.out.println(" 1 * " + x + " + 2 * " + y + " + 3 * "+ z);
    }

}

Given K Sorted Sequences merge them to get the final sequence

2013-04-19T14:50:00.000-07:00

Problem Statement :-

We are given K sorted sequences each containing N elements. Write an algorithm to merge these all to get final sorted sequence. If question asks that what about non sorted sequences, then we may like to sort them before applying this solution.

Solution Description :-

Take a min heap of size K. Let us define Node as an object which contains two information, first information is the value which we are considering and second the index of the sequence to which this value belongs. For example if we are taking ith element of the jth sequence then out node will have both of these information.

Now initialize the heap with 0th i.e. first value of each of the k sequences.

Repeat till heap is empty. remove the minimum node from the heap, here minimum node should be the one which has lowest value among all the nodes present in the heap. add this value in the final sequence. the node which has been removed from the heap has the array information to which this value belongs. add next element of that particular array to the heap and continue.

I am using the Heap implementation which i have explained with source code in my last post. so if you copy this code to your IDE, please copy that implementation too.

package heap;

import java.util.Arrays;

/**
*
* @author dhirajk
*
*/
public class MergeKSortedSequencesWithNElements {

    public static void main(String[] args) {
        //Value of k, number of arrays and n, number of elements in each of the array
        int k = 5, n=9;
        //Input in the form of two dimensional array
        int[][] input = new int[][]{{1, 6, 12, 18, 24, 30, 36, 42, 48},
                                    {2, 7, 13, 19, 25, 31, 37, 43, 49},
                                    {3, 8, 14, 20, 26, 32, 38, 44, 50},
                                    {4, 9, 15, 21, 27, 33, 39, 45, 51},
                                    {5, 10, 16, 22, 28, 34, 40, 46, 52}};
        //array to maintain the index for each array which we will add to heap next
        //i.e. ith element of this array is index of the element in input[i] which will be added next to the heap
        int[] indexesOfEachArray = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};

        //output array
        int[] output = new int[k*n];
        int outputIndex = 0;


        //populate heap
        Heap<Node> minimumHeap = new MinHeap<>(new Node[k]);
        for(int i = 0; i < k; i++){
            minimumHeap.addToHeap(new Node(i, input[i][0]));
            indexesOfEachArray[i]++;
        }

        //loop till Heap is empty
        while(!minimumHeap.isEmpty()){
            Node node = minimumHeap.remove();
            output[outputIndex++] = node.getValue();
            int arrayIndex = node.getIndexOfArrayInTheInputArray();
            if(indexesOfEachArray[arrayIndex] < n ){
                Node nodeTobeAdded = new Node(arrayIndex,
                        input[arrayIndex][indexesOfEachArray[arrayIndex]]);
                minimumHeap.addToHeap(nodeTobeAdded);
                indexesOfEachArray[arrayIndex]++;//increase the index to point to next element
            }
        }

        //print the final output

        System.out.println(Arrays.toString(output));
    }

    private static class Node implements Comparable<Node>{
        private int indexOfArrayInTheInputArray;
        private Integer value;

        Node(int indexOfArrayInTheInputArray, int value){
            this.indexOfArrayInTheInputArray = indexOfArrayInTheInputArray;
            this.value = value;
        }

        public int getIndexOfArrayInTheInputArray() {
            return indexOfArrayInTheInputArray;
        }

        public int getValue() {
            return value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value.compareTo(o.getValue());
        }


    }

}

Simple Heap Implemenation in Java

2013-04-19T13:32:00.003-07:00

This is very simple heap implementation in java. I have implemented it as I am going to solve few trending questions using this implementation.

DISCLAIMER :- Note here that Ideally, We would like to have implementation of heap to be backed by an array of objects which is private to it. But here I am not concentrating on best practices( for example :- even the array on which heap will be created is provided by the client code! Ooouch...but that is fine with me ). More over, its not grow able nor is thread safe....its just plain simple implementation which will help me in solving few of the DS/Algorithmic problems!

In short Heap is mainly a Data Structure which is used for organizing data in such a manner that retrieving minimum or maximum of the elements take constant time i.e. O(1). Insertion and Deletion takes O(log N);

I will leave the theory as there are plenty of references for that an I don't consider myself very good with writing theories! :(

Here is the implementation. There is an interface and an Implementation of MinHeap which is capable of returning the minimum element at any given moment of the time. Third class is the test class.

package heap;

/**
*
* @author dhirajk
*
* @param <T>
*/
public interface Heap<T extends Comparable<T>> {

    void addToHeap(T element);

    T remove();

    T top();

    void heapify() ;

    void heapifyOnDelete();

    boolean isEmpty();
}

package heap;

import java.util.Arrays;

/**
*
* @author dhirajk
*
* @param <T>
*/
public class MinHeap<T extends Comparable<T>> implements Heap<T>{

    final T[] heap;
    int index = -1;

    public MinHeap(T[] heap) {
        this.heap = heap;
    }

    @Override
    public void addToHeap(T element) {
        //add to heap
        if(index >= heap.length-1){
            System.out.println("Heap Is full!");
            return;
        }
        heap[++index] = element;
        heapify();
    }

    @Override
    public T top() {
        if(index < 0){
            System.out.println("Heap is empty!");
            return null;
        }
        return heap[0];
    }

    @Override
    public T remove() {
        T element = top();
        if(element != null){
            heap[0] = heap[index];
            index--;
            heapifyOnDelete();
        }
        return element;
    }


    public void heapify() {
        int startPoint = index;
        while(startPoint > 0){
            int parentIndex = (startPoint-1)/2;
            if(heap[parentIndex].compareTo(heap[startPoint]) > 0){
                T temp = heap[parentIndex];
                heap[parentIndex] = heap[startPoint];
                heap[startPoint] = temp;
                startPoint = parentIndex;
            }else{
                return;
            }
        }
    }

    @Override
    public void heapifyOnDelete() {
        int startPoint = 0;
        while(startPoint <=index){
            int indexOfLeftChild = 2 * startPoint + 1;
            int indexOfRightChild = 2 * startPoint + 2;
            boolean isMinimum = true;;
            if(indexOfLeftChild <= index && heap[startPoint].compareTo(heap[indexOfLeftChild]) >= 0){
                isMinimum = false;
            }

            if(isMinimum && indexOfRightChild <= index &&
                    heap[startPoint].compareTo(heap[indexOfRightChild]) >= 0){
                isMinimum = false;
            }

            if(isMinimum)
                return;

            T element = heap[startPoint];
            if(indexOfRightChild <= index){
                //see which one is smaller among the two and copy that to the root
                if(heap[indexOfLeftChild].compareTo(heap[indexOfRightChild]) < 0){
                    heap[startPoint] = heap[indexOfLeftChild];
                    heap[indexOfLeftChild] = element;
                    startPoint = indexOfLeftChild;
                }else{
                    heap[startPoint] = heap[indexOfRightChild];
                    heap[indexOfRightChild] = element;
                    startPoint = indexOfRightChild;
                }
            }else{
                heap[startPoint] = heap[indexOfLeftChild];
                heap[indexOfLeftChild] = element;
                startPoint = indexOfLeftChild;
            }
        }
    }

    public boolean isEmpty(){
        return index < 0;
    }

    @Override
    public String toString() {
        return "MinHeap [heap=" + Arrays.toString(heap) + ", index=" + index
                + "]";
    }
}

package heap;

/**
*
* @author dhirajk
*
*/
public class HeapTest {

    public static void main(String[] args) {
        Heap<Integer> heap = new MinHeap<>(new Integer[20]);
        heap.addToHeap(5);
        System.out.println(heap);
        heap.addToHeap(15);
        System.out.println(heap);
        heap.addToHeap(4);
        System.out.println(heap);
        heap.addToHeap(1);
        System.out.println(heap);
        heap.addToHeap(0);
        System.out.println(heap);
        heap.addToHeap(30);
        System.out.println(heap);
        heap.addToHeap(20);
        System.out.println(heap);
        heap.addToHeap(0);
        System.out.println(heap);
        System.out.println("********************************************************************");
        while(!heap.isEmpty()){
            System.out.println(heap.remove());
            System.out.println(heap);
        }
    }

}

Pairs

2013-04-05T10:49:00.003-07:00

GIVEN N NUMBERS FIND NUMBER OF PAIRS WHICH HAVE A DIFFERENCE OF K.

Input Format:
1st line contains N & K (integers). WHERE N IS NUMBER OF ELEMENTS AND K IS DIFFERENCE
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.
Sample Input:
4 10
10 20 30 40
Sample Output #00:
3

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] input = new String[2];
        String s;
        int i = 0;
        try {
            while ((s = in.readLine()) != null && s.length() != 0){
                input[i++] = s;
            }
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        i = 0;
        int difference = Integer.parseInt(input[0].split(" ")[1].trim());
        int[] sequence = new int[Integer.parseInt(input[0].split(" ")[0].trim())];
        if(sequence.length == 0)
        {
            System.out.println(0);
            return;
        }
        for(String temp : input[1].split(" ")){
            sequence[i++] = Integer.parseInt(temp.trim());
        }

        quickSort(sequence, 0, sequence.length-1);

        int numberOfPairs = getNumberOfPairs(sequence, difference);
        System.out.println(numberOfPairs);
    }

    private static int getNumberOfPairs(int[] sequence, int difference) {
        int startpoint = 0;
        int countOfPairs = 0;
        while(startpoint < sequence.length){
            int toSearch = sequence[startpoint] + difference;
            for (int index = startpoint + 1; index < sequence.length; index++) {
                if (sequence[index] == toSearch)
                    countOfPairs++;
                else if (sequence[index] > toSearch)
                    break;
            }
            startpoint++;
        }
        return countOfPairs;
    }

    static void quickSort(int[] ar, int startPoint, int endPoint) {
        int partitionIndex = partition(ar, startPoint, endPoint);
        if (partitionIndex < 0 || startPoint >= ar.length)
            return;
        if (partitionIndex > 0) {
            quickSort(ar, startPoint, partitionIndex - 1);
        }
        if (partitionIndex + 1 < endPoint) {
            quickSort(ar, partitionIndex + 1, endPoint);
        }
    }

    static int partition(int[] ar, int startPoint, int endPoint) {
        if (ar == null || endPoint - startPoint <= 0)
            return -1;

        int partionValue = ar[startPoint];
        int indexOfPartitionValue = startPoint;
        int index = startPoint + 1;

        do {
            if (ar[index] < partionValue) {
                int temp = ar[index];
                for (int i = index; i > indexOfPartitionValue; i--) {
                    ar[i] = ar[i - 1];
                }
                ar[indexOfPartitionValue] = temp;
                indexOfPartitionValue++;
            }
            index++;
        } while (index <= endPoint);

        return indexOfPartitionValue;
    }
}

QuickSort

2013-04-05T10:43:00.000-07:00

In Memory Quick Sort implementation in java. pivot has been kept as the first element of input array(We can easily extend this to keep pivot as last element or random element). I am printing each the sub arrays after each full cycle of partioning. Main method is redundant and is just for running test with one array.

import java.util.Arrays;

public class QuiclSort {

    public static void main(String[] args) {
        int[] input = new int[] { 5, 8, 1, 3, 7, 9, 2 };

        quickSort(input, 0, input.length - 1);
        System.out.println(Arrays.toString(input));
    }

    static void quickSort(int[] ar, int startPoint, int endPoint) {
        int partitionIndex = partition(ar, startPoint, endPoint);
        if (partitionIndex < 0 || startPoint >= ar.length)
            return;
        if (partitionIndex > 0) {
            quickSort(ar, startPoint, partitionIndex - 1);
        }
        if (partitionIndex + 1 < endPoint) {
            quickSort(ar, partitionIndex + 1, endPoint);
        }
        print(Arrays.copyOfRange(ar, startPoint, endPoint + 1));
    }

    static int partition(int[] ar, int startPoint, int endPoint) {
        if (ar == null || endPoint - startPoint <= 0)
            return -1;

        int partionValue = ar[startPoint];
        int indexOfPartitionValue = startPoint;
        int index = startPoint + 1;

        do {
            if (ar[index] < partionValue) {
                int temp = ar[index];
                for (int i = index; i > indexOfPartitionValue; i--) {
                    ar[i] = ar[i - 1];
                }
                ar[indexOfPartitionValue] = temp;
                indexOfPartitionValue++;
            }
            index++;
        } while (index <= endPoint);

        return indexOfPartitionValue;
    }

    private static void print(int[] ar) {
        for (int a : ar) {
            System.out.print(a + " ");
        }
        System.out.println();
    }
}

Find the maximum element in a stack in O(1) time complexity and O(n) space complexity

2013-03-10T03:06:00.000-07:00

Problem statement :-

We need to give the maximum element among the content of a stack. Time complexity :- O(1) Space Complexity :- not to exceed O(n)

Solution :-

As per all my older posts on stack , This too uses classes implemented in my post :- Array Based Stack Implementation

Basic implementation is of just 10-15 lines of code but as my earlier posts, I have written my test cases in main method itself and that's why implementation may be looking bigger!

The algorithm/strategy is explained in the comment part of the class implementation. For readability perspective copy paste the code in you IDE.

package stackRelatedProblems;

import javax.naming.OperationNotSupportedException;

/**
*
* Lets jump to solution strategy. We will maintain two stacks, one will have the elements which
* has been asked to push i.e. it will be our primary stack which will contain all of the elements.
* Second stack will be the one which will contain the highest elements found so far. Confused!!!
* Let us go in deep of this algorithm
*
* Lets say that the first element asked to push is x. we will push this in the primary stack.
* Now we will compare this element with the top of our secondary stack, since its empty too,
* we will push it in that stack too. Now for subsequent push request, we will keep pushing
* elements in the primary stack and will push it in the secondary stack if and only if, its
* greater than or equal to the top element of the secondary stack.
*
* For pop, we will pop the element from the primary stack. We will compare this element with the
* top element of the secondary stack, if both are equal, we will call pop on the secondary stack too
* else will not change(pop) the secondary stack at all.
*
* This way, we will always have the biggest element of primary stack as the top element in the
* secondary stack....
*
* Same logic can be applied to get lowest element.
*
* @author dhirajk
*
*/

public class PrintBiggestElementAtAnyGivenPointInAStack {

    public static void main(String[] args) throws OperationNotSupportedException {
       Stack<Integer> inputStack = new StackArrayImplementation();
       Stack<Integer> stackContainingTheBiggestElement = new StackArrayImplementation();
       pushElement(inputStack, stackContainingTheBiggestElement, 1);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 20);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 15);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 9);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 20);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 17);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 20);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 21);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 28);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 26);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 41);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       pushElement(inputStack, stackContainingTheBiggestElement, 40);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());

       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());
       popElement(inputStack, stackContainingTheBiggestElement);
       System.out.println("Stack :- " + inputStack + " Largest Element : " + stackContainingTheBiggestElement.top());

    }

    private static void popElement(Stack<Integer> inputStack,
           Stack<Integer> stackContainingTheBiggestElement) throws OperationNotSupportedException{
       int poppedOutElement = inputStack.pop();
       if(poppedOutElement == stackContainingTheBiggestElement.top())
           stackContainingTheBiggestElement.pop();
    }

    private static void pushElement(Stack<Integer> inputStack,
           Stack<Integer> stackContainingTheBiggestElement, int i) throws OperationNotSupportedException {
       inputStack.push(i);
       if(stackContainingTheBiggestElement.isEmpty()){
           stackContainingTheBiggestElement.push(i);
       }else{
           if(stackContainingTheBiggestElement.top() <= i)
               stackContainingTheBiggestElement.push(i);
       }
    }

}

Reverse the Elements of a Stack

2013-03-10T01:34:00.000-08:00

Problem Statement :-

Write a program to reverse the elements of a stack without using any other stack or data structure. few fixed number of variables can be used i.e. space complexity must be O(1)

Solution :-

I am pasting the solution here. Stack used by me is my own implementation of stack and source code can be found in one of my blog with url as Array Based Implementation of Stack

I have explained the algo/pseudo code in the comment of the implementation. For better readability, copy paste the code in IDE.

Its a recursive solution which have time complexity of O(n2) i.e. order n square.

package stackRelatedProblems;

import javax.naming.OperationNotSupportedException;

/**
* Reverse the elements of a stack without using extra space i.e. explicitly defined
* extra space!
*
* This recursive way of doing reversing the stack is O(n2) time complex and in place algorithm.
* Basic idea/logic is that for each value of i = 2, 3,...till the size of the stack, keep reversing the
* elements from the top till i. After each iteration we will have top i elements reversed in the stack.
*
* So the Algorithm/Pseudo code can be outlined as :_
*
* Main Method
*
* 1) (GLOBAL VARIABLES) lastElementPoppedOutOfTheStack = -1, isPushingTheLastElement = false;
* 2) repeat for i = 2, 3, 4,..., sizeOfTheStack
*         a) Call the methode reverseTheStack(stack, i)
*         b) stack.push(lastElementPoppedOutOfTheStack)
*
*
* reverseTheStack(stack, i)
* 1)isPushingTheLastElement = true;
* 2)if(1 > 0)
*         a) x = stack.pop();
* 3) else
*         a) return;
* 4) if(i == 1)
*         a) lastElementPoppedOutOfTheStack = x;
* 5) call reverseTheStack(stack, ++i);
* 6) call pushTheElementBack(stack, x)
*
*
* pushTheElementBack(stack, x)
*
* 1)if(!isPushingTheLastElement)
*         a) stack.push(x);
* 2) else
*         a) isPushingTheLastElement = false
*
* @author dhirajk
*
*/

public class ReverseAStack {

    static Integer lastToBePushed = -1;
    static int sizeOfThestack;
    static boolean isPushingTheLastElement = false;

    public static void main(String[] args) throws OperationNotSupportedException {
        Stack<Integer> stackOfInteger = new StackArrayImplementation();
        stackOfInteger.push(1);
        stackOfInteger.push(2);
        stackOfInteger.push(3);
        stackOfInteger.push(4);
        stackOfInteger.push(5);
        stackOfInteger.push(5);
        stackOfInteger.push(1);
        sizeOfThestack = stackOfInteger.size();
        System.out.println("Before reversing : " + stackOfInteger);
        for(int i = 2; i <= sizeOfThestack; i++) {
            reverseTheStack(stackOfInteger, i);
            stackOfInteger.push(lastToBePushed);//Push the last popped out element
            System.out.println("i : = " + i + " Stack : " + stackOfInteger);
        }
        System.out.println("After Reversing : " + stackOfInteger);
    }

    private static void reverseTheStack(Stack<Integer> stackOfInteger, int i) throws OperationNotSupportedException {
        int x;
        isPushingTheLastElement = true;
        if(i > 0){
            x = stackOfInteger.pop();
        }else{
            return;
        }

        if(i == 1){
            lastToBePushed = x;
        }
        reverseTheStack(stackOfInteger, --i);

        pushTheElementBack(stackOfInteger, x);
    }

    private static void pushTheElementBack(Stack<Integer> stackOfInteger, Integer x) {
        if(!isPushingTheLastElement){
            stackOfInteger.push(x);//Check makes sure that we do not push the last element popped out of the stack. This one will be pushed as last
        }else{
            isPushingTheLastElement = false;
        }
    }

}

Implement Queue using two Stacks

2013-03-04T19:20:00.000-08:00

Java implementation of a queue using two stacks. Stack implementation is not been given here but can be retrieved from my older post http://technicalstuffbydhiraj.blogspot.in/2013/02/array-based-stack-implementation.html

Here is the simple implementation in java

package stackRelatedProblems;

import javax.naming.OperationNotSupportedException;

/**
* Implement a queue using stack/stacks
*
* @author dhirajk
*
*/

public class QueueImplementaionUsingStacks {

    private Stack<Integer> inputStack, outputStack;

    public QueueImplementaionUsingStacks() {
        inputStack = new StackArrayImplementation();
        outputStack = new StackArrayImplementation();
    }

    public void enque(int element){
        inputStack.push(element);
    }

    public int dequeue() throws OperationNotSupportedException{
        if(outputStack.isEmpty()){
            if(inputStack.isEmpty()){
                throw new OperationNotSupportedException("No element to deque");
            }
            while(!inputStack.isEmpty()){
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.pop();
    }


    //Test using a main method
    public static void main(String[] args) throws OperationNotSupportedException {
        QueueImplementaionUsingStacks queue = new QueueImplementaionUsingStacks();
        queue.enque(10);
        queue.enque(11);
        queue.enque(12);
        queue.enque(13);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        queue.enque(14);
        queue.enque(15);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());

    }
}

To Check whether a given String has duplicate characters or not

2013-02-28T02:22:00.000-08:00

Problem statement :- Given a String(simple String and not sentence, though this can be extended for sentences too!) find if all the characters are unique or not.

I have not implemented it a way to take input from console but it would be piece of cake for any one to extend the program to do that.

The first implementation uses a set to check if all the characters are unique or not! We may also use a hashmap/array to get the intended result. Implementation in a O(n) time complex with O(n) space requirement, where n is the number of the characters in the string.

Second implementation requires no extra memory at all but is O(nlog(n)) complex.

Copy paste the class in your IDE to make the class more readable.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
*
*
* @author dhirajk
*
*/
public class DoStringHasAllUniqueCharacters {

    public static void main(String[] args) {
        String input = "TestString";
        boolean duplicate = false;
        //With a data structure
        // O(n)
        System.out.println("********************* Using Set *************************");
        Set<Character> set = new HashSet<Character>();
        for(char characterValue : input.toCharArray()){
            if(!set.add(characterValue)){
                System.out.println("String has got duplicate characters. First one is : " + characterValue);
                duplicate = true;
                break;
            }
        }
        if(!duplicate){
            System.out.println("String does not contains any duplicate charater!");
        }
        duplicate = false;


        //Without any data structure
        //sort the string based on the characters it contain and then see if any two consecutive
        //characters are same! its a O(n + nlog(n)) algo ~ O(nlog(n))


        System.out.println("********************* Without Using any data structure *************************");
        char[] characters = input.toCharArray();
        Arrays.sort(characters);//Use any sorting algo
        for(int i = 0 ; i < characters.length -1; i++){
            if(characters[i] == characters[i+1]){
                System.out.println("String has got duplicate characters");
                duplicate = true;
                break;
            }
        }

        if(!duplicate){
            System.out.println("String does not contains any duplicate charater!");
        }
        duplicate = false;
    }

}

Span of share Problem

2013-02-27T06:54:00.000-08:00

The problem statement as well as description is elaborated in the class comment.

package stackRelatedProblems;

import java.util.Arrays;

import javax.naming.OperationNotSupportedException;

/**
*
* NOTE :- QUESTION IS TAKEN FROM NAVEEN GARG'S LECTURE WHICH IS AVAILABLE ON INTERNET
* Question :-
*
* span-of-share on a particular day X is defined as "Number of day the share value have been lesser than today's value(including today)" . Let us understand it with an example :-
* (Based on the example of data given below) on day 0 share value is 20, Since its the start date we say that span-of-share is 1 ;
* on day 1, share price is 30. If we see backward that is starting from day 0, today is second day when price has been equal to or less than 30...so span-of-share value for day 1 is 2
* on day 2, share price is 10, we will start looking at the share value on previous day i.e. day 1. value was 30 i.e. greater than today's value. hence, span-of-share for day 2 is 1
* on day 3, share price is 40, start scanning backward from day 2. as we can see that on day 2,1 and 0 values have been less than 40(today's value). hence today's span-of-share is 4
* Similarly for day 4, span-of-share is 5
* on day 5, value is 25. start scanning backward from previous day i.e. day 4. we can see that the value is greater than 25 hence, day 5 span-of-share is 1
*
* Let the share-value and span-of-share on different consecutive days are tabulated as follows :
*
* Share Price             :-        20    30    10    40    60    25    15    35    70
* Day(Starting from 0) :-        0    1    2    3    4    5    6    7    8
* span-of-share        :-        1    2    1    4    5    1    1    3    9
*
* problem statement is that given the above data(first two rows) we need to calculate the third row i.e. span-of-share for each day.
*
*
* One approach will be to scan backward for each value and hence calculate the span-of-share. but the best solution is using the stack!
* If we maintain a stack which contains only the candidates which should be considered to decide today's span-of-share value then our work can get easier!
*
* @author dhirajk
*
*/
public class SpanOfSharePricesProblem {

    public static void main(String[] args) throws OperationNotSupportedException {
        //the index in the array is day and the value is the price at that day;
        int[] input = {20,    30,    10,    40,    60,    25,    15,    35,    70, 70};

        int[] output = new int[input.length];

        output[0] = 1;

        Stack<Integer> stack = new StackArrayImplementation();
        Stack<Integer> indexStack = new StackArrayImplementation();
        stack.push(input[0]);
        indexStack.push(0);

        for(int i = 1; i < input.length; i++){
            int spanOfShare = 1;
            int lastElementInStackIndex = -1;
            while(!stack.isEmpty()){
                if(stack.top() >= input[i]){
                    break;
                }else{
                    stack.pop();
                    lastElementInStackIndex = indexStack.pop();
                    spanOfShare += output[lastElementInStackIndex];
                }
            }
            output[i] = spanOfShare;
            stack.push(input[i]);
            indexStack.push(i);
        }

        System.out.println(Arrays.toString(output));
    }

}

Array Based Stack Implementation

2013-02-27T05:52:00.000-08:00

Array Based implementation of the stack.

This stack implementation can grow its size if its full. The array used inside this implementation doubles itself if no slot is vacant for incoming data. The stack has an ability to shrink too if half of its slots are vacant. Simple test class is also attached with this blog.

The Stack Interface is as follows :-

package stackRelatedProblems;

import javax.naming.OperationNotSupportedException;

public interface Stack<T> {

    /**
    * isEmpty checks if the stack is empty
    *
    * @return true if stack is empty
    */
    boolean isEmpty();

    /**
    * push inserts an element at the top of the stack
    *
    * @param element
    */
    void push(T element);

    /**
    * Pop returns the element at the top
    *
    * @return Element at the top
    * @throws OperationNotSupportedException If the stack is empty
    */
    T pop() throws OperationNotSupportedException;

    /**
    * isFull returns true if stack is full
    *
    * @return true if stack has reached its capacity.
    */
    boolean isFull();

    /**
    * OperationNotSupportedException
    *
    * @return returns the element at top but never removes it from the stack
    * @throws OperationNotSupportedException If stack is empty
    */
    T top() throws OperationNotSupportedException;

    /**
    * size
    *
    * @return Size of the stack. By size, it means how many elements are present in the stack and not the capacity of the stack!
    */
    int size();
}

The Implementation is as follows :-

package stackRelatedProblems;

import java.util.Arrays;

import javax.naming.OperationNotSupportedException;

/**
* This stack implementation is based on array as inner data structure and the size is not fixed i.e.
* its a growable stack implementation where the array will grow if its full! It will also shrink if
* half of its spaces are empty!
*
*
* @author dhirajk
*
* @param
*/
public class StackArrayImplementation implements Stack<Integer>{

    private Integer[] arrayOfElements;
    private int topIndex;

    public StackArrayImplementation() {
        this.arrayOfElements = new Integer[1];
        topIndex = -1;
    }

    public boolean isEmpty() {
        return arrayOfElements != null && topIndex == -1;
    }

    public void push(Integer element) {
        if(arrayOfElements == null){
            throw new NullPointerException("Array of elements is null!");
        }

        if(isFull()){
            doubleTheArray();
        }

        arrayOfElements[++topIndex] = element;
    }



    public Integer pop() throws OperationNotSupportedException{
        if(!isEmpty()){
            if(topIndex+1 <= arrayOfElements.length/2){
                shrinkTheArrayByHalf();
            }
            return arrayOfElements[topIndex--];
        }else{
            throw new OperationNotSupportedException("The Stack is already empty. can not pop anything");
        }
    }

    public boolean isFull() {
        return (topIndex == arrayOfElements.length-1);
    }

    public Integer top() throws OperationNotSupportedException{
        if(!isEmpty()){
            return arrayOfElements[topIndex];
        }else{
            throw new OperationNotSupportedException("STack is empty, No top element to return");
        }
    }

    public int size() {
        return topIndex+1;
    }

    private void doubleTheArray() {
        //double the array.
        System.out.println("Increasing the size of the internal Array from : " + arrayOfElements.length + " to " + 2 * arrayOfElements.length + "! ");

        Integer[] newArrayOfElements = new Integer[2 * arrayOfElements.length];
        for(int i = arrayOfElements.length-1; i >=0; i--){
            newArrayOfElements[i] = arrayOfElements[i];
        }
        arrayOfElements = newArrayOfElements;
    }

    private void shrinkTheArrayByHalf() {
        //Shrink the array by half
        System.out.println("Decreasing the size of the internal Array from : " + arrayOfElements.length + " to " + arrayOfElements.length/2 + "! ");
        Integer[] newArrayOfElements = new Integer[arrayOfElements.length/2];
        for(int i = topIndex; i >=0; i--){
            newArrayOfElements[i] = arrayOfElements[i];
        }
        arrayOfElements = newArrayOfElements;
    }

    @Override
    public String toString() {
        return "StackArrayImplementation [arrayOfElements="
                + Arrays.toString(Arrays.copyOf(arrayOfElements, topIndex+1)) + ", topIndex=" + topIndex
                + ", [INFO] Size Of Internal Array is : " + arrayOfElements.length +"]";
    }


}

Simple test class with a main method :-

package stackRelatedProblems;

import javax.naming.OperationNotSupportedException;

public class TestStackArrayImplementation {
    public static void main(String[] args) {
        Stack<Integer> stack = new StackArrayImplementation();
        try{
            stack.pop();
        }catch(OperationNotSupportedException e){
            System.out.println(e);
        }

        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(80);
        stack.push(90);

        System.out.println("Stack :- " + stack);

        try{
            System.out.println("(1)Get first Element : " + stack.pop());
            System.out.println("Get The element at top : " + stack.top());
            System.out.println("(2)Get first Element : " + stack.pop());
            System.out.println("(3)Get first Element : " + stack.pop());
            System.out.println("(4)Get first Element : " + stack.pop());
            System.out.println("(5)Get first Element : " + stack.pop());
        }catch(OperationNotSupportedException e){
            System.out.println(e);
        }

        System.out.println(stack.size());

        stack.push(50);
        stack.push(100);
        System.out.println("Stack :- " + stack);
    }
}

find the element which has repeated for more than n/3 times in a given array

2012-08-19T07:52:00.002-07:00

Problem statement is given as comment. This is extension to the problem and solution which I have mentioned prior to this post i.e. get the element which has been repeated more than n/2 times in given array.

Again, this an O(n) time complex and O(1) space required algorithm...needless to say, one of the best possible algorithm for this type of problems!

package google;

public class FindTheElementWhichIsRepeatedMoreThanNBy3Times {

    /**
    * Problem Statement :- Find the element which is repeated for more than n/3 times in a given array of ints
    */
    public static void main(String[] args) {
        int[] input = {1, 2, 3, 2, 2, 3, 3};
        int probableValue1 = input[0];
        int probableVaulue1Count = 1;
        int i = 1;

        if(i == input.length){
            System.out.println("Element : " + probableValue1 + " Count Of The Element : " + probableVaulue1Count);
            return;
        }
        while(probableValue1 == input[i]){
            i++;
            probableVaulue1Count++;
            continue;
        }
        int probableVlaue2 = input[i];
        int probableValue2Count = 1;
        boolean probableValue1Turn = true;
        for(; i < input.length; i++){
            if(input[i] == probableValue1){
                probableVaulue1Count++;
            }else if(input[i] == probableVlaue2){
                probableValue2Count++;
            }else{
                if(probableValue1Turn){
                    probableVaulue1Count--;
                    if(probableVaulue1Count == 0){
                        probableValue1 = input[i];
                        probableVaulue1Count++;
                        probableValue1Turn = !probableValue1Turn;
                    }
                }else{
                    probableValue2Count--;
                    if(probableValue2Count == 0){
                        probableVlaue2 = input[i];
                        probableValue2Count++;
                        probableValue1Turn = !probableValue1Turn;
                    }
                }
            }
        }

        probableVaulue1Count = 0;
        probableValue2Count = 0;

        for(i = 0; i< input.length; i++){
            if(probableValue1 == input[i]){
                probableVaulue1Count++;
            }else if(probableVlaue2 == input[i]){
                probableValue2Count++;
            }
        }

        if(probableVaulue1Count > input.length/3){
            System.out.println("Element : " + probableValue1 + " Count Of The Element : " + probableVaulue1Count);
        }

        if(probableValue2Count > input.length/3){
            System.out.println("Element : " + probableVlaue2 + " Count Of The Element : " + probableValue2Count);
        }

        if(!(probableVaulue1Count > input.length/3) && !(probableValue2Count > input.length/3)){
            System.out.println("No Such Element found");
        }
    }
}

Find the number which has repeated more than n/2 times in a given input

2012-08-19T07:48:00.003-07:00

Problem statement is in the comment. Though we have kept the input static(i.e we know prior to execution that how much numbers we are going to get!), Even if the series of numbers are keep on coming with no prior knowledge of the fact that how many numbers are there...we can always use the first for loop to count the total number of input!

It is an O(n) time complex and O(1) space required algorithm and one of the best for problems like this. :)

package google;

public class FindTheElementWhichRepeatsMoreThanNBy2Times {
    /**
    * Problem Statement :- Find the element which is repeated n/2 times in a given sequence of the int's...
    */
    public static void main(String[] args) {
        int[] input = {1, 2, 1};

        int element = input[0];
        int countOfTheElement = 1;

        for(int i = 1 ; i < input.length; i++){
            if(element != input[i]){
                countOfTheElement--;
                if(countOfTheElement == 0){
                    element = input[i];
                    countOfTheElement++;
                }
            }else{
                countOfTheElement++;
            }
        }

        countOfTheElement = 0;
        for(int i = 0 ; i < input.length; i++){
            if(input[i] == element){
                countOfTheElement++;
            }
        }

        if(countOfTheElement > input.length/2){
            System.out.println(" Element : " + element + " count Of The Element is : " + countOfTheElement);
        }else{
            System.out.println("NO Such Element found!!!");
        }
    }
}

Print all interleaving strings for given two strings

2012-08-19T07:43:00.002-07:00

Problem statement is in comment of the code.

package google;

import java.util.HashSet;
import java.util.Set;

/**
*
* Problem statement :-
* Given two strings .Print all the interleavings of the two strings.
    Interleaving means that the if B comes after A .It should also come after A in the interleaved string.
    ex-
    AB and CD
    ABCD
    ACBD
    ACDB
    CABD
    CADB
    CDAB
*
*
*/

public class InterleavingWords {
    static int count = 0;
    static Set<String> setOfString = new HashSet<String>();
    static Set<String> set = new HashSet<String>();

    public static void main(String[] args) {
        String str1 = "abc";
        String str2 = "def";
        char[] charArray1 = str1.toCharArray();
        char[] charArray2 = str2.toCharArray();
        char[] out = new char[charArray1.length + charArray2.length];
        interleavingSrings(charArray1, charArray2, out, 0, 0, 0);
        System.out.println(count);
    }

    private static void interleavingSrings(char[] charArray1,
            char[] charArray2, char[] out, int i, int j, int k) {

        if(k == out.length){
            System.out.println(out);
            k = 0;
            count++;
            System.out.println(" Not a Duplicate Element : " + set.add(String.valueOf(out)));
        }else{
            for(int t = i; t < charArray1.length; t++){
                out[k] = charArray1[t];
                interleavingSrings(charArray1,charArray2, out, t+1, j, k+1);
            }

            for(int l = j; l < charArray2.length; l++){
                out[k] = charArray2[l];
                interleavingSrings(charArray1, charArray2, out, i, l + 1, k+1);
            }

        }
    }
}

Remove repeated element from a given sorted array

2012-08-19T07:41:00.000-07:00

Problem statement is in comment of the code.

package google;

import java.util.Arrays;

public class InlineRemovalOfRepeatedValuesInSortedArray {

    /**
    * Question :- given an array of sorted integers with duplicate values , sort the array so that there are only unique values
    * left in sorted order ( do not use any additional data type , do inplace sort )
    *
    * No Need of pseudo code
    */

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 3,3, 4, 4,4};
        Arrays.sort(input);

        int i = 0, j = i+1;
        for(; j < input.length; ){
            if(input[i] == input[j])
                break;
            else{
                i++; j++;
            }
        }

        for(; j < input.length;){
            if(input[i] !=input[j]){
                input[++i] = input[j++];
            }else{
                j++;
            }
        }

        int k = 0;
        while(k <= i && k < input.length){
            System.out.println(input[k]);
            k++;
        }
    }
}

Implement ++ functionality for an array of integers

2012-08-19T07:38:00.003-07:00

Problem statement :- we are given an array which will contain ints in the range of 0-9, write a routine to implement ++ functionality i.e. given such an array return an array which has got its first element increased by one maintaining the property that no element can go beyond 9 and hence we will have to propagate the change to higher members.

example :- input [9, 9, 9, 9]
                  output [1, 0, 0, 0, 0]

package google;

public class ImplementPlusPlusFunctionalityForAnIntegerArray {
    public static void main(String[] args) {
        int[] input = {9,9,9,9};
        int carry = 0;
        if(input[input.length - 1] == 9){
            int i = input.length - 1;
            carry = 1;
            while(i >=1 && carry == 1){
                if(input[i] == 9){
                    input[i--] = 0;
                    carry = 1;
                }else{
                    input[i--] += 1;
                    carry = 0;
                    break;
                }
            }
        }else{
            input[input.length - 1] += 1;
        }

        if(input[0] == 9 && (input.length == 0 || carry == 1)){
            input = new int[input.length + 1];
            input[0] = 1;
            for(int i = 1 ; i < input.length; i++){
                input[i] = 0;
            }
        }

        for(int i : input){
            System.out.println(i);
        }
    }
}

Adjust a given sentence to the given width of a line

2012-08-19T07:34:00.001-07:00

Problem statement and approach in given as comment in the implementation.

package google;

public class AdjustTheWordWithLineWidth {

    /**
    * Question : Given a line, adjust this line to the page width.
    * For example, given "Dog is cute" (length of chars is 11) and the page width is 15, adjust the line to "Dog is cute".
    * The extra spaces should be distributed as much even as possible. Assume there is no space before the first word or after the last word.
    *
    * Logic and Pseudo code :-
    *
    * Let say that the width of the line be W and the sentence given be a0 a1 a2....an and length(ai) be a function which gives the length
    * of a word at position i.
    *
    * We need to fit our sentence in the line and lets assume that sentence given is of smaller length as compared to the line width to the
    * extent that at least it will get fitted in it keeping just one space between each of the words.
    *
    * we can represent our fitting problem mathematically as W = (n-1) + sum of(length(ai)) where i will take value from 0 till n.
    * n-1 is the minimum space required in between the n words. As we can conclude that length part is going to be constant and only way to
    * adjust the sentence is by increasing the space between them i.e. by varying the n-1 part. or we can calculate that how much of space we
    * can give by dividing the width by the total length of the sentence!
    *
    */
    public static void main(String[] args) {
        String sentence = "This is goning to be fun!";
        int lineSize = 31;
        String[] words = sentence.split(" ");
        int numberOfWords = words.length;
        int sizeOfTheSentence = sentence.length() - (numberOfWords - 1);
        int numberOfSpacesWhichCanBeAccomodated = (lineSize-sizeOfTheSentence)/(numberOfWords - 1);
        StringBuffer stringBuffer = new StringBuffer();
        for(String temp : words)
        {
            stringBuffer.append(temp);
            for(int i = 0 ; i < numberOfSpacesWhichCanBeAccomodated; i++)
                stringBuffer.append(" ");
        }
        System.out.println(stringBuffer.toString().trim());

    }
}

Permutation Of a String : Java Implementation

2012-08-19T07:31:00.000-07:00

Print all the permutation of a String. The String may also contain few repeating characters, this implementation makes sure that it prints only unique permutations. It is an inline implementation. Here we have used a set "just to test that all the generated permutations are unique" and nothing else! Also we have used a count variable to give the total number of permutations generated.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Permutation {
    static int count = 0;
    static Set<String> setOfString = new HashSet<String>();
    static Set<String> set = new HashSet<String>();

    public static void main(String[] args) {
        String str = "abcc";
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        permutate(charArray, 0);
        System.out.println(count);
    }

    private static void permutate(char[] str, int index) {


        int lastChar = 0;
        if( index == str.length )
        {
            System.out.println(str);
            count++;
            System.out.println("Not a duplicate string : " + set.add(String.valueOf(str)));
            return;
        }
        for(int i = index; i < str.length; i++ )
        {
            if( lastChar == str[i] || (index != i && str[index] == str[i])) {
                continue;
            } else {
                lastChar = str[i];
            }

           //Swap
           char temp = str[index];
            str[index] = str[i];
            str[i] = temp;
            permutate( str, index + 1 );
            //Swap
            temp = str[index];
            str[index] = str[i];
            str[i] = temp;
        }
    }
}

Circular buffer : Java Implementation

2012-08-12T07:25:00.001-07:00

Problem Statement :

Implement a circular buffer of size N. Allow the caller to append, remove and list the contents of the buffer. Implement the buffer to achieve maximum performance for each of the operations.

The new items are appended to the end and the order is retained i.e elements are placed in increasing order of their insertion time. When the number of elements in the list elements exceeds the defined size, the older elements are overwritten.

There are four types of commands.

"A" n - Append the following n lines to the buffer. If the buffer is full they replace the older entries.

"R" n - Remove first n elements of the buffer. These n elements are the ones that were added earliest among the current elements.

"L" - List the elements of buffer in order of their inserting time.

"Q" - Quit.

Your task is to execute commands on circular buffer.

Input format :

First line of input contains N , the size of the buffer.

A n - append the following n lines to the buffer.

R n - remove first n elements of the buffer.

L - list the buffer.

Q - Quit.

Output format :

Whenever L command appears in the input, print the elements of buffer in order of their inserting time. Element that was added first should appear first.

Sample Input :

A 3

Fee

A 1

Fum

R 2

Sample Output :

Fum

Constraint :

0 <= N <= 10000

Number of removing elements will <= number of elements presents in circular buffer.

total number of commands <= 50000.

total number of characters in input <= 20000000.

Solution :-

I have implemented following way, Thought I tested the code(and it was running as expected in all my custom tests...) I am not sure why its been shown as failing for many of the use cases when I did submit it online. I will appreciate If anyone can help me in finding what problem does this code have! Thanks in advance..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class Solution3 {

    private static final String COMMAND_ADD = "A";
    private static final String COMMAND_REMOVE = "R";
    private static final String COMMAND_LIST = "L";
    private static final String COMMAND_QUIT = "Q";

    private static Map<String, String> lruCache;


    public static void main(String[] args) {
        takeTheInput();
    }

    @SuppressWarnings("serial")
    private static void takeTheInput() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean inputStrated = false;

        try {
            String line;
            String command = null;
            int numberOfEntriesTobeAddedOrRemoved = 0;
            String[] input = null;
            int index = 0;
            boolean firstTime = true;
                while((line = br.readLine()) !=null && !(line.trim().isEmpty())){
                    //initialize the cache
                    if(firstTime){
                        final int sizeOfLRUCache = Integer.parseInt(line);
                        lruCache = new LinkedHashMap<String, String>(sizeOfLRUCache){
                            protected boolean removeEldestEntry(Map.Entry<String, String> eldest){
                                return size() > sizeOfLRUCache;
                            }
                        };
                        firstTime = false;
                        continue;
                    }

                    //parse the commands / create the input array
                    if(!inputStrated){
                        String[] arrayOfCommands = line.split(" ");
                        command = arrayOfCommands[0];
                        if(command.equalsIgnoreCase(COMMAND_ADD) || command.equalsIgnoreCase(COMMAND_REMOVE)){
                            numberOfEntriesTobeAddedOrRemoved = Integer.parseInt(arrayOfCommands[1]);
                        }

                        if(command.equalsIgnoreCase(COMMAND_ADD)){
                            input = new String[numberOfEntriesTobeAddedOrRemoved];
                            inputStrated = true;
                            index = 0;
                            continue;
                        }else{
                            input = null;
                        }
                    }else{
                        if(index < numberOfEntriesTobeAddedOrRemoved){
                            input[index++] = line;
                        }
                        if(index < numberOfEntriesTobeAddedOrRemoved)
                            continue;
                    }

                    //Execute The Command

                    new Command(command, numberOfEntriesTobeAddedOrRemoved, input).execute();
                    inputStrated = false;
                    if(line == "\r"){
                        br.close();
                        break;
                    }
                }
            } catch (IOException e) {
                System.out.println("IOEXCEPTION : " + e.getMessage());
            }
    }

    static class Command{
        private String command;
        private int numberOfLinesOfInput;
        private String[] input;

        Command(String command, int numberOfLinesOfInput, String[] input){
            this.command = command;
            this.numberOfLinesOfInput = numberOfLinesOfInput;
            this.input = input;
        }

        void execute(){
            if(command.equalsIgnoreCase(COMMAND_ADD)){
                int i = 0;
                while(i < numberOfLinesOfInput){
                    lruCache.put(input[i], input[i]);
                    i++;
                }
            }else if(command.equalsIgnoreCase(COMMAND_REMOVE)){
                removeTheOldestElements(numberOfLinesOfInput);
            }else if (command.equalsIgnoreCase(COMMAND_LIST)) {
                listAllTheElelements();
            }else if (command.equalsIgnoreCase(COMMAND_QUIT)){
                System.exit(1);
            }
        }

        private void listAllTheElelements() {
            Iterator<String> iterator = lruCache.values().iterator();
            while(iterator.hasNext())
                System.out.println(iterator.next());
        }

        private void removeTheOldestElements(int numberOfLinesOfInput2) {
            Iterator<String> iterator = lruCache.values().iterator();
            while(iterator.hasNext() && numberOfLinesOfInput2 > 0){
                iterator.next();
                iterator.remove();
                numberOfLinesOfInput2--;
            }
        }

        public String getCommand() {
            return command;
        }
        public void setCommand(String command) {
            this.command = command;
        }
        public int getNumberOfLinesOfInput() {
            return numberOfLinesOfInput;
        }
        public void setNumberOfLinesOfInput(int numberOfLinesOfInput) {
            this.numberOfLinesOfInput = numberOfLinesOfInput;
        }
        public String[] getInput() {
            return input;
        }
        public void setInput(String[] input) {
            this.input = input;
        }


    }
}

Top Four : java Implementation

2012-08-12T07:14:00.001-07:00

Problem Statement

Given an unordered list of N elements, write a function to find the top four elements of the given list. Make sure your function runs in linear time O(N).

Input format :

First line of input contains N , number of elements in list.

Next N line , each contains a element.

Output format :

Print the top four elements of list.

Sample input :

6930886

-1692777

4636915

7747793

-4238335

9885386

9760492

6516649

Sample ouput :

9885386

9760492

7747793

6930886

Constraint :

N < 1000000.

all numbers will fit in 32-bit integer.

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class Solution4 {



    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<Integer> setOfInput = new TreeSet<Integer>();

        try {
            String line;
            boolean firstTime = true;
                while((line = br.readLine()) !=null && !(line.trim().isEmpty())){
                    if(firstTime) {
                        firstTime = false;
                        continue;
                    }
                    setOfInput.add(Integer.parseInt(line));
                    if(setOfInput.size() > 5) ((TreeSet<Integer>)setOfInput).pollFirst();
                    if(line == "\r"){
                        br.close();
                        break;
                    }
                }
            } catch (IOException e) {

            }
            Iterator<Integer> i = ((TreeSet<Integer>)setOfInput).descendingIterator();
            int index = 0;
            while(i.hasNext() && index++ < 4){
                System.out.println(i.next());
            }
    }
}

Frequent Terms : Java Implementation

2012-08-12T05:32:00.000-07:00

Problem statement

Frequency Counting of Words / Top N words in a document.

Given N terms, your task is to find the k most frequent terms from given N terms.

Input format :

First line of input contains N, denoting the number of terms to add.

In each of the next N lines, each contains a term.

Next line contains k, most frequent terms.

Output format :

Print the k most frequent terms in descending order of their frequency. If two terms have same frequency print them in lexicographical order.

Sample input :

Fee

Fum

Fee

Fum

Fee

Sample output :

Fee

Constraint :

0 < N < 300000

0 < term length < 20.

Solution :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class Solution {



    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String, Integer> mapOfinputs = new TreeMap<String, Integer>();
        int k = 0;
        try {
            String line;
            int numberOfInput = -1;

                while((line = br.readLine()) !=null && !(line.trim().isEmpty())){
                    line = line.trim();
                    if(numberOfInput == 0) {
                        k = Integer.parseInt(line);
                        br.close();
                        break;
                    }
                    if(numberOfInput == -1) {
                        numberOfInput = Integer.parseInt(line);
                        continue;
                    }
                    if(mapOfinputs.containsKey(line)){
                        mapOfinputs.put(line, mapOfinputs.get(line) + 1);
                    }else{
                        mapOfinputs.put(line, 1);
                    }
                    if(line == "\r"){
                        br.close();
                        break;
                    }
                    numberOfInput--;
                }
            } catch (IOException e) {

            }

            Map<Integer, Set<String>> finalMap = new TreeMap<Integer, Set<String>>();
            for(String str : ((TreeMap<String, Integer>)mapOfinputs).keySet()){
                int countOfString = mapOfinputs.get(str);
                if(finalMap.containsKey(countOfString)){
                    if(finalMap.get(countOfString).add(str));
                }else{
                    Set<String> treeSet = new TreeSet<String>();
                    treeSet.add(str);
                    finalMap.put(countOfString, treeSet);
                }

            }

            for(int i : ((TreeMap<Integer, Set<String>>)finalMap).descendingKeySet()){
                for(String str : ((TreeSet<String>)finalMap.get(i))){
                    if(k-- > 0)System.out.println(str);
                }
            }
    }
}