Find Maximum element in a Binary Tree


public int findMax(Node root) {
		int rootValue, left, right;
		int max = Integer.MIN_VALUE;

		if (root != null) {
			rootValue = root.getData();
			left =findMax(root.getLeft());
			right=findMax(root.getRight());
			if (left>right) max=left;
			else max=right;
			if(rootValue>max){
				max=rootValue;
			}
		}
		return max;
	}


Class

class Node {
	int data;
	Node left;
	Node right;

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}
}

Kadane’s Algorithm – Maximum sum subarray

public class KadaneAlgo {
	public static void main(String args[]){
		int[] inputArray={-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
		maxSubArray(inputArray);
		
	}

	public static void maxSubArray(int[] inputArray) {
		int cumulativeSum = 0;
		int maxSum = Integer.MIN_VALUE;
		int startIndex = 0;
		int endIndex = 0;
		int startIndexUntilNow = 0;

		for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
			cumulativeSum += inputArray[currentIndex];
			if (cumulativeSum > maxSum) {
				maxSum = cumulativeSum;
				startIndex = startIndexUntilNow;
				endIndex = currentIndex;
			}
                        if (cumulativeSum < 0) {
				startIndexUntilNow = currentIndex+1;
				cumulativeSum = 0;
			}
		}
		System.out.println("MaxSum : "+maxSum);
		System.out.println("Start Index : "+startIndex);
		System.out.println("End Index : "+endIndex);
	}

}


Towers of Hanoi

Towers of Hanoi

The minimum number of moves required to solve a Tower of Hanoi puzzle is 2^n – 1, where n is the number of disks.

Recursion

import java.util.Scanner;

public class TowersOfHanoi {
	private static int move = 1;

	public static void main(String args[]) {
		System.out.println("Enter number of Disks:");
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		solve(x, 'A', 'B', 'C');
	}

	public static void solve(int n, char srcPeg, char destPeg, char auxPeg) {
		if (n == 1) {
			System.out.println(move + ": Moved Disk from " + srcPeg + " to "
					+ destPeg);
			move++;
			return;
		}
		solve(n - 1, srcPeg, auxPeg, destPeg);

		System.out.println(move + ": Moved Disk from " + srcPeg + " to "
				+ destPeg);
		move++;
		solve(n - 1, auxPeg, destPeg, srcPeg);
	}
}


Recursion – Finding Factorial

Recursive
import java.util.Scanner;

public class Factorial {
	public static void main(String args[]) {
		System.out.println("Enter a number :");
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		System.out.println("Factorial of " + x + " is : " + factorial(x));
	}

	public static int factorial(int x) {
		if (x == 0 || x == 1) {
			return 1;
		} else {
			return x * factorial(x - 1);
		}
	}
}

Iterative

import java.util.Scanner;

public class IterativeFactorial {
	public static void main(String args[]){
		System.out.println("Enter a number :");
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		System.out.println("Factorial of " + x + " is : " + factorial(x));
	}
	public static int factorial(int x){
		int product=1;
		if (x == 0 || x == 1) {
			return product;
		}else{
			for(int i=1;i<=x;i++){
				product=product*i;
			}
			return product;
		}
	}
}

Creating Dynamic sitemap with Codeigniter

Recipe for creating Dynamic sitemap with CodeIgniter.
Like yoursite.com/sitemap.xml

Example.
Suppose you have an articles blog where url for each article is by article ID Like yoursite.com/123 .
All articles are stored in articleTable of the database.

First Create a model to get URLs.

  • Create a file named url_model.php in application/models directory.
  • Get Urls from database
[php]
<?php

class Url_model extends CI_Model{

	public function __construct(){
		$this->load->database();
	}
	public function getURLS(){

		$this->db->select('articleID');
		$query=$this->db->get('articleTable');
		return $query->result_array();
	}
}
?>
[/php]

Create Controller for Sitemap.

  • Create a file named sitemap.php in application/controllers directory.
  • Get Urls from model and load them in view
[php]
<?php

Class Sitemap extends CI_Controller {

	public function __construct(){
		parent::__construct();
		$this->load->model('url_model');
	}

	function sitemap()
	{

		$data['urlslist'] = $this->url_model->getURLS();
		$this->load->view("sitemap_view",$data);
	}
}

?>

[/php]

Create View for Sitemap

  • Create a file named sitemap_view.php in application/views directory.
  • Display the Urls in format
[php]
<?php echo'<?xml version="1.0" encoding="UTF-8" ?>' ?>

