Explore topic-wise InterviewSolutions in .

Correct choice is (c) O (log N)

For EXPLANATION: In order to perform the deletion on the rope DATA structure, ONE can delete the given string at any position x to form a new string in O (log n) time. So, the time complexity for worst case is O (log n). This can be done by TWO split operations and one concatenation operation.

Right choice is (a) True

Best EXPLANATION: In order to PERFORM the insertion on the ROPE data structure, the time complexity is O (log n). In order to perform the deletion on the rope data structure, the time complexity for worst CASE is O (log n). While for ARRAYS the time complexity is O (n).

The correct OPTION is (b) Balanced

The best I can explain: To perform the BASIC operations on a ROPE DATA structure like insertion, deletion, concatenation and SPLITTING, the rope should be a balanced tree. After performing the operations one should again re-balance the tree.

Correct choice is (c) O (log n)

To explain: In order to perform the splitting on the rope data structure, one can SPLIT the given STRING into two new string S1 and S2 in O (log n) TIME. So, the time complexity for worst case is O (log n).

Correct option is (d) O (1)

EXPLANATION: In order to perform the concatenation on the rope DATA structure, one can create two nodes S1 and S2 and then performing the operation in constant time that is the time complexity is O (1).

Correct option is (d) Binary Tree

Easy explanation - Rope is a special binary tree in which the end NODES contain the string and its length. The array is a linear data structure. Linked LIST is a linear data structure having a node CONTAINING data INPUT and the ADDRESS of the next node. The queue is a data structure working on the principle of FIFO.

Correct answer is (a) Cord

Easy explanation - Array is a LINEAR data STRUCTURE. Strings are a collection and sequence of codes, alphabets or characters. LINKED List is a linear data structure having a NODE containing data input and the ADDRESS of the next node. The cord is also known as the rope data structure.

Correct option is (B) Splay Tree

Best explanation: Splay tree is a self – adjusting BINARY search tree. It performs basic operations on the tree LIKE insertion, deletion, LOOP up performing all these operations in O (log n) time.

The correct OPTION is (d) k+1 O (LOG (log n))

The explanation is: The UPDATE COST also is bounded by the upper bound. We perform one cut as well as one join operation for the AUXILIARY tree, so the total update cost for the auxiliary tree is found to be k+1 O (log (log n)).

The correct option is (d) k+1 O (log (log n))

The BEST I can explain: Since each search operation in the AUXILIARY tree takes O (log (log n)) time as auxiliary tree SIZE is bounded by the height of the REFERENCE tree that is log n. So for k+1 auxiliary trees, TOTAL search time is k+1 O (log (log n)).

The CORRECT choice is (d) k+1 O (log (log n))

Best EXPLANATION: UPPER BOUND is found to analyze the work done by a tango TREE on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).

Correct answer is (b) Cut

To explain: A preferred path is broken into TWO parts. One of them is known as TOP part while other is known as bottom part. To BREAK a preferred path into two SETS, cut operation is USED at a particular node.

Correct option is (a) True

The best I can explain: PARTITIONING METHOD is used by tango tree which PARTITIONS a binary search tree into small sets of paths and then STORING them to auxiliary TREES. Hence tango tree is represented as a tree of trees.

The correct option is (a) JOIN

For EXPLANATION: If the TOP NODE of one of the reference tree amongst the two, is the is the child of the bottom node of the other reference tree, then the join OPERATION can be carried out to join the two auxiliary trees.

Correct option is (a) Red – Black Tree

For explanation: The path starting from the root and FOLLOWING the path of PREFERRED child node till the END of LEAF node is known as preferred path. Nodes are stored in Red – Black tree for the representation of the preferred path.

Correct choice is (a) COMPLETE Binary Search Tree

For EXPLANATION: Tango tree is constructed by simulating a complete binary search tree. This tree is also known as Reference tree, that CONTAINS all the elements of the tree. Also, the reference tree is never showed in ACTUAL implementation.

The correct choice is (d) O (log (log n))

The explanation is: TANGO tree is an online binary SEARCH tree whose time COMPLEXITY is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data PROVIDED piece by piece.

The correct CHOICE is (b) Buenos Aires

For explanation: Tango is a popular COUPLE dance or partner dance that was ORIGINATED in the 1880S somewhere between Argentina and Uruguay. Buenos Aires is a capital city off Argentina. Hence they named after Buenos Aires.

Right answer is (c) Binary Search Tree

Easiest explanation - TANGO tree is an EXAMPLE of binary search tree which was developed by four famous SCIENTISTS Erik Demaine, Mihai Patrascu, JOHN Lacono and Harmon in the year 2004.

