Housing Software engineer interview
I was interviewed on-campus at IIT Kharagpur for Software engineer role at Housing
Resume Shortlist Technical Interview Technical Interview Technical Interview Technical Interview
I dont really know what special I did. I just put some start up internship ahead of interns in two well established companies and mentioned my web based projects.
- Question 1: Given a BST and two positions in a bst exchanged to give a violation in bst rule. Find the two elements and exchange them. Corner case to be considered is that root can also be a node which id exchanged.
- Question 2: Design a system for Bookmyshow.com. When we book seats we the seats must be locked till the time payment gateway is reached. Also consider no payment done and payment failures. This is a question on state machines and transaction management acc to me. Still verify not sure
- Question 3: Given a set of n steps. A person can climb one or two steps at a time. Find the number of ways in which one can reach the nth step. (Easy stuff.. I probably wasn't doing good by this time)
- Question 1: Given an array a1, a2...an. Find all pairs such that ai>aj having i<j. (nlogn solution)
- Question 2: Given many pairs intervals with their start and end. Find the maximum interval which intersects the maximum number of intervals. Look for corner cases again!
- Question 3: There was one easy string question.. Dont remember.something on trie data structure
- Question 4: Given a string (say alpha) and a dictionary database from where I can find if a word is present in the dictionary by a O(1) time look up. Find if there exists a path from the root word(aplha) to leaf node having a single letter such that a child is formed by removing one letter at a time such that each word intermediately formed is also in the dictionery. Eg. If there is a path aplha->plha->pha->pa->a. And all the nodes are in dictionery. Dynamic programming solution exists.
- Question 5: Implement an auto suggest in search engine. Like for google when u type max say maximum must be suggested in drop down. This is a problem on Information Retrieval.
- Question 1: Easy one. How to make a linked list with for a number like 12345 must be stored in linked list as 1->2->3->4->5.
- Question 2: I dont remember again a question. Was on strings again :P. But easy
- Question 3: Implement a ctlr+f (find) functionality in a file. Make a data structure for this implementation.
- Question 4: Given two sorted arrays find of size n and m. The n sized array has m spaces empty at the end. Code to merge these to arrays in single pass O(n+m).
- Question 1: Given a binary tree. Code to have each node point to the next node in the same level. Last element in the level must point to NULL.
- Question 2: Make a set of all nodes that can occur in any path from a source to a destination in both directed as well as undirected graph. Note that a node can be visited any number of times not necessarily only once.
- Question 3: Given two sides of a river having the same cities labeled in characters. Bridges are to be drawn from one side to another that can connect the same labels but the bridges shudnt cross each other. Find the max no of bridges that can be connected. Eg Side 1: A B C D Side 2: D C A B So bridges connecting A to A etc need to be made. But when A to A is connected above D to D is not possible. Dynamic programming solution exists.
Be clear with your basics
Make a cv which is appealing, and highlight some key things regarding web development or algorithms or system development
Motivation for applying
Interest in Software Engineering
They started speaking in Hindi after a while. It was very friendly.
Read Full post...