Thanks a lot buddy On 12 September 2011 00:19, siva viknesh <sivavikne...@gmail.com> wrote:
> 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. > > -- **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.
