Directi Application Developer Interview Questions and Answers

Round: Test
Experience: There is a drought situation in Agrabah.King got worried and called Aladdin for helping him out. 
As he is a modern Aladdin he took printouts of places around Agrabah from google maps.For 
analyzing the map properly, he converted the map into a M x N grid. Each point is represented 
by either ‘0’ or ‘1’.
‘1’ represents the unit area of water and ‘0’ represents the unit area of land. King told him to find 
the largest continuous patch of water so that he can send his people over there.
As our Aladdin is modern, but not a good programmer, he wants your help. Help him out by 
printing out the largest area water patch available on map.


Round: Phone interview
Experience: 1)There are three types of balls arranged linearly in a random order Red, Green and Blue. Now 
your job is to sort them so that the Red balls are in front follwed by the Green balls and the Blue 
balls are pushed to the bask.
This problem was the same as sorting the array of 0, 1 and 2. we  can do this in o(n) 
using two pointers.
2)Given an n x n matrix, where every row and column is sorted in increasing order. Given a 
number x, how to decide whether this x is in the matrix. The designed algorithm should have 
linear time complexity.
a) Start with top right element
b) Loop: compare this element e with x
 i) if they are equal then return its position
 ii) e < x then move it to down (if out of bound of matrix then break return false)
 iii) e > x then move it to left (if out of bound of matrix then break return false)
c) repeat the i), ii) and iii) till you find element or returned false
3)In the same matrix mentioned above find the kth maximum element.
I said that we just need to compare the last K x K sub matrix and to find the Kth element.
4)Given a set of integers, Display the non­empty subsets whose sum is zero. For example, 
given the set { −7, −3, −2, 5, 8}, the answer is the subset { −3, −2, 5} which  sums to zero.
This is the special case of knapsack problem and hence it is NP­Complete so i said we 
cannot find the solution in polynomial time.We consider all the subsets with k elements. Then 
check how many of these sets have a sum of 0. This is an exponential time algorithm.
5)Create a data structure where inserting, deleting and finding the minimum element all have 
O(1) time.
i said we can use augmented stack where with each element we can augment the 
minimum element along with its actual value.Then he said “what if you cannot create any new 
data structure but have to use only the previously available data structures?” I replied that then 
we can use two stacks one to store the actual data and other to store the minimum values.

Skills:
College Name: Anna University Chennai

Round: Test
Experience: 1.    Queue in O(1)  solution.. I came up with a method and it was not the most optimal one… 
and I asked if I should optimize more.. he said he was happy with the solution I gave and 
proceeded to the next question…
2.       For eg.. if there is a string abda. I shud reverse it n/2 times.. ie… say
1st rev: adba
2nd rev: (during the second reversal I shouldnot rev from beg.. but rev the string between ( i+1,j­
1) where i=0,j=n­1in the first case….)ie
a db a => a bd a….
so it is abda finally….after n/2 reversal we get the initial string which is abda.. this is a 
favourable case and I increment the count by 1…
The question is give the string length say n=4 how do u find out the total number of strings 
which will have the favourable condition after n/2 reversals…. I came up with a solution… just 
think over it.. not a difficult one… just 5mins of thinking will get u reach the right answer….
3.    There are 100 petrol pumps between two points A and B/.. u have to select 10(say) petrol 
pumps such that the largest distance between any two petrol pumps should be minimum…I gave 
a top down approach.. guess he expected a bottom up approach….  But at the end he was quite 
happy with my answer…
4. tel me a scenario where i cud use MERGE SORT AND QUICK SORT AND WHERE I CAN 
USE ONE NOT THE OTHER.. and the differences...
MERGE SORT:
when there is 1GB of things to be solved we can divide that 1 GB into A*B=1GB , such that 
each division will have a size of A(MBs)... in this case I cannot bring the entire 1GB into 
memory.. So i ll bring A(MB) into memory at a time sort it and keep it and sort all the B 
divisions and do a B­WAY Merge... which will be easier... But this kinda thing cant be done in 
quick sort...
Quick SORT:
if we want to find the Kth smallest v can use quick sort without sorting the entire array but its 
enuogh.. till the pivot element is placed at the kth position... (random select...)...... this cant be 
applied for merge sort..where v have to sort the entire thick to identify.. kth smallest...


Round: Technical Interview
Experience: This round involved all concepts right from OS, DBMS, Networks, Data structure, Algorithms, your 
projects,  a slight touch on testing…
Topics covered in each subject:
OS: Threads, process… difference.. if threads have more advantages y go for process??
Semaphores, Synchronization, concurrency problems, Second chance algorithm in virtual 
memory chapter….
DBMS: Second highest salary… TRY TO USE TOP… I TOLD HIM TWO SOLUTIONS ONE 
WITH TOP AND OTHER WITHOUT TOP … But he emphasized me to use TOP first.. So use 
that…
He gave me a set of tables and asked me write queries
Indexing was also an important concept he asked me.. B+ trees properties and how used in DB.
Normalization of my tables in my project….
Data structures:
Difference between binary trees,  hash map, Tries.
A scenario where BST has advantages than hash map without any collision.
How do we avoid collision in hash
Example of a good hash being used…(I told STL..he said no that’s a different concept.. I then 
said…Java hash map…..that was the right answer… time for getting.. most of the time O(1) and 
depending on the inputs and the things it might vary accordingly )
Tries advantages and wen can it be used….and application of it..
Networks:
Layers of OSi.. explanation of each layer 
Google.com steps involved
About DNS
Testing:
What do u know about testing…
I explained back and white box testing… alpha n beta testing.. and he said..he was  not proficient 
in it..n stopped…
Algorithms: (besides the algorithm round)
Difference in greedy n dynamic… which is better….
Kinda company oriented questions:
advantages and disadvantages of that site…
what I know About Advertising online…
all this went for around 1.5 hrs

Skills:
College Name: Anna University Chennai

Round: Test
Experience: 1. My first question was to design a data structure to store a dictionary . I gave a solution to use 
a trie with 26 pointers for each character . Now he asked me to reduce the no of pointers . 
He gave me an example of our phone , where we use only 10 digits to make a combination of 
all the words instead of 26 different buttons of every character .
Then for this type of a system he asked me to design a data structure . Well I gave a solution 
with which he was satisfied . 
Note : for this hashing is not an efficient solution .
2. The next one was to design a data structure ( he explicitly expressed it as a queue ) where 
inserting , deleting and finding minimum is done in O(1) time . here you can use additional 
memory but they were very much concerned about the time i.e O(1)  . I answered them using 
additional queue .
3. Then he asked me a algorithm problem  . The statement goes like this
You are given two end points ( consider them as two end stations at some distance  ) 
there are 100 stations between these two . Now you need to build a train track between these 
two end points which includes only 10 stations and not more than that . Now the objective is to 
find such 10 stations such that the maximum distance between any two consecutive stations is 
minimum 

College Name: Anna University Chennai