1) I have a problem to solve which takes as input a number n.

The problem has a property that

given the solution for (n-1), I can easily solve the problem for n. Which programming technique
will I use to solve such a problem?
d) Recursion
Ans: d
Recursion means calling again and again. Therefore problem n can be solved with the solution n-
1, by repeatedly calling it.

2) The memory space needed by an algorithm has a fixed part independent of the problem
instance solved and a variable part which changes according to the problem instance solved. In
general, which of these two is of prime concern to an algorithm designer?
b) Variable Part
Ans: b
Variable part, since it changes according to the problem instance solved.

3) Pankaj and Mythili were both asked to write the code to evaluate the following expression:
a - b+ c/(a-b) + (a-b)^2
Pankaj writes the following code statements (Code A):
print (a-b) + c/(a-b) + (a-b)*(a-b)
Mythili writes the following code statements (Code B):
d = (a-b)
print d + c/d + d*d
If the time taken to load a value in a variable, for addition, multiplication or division between
two operands is same, which of the following is true?
a) Code A uses lesser memory and is slower than Code B
Ans: a
Code A uses lesser memory and it is slower than code B. Since code B uses another variable d it
needs to have more memory than code A. But code B will execute faster.

4) A queue is implemented as a singly-linked-list for easy addition and deletion of elements.

Each node has an element and a pointer to another node. Which node will point to empty/no
location?
a) Rear
Ans: a
The new node will always be added at the rear end, so the new/empty location will be pointed by
Rearend.

5) Q is an empty queue. The following operations are done on it:

ADD 5
ADD 7
ADD 46
DELETE
ADD 13
DELETE
DELETE
ADD 10
What will be the content of Q after these operations? Front is marked by (F) and Rear is marked
by (R).
a) 10(R) 13(F)
Ans: a
Queue follows FIFO principle, so performing the FIFO operation the Front will be pointing to 13
and Rear will be pointing to 10.

6) A is an empty stack. The following operations are done on it.

PUSH(1)
PUSH(2)
POP
PUSH(5)
PUSH(6)
POP
What will the stack contain after these operations?
d) 1 5

Ans: d
To an Empty Stack A,
PUSH(1): 1
PUSH(2): 1 2
POP: 1
PUSH(5): 1 5
PUSH(6): 1 5 6
POP: 1 5
By the end of all the operation, the elements remaining are 1 5.

7) What is implied by the argument of a function?

a) The variables passed to it when it is called
Ans: a
The variables that are passed as inputs to a function in a function call are called arguments.

8) In a sequential programming language, code statements are executed in which order?

b) From top to bottom
Ans: b
In a sequential programming language code statements are executed from top to bottom.

9) A pseudo-code is used. Assume that when two data-types are processed through an operator,
the answer maintains the same data-type as the input data-types. Assume that all data-types have
enough range to accommodate any number. If two different data-types are operated on, the result
assumes the more expressive data-type.
What will be the output of the following pseudo-code statements?
Integer a = 456, b, c, d =10
b = a/d
c=a-b
print c

d) 411
Ans: d
a/d = 456/10 = 45.6 =45 ( input data type and the output must be same) c = 456 45 = 411

10) Geeta takes as input 2 integer numbers, a and b, whose value can be between 0 and 31. She
stores them as 5 bit numbers. She writes the following code to process these numbers to produce
a third number c c = 2*(a - b)
In how many minimum bits should Geeta store c?
b) 7 bits
Ans: b
c = 2*(a - b)
For lowest number, when a=0 and b=31 c= 2*(0-31) = -62
For highest number, when a=31 and b=0 c= 2*(31-0) = 62
Range= -62 to 62, so It will fit on (-64 to 63) i.e., 2^7
Bits Required = 7

Amcat Programming Question - Set 2

11) Which of the following data structures may give overflow error, even though the current
number of elements in it is less than its size?
a) Queue implemented in a linear array
Ans: a
In a queue data structure implemented in a static linear array, for an enqueue operation the rear
pointer is incremented. Similarly, for a dequeue operation, the front pointer is incremented.
When the front pointer is incremented, the memory space before front becomes useless. So even
if the size is more the queue will end up showing an overflow error.

12) Number of possible ordered trees with 3 nodes A, B, C is

b) 12
Ans: b

