Partner Sites
Aricent Technical and C model questions
1. Sample Questions.
1) When we talk about linked lists, does it have to do with (choose the most
closely related item):
i. data types (such as priority queues)
ii. goals (such as adaptability)
iii. implementation (of, say, a sequence)
2) Underscore the line(s) (if any) in the following code which potentially break
the principle of encapsulation:
class Node {
public Object element;
public Node next;
Node(){this(null, null); }
void setNext(Node newText){next = newText; }
Node getNext(){return next; }
}
3) What is the primary reason to use quadratic probing instead of linear probing?
(choose the most closely related item):
i. Easier to expand the hash table when it gets full
ii. To avoid the primary cluster which may cause excessive data collision
iii. Achieve the same search time with less memory
iv. Easier to support delete
4) Suppose that there are N distinct elements in a binary heap (with the maximum
at the root). Which positions could possibly be occupied by the fourth largest
element?
i. 1
ii. 2 or 3
iii. 4 through 7
iv. 2 through 15
v. 16 and higher
5) Characterize, using the big-Oh notation, the worst-case running time of the
following algorithm:
Let A be a given array of n integers.
for i <- 0 to n-1 do
for j <- 0 to (i*i)-1 do
Let A[j mod n] <- j.
end for
end for
Best characterization: O(_______).
2. (Linked list) Recall we did singly linked list in PA #4. To refresh your memory,
· Consider a list with elements (1,2,3,4,5)
· The list will be like 1_ 2_3_4_5
Singly linked list doesn’t have loops. Suppose your friend (call him Bob)
has inadvertently introduced a loop into his implementation on PA #4
· Consider a list with elements (1,2,3,4,5)
· Let 3 point to 1 instead of pointing to 4
· The list will be like 1_ 2_3 4_5
Since most of your friends suffer from the same bug while implementing PA#4
you decide to help them by writing a function which detects loops in a singly
linked list.
· Write program that outputs ‘false’ if there is no loop in the list input and
‘true’ if there is a loop in a list output
· Fill in the following code
o class list_sorted {
public:
// You need to implement this
bool FindLoop() {
}
private:
node* pHead;
};
o struct node{
public:
int x;
node* next;
};
· Hint:
o Change the node data structure. Have some sort of counter which
indicates how many times a node is visited when you traverse through
the link list.
o There might be better ideas than this!
3. (Hash table) You have a hash table of size m = 11 and two has functions h1 and h2:
h1(x) = (sum of the values of the first and last letters of x) mod m
h2(x) = ((value of the last letter) mod (m – 1)) + 1
Where the value of a letter is its position in the alphabet, as in the following table:
a b c d e f g h i g k l m
1 2 3 4 5 6 7 8 9 10 11 12 13
n o p q r s t u v w x y z
14 15 16 17 18 19 20 21 22 23 24 25 26
1) Draw a picture of the resulting hash table after inserting the following words (by
the order):
ibex, hare, ape, bat, koala, mud, dog, carp, stork
2) Highlight cells that are looked at when trying to find bird. Do this for each of the
following techniques.
Chaining with h1 as your hash function.
Linear probing with h1 as your hash function.
4. (Heap) Give an algorithm for changing the value of an arbitrary element from a heap
of size N. Also, determine the worst case time complexity of your algorithm.
Describe your algorithm in pseudo-code. You may assume that the position of the
element whose value to be changed is given.
5. (Binary tree) Let T be a binary tree.
1) If T has seven nodes, what is its minimum height?
What is its maximum height?
Draw two trees with seven nodes that achieve the minimum and maximum height,
respectively.
2) When deleting a node of a binary search tree, if we decide to replace it with a
node in its left subtree (of course, if it has one),which node should we choose?
3) A particular binary search tree has the following known about it:
A pre-order traversal yields 88, 6, 1, 3, 2, 5, 4, 30, 10, 20.
A post-order traversal yields 2, 4, 5, 3, 1, 20, 10, 30, 6, 88.
Draw this tree
.
4) What is the in-order traversal of the tree from 3)?
5) Using the node value
