**Round 1 (Online test : MCQ+Coding)**

-Online on Hackerrank

__Coding Questions:__

Q1. Print all possible words from phone digits?

Q2. Given a matrix where elements are inserted as 1 to n in row 0, n+1 to 2n in row 1 and so on till n^2 and you traverse the matrix in spiral manner, find the kth number you will visit.

Example:

n = 3

matrix:

1 2 3

4 5 6

7 8 9

k = 4, output: 6

k = 6, output: 8

**Round 2:**

Q1. If a=1, b=2, c=3,….z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

For example:

Input: “1123″. You need to general all valid alphabet codes from this string.

Output List

aabc //a = 1, a = 1, b = 2, c = 3

kbc // since k is 11, b = 2, c= 3

alc // a = 1, l = 12, c = 3

aaw // a= 1, a =1, w= 23

kw // k = 11, w = 23

Q2. What is a binary tree? What are different types of traversals in a BT? What is the difference between these traversals? Which of the traversal is based on BFS and which is based on DFS?

**Round 3:**

Q1. Given a N*M matrix, print all squares/rectangles of all possible sizes(all 1*1, then all 1*2…. 2*1… )

Q2. Given a linked list like 10->8->3->4->5->6

modify it to

4->3->-1->4->5->6

The last number is subtracted from first number, 2nd last from 2nd number and so on till middle of link list.

First gave him a brute force approach O(N^2) , then O(N) approach in which reverse of 2nd half of list is done. He told to do this without reversing the list.

Then used a stack and gave him final solution.

**Round 4:**

What is a max heap? What is a min heap? What are some real life applications of heaps?

- How to insert in a heap? What is the time complexity?

- How to delete a min element from a min heap? What is the time complexity?