Coding Skills (Advanced)
Please read all instructions very carefully before you begin.
This is the PAC – Coding Skills (Advanced Level) assessment.
It is composed of 20 questions.
You will have 40 minutes to complete this assessment. Please note that once you have completed a question you will NOT be able to return to it in order to make changes.
No points will be deducted for wrong answers.
This assessment incrementally develops an implementation of a certain kind of tree structure. (Its definition and an example will be presented with each question.) Along the way you will be asked questions to test your understanding of the implementation and ability to think about its design. The code presented will be in Java, but will not use any advanced features of the language and should be easily understood by someone more familiar with C++.
Wherever a question shows a class definition assume that the class contains other methods that are omitted for the purposes of the question. When a question shows methods for some classes but not others it means the other classes do not define those methods.
Assume that all code is syntactically correct. The questions are not intended to test your knowledge of language details.
Assume that all methods are public; the questions have nothing to do with access restrictions.
Assessment Breakdown
Section 1 : 20 Minutes : 10 Questions
Section 2 : 20 Minutes : 10 Questions
Totals 40 Minutes : 20 Questions
Question Number 1
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
class InternalNode extends Node {
Node left, right;
InternalNode(node l, node r) {
left = l;
right = r;
}
}
What should be done to modify the constructor to handle the case when both l and r are null?
(a) Nothing—it’s OK
(b) Assert that they can’t both be null
(c) Throw an exception if both are null
(d) Create terminal nodes for left and right with null values
Question Number 2
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
abstract class Node {
}
class TerminalNode extends Node {
String value;
String getValue() {
return value;
}
}
class InternalNode extends Node {
}
What constructors should TerminalNode have according to the specifications for the tree structure?
TerminalNode(String)
TerminalNode(Node)
(a) A
(b) B
(c) Both
(d) Neither
Question Number 3
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
class InternalNode extends Node {
%%% left, right;
}
What type should replace %%% in the above?
(a) Object
(b) Node
(c) InternalNode
(d) TerminalNode
Question Number 4
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
class InternalNode extends Node {
Node left, right;
}
What constructors should InternalNode have according to the specifications for the tree structure?
InternalNode(String)
InternalNode(Node)
InternalNode(Node, Node)
(a) A
(b) B
(c) C
(d) More than one of the choices
Question Number 5
Given a code snippet answer the following question.
struct AVLTree
{
AVLTree * left;
AVLTree * right;
int element;
int height;
};
int MAX(int a, int b){
if(a>=b)
return a;
if(a<b)
return b;
}
int height(AVLTree *node)
{
if (node == NULL)
{
return -1;
}
else
{
return node->height;
}
}
AVLTree * single_rotation_with_left(AVLTree *k2)//Func1
{
AVLTree *k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->left), height(k2->right)) + 1;
return k1;
}
AVLTree * single_rotation_with_right(AVLTree *k2)//Func2
{
AVLTree *k1;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->right), height(k2->left)) + 1;
return k1;
}
AVLTree *double_rotation_with_left(AVLTree *k3)
{
k3->left = single_rotation_with_right(k3->left);
return single_rotation_with_left(k3);
}
AVLTree *double_rotation_with_right(AVLTree *k3)
{
k3->right = single_rotation_with_left(k3->right);
return single_rotation_with_right(k3);
}
void insert(int value, AVLTree **node)
{
if (*node == NULL)
{
*node = new AVLTree;
if (*node == NULL)
{
return;
}
(*node)->element = value;
(*node)->height = 0;
(*node)->left = (*node)->right = NULL;
return;
}
else if (value < (*node)->element)
{
insert(value, &((*node)->left));
if (height((*node)->left) - height((*node)->right) == 2)
{
if (value < (*node)->left->element)
{
*node = single_rotation_with_left(*node);
}
else
{
*node = double_rotation_with_left(*node);
}
}
}
else if (value > (*node)->element)
{
insert(value, &((*node)->right));
if (height((*node)->right) - height((*node)->left) == 2)
{
if (value > (*node)->right->element)
{
*node = single_rotation_with_right(*node);
}
else
{
*node = double_rotation_with_right(*node);
}
}
}
(*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;
}
AVLTree *searchmin(AVLTree *node)
{
if (node == NULL)
{
return NULL;
}
else if (node->left == NULL)
{
return node;
}
else
{
return searchmin(node->left);
}
}
AVLTree *searchmax(AVLTree *node)
{
if (node == NULL)
{
return NULL;
}
else if (node->right == NULL)
{
return node;
}
else
{
return searchmax(node->right);
}
}
void Search(AVLTree **parent,AVLTree **node,int i){
while((*node!=NULL)&&((*node)->element != i)){
parent = node;
if((*node)->element >i)
*node = (*node)->left;
else
*node = (*node)->right;
}
}
AVLTree * del(int value, AVLTree **node)
{
AVLTree * x;
AVLTree *tmp_cell;
if (*node ==NULL) return NULL;
if (value < (*node)->element)
{
(*node)->left = del(value, &((*node)->left));
if (height((*node)->right) - height((*node)->left) >= 2)
{
if ((*node)->left && (value < (*node)->left->element))
{
(*node) = double_rotation_with_right((*node));
}
else
{
(*node) = single_rotation_with_right((*node));
}
}
}
else if (value > (*node)->element)
{
(*node)->right = del(value, &((*node)->right));
if (height((*node)->left) - height((*node)->right) >= 2)
{
if ((*node)->right && (value > (*node)->right->element))
{
(*node) = double_rotation_with_left((*node));
}
else
{
(*node) = single_rotation_with_left((*node));
}
}
}
else if ((*node)->left && (*node)->right)
{
tmp_cell = searchmin((*node)->right);
(*node)->element = tmp_cell->element;
(*node)->right = del((*node)->element, &((*node)->right));
}
else
{
tmp_cell = (*node);
if ((*node)->left == NULL)
(*node) = (*node)->right;
else if ((*node)->right == NULL)
(*node) = (*node)->left;
free(tmp_cell);
tmp_cell = NULL;
}
return (*node);
}
int numofnode(AVLTree **p)
{
if ((*p!=0)&&((*p)->element != 13))
return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;
else
return 0;
}
Consider an input sequence that is provided as an input to the insert method
20,50,45,30,35,55,10,100,90,70,5,99,8,96
Give the resulting tree and 45 as input to the method called Del. After Del gets executed, use the insert method to insert 45.
What would be the height of the node 45 in the resulting tree?
(a) 0
(b) 3
(c) 4
(d) 2
Question Number 6
Given a code snippet answer the following question.
struct AVLTree
{
AVLTree * left;
AVLTree * right;
int element;
int height;
};
int MAX(int a, int b){
if(a>=b)
return a;
if(a<b)
return b;
}
int height(AVLTree *node)
{
if (node == NULL)
{
return -1;
}
else
{
return node->height;
}
}
AVLTree * single_rotation_with_left(AVLTree *k2)//Func1
{
AVLTree *k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->left), height(k2->right)) + 1;
return k1;
}
AVLTree * single_rotation_with_right(AVLTree *k2)//Func2
{
AVLTree *k1;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->right), height(k2->left)) + 1;
return k1;
}
AVLTree *double_rotation_with_left(AVLTree *k3)
{
k3->left = single_rotation_with_right(k3->left);
return single_rotation_with_left(k3);
}
AVLTree *double_rotation_with_right(AVLTree *k3)
{
k3->right = single_rotation_with_left(k3->right);
return single_rotation_with_right(k3);
}
void insert(int value, AVLTree **node)
{
if (*node == NULL)
{
*node = new AVLTree;
if (*node == NULL)
{
return;
}
(*node)->element = value;
(*node)->height = 0;
(*node)->left = (*node)->right = NULL;
return;
}
else if (value < (*node)->element)
{
insert(value, &((*node)->left));
if (height((*node)->left) - height((*node)->right) == 2)
{
if (value < (*node)->left->element)
{
*node = single_rotation_with_left(*node);
}
else
{
*node = double_rotation_with_left(*node);
}
}
}
else if (value > (*node)->element)
{
insert(value, &((*node)->right));
if (height((*node)->right) - height((*node)->left) == 2)
{
if (value > (*node)->right->element)
{
*node = single_rotation_with_right(*node);
}
else
{
*node = double_rotation_with_right(*node);
}
}
}
(*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;
}
AVLTree *searchmin(AVLTree *node)
{
if (node == NULL)
{
return NULL;
}
else if (node->left == NULL)
{
return node;
}
else
{
return searchmin(node->left);
}
}
AVLTree *searchmax(AVLTree *node)
{
if (node == NULL)
{
return NULL;
}
else if (node->right == NULL)
{
return node;
}
else
{
return searchmax(node->right);
}
}
void Search(AVLTree **parent,AVLTree **node,int i){
while((*node!=NULL)&&((*node)->element != i)){
parent = node;
if((*node)->element >i)
*node = (*node)->left;
else
*node = (*node)->right;
}
}
AVLTree * del(int value, AVLTree **node)
{
AVLTree * x;
AVLTree *tmp_cell;
if (*node ==NULL) return NULL;
if (value < (*node)->element)
{
(*node)->left = del(value, &((*node)->left));
if (height((*node)->right) - height((*node)->left) >= 2)
{
if ((*node)->left && (value < (*node)->left->element))
{
(*node) = double_rotation_with_right((*node));
}
else
{
(*node) = single_rotation_with_right((*node));
}
}
}
else if (value > (*node)->element)
{
(*node)->right = del(value, &((*node)->right));
if (height((*node)->left) - height((*node)->right) >= 2)
{
if ((*node)->right && (value > (*node)->right->element))
{
(*node) = double_rotation_with_left((*node));
}
else
{
(*node) = single_rotation_with_left((*node));
}
}
}
else if ((*node)->left && (*node)->right)
{
tmp_cell = searchmin((*node)->right);
(*node)->element = tmp_cell->element;
(*node)->right = del((*node)->element, &((*node)->right));
}
else
{
tmp_cell = (*node);
if ((*node)->left == NULL)
(*node) = (*node)->right;
else if ((*node)->right == NULL)
(*node) = (*node)->left;
free(tmp_cell);
tmp_cell = NULL;
}
return (*node);
}
int numofnode(AVLTree **p)
{
if ((*p!=0)&&((*p)->element != 13))
return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;
else
return 0;
}
Consider an input sequence that is provided as an input to the insert method
20,50,45,30,35,55,10,100,90,70,5,99,8,96
The resulting tree is given as input to the following code snippet
int nol(AVLNode **p)
{
if (*p==0)
return 0;
if ((*p)->left==0 && (*p)->right ==0)
return 1;
else
return (nol(&(*p)->right)+nol(&(*p)->left) + 1);
}
Which one of the following would be the output of above code snippet?
(a) 8
(b) 7
(c) 6
(d) 14
Question Number 7
Given a code snippet answer the following question.
struct AVLTree
{
AVLTree * left;
AVLTree * right;
int element;
int height;
};
int MAX(int a, int b){
if(a>=b)
return a;
if(a<b)
return b;
}
int height(AVLTree *node)
{
if (node == NULL)
{
return -1;
}
else
{
return node->height;
}
}
AVLTree * single_rotation_with_left(AVLTree *k2)//Func1
{
AVLTree *k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->left), height(k2->right)) + 1;
return k1;
}
AVLTree * single_rotation_with_right(AVLTree *k2)//Func2
{
AVLTree *k1;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->right), height(k2->left)) + 1;
return k1;
}
AVLTree *double_rotation_with_left(AVLTree *k3)
{
k3->left = single_rotation_with_right(k3->left);
return single_rotation_with_left(k3);
}
AVLTree *double_rotation_with_right(AVLTree *k3)
{
k3->right = single_rotation_with_left(k3->right);
return single_rotation_with_right(k3);
}
void insert(int value, AVLTree **node)
{
if (*node == NULL)
{
*node = new AVLTree;
if (*node == NULL)
{
return;
}
(*node)->element = value;
(*node)->height = 0;
(*node)->left = (*node)->right = NULL;
return;
}
else if (value < (*node)->element)
{
insert(value, &((*node)->left));
if (height((*node)->left) - height((*node)->right) == 2)
{
if (value < (*node)->left->element)
{
*node = single_rotation_with_left(*node);
}
else
{
*node = double_rotation_with_left(*node);
}
}
}
else if (value > (*node)->element)
{
insert(value, &((*node)->right));
if (height((*node)->right) - height((*node)->left) == 2)
{
if (value > (*node)->right->element)
{
*node = single_rotation_with_right(*node);
}
else
{
*node = double_rotation_with_right(*node);
}
}
}
(*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;
}
AVLTree *searchmin(AVLTree *node)
{
if (node == NULL)
{
return NULL;
}
else if (node->left == NULL)
{
return node;
}
else
{
return searchmin(node->left);
}
}
AVLTree *searchmax(AVLTree *node)
{
if (node == NULL)
{
return NULL;
}
else if (node->right == NULL)
{
return node;
}
else
{
return searchmax(node->right);
}
}
void Search(AVLTree **parent,AVLTree **node,int i){
while((*node!=NULL)&&((*node)->element != i)){
parent = node;
if((*node)->element >i)
*node = (*node)->left;
else
*node = (*node)->right;
}
}
AVLTree * del(int value, AVLTree **node)
{
AVLTree * x;
AVLTree *tmp_cell;
if (*node ==NULL) return NULL;
if (value < (*node)->element)
{
(*node)->left = del(value, &((*node)->left));
if (height((*node)->right) - height((*node)->left) >= 2)
{
if ((*node)->left && (value < (*node)->left->element))
{
(*node) = double_rotation_with_right((*node));
}
else
{
(*node) = single_rotation_with_right((*node));
}
}
}
else if (value > (*node)->element)
{
(*node)->right = del(value, &((*node)->right));
if (height((*node)->left) - height((*node)->right) >= 2)
{
if ((*node)->right && (value > (*node)->right->element))
{
(*node) = double_rotation_with_left((*node));
}
else
{
(*node) = single_rotation_with_left((*node));
}
}
}
else if ((*node)->left && (*node)->right)
{
tmp_cell = searchmin((*node)->right);
(*node)->element = tmp_cell->element;
(*node)->right = del((*node)->element, &((*node)->right));
}
else
{
tmp_cell = (*node);
if ((*node)->left == NULL)
(*node) = (*node)->right;
else if ((*node)->right == NULL)
(*node) = (*node)->left;
free(tmp_cell);
tmp_cell = NULL;
}
return (*node);
}
int numofnode(AVLTree **p)
{
if ((*p!=0)&&((*p)->element != 13))
return numofnode (&(*p)->right) + numofnode (&(*p)->left) + 1;
else
return 0;
}
Consider an input sequence that is provided as an input to the insert method
20,50,45,30,35,55,10,100,90,70,5,99,8,96
What would be the height of the node 55 in the resulting tree?
(a) 4
(b) 3
(c) 0
(d) None of these
Question Number 8
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
The height of a tree is defined as follows:
The height of a terminal node is 0.
The height of an internal node is 1 + the maximum of the heights of its children.
Suppose it is specified that height() will only be called on InternalNodes.
Consider the following a implementation of InternalNode.height(), with no implementation in either Node or TerminalNode?
int height() {
int lheight = (left == null) ? 0 : left.height();
int rheight = (right == null) ? 0 : right.height();
return (lheight > rheight ? lheight : rheight);
}
Which, if any, of the following are problems that will cause the above code to fail:
It won’t compile because there is no definition (concrete or abstract) in Node.
1 should be added to the value of the return
(a) The code is correct as is.
(b) A: it won’t compile, but if that were fixed it would work and produce the correct result.
(c) B: it will compile but produce the wrong result.
(d) Both: it won’t compile, and even if that were fixed, it would produce the wrong result.
Question Number 9
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
Which of the following is the first to correctly define methods for counting the empty subtrees of a tree? (Only the relevant methods are shown for each class, and if the class isn’t shown in the answer it doesn’t contain a countEmptySubtrees member.)
class InternalNode extends Node {
int countEmptySubtrees() {
return left.countEmptySubtrees()) + right.countEmptySubtrees());
}
}
class InternalNode extends Node {
int countEmptySubtrees() {
return
((left == null) ? 1 : left. countEmptySubtrees()) +
((right == null) ? 1 : right. countEmptySubtrees());
}
}
abstract class Node {
abstract int countEmptySubtrees();
}
class TerminalNode extends Node {
int countEmptySubtrees() {
return 0;
}
}
class InternalNode extends Node {
int countEmptySubtrees() {
return
((left == null) ? 1 : left. countEmptySubtrees()) +
((right == null) ? 1 : right. countEmptySubtrees());
}
}
(a) A
(b) B
(c) C
(d) None of them provide a correct implementation.
Question Number 10
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
We want to define Boolean contains(String str) to return True if the tree contains a node with str as its value and False otherwise. Here are definitions for two of the three classes:
abstract class Node {
abstract boolean contains(String str);
}
class TerminalNode extends Node {
boolean contains(String str) {
return value.equals(str);
}
}
Which of the following methods is the first to correctly implement contains for InternalNode?
class InternalNode extends Node {
boolean contains(String str) {
if (left.contains(str))
return true;
if (right.contains(str))
return true;
}
}
class InternalNode extends Node {
boolean contains(String str) {
if (left != null)
return left.contains(str);
if (right != null)
return right.contains(str);
}
}
class InternalNode extends Node {
boolean contains(String str) {
return
((left != null) && left.contains(str)) ||
((right != null) && right.contains(str));
}
}
(a) A
(b) B
(c) C
(d) None of them is a correct implementation.
.jpg)
.jpg)
.jpg)
