Interview Experience 28

#SoftwareEngineer

##Round 1- Pen Paper Coding Round- (most optimized approach was required)

1. Given a mXn matrix and position of a no , now u have to print the matrix in spiral order starting from that no

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

no=9 output= 9 4 5 10 15 14 13 8 3 12 7 2 11 6 1

2. A no is given as a 1d array , u have to find the smallest no by removing exactly k digits from the array,u cannot change the order of digits after removing k characters from string.

eg no= 123443122 k=3 o/p= 123122

3. A matrix is given , u have to convert the whole matrix into a 2d linked list (each linked list node will have 2 pointers right pointer which will point to adjacent right node and a down pointer, to point to adjacent down node. Time- O(nxm) space-O(1)

##Round 2. Technical interview F2F (Proper working code was to be writted for each question)

1. string = aaaabbbbccd o/p= a4b4c2d This conversion has to be done in place without explicitly making a new string . Corner cases has to be handled properly. (I was using c++ string STL functions insert and erase to count frequency of each character than inserting and erasing but he told me not to use any inbuilt functions. So i simply solved using standard approach of maintaining 2 indexes.)

2. Suppose u have n computers in your computer lab i.e maximum n students can use computers at a given time . he gave me a string like abcddcaefggefb

and no of computers = 3 find how many will not be able to get a computer.

string explanation= a comes, b comes, c comes - all three will get computer, now d comes but no computer is available so he leaves immediately , now c leaves, a leaves, e comes (gets computer), f comes (gets computer), now all computers are again occupied (by b,e,f), g comes and leaves immediately, then e leaves, f leaves and finally b leaves.

answer=2 (d,g).

I maintained a STL's unordered_set of currently occupied computers, when a character is not in the hash that means it has come ,if there is space to allocate a computer i insert the character in my hash otherwise i increment the answer count and if the character is already present in my hash then i removed the character from hash, as this character is leaving.

time complexity O(n)

space complexity O(n)

3. A integer array is given , u have to return the index where the left sum = right sum .

First I told him the naive approach Time complexity=O(n^2), that for every index we will calculate the left and right sum.

Then i told him O(n) time complexity and O(n) Space complexity approach- by maintaining 2 sum array , 1st array will store sum from 1st element to that particular element and second array will store sum from last element to that particular element. and then simply iterating over the array and just checking the left sum and right sum array value for that index. Then i told him the constant space solution - by first calculating the total sum of array (I assume it wont overflow :P), then simply iterate over the array and maintain left sum in a variable and by using total sum we can calculate right sum and compare them.

Then he argued that i was traversing the array 2 times ,do it in 1 traversal , then i told him i don't think it can be done in one traversal in constant space, cause i have to travel once to get the total sum, which will be needed to calculate the right sum in the second traversal. then he said yes obviously, it cant be done in 1 traversal. -_-

3. given a binary tree check if it is a perfect binary tree or not in O(1) space complexity (You cant use recursion , any auxiliary data structure like stack , queue) .

##Round 3 Technical Interview 2:

1. Lowest common ancestor of a n-ary tree.

-Wrote the full working code then explained them by doing a dry run on a sample tree.

2. A integer matrix is given which is row wise and column wise sorted ,You have to print the matrix in sorted order in constant space.

I was struggling as i was not able to figure out a constant space solution, then i told him space will be needed as i need to keep track of various indexes to compare so he asked me how much maximum space i need as i am not going to give O(n^2) space. I figured out a O(n) space solution , by maintaining a array ar[] such that ith index of the array indicates that for ith column of matrix numbers has been printed till ar[i], then choosing the minimum no from this array and incrementing its value by 1,(to point to next row of that column). he was satisfied with the approach. he did't ask me to write the code for this problem, for this problem he wanted to see how the person comes up with the solution as he gave a constant space constraint and it was not possible to solve this in constant space.

##Round 4 HR round

Interviewer who took my 2nd technical interview took this interview. Basic hr questions, discussion on things written in CV.