gistFiles

FAQs---------------------------------------------------------------------------

Q1 Can we use a stack instead of Queue?
ANS No, because in that case order of elements gets changed as expected.

Q2 Why are we taking a 'size' variable, instead of using 'queue.size()' method?
ANS Because in inner while loop, further elements will also get added in the queue due to which the value of this method gets changed continuously but we want to process only those elements that were present initially, in one go.

Q3 What are we storing in arraylist of arraylist?
ANS In this data structure each inner arraylist is representing a diagonal of tree.

Q4 Can we use another approach to solve this problem?
ANS Yes, we can solve this problem using recursive approach too.

Q5 What does a an empty queue signifies?
ANS It signifies that all elements of tree has been processed.

HINTS-------------------------------------------------------------------------

1. All the nodes that are lying on the line of slope -1 lies in the same diagonal. 

2. Now, create an arrayList of arraylist 'ans' to store the different diagonals in each arraylist.

3. At a node, it's right child will lie in the same diagonal as of node while left child will act as a initial node of some component in next diagonal.

4. Then we perform the diagonal order traversal with the help of an extra queue i.e. while we are at 1 diagonal, prepare next diagonal correspondingly.

5. Now, each time while accessing the node we add its left child in the queue i.e. next diagonal, and keep moving to the right child until reaches a NULL value and add it in the 'smallAns' arraylist i.e. current diagonal.

MCQ------------------------------------------------------------------------------

Q1 What is the time complexity of used approach?
A) O(N)
B) O(N^2)
C) O(N LOG N)
D) O(LOG N)

ANS = A

Q2               2
               /   \
             /       \
           7           15 
        /    \       /    \
      3        6  14        9
        \                    \
          4                   13 
List all the nodes belonging to same DIAGONAL level.
A) {3},{7,4},{2,6,14},{15},{9},{13}
B) {2},{7,15},{3,6,14,9},{4,13}
C) {2,15,9,13},{7,6,14},{3,4}
D) None of the above

ANS = C

Q3 Queue implements:
A FIFO(First In First Out)
B LIFO(Last In First Out)
C both (a) and (b)
D none of the above

ANS = A

Q4               2
               /   \
             /       \
           7           15 
        /    \       /    \
      3        6  14        9
        \                    \
          4                   13 
What will be the number of diagonals present in above tree?
A) 2
B) 3
C) 4
D) None of the above

ANS = B

Q5 "While we are at one diagonal then, in order to prepare next diagonal we add ______ nodes of all the nodes in queue." Complete the statement.
A) right
B) same
C) left
D) Wrong statement

ANS = C

___________________________________________________________________________________________________QUES 2

FAQs---------------------------------------------------------------------------

Q1 Can we use a stack instead of Queue?
ANS No, because in that case order of elements gets changed as expected. 

Q2 Why are we taking a 'size' variable, instead of using 'queue.size()' method?
ANS Because in inner while loop, further elements will also get added in the queue due to which the value of this method gets changed continuously but we want to process only those elements that were present initially, in one go.

Q3 What are we storing in arraylist of arraylist?
ANS In this data structure each inner arraylist is representing a diagonal(anti-clockwise) of tree.

Q4 Can we use another approach to solve this problem?
ANS Yes, we can solve this problem using recursive approach too.

Q5 What does a an empty queue signifies?
ANS It signifies that all elements of tree has been processed.

HINTS-------------------------------------------------------------------------

1. All the nodes that are lying on the line of slope +1 lies in the same diagonal. 

2. Now, create an arrayList of arraylist 'ans' to store the different diagonals in each arraylist.

3. At a node, it's left child will lie in the same diagonal as of node while right child will act as a initial node of some component in next diagonal.

4. Then we perform the anti-clockwise diagonal order traversal with the help of an extra queue i.e. while we are at 1 diagonal, prepare next diagonal correspondingly.

5. Now, each time while accessing the node we add its right child in the queue i.e. next diagonal, and keep moving to the left child until reaches a NULL value and add it in the 'smallAns' arraylist i.e. current diagonal.

MCQ------------------------------------------------------------------------------

Q1 What is the time complexity of used approach?
A) O(N)
B) O(N^2)
C) O(N LOG N)
D) O(LOG N)

ANS = A

Q2               2
               /   \
             /       \
           7           15 
        /    \       /    \
      3        6  14        9
        \                    \
          4                   13 
List all the nodes belonging to same DIAGONAL(anti-clockwise) level.
A) {3},{7,4},{2,6,14},{15},{9},{13}
B) {2,15,9,13},{7,6,14},{3,4}
C) {2,7,3},{15,14,6,4},{9},{13}
D) None of the above

ANS = C

Q3               2
               /   \
             /       \
           7           15 
        /    \       /    \
      3        6  14        9
        \                    \
          4                   13 
What will be the number of components present in above tree's diagonal 2?
A) 1
B) 4
C) 2
D) 3

ANS = D

