Related InterviewSolutions

• Which of the following statements are TRUE?1. The problem of determining whether there exists a cycle in an undirected graph is in P.2. The problem of determining whether there exists a cycle in an undirected graph is in NP.3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A. (A) 1, 2 and 3(B) 1 and 2 only(C) 2 and 3 only(D) 1 and 3 only
• What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?(A) A(B) B(C) C(D) D
• In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the lines in set (s+1). The main memory blocks are numbered 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines from.(A) (j mod v) * k to (j mod v) * k + (k-1)(B) (j mod v) to (j mod v) + (k-1)(C) (j mod k) to (j mod k) + (v-1)(D) (j mod k) * v to (j mod k) * v + (v-1)
• Consider the following sequence of micro-operations. MBR ← PC MAR ← X PC ← Y Memory ← MBRWhich one of the following is a possible operation performed by this sequence?(A) Instruction fetch(B) Operand fetch(C) Conditional branch(D) Initiation of interrupt service
• Suppose p is the number of cars per minute passing through a certain road junction between 5 PM and 6 PM, and p has a Poisson distribution with mean 3. What is the probability of observing fewer than 3 cars during any given minute in this interval?(A) 8 / (2e3)(B) 9 / (2e3)(C) 17 / (2e3)(D) 26 / (2e3)
• Out of all the 2-digit integers between 1 and 100, a 2-digit number has to be selected at random. What is the probability that the selected number is not divisible by 7?(A) 13/90(B) 12/90(C) 78/90(D) 77/90
• Complete the sentence:Universalism is to particularism as diffuseness is to _________________(A) specificity(B) neutrality(C) generality(D) adaptation
• The smallest integer that can be represented by an 8-bit number in 2’s complement form is(A) -256(B) -128(C) -127(D) 0
• A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?(A) -2(B) -1(C) 1(D) 2
• Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?(A) X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)(B) X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)(C) X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)(D) X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)