Coding Skills (Advanced)
instructions
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
|
Questions
|
Time
|
Section
1
|
10
|
Minutes 20
|
Section
2
|
10
|
Minutes 20
|
Total
|
19
|
Miinutes 40
|
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.
No comments :
Post a Comment