Test Methods

Question 1

Row Lengths Decrease

int[][] t

Answer 1

public static boolean rowLengthsDecrease(int[][] t){
	//start with single for loop to target each row
	for (int i = 0; i < t.length -1; i++){
		if (t[i].length < t[i+1].length){
			return false;
		}
	}
	return true;
}

Question 2

Row Values Increase

int[][] t

Answer 2

public static boolean rowValuesIncrease(int[][] t){
	for (int i=0; i < t.length-1; i++){
		for (int j=0; j < t[i].length-1; j++){
			if (t[i][j] >= t[i][j+1]){
				return false;
			}
		}
	}
	return true;
}

Question 3

Column Values Increase

int[][] t

Answer 3

public static boolean columnValuesIncrease(int[][] t){
	for (int i=1; i < t.length; i++){
		for (int j= 0; j < t[i].length; j++){
			if (t[i-1][j] >= t[i][j]){
				return false;
			}
		}
	}
	return true
}

Question 4

Is Set of 1 to N

int[][] t

Answer 4

public static boolean isSetOf1toN(int[][] t){
	//3 key stages
	//stage 1: get cell count of t 
	int cellCount = 0;
	for (int i = 0; i < t.length; i++){
		cellCount += t[i].length;
	}		
	// stage 2: create array of booleans to check if
	// any cell values are > no. of cells (they can't be)
	boolean[] s = new boolean[cellCount];
	for (int i=0; i < t.length; i++){
		for (int j=0; j < t[i].length; j++){
			int cellValue = t[i][j];
			if (cellValue > s.length){
				return false;	
			}
			s[cellValue -1] = true;
		}
	}
	for (Boolean value : s){
		if (!value){
			return false;
		}
	}
	return true;
}

Question 5

Add Value (Week 8)
(Integer value)

Answer 5

public void addValue(Integer value){
	if (smallest == null){
		smallest = new Cell(value);
		return;							
	}

    Cell bump = smallest;
    value = addToRow(smallest, value);

	while (value != null){
		if (bump.below == null){
			bump.below = new Cell(value);
			bump.below.above = bump;
			return; 
		}
		bump = bump.below;
		value = addToRow(bump, value);
	}
}

Question 6

Add to Row (Week 8)

Cell curr, int value

Answer 6

public Integer addToRow(Cell curr, int value){
int current = value;
while (current > curr.value && curr.right != null){
curr = curr.right;
}

	while (curr.value > current){
		current = curr.value;
		curr.value = value;
		return current;
	}

	if (curr.right == null){
		curr.right = new Cell(value);
		curr.right.left = curr;
		if (curr.above != null){
			curr.right.above = curr.above.right;
		}
	}
	return null;
}

Question 7

Size (Week 10)

Answer 7

public int size(){
	if (nodeValue == null){
		return 0;
	}
	int countNodes = 1;
	for (Tree child : children){
		countNodes += child.size();
	}
	return countNodes;
}

Question 8

Max Degree (Week 10)

Answer 8

public int maxDegree(){
if (children.isEmpty()){
return 0;
}
int[] widths = new int[children.size() + 1];
widths[children.size()] = children.size();

for (int i = 0; i < children.size(); i++){
	widths[i] = children.get(i).maxDegree();
}

	int maxWidth = 0;
	for (int width : widths){
		if (width > maxWidth){
			maxWidth = width;
		}
	}
	return maxWidth;
}

Question 9

Post Order (Week 10)
Returns a List

Answer 9

public List postOrder(){
	ArrayList nodes = new ArrayList();
	if (children.isEmpty()){
		nodes.add(rootValue);
		return nodes;
	}
	for (Tree child : children){
		nodes.addAll(child.postOrder());
	}
	nodes.add(rootValue);
	return nodes;
}

Question 10

To Indented String (Week 10)

Answer 10

public String toIndentedString(){
	String indentTree = rootValue + "\n";
	if (children.isEmpty()){
		return indentTree;
	}
	String childStr = "";
	for (Tree child : children){
		childStr += child.toIndentedString();
	}
	String[] childArr = childStr.split("\n");

	for (String child : childArr){
		indentTree += "  " + child + "\n";
	}
	return indentTree;
}

Question 11

Add (Week 11)

T element

Answer 11

public void add(T element){
if (root == null){
root = element;
}

int comparison = root.compareTo(element);

	if (comparison > 0){
		if (left == null){
			left = new LinkedBST(element);
		} else {
			left.add(element);
		}
	} else if (comparison < 0) {
		if (right == null){
			right = new LinkedBST(element);
		} else {
			right.add(element);
		}
	}
}

Question 12

Search (Week 11)

T element

Answer 12

public boolean search(T target){
if (root == null){
return false;
}

int comparison = root.compareTo(target);
if (comparison == 0){
	return true;
} else if (comparison > 0 && left != null){
	return left.search(target);
} else if (comparison < 0 &amp;&amp; right != null){
	return right.search(target);
}

return false; }

Question 13

Height (Week 11)

Answer 13

public int height(){
if (root == null){
return 0;
}

	int lTotal = 0;
	int rTotal = 0;
	if (left != null){
		lTotal += 1 + left.height();
	}
	if (right != null){
		rTotal = 1 + right.height();
	}

return Math.max(lTotal, rTotal); }

Question 14

Size (Week 11)

Answer 14

public int size(){
if (root == null){
return 0;
}

	int total = 1;		
	if (left != null){
		total += left.size();
	}
	if (right != null){
		total += right.size();
	}

return total; }

Question 15

Size Above (Week 11)
(T low)

Answer 15

public int sizeAbove(T low){
if (root == null){
return 0;
}

int count = 0;
int comparison = root.compareTo(low);

if (comparison >= 0){
	count++;
}

	if (right != null){
		count += right.sizeAbove(low);
	}
	if (left != null){
		count += left.sizeAbove(low);
	}

return count; }

Question 16

Size Below (Week 11)
(T high)

Answer 16

public int sizeBelow(T high){
int result = size() - sizeAbove(high);
return result;
}

Question 17

Size Between (Week 11)
(T low, T high)

Answer 17

public int sizeBetween(T low, T high){
	if (root == null){
		return 0;
	}
	int result = size() - (sizeAbove(high) + sizeBelow(low));

    return result; }