Note
Studied by 12 peopleJava Programming and Data Structures Review
Question 1
What will this small program output?
class Main {
public static void foo() {
System.out.println(x);
}
public static int x = 42;
public static void main(String[] args) {
x = 6;
foo();
}
}
Answer: 6
Question 2
What is the output of this Java program?
class Driver {
public static void main(String[] args) {
int a = foo(3);
int b = bar(4);
}
static int foo(int a) {
a = bar(a + 1);
System.out.print(a);
return a;
}
static int bar(int a) {
System.out.print(a);
return a - 1;
}
}
Answer: 434
Question 3
What is the output of this Java program?
class Driver {
public static void main(String[] args) {
int a = 2;
int b = 1;
int c = 2;
int x = 1;
if (a > 1) {
x = x + 200;
}
if (b > 4) {
x = x + 10;
}
if (c > 7) {
x = x + 2;
}
System.out.print(x);
}
}
Answer: 201
Question 4
Consider the following operations on a stack. What will be the final output?
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.pop();
stack.push(30);
stack.push(40);
stack.pop();
stack.push(stack.peek());
System.out.println(stack.pop() + stack.pop() + stack.peek());
Answer: 70
Question 5
Evaluate the following code to determine the output. Hint - ASCII value of A is 65.
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Character> list = new ArrayList<>();
for (char c = 'B'; c <= 'D'; c++)
list.add(c);
for (int i = 0; i < list.size(); i++) {
list.set(i, (char) (list.get(i) + 2));
}
list.add((char) (65 + 1));
list.remove(1);
list.remove(Integer.valueOf('C'));
list.add(0, (char) (list.get(1) - 1));
System.out.println((int) list.get(1));
}
}
Answer: 68
Question 6
What is the output of the following code?
public static void main(String[] args) {
int[] arr = {1, 2, 5, 10, 12, 14, 16, 18, 20, 22, 28, 32};
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] % 2 == 0) {
arr[i] = arr[i] / 2;
}
}
System.out.println(arr[4] + arr[1]);
}
Answer: 7
Question 7
What is the output of this Java program?
class Driver {
public static void main(String[] args) {
int a = 16;
int b = a + 14;
while (a < b) {
a = a + 2;
b = b - 1;
}
System.out.print(a + b);
}
}
Answer: 51
Question 8
What is the output of this Java program?
class Driver {
public static void main(String[] args) {
int a = 56;
for (int i = 6; i > 1; i--) {
a = a - i;
}
System.out.print(a);
}
}
Answer: 36
Question 9
Which of the following scenarios would cause a NullPointerException when working with linked lists? (Select all that apply)
Accessing head.data when the list is empty
Setting temp.next = null when temp is null.
Iterating through the list while checking for null references.
Adding a new node without initializing the head.
Answer: 1, 2
Question 10
What is the output of the following recursive code?
public class Main {
public static void main(String[] args) {
System.out.print(foo("hello"));
}
public static String foo(String var) {
if (var.length() <= 1)
return var;
System.out.print(var.charAt(1));
return foo(var.substring(1));
}
}
Answer: "elloo"
Question 11
Which of the following would correctly declare and instantiate a 2D array with a total of 24 ints? Choose all that apply.
int[2] values = new int[12];
int[,] values = int[2,12];
int[][] values = new int[3][8];
int[][] values = new int[2][12];
int[12] values = new int[2];
int[] values = int[24];
int[4] values = new int[8];
int[24] values = new int[24];
int[][] values = new int[12][2];
int[][] values = new int[8][3];
int[][] values = new int[24];
none of these
int[,] values = int[4,8];
Answer: int[][] values = new int[2][12]; and int[][] values = new int[12][2];int[3][8]; & int[][] values = new int[8][3];
Question 12
What would be the output of the following code?
public class Foo {
public int var;
public String str;
public Foo(int var, String str) {
this.var = var;
this.str = str;
}
}
class Main {
public static void main(String[] args) {
Foo foo = new Foo(10, “bar”);
foo.var = 5;
System.out.print(foo.var + foo.str);
}
}
Answer: 5bar
Question 13
What would be the output of the following code?
MyStack<Integer> s = new MyStack<Integer>();
s.push(8);
s.push(16);
s.pop();
s.push(32);
s.push(18);
s.peek();
System.out.print(s.size());
Answer: 3
Question 14
Given the following declaration:
int[] values = {1,3,5,0,2,8,7,2,5,2};
Evaluate the following expression:
values[values[5]]
Answer: 5
Question 15
What is the output of this Java program?
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
for (int i = 1; i <= 4; i++) {
s.push(i + 1);
}
while (!s.isEmpty()) {
System.out.print(s.pop() + 2 + " ");
}
}
}
Answer: 7 6 5 4
Question 16
What is the Big O run time complexity for retrieving the value at a given index in a linked list?
Answer: O(n) linear
Question 17
What is the Big O run time complexity for retrieving the value at a given index in a stack?
Answer: O(n) linear
Question 18
What is the Big O run time complexity for removing the first value in a queue?
Answer: O(1) constant
Question 19
What is the Big O run time complexity for removing the top value in a stack?
Answer: O(1) constant
Question 20
Which of the following would have a exponential Big O run-time complexity?
Answer: Determine if two logical statements are equivalent by brute force
Question 21
Which of the following would have a logarithmic Big O run-time complexity?
Answer: Find the phone number in a phone book, given a person’s name
Question 22
Which of the following run-time complexity orders is best?
Answer: O(log n) Logarithmic time
Question 23
Which of the following run-time complexity orders is worst?
Answer: O(n) Linear time
Question 24
A name defined in an outer scope is not available in all blocks nested inside that scope.
Answer: False
Question 25
Which keyword is used in Java to create an object?
Answer: New
Question 26
Which object oriented element is best defined as "objects best viewed as packages of responsibility"?
Answer: Encapsulation
Question 27
We can more easily debug a program when the responsibilities are well encapsulated. Group of answer choices
Answer: True
Question 28
Given the following partial code, fill in the blank to complete the code necessary to insert node x in between the last two nodes. (don't forget the semicolon)
...
class Node {
public Object data = null;
public Node next = null;
}
...
Node head = new Node(); // first Node
head.next = new Node(); // second Node
head.next.next = new Node(); // third node
Node x = new Node(); // node to insert
x.next = head.next.next;
// _________________ //
Answer: head.next.next = x;
Question 29
Given the following partial code, fill in the blank to complete the code necessary to insert node x after the third node. (don't forget the semicolon)
...
class Node {
public Object data = null;
public Node next = null;
}
...
Node head = new Node(); // first Node
head.next = new Node(); // second Node
head.next.next = new Node(); // third node
Node x = new Node(); // node to insert
// _________________ //
Answer: head.next.next.next = x;
Question 30
Given the following partial code, fill in the blank to complete the code necessary to remove first node. (don't forget the semicolon)
...
class Node {
public Object data = null;
public Node next = null;
}
...
Node head = new Node(); // first Node
head.next = new Node(); // second Node
head.next.next = new Node(); // third node
head.next.next.next = new Node(); // fourth node
// _________________ //
Answer: head = head.next;
Question 31
Given the following partial code, fill in the blank to complete the code necessary to remove the second node. (don't forget the semicolon)
...
class Node {
public Object data = null;
public Node next = null;
}
...
Node head = new Node(); // first Node
head.next = new Node(); // second Node
head.next.next = new Node(); // third node
head.next.next.next = new Node(); // fourth node
// _________________ //
Answer: head.next = head.next.next;
Question 32
Evaluate the following code to determine what value will be at the front of the queue after the code completes.
MyQueue<Integer> q = new MyQueue<Integer>();
q.add(38);
q.add(56);
q.add(73);
Answer: 38
Question 33
Evaluate the following code to determine what value will be at the back of the queue after the code completes.
MyQueue<Integer> q = new MyQueue<Integer>();
q.add(33);
q.add(43);
q.add(74);
Answer: 74
Question 34
Evaluate the following code to determine the output.
MyStack<Integer> s = new MyStack<Integer>();
s.push(22);
s.push(47);
s.push(72);
s.pop();
s.pop();
System.out.println(s.pop());
Answer: 22
Question 35
Evaluate the following code to determine what value will be at the bottom of the stack after the code completes.
MyStack<Integer> s = new MyStack<Integer>();
s.push(31);
s.push(61);
s.push(86);
Answer: 31
Question 36
Below is an Quicksort algorithm with several pieces missing (represented by XXXXXXXXXX, and the underlined space). Fill in the missing blank (underlined space) with the correct piece of code.
static void quicksort(MyList aList) {
quicksortHelper(XXXXXXXXXXXXXXX, XXXXXXXXXXXXXXX, aList.size() - 1);
}
static void quicksortHelper(MyList aList, int lowIndex, int highIndex) {
if (lowIndex < highIndex) {
int pIndex = partition(aList, XXXXXXXXXXXXXXX, XXXXXXXXXXXXXXX);
quicksortHelper(aList, XXXXXXXXXXXXXXX, XXXXXXXXXXXXXXX);
quicksortHelper(aList, XXXXXXXXXXXXXXX, _______________);
}
}
static int partition(MyList aList, int low, int high) {
//pick the value at high index as the pivot value
int pivotValue = aList.at(high);
int storeIndex = XXXXXXXXXXXXXXX;
// Compare remaining array elements against pivot value
for (int compareIndex = XXXXXXXXXXXXXXX; compareIndex < XXXXXXXXXXXXXXX; compareIndex++) {
if (aList.at(XXXXXXXXXXXXXXX) <= pivotValue) {
temp = aList.at(compareIndex);
aList.setAt(compareIndex, aList.at(XXXXXXXXXXXXXXX));
aList.setAt(storeIndex, temp);
storeIndex = XXXXXXXXXXXXXXX;
}
}
// Move pivot value to its final place
temp = aList.at(storeIndex);
aList.setAt(storeIndex, aList.at(high));
aList.setAt(high, temp);
// return the index of the pivot value
return XXXXXXXXXXXXXXX;
}
Answer: highIndex?
Question 37
Which of the following recursive methods is equivalent to this iterative method?
String bar(String s) {
String x = "";
for (int i = 0; i < s.length(); i++)
x = s.charAt(i) + x;
return x;
}
Answer: The first one
String bar(String s) {
if (s.length() == 0)
return s;
return s.charAt(s.length() - 1) + bar(s.substring(0, s.length() - 1));
}
Question 38
Which of the following iterative methods is equivalent to this recursive method?
int foo(int n) {
if (n <= 1)
return n;
return n + foo(n – 1);
}
Answer: The first one
int foo(int n) {
int x = 0;
while (n > 0) {
x += n;
n--;
}
return x;
}
Question 39
How many private methods (including constructors) does this class have? Refer to the following UML Class Diagram when answering this question.
Answer: 3
Note: The private methods are -Pet(), -getAge() and -scratch(itches : int).
Question 40
How many arguments does the setName method take? Refer to the following UML Class Diagram when answering this question.
Answer: 1
Question 41
If you do not declare a default constructor in your class, the compiler will always create a default constructor for you.
Answer: True
Question 42
The "inherits" keyword is used to specify inheritance in Java.
Answer: False
Question 43
The Java keyword throw is used to catch an exception.
Answer: False. throw is used to throw an exception, catch is used to catch an exception.
Question 44
Any recursive algorithm can be written iteratively.
Answer: True
Question 45
Evaluate the following code to determine the output.
class Foo {
public int i = 62;
public Foo(int i) {
this.i = i;
}
}
...
Foo x = new Foo(5), y = new Foo(89);
y = x;
y.i = 49;
System.out.println(x.i);
Answer: 49
Note: y = x means that y now references the same object as x. Therefore, modifying y.i also modifies x.i.
Question 46
Evaluate the following code to determine the output.
class Foo {
public int i = 96;
public Foo(int i) {
this.i = i;
}
}
...
Foo x = new Foo(63), y = new Foo(98);
x.i = y.i;
y.i = 4;
System.out.println(x.i);
Answer: 98
Note: x.i = y.i assigns the value of y.i (which is 98) to x.i. The subsequent change to y.i does not affect x.i.
Question 47
Binary Tree traversals – consider the following tree:
40
/ \
19 27
/ \ \
32 84 30
/ \
16 23
Show how the tree would be printed using each of the traversals below:
a. Pre-Order:
Answer: 40, 19, 32, 16, 23, 84, 27, 30
b. In-Order:
Answer: 16, 32, 23, 19, 84, 40, 27, 30
c. Post-Order:
Answer: 16, 23, 32, 84, 19, 30, 27, 40
Question 48
class TreeNode {
char value;
TreeNode left;
TreeNode right;
public TreeNode(char value) {
this.value = value;
}
}
public static String traverse(TreeNode root) {
if (root == null) return "";
StringBuilder result = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.append(node.value);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result.toString();
}
public static void main(String[] args) {
TreeNode root = new TreeNode('L');
root.left = new TreeNode('M');
root.right = new TreeNode('N');
root.left.left = new TreeNode('O');
root.left.right = new TreeNode('P');
root.right.left = new TreeNode('Q');
System.out.println(traverse(root));
}
Answer: LMOPNQ
Note: This is a pre-order traversal implemented iteratively using a stack.
Question 49
import java.util.*;
class Node {
int val;
Node left, right;
Node(int val) {
this.val = val;
}
}
public class BFSOddEvenMagic {
public static void main(String[] args) {
Node root = new Node(19);
root.left = new Node(20);
root.right = new Node(25);
root.right.left = new Node(15);
root.right.right = new Node(10);
bfsMagic(root);
}
static void bfsMagic(Node root) {
Queue<Node> q = new LinkedList<>();
q.add(root);
int level = 0;
int result = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node node = q.poll();
if ((level % 3 == 1) && (node.val % 5 == 0)) {
result *= node.val;
}
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
level++;
}
System.out.println(result);
}
}
Answer: 500
Level 0: root (19) - not level % 3 == 1.
Level 1: 20, 25 - level % 3 == 1, so check node.val % 5 == 0. 20 % 5 == 0, so result = 1 * 20 = 20.
Level 2: 15, 10 - not level % 3 == 1.
Therefore 20 * 25 = 500
Question 50
Given that:
int[] list = {4, 8, 12, 18, 23, 27, 33, 37, 42, 46, 52, 56, 61, 68, 71};
and:
int targetValue = 31;
and given this Binary Search algorithm:
public static int BinarySearch(int[] list, int targetValue) {
int mid, low, high;
low = 0;
high = list.length - 1;
while (high >= low) {
mid = (high + low) / 2;
if (list[mid] < targetValue) {
low = mid + 1;
} else if (list[mid] > targetValue) {
high = mid - 1;
} else {
return mid;
}
}
return -1; // not found
}
Answer: 18