13) Farhan writes a code to find the factorial of an inputted number. His code gives correct
answers for some inputs and incorrect answers for others. What kind of error does his program
have?
c) Logical Error
Ans: c
Syntactical Error and Run-time error will not give any output. Logical error is a bug in a program
that causes it to operate incorrectly,but not to terminate abnormally. A logic error produces
unintended or undesired output, although it may not immediately be recognized as such. The
problem to the given question can be Integer overflow. If int is 32 bits, then the largest value it
can represent is 2147483647. But 13 factorial is 6227020800. If it is 64-bit integer type such
along long, this can give up to 20 factorial.

14) As part of the maintenance work, you are entrusted with the work of rearranging the library
books in a shelf in proper order, at the end of each day. The ideal choice will be Bubble Sort
b) Selection Sort
Ans: b
Sorting of books in a library is an example of insertion sort. We pick a book and place it in its
corresponding place as it is done in an insertion sort.

15) A hash table can store a maximum of 10 records. Currently there are records in locations 1,
3, 4, 7, 8, 9, 10. The probability of a new record going into location 2, with a hash function
resolving collisions by linear probing is
a) 0.6
Ans: a
The probability is 6/10. Due to uniform distribution, the probability that the new record will be
placed to any location X will be same for any X of (1,2,3,4,5,6,7,8,9,10) & will be equal to 1/10.
Now if the hash function will try to place the new record in to any of the locations 1,7,8,9,10 the
record will be redirected to location 2 due to collision resolution by linear probing. And if hash
function will try to place the new record into 2, since location 2 is available, the record will go to
location 2. So The probability of going new record into location 2, will be same as probability
that the output of hash function is any one of (1,2,7,8,9,10) out of (1,2,3,4,5,6,7,8,9,10) where
each location is equally likely. So the chances will be 6/10 i.e., 0.6

16)An array contains the following elements in order: 7 6 12 30 18. Insertion sort is used to sort
the array in ascending order. How many times will an insertion be made?
a) 2
Ans: a

The insertion is made twice. First insertion is inserting 6 before 7. Second insertion is inserting
18 between 12 and 30.
17) Ragu writes a program to find an element in the array A[5] with the following elements in
order: 18 32 44 46 57. She runs the program to find a number X. X is found in the first iteration
of binary search. What is the value of X?
a) 44
Ans: a
The array has 18 32 44 46 57 Binary search is performed only on sorted arrays. In this search the
middle element is identified and if the element to be searched is lesser than the middle element
then all the elements to the right of the middle value are neglected and again the middle value is
obtained for the remaining elements. If the element to be searched is greater than the middle
element then all the elements to the left of the middle value are neglected and again the middle
value is obtained for the remaining elements. If the value is obtained in the first iteration itself,
then the value should be the middle element of the array. Here the middle element is 44.

18) A stack is implemented as a linear array A[0...N-1]. Farhan writes the following functions
for pushing an element E in to the stack.
function PUSH( top, E, N )
{
if(X)
{
top= top+1
A[top] = E
}
else
{
print "Overflow"
}
return top
}
Fill in the condition X
b) top <N-1
Ans: b
The array is 0,1,2,,N-1. The maximum size of the array is N-1. To perform a PUSH operation,
the stack should have free space. This is checked using the top pointer. If the top pointer is less
than N1(maximum size) then PUSH operation can be done. If not the condition is called Stack
Overflow. Hence X should be top<N-1.

19) A queue is implemented by a linear array of size 10 (and not as a circularly connected array).
Front and Rear are represented as an index in the array. To add an element, the rear index is
incremented and the element is added. To delete an element, the front index is incremented. The
following operations are done on an empty queue.
ADD 1; DELETE; ADD 2; ADD 3; ADD 4; DELETE, DELETE
After this set of operations, what is the maximum capacity of the queue?
b) 7
Ans: b
The maximum size of the queue is 10. For every DELETE operation the front pointer is
incremented and the space becomes useless. Here, there are three DELETE operations. So, the
front pointer is incremented by three spaces and these three spaces become useless. Hence 10-
3=7. Only 7 spaces are available which the maximum size of the array is.

20) Riyaz has a book of tickets and wants to store ticket numbers in a data structure. New tickets
are added to the end of the booklet. Ticket at the top of the stack is issued to the customer. Which
data structure should Riyaz use to represent the ticket booklet?
a) Queue
Ans: a
Tickets are added to the end and are removed from the top. This follows the logic of First In First
Out. This logic can be represented using a queue data structure.

Amcat Programming Questions - Set 3