Q4               2
               /   \
             /       \
           7           15 
        /    \       /    \
      3        6  14        9
        \                    \
          4                   13 
What will be the number of diagonals present in above tree?
A) 2
B) 3
C) 4
D) None of the above

ANS = C

Q5 "While we are at one diagonal then, in order to prepare next diagonal we add ______ nodes of all the nodes in queue." Complete the statement.
A) right
B) same
C) left
D) Wrong statement

ANS = A

_______________________________________________________________________________QUES 3

FAQs--------------------------------------------
Q1 How we got the formula for a node label's complement?
ANS Since, for a node (n'-start)=(end-n) => n'=end+start-n. And, on the basis of observation [start = (2^level no) = llv(last level value)] and [end = 2*llv-1]. Therefore, n'=(2*llv-1)+(llv)-n = 3*llv-1-n where, n is label given.

Q2 What is the llv variable representing?
ANS It represents the last level's value on which our node with given label lies and level value is given as 2^(level number).

Q3 What is the significance of 'llv /= 2;'?
ANS In upper while loop, llv gets updated 1 time extra. So, to get last level value we update llv by llv/2 using this statement.

Q4 What is the significance of 'int par = comp / 2;'?
ANS It is basically calculating the parent node's label for the calculated complementary node.

Q5 Are we creating a tree?
ANS No, actually no tree has been created. We are just working with node labels and formulas.

HINTS-------------------------------------------
1. No tree formation is required.
2. Based on the label of the current node, find what the label must be for the parent of that node.
3. Use the fact that in normal binary tree, parent is calulated as node_label/2.
4. In zig zag binary tree, directions has been swapped. So, for a node calculate node's complement on the same level and find parent for that.
5. To find node's complement drive a formula using the fact that n and n' will be equidistant from the start and end of that level respectively.

MCQs--------------------------------------------
Q1 If we are at a node'n', then what will be the label of it's parent node in a normal complete binary tree?
A) (2^n)
B) (n/2)
C) (n+1)/2
D) (n-1)/2

ANS = B

Q2 What will be the time complexity of this approach with n=label?
A) O(LOG N)
B) O(N)
C) O(N LOG N)
D) O(N^2)

ANS = A

Q3 What will be the space complexity of this approach with n=label?
A) O(LOG N)
B) O(N)
C) O(N LOG N)
D) O(N^2)

ANS = A

Q4 Is binary tree symmetric?
A) NO
B) YES
C) MAY BE

ANS = B

Q5 Time complexity of Collections.reverse() method?
A) LOGARITHMIC
B) QUADRATIC
C) LINEAR
D) EXPONENTIAL

ANS = C

Ques : Word Search li_____________________________________________________________________________________

FAQs---------------------------------------------
Q1 Explain the approach used.
ANS To find all the strings in crossword, we iterate over all characters in crossword and for each character check whether any string to be found has initial as this character. Instead of picking a particular string and checking its existence in whole crossword. This will result in reduced time complexity.

Q2 What is the significance of node.str?
ANS It marks the ending of a complete string.

Q3 What is the significance of node.count?
ANS It represents how many strings are using that node.

Q4 Name the algorithm technique used.
ANS Backtracking

Q5 What is the use of checking 'if (child.str != null)' condition?
ANS If we got a node whose str data member value is not null, it represents the end of a string means a complete string has been reached. So, add it in ans arraylist.

MCQ---------------------------------------------
Q1) Trie is also known as _________
a) Digital Tree
b) Treap
c) Binomial Tree
d) 2-3 Tree
ANS = A

Q2) Which of the following is the efficient data structure for searching words in dictionaries?
a) BST
b) Linked List
c) Balancded BST
d) Trie
ANS = D

Q3) Following code snippet is the function to insert a string in a trie. Find the missing line.
    for (int i = 0; i < s.length(); i++) {
      char ch = s.charAt(i);
      if (curr.childs[ch - 'a'] == null) {
        curr.childs[ch - 'a'] = new Node();
        curr.count++;
      }
      ______________________________________
    }
    curr.str = s;
a) curr = curr.childs[(ch - 'a')++];
b) curr = curr.childs[ch];
c) curr = curr.childs[ch - 'a'];
d) Nothing is missing
ANS = C

Q4) Which of the following is not true?
a) Trie requires less storage space than hashing
b) Trie allows listing of all the words with same prefix
c) Tries are collision free
d) Trie is also known as prefix tree
ANS = A

Q5) What can be the maximum depth of the trie with n strings and m as the maximum sting the length?
a) log2n
b) log2m
c) n
d) m
ANS = D

HINTS------------------------------------------
1) Try to use Trie data structure for efficient searching.
2) Make a trie for all the strings need to be searched in crossword puzzle.
3) Now, iterate over all the characters in crossword and check for any word with character as its initial.
4) Proceed for matching characters in order to match further string.
5) Use backtracking to check rest of the characters of word with the help of an visited array.