Activity Selection Problem

Problem: You are given some set of activities, with starting time and finish time. You have to tell the maximum number of activity can be performed by given person.

Algo:
Step1: sort the activity in increasing order according to finish time.  
Step2: Start counter with 1. Because first activity is always selected.
Step 3: i=0;
Step3: Do the following steps for i<n, where n is the number of activities
             if ith activity's finish time is less than (i+1)th activities start time.
             increase the counter value


Reason Why we sort the activities according to finish time
we always print first activity, This activity always performed, But This gives confusion that, if first activity finish time is more than two activity which start after first activity.
for Example:
number of activity is 3
1 2 4
6 3 5
So only one activity will be performed, But there are two activity that can performed.
Here we forget that activity are sorted by their finish order.
So
2 4 1
3 5 6
So number of activity is two.
Now if we print first activity inside the for loop then last activity will not print, because condition if (s[j] >= f[i]) will fail, So we don't know which activity,
So print first activity outside for loop, Now in for loop activity which start time print, if (s[j] >= f[i]) print j activity, because i already printed.

Data Structure Used for Snake and Ladder game

Rules for **Snake and Ladder** are:

 1. There are two players in this game and board size is 100.(10 X 10)
 2. Possible outcomes by throwing a dice are 1,2,3,4,5,6. 3. If output is 6 then current player will get a chance again to throw the Dice.
 4. If outcome of the Dice is 1,2,3,4,5,6 and player positioned on mouth of snake then his current position will change to tail of snake, and he will not get other chance until he throws a dice which has value 6.
 5. If outcome of the Dice is 1,2,3,4,5,6 and player positioned at below of ladder then His current position will change to topmost position of ladder and he will get another chance to throw the dice again.
 6. If player's current position+ roll >100 then take the following considerations i. if(roll==6) current player will get the chance again ,otherwise other player will get.
 7. Any player reach 100 earlier than other player will be the winner and game will end. We are passing only one HashMap, which contains the current position as key and next position as value. I think one HashMap will complete all the requirement of the Ladder and Snake  

