## Bubble Sort Algorithm

Below is the code to do Bubble Sorting in Java for integer values

```
public class BubbleSort {
// logic to sort the elements
public static void srtbubble(int array[]) {
int n = array.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) { k = i + 1; if (array[i] > array[k]) {
swap(i, k, array);
}
}
print(array);
}
}
private static void swap(int i, int j, int[] array) {
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void print(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n");
}
public static void main(String[] args) {
int[] input = { 14, 21, 19, 62, 233, 142, 134, 10, 41 };
srtbubble(input);
}
}
```

Output:

14, 19, 21, 62, 142, 134, 10, 41, 233, 14, 19, 21, 62, 134, 10, 41, 142, 233, 14, 19, 21, 62, 10, 41, 134, 142, 233, 14, 19, 21, 10, 41, 62, 134, 142, 233, 14, 19, 10, 21, 41, 62, 134, 142, 233, 14, 10, 19, 21, 41, 62, 134, 142, 233, 10, 14, 19, 21, 41, 62, 134, 142, 233, 10, 14, 19, 21, 41, 62, 134, 142, 233, 10, 14, 19, 21, 41, 62, 134, 142, 233, 10, 14, 19, 21, 41, 62, 134, 142, 233,

## Finding loop in a singly linked-list

You can detect it by simply running *two* pointers through the list.

Start the first pointer **p1** on the first node and the second pointer **p2** on the second node.

Advance the first pointer by one every time through the loop, advance the second pointer by two. If there is a loop, they will eventually point to the same node. If there’s no loop, you’ll eventually hit the end with the advance-by-two pointer.

Consider the following loop:

```
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
^ |
| |
+------------------------+
```

Starting A at 1 and B at 2, they take on the following values:

```
p1 p2
= =
1 2
2 4
3 6
4 8
5 4
6 6
```

Because they’re equal, and P2 should always be beyond `p1`

