Fist Round(Online):
20 MCQ questions and 2 Coding Questions .
Coding Questions :
1. Merge overlapping intervals(Very well known repeating problem).
2. Given a singly linked list you have to subtract the value of first node from the last node and so on until you reach the middle node.
Eg: Input: 5 -> 4 -> 3 -> 2 -> 1
Output: 4 -> 2 -> 3 -> 2 -> 1
F2F-1:
1) Given a sorted circular link list and a pointer to random node, now insert a new node. I did it , but i used if and else for some special cases in my code so he asked me to do it without if else for special cases (generic & simple code ).
2) Given a pointer to node in tree and a root pointer. Print all the nodes which are at a distance k from the given node.
F2F-2:
1) He gave me task scheduling problem:
Given a set of modules, some modules depend on previous modules and can only be executed, if the requirements of that module is complete.
2) Given a string of letters from alphabet. Remove all pairs(2 consecutive same character) of characters which occur consecutively.And do it recursively on remaining string.
3) Given a binary tree set the sibling pointers . I told him that i already know the question so he said code it .
4) He asked me about hashing .
4.1 He asked me about complexity . I told him about O(logn) and O(1) .
4.2 Then he asked me about how do you get O(1). I told him my approach . He said how will you rehash it when required . I told him that i will use extra memory and copy the hash map . Then i Optimized and did it in-place using a Boolean field.
4.3 Then he took this question to OS and asked me to do it using threads .
4.4 Asked me what all problems you will need to take care about this problem while using threads and give solution to it.
5) Discussion on my projects
F2F-3:
He gave me 3 coding questions :
1) Given a number n find the number of valid permutations of a string formed using characters ‘(‘ and ‘)’ . A string is valid if it has matching opening and closing parenthesis .
2) Given a singly link list reverse every 3 nodes and if nodes are less than 3 then reverse them also.
3) Given a string of letters from alphabet insert frequency of each character in the string.
Time Complexity Required O(n) Space Complexity Required O(1)