<urlset xmlns="http://www.sitemaps.org/schemas/sitemap/0.9">
    <url>
        <loc><?php echo base_url();?></loc>
        <priority>1.0</priority>
    </url>

    <!-- Your Sitemap -->
    <?php foreach($urlslist as $url) { ?>
    <url>
        <loc><?php echo base_url()."/".$url['articleID']?></loc>
        <priority>0.5</priority>
    </url>
    <?php } ?>

</urlset>

[/php]

Edit routes.php

  • Open routes.php in application/config directory.
  • Add the following line to routes
[php]
$route['sitemap\.xml'] = "sitemap/sitemap_view";
[/php]

Your sitemap is ready and can be accessed from yoursite.com/sitemap.xml. It can also be submitted to services like Google Webmaster tools

Websites not loading on BSNL Broadband !

Problem :

Some websites donot load properly or donot open at all . The problem comes while using Broadband in PPPoE mode and everything works fine in Bridge mode.

Sites work fine while using proxy or using Opera turbo .

Fix:

The problem is due to wrong MTU values set at Modem and in windows.

Make sure that both Modem and Windows have same MTU value .(for eg. set MTU as 1460 )

Setting MTU in Modem

-Go to your modem homepage ( Like 192.168.1.1)

– Open Interface Setup>Internet Settings (different for different modems)

– Set Encapsulation as PPPoE/PPPoA

-Now set TCP MTU option to 1460 bytes

Setting MTU in Windows 7 or Vista

  • First Check the MTU value of Windows (Enter following in Command Prompt)
  netsh interface ipv4 show subinterfaces 
  • If the Value is different from the value set at modem then change it by following commands in CMD
 netsh interface ipv4 set subinterface "Local Area Connection" mtu=1460 store=persistent

If you are using a Wireless Connection to connect to Internet then

 netsh interface ipv4 set subinterface "Wireless Network Connection" mtu=1460 store=persistent

Restart your modem with Current Settings and the connection will work perfectly.

Setting MTU in Windows XP

 

In Windows xp, changing the MTU value from the defaults, requires you to modify the TCP/IP parameters for the adapter in Windows Registry.

  • Click Start-> Run , type “regedit” and press Enter
  • Go to following Registry Key

HKEY_LOCAL_MACHINE
\SYSTEM
\CurrentControlSet
\Services
\Tcpip
\Parameters
\Interfaces
\<AdapterID>

  • In the right-panel, create a new DWORD named “MTU” with the value (say 1460 in decimal).
  • This sets the Maximum Transmission Unit (MTU) for that particular network adapter. Restart may be required.

 

Coding Puzzle : Tree Design

Problem:

Write a program that prints a tree made out of ‘*’  and ‘|’ . Shape of the tree depends on the given number N.

Input Format:

Given an integer N.

Output Format:

Display the corresponding tree to standard output.

Note: You can find additional sample input/outputs in the sample testcases download.

Constraints: 1 <= N <= 60

Sample Input

1

Sample Output

   *
  ***
 *****
*******
   |

Sample Input

2

Sample Ouput

      *
     ***
    *****
   *******
    *****
   *******
  *********
 ***********
*************
     |||
     |||

Additional larger testcases can be found in the downloadable zip file->Tree-Design_testcases.

Please consult them to confirm patterns and spacings in the output.

 

Solution Code:

import java.util.Scanner;

public class TreeDesign {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int height =0;
		int[] rows = new int[N];
		for (int i = 0; i < N; i++) {
			rows[i] = 4 + i;
			height+=rows[i];
		}

		int width = 7;
		for (int i = 1; i < N; i++) {
			if (i % 2 == 0) {
				width = width + (rows[i] - 1) * 2 - 4;
			} else {
				width = width + (rows[i] - 1) * 2 - 2;
			}
		}
		char [][] tree = new char[height + N][width];
		for (int q = 0; q < height+N; q++) {
			for (int p = 0; p < width; p++) {
				tree[q][p]=' ';
			}
		}
		
		int z=0;
		int x = 0;
		for (int t = N - 1; t >= 0; t--) {
			
			for (int i = height - 1-z; i >= height -z- rows[t] ; i--) {

				for (int j = x; j < width - x; j++) {
					tree[i][j] = '*';
				}
				x++;
			}
			if (t % 2 == 0) {
				x = x - 1 - 1-1;
			} else {
				x = x - 1 - 1 ;
			}
			z=z+rows[t];
		}

		int middle = width/2;
		int index = middle -N/2;
		for (int q = height; q < height+N; q++) {
			for (int p = index; p <= middle+N/2; p++) {
				tree[q][p]='|';
			}
		}
		for (int q = 0; q < height+N; q++) {
			System.out.println(new String(tree[q]));
		}
	}
}