in a non-looping list (because it’s advancing by two as opposed to the advance-by-one behavior of `p1)`

, it means you’ve discovered a loop.

The pseudo-code will go something like this:

- Start with hn(Head Node )of the linked list
- If hn==null; return false; //empty list
- if hn.next!=null
- p1=hn; p2=hn;
- While p2!=null loop
- p1=p1.next//Advancing p1 by 1
- if p2.next!=null
- p2=p2.next.next//Advancing p2 by 2
- else return false

- if p1==p2
- return true// Loop was found

- return false// till now no loop was found

Once you know a node *within* the loop, there’s an `O(n)`

guaranteed method to find the start of the loop.

Let’s return to the original position after you’ve found an element somewhere in the loop but you’re not sure where the start of the loop is.

```
p1,p2 (this is where p1 and p2
| first met).
v
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
^ |
| |
+------------------------+
```

This is the process to follow:

- First, advance
`p2`

and set the`loopsize`

to`1`

. - Second, while
`p1`

and`p2`

are not equal, continue to advance`p2`

, increasing the`loopsize`

each time. That gives the*size*of the loop, six in this case.

If the`loopsize`

ends up as`1`

, you*know*that you must already be at the start of the loop, so simply return`A`

as the start, and skip the rest of the steps below. - Third, simply set both
`p1`

and`p2`

to the first element then advance`p2`

exactly`loopsize`

times (to the`7`

in this case). This gives two pointers that are different by the size of the loop. - Lastly, while
`p1`

and`p2`

are not equal, you advance them together. Since they remain exactly`loopsize`

elements apart from each other at all times,`p1`

will enter the loop at exactly the same time as`p2`

returns to the start of the loop. You can see that with the following walk through:`loopsize`

is evaluated as`6`

- set both
`p1`

and`p2`

to`1`

- advance
`p2`

by`loopsize`

elements to`7`

`1`

and`7`

aren’t equal so advance both`2`

and`8`

aren’t equal so advance both`3`

and`3`

*are*equal so that is your loop start

Now, since each those operations are `O(n)`

and performed sequentially, the whole thing is `O(n)`

.

Algorithm Name: Floyd–Warshall algorithm

## 100 floors with 2 eggs puzzle

## Problem Statement:

There is a building of 100 floors If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs.

Give an Algorithm to find N, while minimizing the number of drops for the worst case.

## Solution:

The Problem comes with a general equation as X(Max Number of floors) = n*n;

So in this case for example, X= 100 Floors( => n=10)

now use the value n to traverse. This means that drop the first egg from 10th floor, then 20th floor, then 30th and so on up to 90.

The floor from which it breaks, say 60th, then go back 10 floors and try each floor to find N.

After Floor 90, Start moving 1 by 1.

Worst case scenario:

eggs break at 99th floor.

Egg drops: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> 90 -> 91 -> 92 -> 93 -> 94 -> 95 -> 96 -> 97 -> 98 -> 99

Max Attempts: **18**

## The water jug problem

We have three water jugs, and each can hold 3oz., 5oz., and 8oz. of water, respectively.

Without the possibility of water spilling when poured from one jug to another, and given that the jugs have no calibration, how do we divide the 8oz. of water equally among two jugs?

**We will define a class named State holding the capacity of A and B jars. It should be noted that only 2 jars are sufficient to define a state, as water held in third jar can be calculated by subtracting the sum of two from the total.**

Define class State like this…

package mystate;

import bfs.threejugproblem.NotSupportedException;

import java.util.ArrayList;

import java.util.List;

public class State

{

int a=0;//3

int b=0;//5

int c=8;//8

public State(int a, int b)

{

this.a=a;

this.b=b;

this.c=8-a-b;

}

public boolean isGoal()

{

return (b==4 && c==4);

}

public boolean equals(Object xx)

{

State x = (State) xx;

if(this.a==x.a && this.b==x.b && this.c==x.c)

{

return true;

}

else

{

return false;

}

}

public int hashCode()

{

return 8;

}

public List getChildren()

{

List children = new ArrayList();

// a -> b

if(a!=0 && b!=5)// if a is not empty

{

if(a+b<=5)

{

children.add(new State(0, a+b));

}

else

{

children.add(new State(a+b-5,5));

}

}

//a->c

if(a!=0 && c!=8)

{

// We are pouring completely from a to c

// a will be 0

// b will be 8-a-c

// c will be a+c

children.add(new State(0, 8-a-c));

}

//b->a

if(b!=0 && a!=3)

{

if(a+b<=3)

{

children.add(new State(a+b, 0));

}

else

{

children.add(new State(3, a+b-3));

}

}

// b->c

if(b!=0 && c!=8)

{

// We are pouring completely from b to c

// a will be 8-b-c

// b will be 0

// c will be b+c

children.add(new State(8-b-c, 0));

}

//c->a

if(c!=0 && a!=3)

{

if(c+a<=3)

{

children.add(new State(c+a, 8-c-a));

}

else

{

// a will be full i.e. 3 liters

// b will be 8-c-a

// c will be c+a-3

children.add(new State(3, 8-c-a));

}

}

// c->b

if(c!=0 && b!=5)

{

if(c+b<=5)

{

children.add(new State(8-c-b , c+b));

}

else

{

children.add(new State(8-c-b, 5));

}

}

return children;

}

@Override

public String toString()

{

return "{"+a+","+b+","+c+"}";

}

}

Depth First Search Algorithm

public class DFSThreeJugProblem

{

public static void main(String[] args)

{

State currentState = new State(0,0);

List visitedStates=new ArrayList();

// Check if the current State has a solution

// given a set of visited States.

dfs(currentState, visitedStates);

}

public static void dfs(State currentState, List vStates)

{

// if it is GOAL

if(currentState.isGoal())

{

// That's it we are done.

for(State v : vStates)

{

System.out.println(v);

System.out.println(currentState);

}

System.exit(0);

}

// if visisted state contains currentState, then just return.

// This is the wrong branch, and we need not traverse it further.

if(vStates.contains(currentState))

return;

// Add current state to visited states.

vStates.add(currentState);

// Make clone of visited states.

List clonedVStates = new ArrayList(vStates);

// Find the set of possible children of current state.

List children = currentState.getChildren();

for(State c : children)

{

// if a children C is not in the visited states

// again call DFS on current child and visited States.

if(!clonedVStates.contains(c))

{

dfs(c, clonedVStates);

}

}

}

}

Breadth First Search algorithm…

public class BFSThreeJugProblem

{

private static List visitedStates=new ArrayList();

private static Queue stateQueue = new LinkedList();

public static void main(String[] args) throws NotSupportedException

{

State currentState = new State(0,0);

// Add current state to state Queue.

stateQueue.add(currentState);

do

{

// Get the first Element from Queue.

State firstElementInQueue = stateQueue.peek();

// If the first Element is the Goal

// We are done.

if(firstElementInQueue.isGoal())

{

for(State p : visitedStates)

{

System.out.println(p.toString());

}

// There is no recursion here, so simple return would do.

return;

}

else

{

// Add firstElement to visited States

visitedStates.add(firstElementInQueue);

// Get the children of first element

List children = firstElementInQueue.getChildren();

for(State v : children)

{

// if children has not already been visited.

if(!visitedStates.contains(v))

{

// add the child to state Queue.

stateQueue.add(v);

}

}

// Remove the first element from state queue.

stateQueue.remove(firstElementInQueue);

}

// do this till state queue is empty.

}while(!stateQueue.isEmpty());

}

}