Round 1 (Online test : MCQ+Coding)
-Online on Hackerrank
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.
n = 3
1 2 3
4 5 6
7 8 9
k = 4, output: 6
k = 6, output: 8
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.
Input: “1123″. You need to general all valid alphabet codes from this string.
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?
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
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.
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?