21) Pragya sells footballs. She has a large container to store footballs which is closed from
below. Footballs are piled one on top of the other in the box. When new balls are supplied,
Pragya puts the balls in the box from the top. When a customer buys a ball, she delivers the ball
at the top of the pile to the customer. Each ball has a code. She wants to store the ball codes in a
data structure to keep track of her inventory. What data-structure should she use?
b) Stack
Ans: b
The foot balls are put in the box from the top and are removed from the top. This follows the
logic Last In First Out. This logic can be represented using a stack data structure.
22) A[0...19] is an array of maximum size 20. The number of elements it contains is stored in the
variable, number Elements. Currently it contains 11 elements. Swati wants to insert an element
val after the mth element in the array. She writes the following code for it:
for X
A[n+1] = A[n]
end
A[m] =val
Fill in X.
c) n = m to (numberElements-1) increment 1

Ans: c
The elements will have to be moved from right to left. The condition would be moving the
elements from the mth position till the last position. The last position can be identified by number
Elements-1(since array index starts from 0,1,2,3,). Number of elements is 11. So the elements
will be stored from 0 to 10. The starting value will be from the m th position. So from mth position
till the last position we will have to increment 1 to create free space. So, n= m to
(numberElements-1) increment 1.

23) To fully specify a singly linked linked-list, which of the following options is necessarily
required?
a) Address of first element
Ans: a
To fully specify a linked list, we need HEAD pointer. The HEAD pointer holds the address of
the first element. Hence address of the first element is required.

24) A list is implemented as a singly linked link-list. The address of the first and last node are
stored in variables first and last. Given the address of a node is given in the variable node, the
element stored in the node can be accessed by the statement node->data and the address to the
next node can be accessed by node->next. Yusuf writes the code to delete the first element from
the linked-list. He writes the following function, where first and last are passed by reference.
function deleteElement(first, last)
{
if (firstisequalnull)
{ print "List empty" }
else
{
first = first->next
}
}
In which of the following scenarios will the code not work properly?
d) It will work well in all possible cases.

Ans: d
When the list has no elements the program will successfully return List empty. When list has a
single element, the node->next value will be NULL. When executing the first=first->next
statement the first pointer will take NULL value which will successfully eliminate the first node
from the list. When list has two elements then the program will move the first pointer to the next
node which will successfully eliminate the first node from the list.

25) Which of these is untrue about a binary search tree?

a) Each node has two children
Ans: a
Each node may have two children. But it is not a compulsion that each node should have two
children. A node in a binary search tree may have no child or a single child or at most two
children.

26) For a binary search tree, which traversal will result in a sorted list?
b) Inorder
Ans: b
In a binary search tree all the elements less than the root node are towards the left subtree and all
the elements greater than the root node are towards the right subtree. The left most node of a tree
will have the minimum value and the right most node of the tree will have the maximum value.
To sort the elements in ascending order, the traversal must be: left sub tree, root, right sub tree.
This is done by in order traversal.

27) Fizahavea binary search tree and want to derive a list sorted in descending order from it. For
each node, what traversal ordering will Fiza use?
c) right sub-tree, root, left sub-tree
Ans: c
In a binsary search tree all the elements less than the root node are towards the left subtree and
all the elements greater than the root node are towards the right subtree. The left most node of a
tree will have the minimum value and the right most node of the tree will have the maximum
value. To sort the elements in descending order, the traversal must be: right subtree, root, left
subtree.

28) For a binary tree with n nodes, what is the time complexity to search an element in it?
a) O(log n)

Ans: a

29) To search an element in a binary tree, all the nodes need not be visited. Therefore, it is not
O(n). The number of possibilities reduces by half for every iteration. Hence the time complexity
is O(log n).
We have a list of elements and we want to sort them using insertion sort. Which data structure
among the following should we use to store the elements to give low time-complexity of sorting
on average?
(Assume all access times as would be in a real-world scenario)
b) Linked List
Ans: b
Stack and hash table cannot be used for sorting since the order of the elements in them cannot be
modified. Array will no be efficient as inserting an element in the middle will have to move all
the elements. Linked list data structure would be efficient for sorting as inserting an element in
the middle will require only change in pointers and no movement of data.

30) Rashmi works on a computer where the time of comparing two numbers is very high and this
time dominates the execution time. She implements a few different sorting algorithms. One
algorithm out of these always took the same amount of execution time irrespective of the input
array. Which sorting algorithm was this?
b) Bubble sort
Ans: b
Bubble sort makes the maximum number of comparisons.