TECHNICAL MCQ
1.
What is the third number from the left while doing bubble sort in the 3rd iteration for 5 1 4 2 8?
2
8
5
4
2.
Which of the following is not the required condition for binary search algorithm?
There must be mechanism to delete and/or insert elements in list.
Number values should only be present
A.The list must be sorted
There should be the direct access to the middle element in any sub list
3.
Number of comparisons required for an unsuccessful search of an element in a sequential search,
organized, xed length, symbol table of length L is
(L+1)/2
2L
L
L/2
4.
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)
Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
5.
The Average case occurs in linear search algorithm ..........
when item is the last element in the array
Item is the last element in the array or item is not there at all
when item is not the array at all
when item is somewhere in the middle of the array
6.
Which of the following Sorting Algorithm will perform the worst if the numbers are ordered in the
opposite form?
Bubble
Selection
Radix
Quick Sort
7.
Which of the following is not a limitation of binary search algorithm?
there must be a mechanism to access middle element directly
binary search algorithm is not efficient when the data elements more than 1500.
must use a sorted array
requirement of sorted array is expensive when a lot of insertion and deletions are needed
8.
Which of the following sorting algorithms in its typical implementation gives best performance when
applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).
Merge Sort
Insertion Sort
Quick Sort
Heap Sort
9.
Binary Search can have _ number of maxm comparsions?
n (D)(n+1)/2
2*log n
log(n) + 1
10.
Which of the following is not a limitation of binary search algorithm?
there must be a mechanism to access middle element directly.
binary search algorithm is not efficient when the data elements more than 1500.
must use a sorted array.
requirement of sorted array is expensive when a lot of insertion and deletions are needed.
-------------------------------------------------------------------------------------------------------
PROGRAMMING
1.
Problem statement
Pavel made a photo of his favourite stars in the sky. His camera takes a photo of all points of the sky
that belong to some rectangle with sides parallel to the coordinate axes.
Strictly speaking, it makes a photo of all points with coordinates (x,y), such that x1≤x≤x2 and y1≤y≤y2,
where (x1,y1) and (x2,y2) are coordinates of the left bottom and the right top corners of the rectangle
being photographed. The area of this rectangle can be zero.
After taking the photo, Pavel wrote down coordinates of n of his favourite stars which appeared in the
photo. These points are not necessarily distinct, there can be multiple stars in the same point of the
sky.
Pavel has lost his camera recently and wants to buy a similar one. Specifically, he wants to know the
dimensions of the photo he took earlier. Unfortunately, the photo is also lost. His notes are also of not
much help; numbers are written in random order all over his notepad, so it's impossible to tell which
numbers specify coordinates of which points.
Pavel asked you to help him to determine what are the possible dimensions of the photo according to
his notes. As there are multiple possible answers, find the dimensions with the minimal possible area of
the rectangle.
Input Format
The first line of the input contains an only integer n , the number of points in Pavel's records.
The second line contains 2⋅n integers a1, a2, ..., a2⋅n , coordinates, written by Pavel in some order.
Constraints
(1≤n≤100000)
(1≤ai≤10^9)
PYTHON CODE :
n=int(input())
a=sorted(map(int,input().split()))
print(min([(a[n-1]-a[0])*(a[-1]-a[n])]+[(a[-1]-a[0])*(y-x)
for x,y in zip(a,a[n-1:])]))
2.
Problem statement
There was an electronic store heist last night.
All keyboards which were in the store yesterday were numbered in ascending order from some integer
number x. For example, if x=4 and there were 3 keyboards in the store, then the devices had indices 4,
5 and 6, and if x=10 and there were 7 of them then the keyboards had indices 10, 11, 12, 13, 14, 15 and 16.
Input Format
The first line contains single integer n — the number of keyboards in the store that remained after the
heist.
The second line contains n distinct integers a1,a2,…,an — the indices of the remaining keyboards. The
integers ai are given in arbitrary order and are pairwise distinct. After the heist, only n keyboards
remain, and they have indices a1,a2,…,an. Calculate the minimum possible number of keyboards that
have been stolen. The staff remember neither x nor the number of keyboards in the store before the
heist.
Constraints
(1≤n≤1000)
(1≤ai≤10^9)
Output Format
Print the minimum possible number of keyboards that have been stolen if the staff remember neither x
nor the number of keyboards in the store before the heist.
PYTHON CODE :
n=int(input());l=list(map(int,input().split()));print(max(l)-min(l)+1-n)
3.
Problem statement
Two players play a game.
Initially there are n integers a1,a2,…,an written on the board. Each turn a player selects one number and
erases it from the board. This continues until there is only one number left on the board, i. e. n−1 turns
are made. The first player makes the first move, then players alternate turns.
The first player wants to minimize the last number that would be left on the board, while the second
player wants to maximize it.
You want to know what number will be left on the board after n−1 turns if both players make optimal
moves.
Input Format
The first line contains one integer n — the number of numbers on the board.
The second line contains n integers a1,a2,…,an .
Constraints
(1≤n≤1000)
(1≤ai≤10^6)
Output Format
Print one number that will be left on the board.
PYTHON CODE :
n=int(input())
print(sorted(map(int,input().split()))[(n-1)//2])
-------------------------------------------------------------------------------
Post a Comment