Directi Questions
Interview Questions :
My interview questions(Anantharam)
1st round (coding) :
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.
This problem is similar to the spoj problem :
http://www.spoj.pl/problems/COUNTISL/
2nd round (Phone interview) :
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.
That was all and i was out...
My interview questions (Lokesh)
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 .
I got struck in this question and could not make up a solution for
this and game over .
My interview questions(Prabhu)
1st round(algo)
1.Given a no. ‘n’, find posible no. of smart strings and input
alphabet is a to z(26 chars).Smart string means a string after
applying following changes, resulting string is same as the original
string.
smart string: given a string of size n, reverse it and again reverse
it excluding the end chars at position 1 and n. Now again reverse it
excluding next to end chars at 2 and n-1. continue this till u reach
middle of string.
eg. consider string “abcdcea”, aftet 1st reverse: “a ecdcb a”, after
2nd reverse: “ab cdc ea”, after 3rd reverse : “abc d cea”. now we
reached middle of string and resulting string is same as original
string. so it is smart.
after analysing the pattern i got the solution for this.
2. given a stack , i want to access the max element in O(1).
it is easy one. use 2 stacks.
3. given an array of numbers containing positive and negative
numbers, return the no. of contiguous subsequences which sum to 0.
4. Modification of LIS: given an array of integers, return the length
of longest alternating subsequence. i.e. a<b>c<d>e.
2nd round(technical):
first question “tell me about yourself”. then went into technical.
I felt it tough one.starting from network,going through OS, DBMS,C+
+,finished with networks,
1. what is HTTP and why it is used?
2. what is cookies and why it is used?
3. why dont we store cookies details in server instead of storing in
client system?
4. what about process, threads?
5. significance of thread over process?
6. i can run concurrent process. then why should i use threads?
7. semaphores?
8. is parallelism possible in merge sort using threads?
9. int x=5;
fun()
{x++;}
if 3 threads run this function and am reading x at last, what will be
value of x?
10. what is index & why we are using it in Database?
11. write query to find 3rd highest mark of students in student table
with name and marks?
Then he asked my favourite language and replied “OOPS-C++”
12. what is purpose of virtual keyword?
13. what is inheritance and why using it?
14. what is polymorphism and why using it?
15. what is overloading and why using it?
16. can we implement overloading using different return types of
function and Why?
17. what is overriding and why using it?
again to networks
18. explain sliding window protocol?
then he asked me to explain my projects.
that’s it and am out.......
2nd round – coding round for developers – unix based ques –
(Sivaviknesh)
...For developers position they said u gotta be an expert in linux ….
…u can use any programming language ..but I found shell found to be d
best…we were allowed to use man pages…
1.Prog shud take process name as input , display the memory occupied
by all the process under that.
2. Process should be daemon .
3. We must write it to into log file that will display the following
for every 5 seconds…Elapsed time, Vmmsize, VmmRss..
..they gave hints…
I tried to use commands like..
..pidof <process name>
Ps v <value returned by pidoff>
… I tried to figure out commands using man pages , but unable to
implement it……
My interview questions(Prashanth)
Algo round:
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 shud optimize more.. he sed
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 shudnot 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 pertrol pumps between two points A and B/.. u
ve to select 10(say) petrol pumps such that the largest distance
between any two petrol pumps shud 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 tym 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 sorttt....
Quick SORT:
if we want to find the Kth smallest v can use quick sort without
sorting the entire array but its enuf.. till the pivot elemnt 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...
the interviewer was happy wit it..
Tech round
This round involved all concepts ryt from OS, DBMS, Networks, Data
structure, Algorithms, ur 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 sed no that’s a
different concept.. I then sed…Java hash map…..that was the ryt
answer… time for getting.. most of the time O(1) and depending on the
inputs and the things it myt 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 abt testing…
I explained back and white box testing… alpha n beta testin.. and he
sed..he was not proficient in it..n stopped…
Algorithms: (besides the algo round)
Difference in greedy n dynamic… which is better….
Kinda company oriented questions:
advantages and disadvantages of that site…
wat I know Abt Advertising online…
all this went for around 1.5 hrs…. ☺ …
On Sep 11, 3:52 pm, Deoki Nandan <deok...@gmail.com> wrote:
> --
> **With Regards
> Deoki Nandan Vishwakarma
>
> *
> *
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
