InterviewSolution
Saved Bookmarks
InterviewSolution
This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
Consider the following grammar.S -> S * ES -> EE -> F + EE -> FF -> idConsider the following LR(0) items corresponding to the grammar above.(i) S -> S * .E(ii) E -> F. + E(iii) E -> F + .E Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?(A) (i) and (ii)(B) (ii) and (iii)(C) (i) and (iii)(D) None of the above |
| Answer» | |
| 2. |
Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is: (GATE CS 2006)(A) n — 1(B) 2n — 2(C) nC2(D) 2 |
| Answer» | |
| 3. |
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:(A) Queue(B) Stack(C) Heap(D) B-Tree |
| Answer» | |
| 4. |
A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?(A) 400(B) 500(C) 600(D) 700 |
| Answer» None | |
| 5. |
In a binary max heap containing n numbers, the smallest element can be found in time(A) O(n)(B) O(Logn)(C) O(LogLogn)(D) O(1) |
| Answer» | |
| 6. |
You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°?(A) A(B) B(C) C(D) D |
| Answer» | |
| 7. |
Which one of the following in place sorting algorithms needs the minimum number of swaps?(A) Quick sort(B) Insertion sort(C) Selection sort(D) Heap sort |
| Answer» | |
| 8. |
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.(A) log2n(B) n(C) 2n + 1(D) 2^n — 1 |
| Answer» | |
| 9. |
Consider the following C-program fragment in which i, j and n are integer variables.for (i = n, j = 0; i >0; i /= 2, j += i);Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?(A) val(j) = (logn)(B) vaI(j) = (sqrt(n))(C) val(j) = (n)(D) val(j) = (nlogn)(A) A(B) B(C) C(D) D |
| Answer» | |
| 10. |
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?(A) R is NP-complete(B) R is NP-hard(C) Q is NP-complete(D) Q is NP-hard |
| Answer» | |
| 11. |
For which one of the following reasons does Internet Protocol (IP) use the timeto- live (TTL) field in the IP datagram header(A) Ensure packets reach destination within that time(B) Discard packets that reach later than that time(C) Prevent packets from looping indefinitely(D) Limit the time for which a packet gets queued in intermediate routers. |
| Answer» | |
| 12. |
Consider the following grammar:S → FRR → S | εF → idIn the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $] respectively.(A) {S → FR} and {R → ε }(B) {S → FR} and { }(C) {S → FR} and {R → *S}(D) {F → id} and {R → ε} |
| Answer» | |
| 13. |
Consider the following translation scheme.S → ERR → *E{print(“*”);}R | εE → F + E {print(“+”);} | FF → (S) | id {print(id.value);}Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input ‘2 * 3 + 4’, this translation scheme prints(A) 2 * 3 + 4(B) 2 * +3 4(C) 2 3 * 4 +(D) 2 3 4+* |
| Answer» None | |
| 14. |
Suppose we have a O(n) time algorithm that finds median of an unsorted array.Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.(A) O(n^2 Logn)(B) O(n^2)(C) O(n Logn Logn)(D) O(nLogn) |
| Answer» | |
| 15. |
Consider these two functions and two statements S1 and S2 about themint work1(int *a, int i, int j){int x = a[i+2];a[j] = x+1;return a[i+2] – 3;}int work2(int *a, int i, int j){int t1 = i+2;int t2 = a[t1];a[j] = t2+1;return t2 – 3;}S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1(A) S1 is false and S2 is false(B) S1 is false and S2 is true(C) S1 is true and S2 is false(D) S1 is true and S2 is true |
| Answer» | |
| 16. |
Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and c[n + m] be another integer array.void xyz(int a[], int b [], int c[]){int i, j, k;i = j = k = O;while ((i<n) && (j<m))if (a[i] < b[j]) c[k++] = a[i++];else c[k++] = b[j++];}Which of the following condition(s) hold(s) after the termination of the while loop? (GATE CS 2006)(i) j < m, k = n+j-1, and a[n-1] < b[j] if i = n(ii) i < n, k = m+i-1, and b[m-1] <= a[i] if j = m(A) only (i)(B) only (ii)(C) either (i) or (ii) but not both(D) neither (i) nor (ii) |
| Answer» | |
| 17. |
Given two arrays of numbers a1, a2, a3,…an and b1, b2, .. bn where each number is 0 or 1, the fastest algorithm to find the largest span(i, j) such that ai + ai+1, ….aj = bi + bi+1, .. bj. or report that there is not such span,(A) Takes O(n3) and Ω(2n) time if hashing is permitted(B) Takes O(n3) and Ω(n2.5) time in the key comparison model(C) Takes θ(n) time and space(D) Takes O(√n) time only if the sum of the 2n elements is an even number |
| Answer» | |
| 18. |
Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and n in G are at least 2. which one of the following statements is true?(A) There must exist a vertex w adjacent to both u and n in G(B) There must exist a vertex w whose removal disconnects u and n in G(C) There must exist a cycle in G containing u and n(D) There must exist a cycle in G containing u and all its neighbours in G. |
| Answer» | |
| 19. |
Given two three bit numbers a2a1a0 and b2b1b0 and c, the carry in, the function that represents the carry generate function when these two numbers are added is:(A) A(B) B(C) C(D) D |
| Answer» | |
| 20. |
A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is:Then R is:(A) Neither a Partial Order nor an Equivalence Relation(B) A Partial Order but not a Total Order(C) A Total Order(D) An Equivalence Relation |
| Answer» | |
| 21. |
Let S = {1, 2, 3, …., m}, m>3. Let x1, x2,….xn be the subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets that contain the element i. That is, f(i) = |{j|i }|.Then, is :(A) 3m(B) 3n(C) 2m + 1(D) 2n + 1 |
| Answer» | |
| 22. |
Consider the following statements about the context free grammarG = {S → SS, S → ab, S → ba, S → Ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?(A) I only(B) I and III only(C) II and III only(D) I, II and III |
| Answer» | |
| 23. |
Let E, F and G be finite sets.Let X = (E ∩ F) – (F ∩ G) and Y = (E – (E ∩ G)) – (E – F).Which one of the following is true?(A) X ⊂ Y(B) X ⊃ Y(C) X = Y(D) X – Y ≠ φ and Y – X ≠ φ |
| Answer» | |
| 24. |
Given a set of elements N = {1, 2, …, n} and two arbitrary subsets A⊆N and B⊆N, how many of the n! permutations π from N to N satisfy min(π(A)) = min(π(B)), where min(S) is the smallest integer in the set of integers S, and π(S) is the set of integers obtained by applying permutation π to each element of S?(A) (n – |A ∪ B|) |A| |B|(B) (|A|2+|B|2)n2(C) n! |A∩B| / |A∪B|(D) |A∩B|2nC|A∪B| |
| Answer» | |
| 25. |
F is an n*n real matrix. b is an n*1 real vector. Suppose there are two n*1 vectors, u and v such that, u ≠ v and Fu = b, Fv = b. Which one of the following statements is false?(A) Determinant of F is zero.(B) There are an infinite number of solutions to Fx = b(C) There is an x≠0 such that Fx = 0(D) F must have two identical rows |
| Answer» | |
| 26. |
For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:(A) (2nCn) / (4^n)(B) (2nCn) / (2^n)(C) 1 / (2nCn)(D) 1/2 |
| Answer» | |
| 27. |
We are given a set X = {x1, …. xn} where xi = 2i. A sample S ⊆ X is drawn by selecting each xi independently with probability pi = 1/2. The expected value of the smallest number in sample S is:(A) 1/n(B) 2(C) sqrt(n)(D) n |
| Answer» | |
| 28. |
Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest. 1. T1 start 2. T1 B old=12000 new=10000 3. T1 M old=0 new=2000 4. T1 commit 5. T2 start 6. T2 B old=10000 new=10500 7. T2 commit Suppose the database system crashes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?(A) We must redo log record 6 to set B to 10500(B) We must undo log record 6 to set B to 10000 and then redo log records 2 and 3.(C) We need not redo log records 2 and 3 because transaction T1 has committed.(D) We can apply redo and undo operations in arbitrary order because they are idempotent |
| Answer» | |
| 29. |
(A) L1 only(B) L3 Only(C) L1 and L2(D) L2 and L3 |
| Answer» | |
| 30. |
A CPU has a cache with block size 64 bytes. The main memory has k banks, each bank being c bytes wide. Consecutive c − byte chunks are mapped on consecutive banks with wrap-around. All the k banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of parallel bank accesses depending on the amount of data obtained by accessing all the k banks in parallel. Each iteration requires decoding the bank numbers to be accessed in parallel and this takes. k/2 ns The latency of one bank access is 80 ns. If c = 2 and k = 24, the latency of retrieving a cache block starting at address zero from main memory is:(A) 92 ns(B) 104 ns(C) 172 ns(D) 184 ns |
| Answer» | |
| 31. |
A CPU has a five-stage pipeline and runs at 1 GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instructioncomputes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 109 instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is:(A) 1.0 second(B) 1.2 seconds(C) 1.4 seconds(D) 1.6 seconds |
| Answer» | |
| 32. |
Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP address 203.197.75.201 and netmask 255.255.192.0. which one of the following statements is true?(A) C1 and C2 both assume they are on the same network(B) C2 assumes C1 is on same network, but C1 assumes C2 is on a different network(C) C1 assumes C2 is on same network, but C2 assumes C1 is on a different network(D) C1 and C2 both assume they are on different networks. |
| Answer» | |
| 33. |
A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative. The minimum size of the TLB tag is:(A) 11 bits(B) 13 bits(C) 15 bits(D) 20 bits |
| Answer» | |
| 34. |
Which one of the first order predicate calculus statements given below correctly express the followingEnglish statement?Tigers and lions attack if they are hungry or threatened. (A) A(B) B(C) C(D) D |
| Answer» | |
| 35. |
A logical binary relation □ ,is defined as follows:Let ~ be the unary negation (NOT) operator, with higher precedence than □.Which one of the following is equivalent to A∧B ?(A) (~A □ B) (B) ~(A □ ~B) (C) ~(~A □ ~B) (D) ~(~A □ B) (A) A(B) B(C) C(D) D |
| Answer» | |
| 36. |
If s is a string over (0 + 1)* then let n0(s) denote the number of 0’s in s and n1(s) the number of 1’s in s. Which one of the following languages is not regular?7″ />(A) A(B) B(C) C(D) D |
| Answer» | |
| 37. |
For S &in; (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s &in; (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}.Which one of the following statements is true?(A) L is recursively enumerable, but not recursive(B) L is recursive, but not context-free(C) L is context-free, but not regular(D) L is regular |
| Answer» | |
| 38. |
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?(A) Both DHAM3 and SHAM3 are NP-hard(B) SHAM3 is NP-hard, but DHAM3 is not(C) DHAM3 is NP-hard, but SHAM3 is not(D) Neither DHAM3 nor SHAM3 is NP-hard |
| Answer» | |
| 39. |
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.void barrier (void) {1: P(S);2: process_arrived++;3. V(S);4: while (process_arrived !=3);5: P(S);6: process_left++;7: if (process_left==3) {8: process_arrived = 0;9: process_left = 0;10: }11: V(S);}The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.Which one of the following rectifies the problem in the implementation?(A) Lines 6 to 10 are simply replaced by process_arrived–(B) At the beginning of the barrier the first process to enter the barrier waitsuntil process_arrived becomes zero before proceeding to execute P(S).(C) Context switch is disabled at the beginning of the barrier and re-enabled at the end.(D) The variable process_left is made private instead of shared |
| Answer» | |
| 40. |
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.void barrier (void) {1: P(S);2: process_arrived++;3. V(S);4: while (process_arrived !=3);5: P(S);6: process_left++;7: if (process_left==3) {8: process_arrived = 0;9: process_left = 0;10: }11: V(S);}The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.The above implementation of barrier is incorrect. Which one of the following is true?(A) The barrier implementation is wrong due to the use of binary semaphore S(B) The barrier implementation may lead to a deadlock if two barrier ininvocations are used in immediate succession.(C) Lines 6 to 10 need not be inside a critical section(D) The barrier implementation is correct if there are only two processes instead of three. |
| Answer» | |
| 41. |
An implementation of a queue Q, using two stacks S1 and S2, is given below:void insert(Q, x) {push (S1, x);}void delete(Q){if(stack-empty(S2)) thenif(stack-empty(S1)) then {print(“Q is empty”);return;}else while (!(stack-empty(S1))){x=pop(S1);push(S2,x);}x=pop(S2);}Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?(A) n+m <= x < 2n and 2m <= y <= n+m(B) n+m <= x < 2n and 2m<= y <= 2n(C) 2m <= x < 2n and 2m <= y <= n+m(D) 2m <= x <2n and 2m <= y <= 2n |
| Answer» | |
| 42. |
Consider the following propositional statements:P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))Which one of the following is true?(A) P1 is a tautology, but not P2(B) P2 is a tautology, but not P1(C) P1 and P2 are both tautologies(D) Both P1 and P2 are not tautologies |
| Answer» | |