int playSnakeAndLadder(HashMap hashMap){
        int player1=1, player2=1;// Initial position of players
        int chance=0;// This value show the change of players if chance is odd then player1 will play
                     // if chance is even then player2 will play
        while(1){
            if((player1==100)||(player2==100))// if any of player's position is 100 return chance;
                return chance;// Here chance shows who win the game, if chance is even player1 wins other //wise player2 wins
        int roll=Randon(6);// this will generate random number from 1 to 6.
        if(chance%2==0){
             int key=roll+player1;// new position of player1             
             boolean isLadder=false;// This is for checking the turn current player if againTurn is ture 
             // then the current player will player again.
             if(hashMap.contains(Key)){
                 player1=hashMap.getValue(Key);
                 // Here player current position will automatically update according to the hashMap.
                 // if there is a snake the key value is greater than it mapping value.
                 // if there is a ladder then key value is less than it mapping value. 
                 if(Key100 && roll!=6)
                   chance=(chance+1)%2;
                else if(player1+roll>100 && roll==6)
                   chance=chance;
                else if(roll==6){
                   player1=player1+roll;
                   chance=chance;
                }
                else{
                   player1=player1+roll;
                   chance1=(chance1+1)%2;
                }                 
           }
       

        else{// Now similarly for player2
                  {
                 int key=roll+player2;// new position of player1             
                 boolean isLadder=false;// This is for checking the turn current player if againTurn is ture 
                 // then the current player will player again.
                 if(hashMap.contains(Key)){
                     player2=hashMap.getValue(Key);
                     // Here player current position will automatically update according to the hashMap.
                     // if there is snake the key value is greater than it mapping value.
                     // if there is ladder then key value is less than it mapping value. 
                     if(Key100 && roll!=6)
                       chance=(chance+1)%2;
                    else if(player2+roll>100 && roll==6)
                       chance=chance;
                    else if(roll==6){
                       player2=player2+roll;
                       chance=chance;
                    }
                    else{
                       player2=player2+roll;
                       chance=(chance+1)%2;
                    }                 
            }
           }
         }
      }

Print All Nodes at K distance from the leaf node in Binary Search or Binary Search Tree

Print All Nodes at K distance from the leaf node in Binary Search or Binary Search Tree

We have to print Nodes at K distance from leaf Node in given Binary Tree. Here I have taken the Binary Search Tree. Because It is easy to make Binary Search Tree than making Binary Tree. 

Please see the following figure, this BST, which is made from following array:

Node Value for BST is:

array[]={10, 5, 6, 7, 3, 4, 17, 20, 15, 16, 18, 19}

Size of BST=12,

Here 10 is the root of the BST. We have to print the all nodes which is K=2 distance from the Leaf Nodes.

Leaf Nodes (Green colour) are 4, 7, 16, 19.

Nodes which are K=2, from leaf Node, are 5, 17, 20, please see yellow colour. For example 5 is at K=2 distance from the leaf node. 

Algorithms: 

First define the variable which we are going to use, 

K=> Given, Distance from the leaf Node.

len=> Initialize with zero, will use as index, in path array and visitedNode array.

path[] array, which will store the node during the tree traversal.

visitedNode boolean array, which will track the node, which are K, distance from leaf.

step1: Check root is null or not, if null return, otherwise step2.

step2: Assign root value to the path at len index. 

          Assign false to visitedNode for len index.

step3: check if the root is leaf node and visitedNode is false and difference between len-k-1>=0.

           Print that root, print=> path[len-k-1]. Change value of visitedNode at index len-k-1 to true. 

           If don't do this then, our algo will print double value. 

           return 

step4: Go to left subtree and repeat step1.

step5: Go to right subtree and repeat step1.

Time Complexity is O(N)

Please find the solution on Ideone:

http://ideone.com/PNelwg

Input: 

12

10 5 6 7 3 4 17 20 15 16 18 19
2

Output:

5 17 20

Now I will remove the visitedNode array, then what will happen, see the Ideone link

http://ideone.com/ECoUOl.

Input: 

12

10 5 6 7 3 4 17 20 15 16 18 19
2

Output:

5 5 17 20
Here we can see the we are again the same Node, So we need vistedNode boolean array to keep trap the Nodes which are at K distance from the leaf Node and print and visited previously.

Data Structures

Question: Design a data structure that can push, pop, and getmin in O(1), on given set of data.


Question: Design a data structure that allow insert, delete, max in O(1)

Question: Design a special stack that support these operation pop(), push(), isFull and getMin() or getMax(), in O(1).
Answer:
Maintain two stack, Main stack and other stack. Other stack will maintain the current max or min in Main stack. If you want minimum element then other stack will maintain minimum element, otherwise if you want maximum element then other stack will maintain current max element.
The answer is, you use two stacks: the main stack, and a min (or max) stack.
So for example, after pushing 1,2,3,4,5 onto the stack, your stacks would look like this:

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

However, if you were to push 5,4,3,2,1, the stacks would look like this:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

For 5,2,4,3,1 you would have:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

and so on.
You can also save some space by pushing to the min stack only when the minimum element changes, iff the items are known to be distinct.

Strings

Question: For a given string, find its first non-repeating character?

Algorithm1: 
Step1: Make an array of 256,
Step2: Count frequency of all character and store in array. Here characters ASCII value is used as index.
Step3: Now again scan the string character by character, and check the frequency of current character. If it is one just break loop and return the first non-repeating character.

Time Complexity is O(n)+O(n)=O(n), but required two scan of given strings. Please remember here we required to scan string two times.

Algorithm2: 

Step1: Declare Data Structure which takes two fields 1. count, 2. index. count will be the frequency of characters and index is the index of character which occurs first time.  

class countCharAndIndex{
      int count;
      int index;
}

Step2: First make an array of countCharAndIndex. And  scan the string and count the frequency of each character and store the index, when any character occurs first time.

    a. countCharAndIndex [] array=new countCharAndIndex[256];
    b. For i=0 to length of countCharAndIndex-1.
           array[str.charAt(i)].count++;
           if(array[str.charAt(i)].count==1)// char str.charAt(i) occur first time
                 array[str.charAt(i)].index=i;
        return array;
  
   Here we need one scan of string.

Step3: Here we need only scan of array, whose length is 256.
   a. result=MAX
   b. for i=0 to 255
           if((array[i].count==1) && (array[i].index<result))
                    result=array[i].index;
       return result.

Time complexity is only O(n)+256=O(n), only one almost one scan.