Solving Programming Problems 2

Solving Programming ProblemsIn my previous tutorial Solving Programming Problems, I walked you threw the process of solving a generic programming problem. We made a method that printed out a tree structure in the console.

In this tutorial, I’ll walk through the process of finding bugs in the code and talk about how we can fix those bugs. I think this topic may be the hardest to teach. I hope the video and the code that follows can help you better grasp how to solve most any programming problem.

If you like videos like this, it helps to tell Google+ with a click

Code From the Video

Solving Programming Problems 2 : Heap2.java

import java.util.Arrays;

public class Heap2 {

	private Data3[] theHeap;

	private int itemsInArray = 0;

	private int maxSize;

	public Heap2(int maxSize) {

		this.maxSize = maxSize;

		theHeap = new Data3[maxSize];

	}

	public void insert(int index, Data3 newData) {

		theHeap[index] = newData;

		itemsInArray++;

	}

	// Old Tree Generation Code

	public void printTree(int rows) {

		int spaces = 0;

		int iteration = 1;

		while (iteration <= rows) {

			int indent = (int) Math
					.abs(((Math.pow(-2, -iteration)) * (-16 + (Math.pow(2,
							iteration)))));

			int indexToPrint = (int) (.5 * (-2 + (Math.pow(2, iteration))));

			int itemsPerRow = (int) (Math.pow(2, iteration - 1));

			int maxIndexToPrint = indexToPrint + itemsPerRow;

			for (int j = 0; j < indent; j++)
				System.out.print(" ");

			for (int l = indexToPrint; l < maxIndexToPrint; l++) {

				System.out.print(theHeap[l].key);

				for (int k = 0; k < spaces; k++)
					System.out.print(" ");

			}

			spaces = indent;

			iteration++;

			System.out.println();

		}

	}

	public void printTree2(int rows) {

		// Number of spaces between items in tree

		int spaces = 0;

		int iteration = 1;

		// Generate all of the indents that are
		// needed depending on the number of rows
		// to print

		int[] indent = getIndentArray(rows);

		while (iteration <= rows) {

			// Find first Index : .5 * (-2 + 2^n)

			int indexToPrint = (int) (.5 * (-2 + (Math.pow(2, iteration))));

			// Number of Items per Row : 2^(n - 1)

			int itemsPerRow = (int) (Math.pow(2, iteration - 1));

			int maxIndexToPrint = indexToPrint + itemsPerRow;

			/*
			 * System.out.println("Indent: " + indent[iteration - 1]);
			 * System.out.println("indexToPrint: " + indexToPrint);
			 * System.out.println("itemsPerRow: " + itemsPerRow);
			 * System.out.println("maxIndexToPrint: " + maxIndexToPrint);
			 */

			// Print the indents needed

			for (int j = 0; j < indent[iteration - 1]; j++)
				System.out.print(" ");

			// Print all of the index values for each row
			// indexToPrint represents the first index in the
			// row, while maxIndexToPrint equals the last

			for (int l = indexToPrint; l < maxIndexToPrint; l++) {

				// If the array isn't full don't try to print
				// indexes that don't exist

				if (l < itemsInArray) {

					System.out.print(String.format("%02d", theHeap[l].key));

					for (int k = 0; k < spaces; k++)
						System.out.print(" ");

				}

			}

			// In a tree the spaces get bigger in the
			// same way that indents get smaller

			spaces = indent[iteration - 1];

			iteration++;

			System.out.println();

		}

	}

	// Calculate each indent per row for the tree
	// then reverse their order to go from biggest
	// to smallest

	public int[] getIndentArray(int rows) {

		int[] indentArray = new int[rows];

		for (int i = 0; i < rows; i++) {

			indentArray[i] = (int) Math.abs((-2 + (Math.pow(2, i + 1))));

		}

		Arrays.sort(indentArray);

		indentArray = reverseArray(indentArray);

		return indentArray;

	}

	// Reverse the indent values in the array
	// so that they go from biggest to smallest

	public int[] reverseArray(int[] theArray) {

		// Index of the first element
		int leftIndex = 0;

		// Index of last element
		int rightIndex = theArray.length - 1;

		while (leftIndex < rightIndex) {
			// Exchange the left and right elements
			int temp = theArray[leftIndex];
			theArray[leftIndex] = theArray[rightIndex];
			theArray[rightIndex] = temp;

			// Move the indexes to check towards the middle
			leftIndex++;
			rightIndex--;
		}

		return theArray;
	}

	// Fill the heap with random numbers based on
	// the number that is passed in

	public void generateFilledArray(int randNum) {

		Data3 randomData1;

		for (int i = 0; i < this.maxSize; i++) {

			randomData1 = new Data3((int) (Math.random() * randNum) + 1);

			this.insert(i, randomData1);

		}

	}

	public static void main(String args[]) {

		System.out.println("OLD TREE");

		Heap2 newHeap = new Heap2(70);

		// If I generate 2 digit numbers nothing lines up

		// newHeap.generateFilledArray(90);

		newHeap.generateFilledArray(9);

		// If I increase to over 4 rows the spaces are lost in the last row

		// newHeap.printTree(5);

		// newHeap.printTree(6);

		System.out.println("\nNEW TREE\n");

		newHeap.printTree2(6);

	}

}

class Data3 {

	public int key;

	public Data3(int key) {

		this.key = key;

	}

}

8 Responses to “Solving Programming Problems 2”

  1. Punit says:

    Hey darek,
    are you gonna show us how to solve basic problems (ie. reverse a number, palindrome number and so on..)
    these kind of questions asked in interviews many of times.

    • Derek Banas says:

      At some point I want to make a tutorial that is just about questions like that. I think that would be great fun! I did that a little bit in my refactoring tutorial

  2. Jacobus says:

    Hi Derek, great stuff you are doing here. As I mentioned on YouTube I covered your tutorials on my website. You can find them here (since Facebook started asking money for leaving messages since today, I am letting you know here! 🙂 )

    http://wordpressexamples.com/web-page-design-tutorial-and-create-a-wordpress-theme2/

    Do well man! Love your stuff.

  3. Logan Moua says:

    AMAZING! My teacher can’t do half what you did here.

  4. umair says:

    Is this the best way to solve any computational problems.

Leave a Reply

Your email address will not be published.

Google+