Right answer is (d) All of the mentioned

The best explanation: Erik Demaine is a well-known PROFESSOR of COMPUTER Science at MIT. John Lacono is an American computer scientist specialized in data structure and ALGORITHM while Mihai Patrascu was a Romanian- American computer scientist. All of them TOGETHER developed the concept of Tango tree.

Right answer is (a) it has DANGLING pointers

Easy explanation - The NODES extreme LEFT and right are pointing to nothing which could be ALSO used EFFICIENTLY.

Correct choice is (a) when both LEFT, RIGHT NODES are having null POINTERS and only right NODE is null pointer respectively

Explanation: They are properties of double and single threaded binary trees respectively.

Correct choice is (a) inorder, postorder, preorder traversals

To explain: In threaded binary trees, the null left pointer POINTS to the PREDECESSOR and the right null pointer point to the successor. In threaded binary trees, we can USE in-order, preorder and postorder traversals to visit EVERY node in the tree.

The correct answer is (a) leftchild_pointer, left_tag, data, right_tag, rightchild_pointer

Easiest explanation - It contains ADDITIONAL 2 pointers over normal binary TREE node structure.

Right CHOICE is (a) there are many pointers which are null and thus useless

The best I can explain: As there are MAJORITY of pointers with null value going WASTED we use threaded BINARY TREES.

Correct answer is (a) Cecilia and Raimund

The BEST I can explain: Cecilia and Raimund invented Treaps. Arne ANDERSSON invented AA – Trees. Donald Shell invented shell sort and HARRIS and Ross formulated maximum flow PROBLEM.

The correct answer is (d) INFINITY

Easiest explanation - The PRIORITY of a null node is set to be infinity in a treap so that during deletion, priority of that PARTICULAR node is set to infinity, rotated and FREED.

Right ANSWER is (a) True

The best explanation: Other than insertion, deletion and search OPERATIONS, several operations like union, intersection and SET difference can be DONE in treaps.

Right choice is (B) a NODE’s priority should be at least as LARGE as its parent

Best EXPLANATION: A node’s priority should SATISFY heap order. That is, any node’s priority should be at least as large as its parent.

Right option is (d) Each NODE has a FIXED PRIORITY field

The explanation is: A treap is the SIMPLEST of all because we don’t have to worry about adjusting the priority of a node.

The correct OPTION is (b) TREAP

Easiest explanation - A treap is the SIMPLEST of all binary SEARCH trees. Each node is given a numeric priority and implementation is non RECURSIVE.

The correct answer is (a) O(N)

The EXPLANATION is: The AVERAGE CASE and worst case space COMPLEXITY of a treap is MATHEMATICALLY found to be O(N).

The CORRECT option is (a) height of a SPLAY tree can be LINEAR when accessing elements in non decreasing order.

The best I can explain: This will be the case after accessing all n elements in non-decreasing order. SINCE the height of a tree corresponds to the worst-case access time, this means that the actual cost of an operation can be HIGH. However the amortized access cost of this worst case is logarithmic O(log n).

Right option is (a) true

Easiest EXPLANATION - There is a ZIG-zag and right operation(zig) which gives the right hand side TREE. REFER splay operations for INSERTION in splay tree.

Right option is (b) In REAL TIME it is estimated that 80% access is only to 20% data, hence most USED ones must be easily available

Easy EXPLANATION - May be the stats showing 80-20% may be not ACCURATE, but in real time that is the widely spread scenario seen. If you are into this type of situation, you must choose implementing splay trees.

Right answer is (a) cache Implementation

The EXPLANATION is: SPLAY trees can be used for FASTER ACCESS to recently accessed items and hence used for cache IMPLEMENTATIONS.

Right CHOICE is (b) MOVING a node to root

For EXPLANATION: Splay trees mainly work using splay OPERATIONS. wheneve we insert, delete and search for a node we splay the respective nodes to root. we have zig-zag and zig-zig operations.

The correct choice is (a) true

Best EXPLANATION: We GO with amortized time complexity when we feel that not all OPERATIONS are worst and some can be efficiently done. in splay TREES not all splay operations will lead to O(logn) worst case complexity.

Right choice is (c) easier to program and faster access to recently accessed items

Best explanation: Whenever you INSERT an ELEMENT or remove or READ an element that will be pushed or STORED at the top which facilitates easier access or recently used stuff.

The correct choice is (b) any sequence of j operations STARTING from an empty tree with h nodes atmost, takes O(jlogh) time complexity

For EXPLANATION: This is a PROPERTY of splay tree that ensures faster access. we PUSH the most RECENTLY used nodes to top which leads to faster access to recently used values.