Finding Nth Additive Prime [Java]

Problem :

A positive integer is called an additive prime number if it is prime and the sum of its digits is also prime.

For example, 83 is prime, and 8 + 3 = 11, which is also prime. Thus, 83 is an additive prime. Note that all single digit primes sum to themselves, and are thus additive primes.

Your task is to calculate elements in the sequence of additive primes.

Input Format:

Given an integer N.

Output Format:

Print the Nth additive prime.

Sample Input00:

1

Sample Output00:

2

Sample Input01:

2

Sample Output01:

3

Sample Input02:

9

Sample Output02:

43

Constraints:

1 <= N <= 200,000

Solution Code:

 

import java.util.Scanner;

public class AdditivePrimes {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = Integer.parseInt(sc.nextLine());
		int S =N*50;
		boolean[] isPrime = new boolean[S];

		int l = 0;
		int number = 2;
		
		for(int i=2;i

 

Coding Puzzle: Recycled Numbers

(Puzzle from Google Codejam Qualifier Round 2012)

Problem

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don’t care about television, but I do sometimes feel that way about numbers.

Let’s say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with An < mB?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing the integers A and B.

Output

For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1), and y is the number of recycled pairs (n, m) with An < mB.

Limits

1 ≤ T ≤ 50.
A and B have the same number of digits.

Small dataset

1 ≤ AB ≤ 1000.

Large dataset

1 ≤ AB ≤ 2000000.

Sample

Input Output
4
1 9
10 40
100 500
1111 2222
Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287

Solution:
-Rotate a number (mathematically)
-If number lies between A & B increment total
-Print total/2 (All pairs occur twice)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;

public class RecycledNumbers {
	public static void main(String args[]) throws IOException {
		BufferedReader bfr = new BufferedReader(new FileReader("inputC.txt"));

		Writer output = null;
		File file = new File("outputC.txt");
		output = new BufferedWriter(new FileWriter(file));

		int T = Integer.parseInt(bfr.readLine());
		int i = 0;
		while (i < T) {

			String[] temp = bfr.readLine().split(" ");
			int total = 0;
			int A = Integer.parseInt(temp[0]);
			int B = Integer.parseInt(temp[1]);
			for (int j = A; j <= B; j++) {

				long number = j;
				long start = number;

				int numdigits = (int) Math.log10((double) number);
				int multiplier = (int) Math.pow(10.0, (double) numdigits);

				while (true)
				{
					long r = number % 10;
					number = number / 10;
					number = number + multiplier * r;

					if (number == start)
						break;
					if ((int) number >= A && (int) number <= B) {
						total++;
					}
				}
			}

			output.write("Case #" + (i + 1) + ": " + (total / 2));
			if (i != T - 1) {
				output.write("\n");
			}

			i++;
		}
		output.close();
	}
}

Test Files (Large Dataset)
Input->Input.txt
Output-> Output.txt

Coding Puzzle : Punch

Puzzle:

We have n punching bags in a row. Mr Lee is going to practice with them for the upcoming Boxing tournament.

Each bag has a resistance level. Mr Lee can punch a bag if its resistance is greater than 0. He is an extremely hard puncher: when Mr Lee punches a bag, not only is its resistance set to 0 (ie: the bag is destroyed), but also the resistances of its immediately adjacent neighbors( one on left and other on right ) are decreased by one. If at any point of time the resistance of a bag drops to zero or less it is considered as destroyed. A punch on a bag with resistance greater than 0 has no impact on an immediate neighbor which is already destroyed.

Mr Lee wants to maximize his (very expensive) workout sessions, and would like to punch on these bags as much as possible. For any set of punching bags, what is the maximum number of punches that he can perform?

Input Format

On the only line of input there are n characters describing the resistances of the bags from 1 to n.

Ouput Format

On the only line of the output print an integer describing the maximum number of punches Mr Lee can punch for that set of bags.

Sample Input

11

Sample Ouput

1

Sample Input

021

Sample Output

2

Explanation

In the first example there are two bags, and we can punch only one of them before destroying both. In the second example we can punch on the third bag and then on the second bag to obtain two punches.

Constraints

Each bag has a resistance level between 0 and 3 ( inclusive ) and the number of bags is not more than 100

 
Solution:

-Find bag with minimum resistance
-Punch that bag and decrement the neighbors

Code:

import java.util.Scanner;

public class Punch {
	static int []A;
	static int total;
	public static void main (String args[]) {
		Scanner sc = new Scanner(System.in);
		String input  = sc.next();
		
		int numdigits = input.length();
		A = new int[numdigits];
		
		for(int i=0;i