Interview Experience 138

2018

Software Engineer

Round 1 - Technical

Three questions were asked in this round, all related to data structures and algorithms. I was asked to give an efficient logic for each ques and write the pseudo for it. The questions were:

1. Given a sorted array find the magic point, point where a[i]=i. Tips: Proceed with Binary search approach, considering all boundary cases and duplicate value case.
2. Given 3 strings A, B and C, check if the C is an interleaving of A and B or not. Tips: Understand the DP solution, but be prepared with other brute force solution as well. I gave the DP solution but he asked can it be done without using DP. So I gave a solution using the merging concept of merge sort, considering both the orders AB and BA. Again consider the boundary cases.
3. Given a BST, Update the value of every node to the sum of all nodes greater that node in the BST. Tips: A 2 traversal method can be implemented using In-Order traversal. But if asked to do it in one traversal, use In-Order traversal in reverse order.

Round 2 - Technical

Firstly I was asked questions about my Internships. Then three questions were asked in this round, again all were related to concepts of data structures.

1. You are given some IP ranges and a token associated with each IP range. The ranges have no overlapping but they are not continuous. When a user requests for a token from an IP, You find the range to which this IP belongs, and return the corresponding token in response. I was asked to create a structure for this problem which will carry out the task. Tips: Ask about which IP addresses should be taken into consideration, like I confirmed that I should handle IP address from 10.0.0.0 to 10.0.0.255 (256 IP’s).This will help you in your design. Then think about arrays and link list for storing the ranges. For searching, use binary search and look for boundary conditions. I also proposed a binary search tree solution where each node stores 2 values, the start and end value of a range. The idea of using this was to keep the ranges sorted and avoid extra sorting time.
2. Given 2 matrices, which are row and column sorted, and a value X, find pairs by taking 1 element from each matrix such that the sum of the pair elements equals X. Tips: Use the concept of searching for a pair with a given sum in an array. Another solution would be to subtract X from elements of first matrix and then for each element, find the corresponding X-a[i][j] value in the second matrix using the efficient concept of searching for a number in a row and column sorted matrix. Although the first one will be better in terms of time complexity.
3. Given an unsorted array, find the smallest missing positive number. Tips: Consider moving all negative numbers to one side of the array, and then deal with the positive side of the array. The interviewer required an O(n) solution hence this was required. Other options which I gave were sorting the array and frequency count method.

Round 3 - HR Round

1. Tell me about yourself. (Interests, Hobbies, Extra curricular activities)
2. Tell me your strength.
3. If I asked your teachers and colleagues about you, what feedback will be obtained.
4. Willingness to relocate and working on any new technology.
5. Preferred Working languages and softwares.
6. What do you know about the organization.