Wednesday, June 17, 2009

Adobe Interview of Sandeep Jain

Hi all,

Here it goes... :)

Written

I am not putting down the written questions as they were same to almost everyone else. But I would sincerely request that you practice all the written questions that are already available to you.


Interviews

I went through four rounds of technical interview. In all these they mostly asked about my internship at Trilogy, my current work in Decho. (So if you are going off campus make sure you are clear about your past experience)
Secondly since my interview was in Bangalore (arranged separately), The Bangalore interviewers were not aware of me being an on-campus, and they treated me more as an off-campus/experienced candidate. Probably thats why they asked a lot about my current and past work-ex.


Round 1

- Tell me something about yourself (and all those regular questions)
- Write the basic structure of linklist node?
- Now using this structure waf for reversing a link list? (I wrote iterative one)
- Show me the stack trace on this function for atleast three nodes.
- Write a similar recursive code, he again asked me to show the stack trace?
- How will you find whether a link list has loop in it? (and the stack trace of my code)
- How will you find kth node from the end? (again with stack trace of my code)
- How will you write a zip command? (basically file compression)
I gave him two ans: One replace char with char and frequency (but then I pointed out the -ves of this approach myself). Second was using Huffman code
- What are function pointers, how to use them, why to use them?

75% interview was bout, Trilogy's project, so Java, JavaScript, etc etc. BUT strictly project specific, which will never be asked to you people.

Note: I had to write these questions on white board, and he wanted me to teach him.


Round 2

- Started with puzzle, that 4 people, 17 minute river crossing question. Which we all did in the starting of our preparation. I said I already know this.
- Virtual functions, why we need them?
- Why or Why cant Constructors & Destructors be virtual?
- What happens when we make a Destructor virtual?
- Can we call virtual functions in constructor?
I said yes we can, BUT the there is no point of using the word virtual here, because polymorphism doesn't come into picture during construction.
- He gave a list of integers, asked me to make a heap out of it, then usage of heap, complexity of heap, complexity of binary search, why is it the fastest.
- Now came the big question. Write a Generalize Link List program. I didn't know what it was. So he explained: Its a list that can store any kind of data, int, char, float or double.
I gave him 3 solutions using unions, void*, and a mix of both.
- Then he asked about Templates, I said, I only know basics, not much.
- STL... I said (an assertive one) NO, never used, jst heard of it. :P
- Then he moved to pointers :D :D \:D/
- Function pointers, asked me to write 2-4 complex declarations using function pointers.
- Give a practical e.g. where you have used function pointers, where in windows do you think we use function pointers. (Thanks to windows programming & VC++)
- What happens when we throw an exception?
- How will you check if a link list is corrupted?
- Data Break points their usage (this had to do with checking of corruption)


Round 3

This guy looked scary, serious, intelligent and I was damn nervous just after looking at him (wat lag gayi thi).

- Began in the usual manner, about yourself, about the projects in Trilogy & Decho. Since both were on web apps, so he asked about EJB, how do Apache or JBoss servers work. Thn lots of things about Trilogy's project. (I answered to the best of my knowledge, thou I don't think that was sufficient)
- One puzzle, rope of uneven thickness burns in 1 hr, measure half hr. (bacho wala tha ye :P)
- Another Puzzle, two robots are designed to move either right or left, if they collide with anything they will stop, otherwise they will keep moving. Write a module such that, if I put the two robots on an infinte line, nd run Your module on both of them, in an infite loop, they shud have a high probability of collision.
- Waf that takes root of a tree and a sum. & returns if the tree has a path(root to leaf) such that sum of the nodes on this path is same as the input sum.
- Templates again, I gave the same ans.. that I know very little... (but is baar main nai bacha) he said tell me how much do u know, rather whatever you know.
- STL again, I said no.
- Benefits of using templates and STL, followed by a discussion on Java vs C/C++
- This guy also moved to function pointers, I gave my prev e.g only. but he asked for code, nd advantage of my code.
- I am developing a project that I want to work across different platforms, what would you suggest I should do? I said strictly use language standards, and no compiler dependent features.
Then he said but I need to use certain libraries of different platforms. Like we have certain ones on linux. I said you can use conditional compilation using #if & #elif etc... cuz we have certain inbuilt symbols like ___win somethin something___ whenver we need to use such code. We can keep them in such blocks (while giving this answer one more variation clicked so) I said OR you can put all dependent code in individual modules. and make an independent module that uses these. (wrapper kind of thing) in this wrapper you can use the ususal #if #elif


Round 4

This was from noida, video conference with some engg. head in Noida

- WAF which takes an integer input i (i can be 1 or 2) and returns 2 or 1 (alternates) respectively.
- Then a lot about project in Trilogy, and Decho
- Difference between GET nd POST, which is better?
- He almost exhausted me bout Decho projects. Everything and anything that I had learned in past 1 month was covered. XML, XPath whatever I knew.
- Last question, I want a sort function that can sort anything, ints, doubles, structures, even arrays, anything you can imagine. Write the prototype. Then he asked me to explain the parameters I had taken, and why I had taken them.


HR Round

This was more of a formality.
General questions on family background, brothers n sisters, what I do for leisure, why I wanted to go to Noida and all those stuff.

I hope I was of some help...
All the Best... :)

Saturday, May 9, 2009

Adobe Interview of Preeti Singh

Written:

1) declaration of sprintf.
2) is dere difference in typedef(encoded pointer correctly) and #define(just replacement).
3) write generic function for swap(), which works for every data type e.g int,float,char.........
4) find out depth of tree.
5) how many times a swap function would be called if given array is ascending and we have to sort in descending order.
for(i=0;i<n;i++)
for(j=0;j<n-1;j++)
if(a[j]<a[j+1])

6) rectangle intersecting or not, given left upper and right lower vertax;
7) WAP to print all path from node to leaf
8) getbits(x,p,n)
9) one question from OS about producer/consumer, how to update queue in critical section.
10) int arr[] = {1,2,3,4};
int *ptr;
ptr = arr;

for(i=0;i<4;i++)
{
printf("%d ",*ptr);
ptr +=sizeof(int); i
}

11) how void free(void *) work?

Aur yad ni aa rahe :(


Interview Round 1

1) Asked me about my current project and development work i m doing.
2) How to keep record of number of packets comin from some computer passing through router if
IP Address is dynamically changing(Related to my 5 month project on SNMP protocol).
3) Code to reverse a string word by word.
4)Puzzle 1: five containers having same number of balls. out of 5 one container having all defective balls.
We are given one weighing machine on which we can check weight only once. We hav to find which container have
defective ball, using weighing machine only once.

5) Puzzle 2: you are given a rectangular sheet of paper. Cutting one rectangle from that paper from anywhere.
Draw one line such that it divides the remaining area of rectangle in two equal parts.
6)
char c = 5;
void foo(int *b)
{
b = &c;
}

int main()
{
int i;
foo(&i);
printf(i);
printf(&i);
}

what ll be output??


Interview Round 2

1) About Project currently i m working on.
2) Write a code to traverse a binary tree label by label.
3) Find nth node from end in a link list.
4) given two time stamp(starting and end), find out all possibility when the two time stamp overlap.
5) Puzzle: 100 door puzzle.
6) Given 2 container of 3ltr and 5ltr and unlimited quantity of water. Measure 4ltr of water.


Interview Round 3:

1) About Project.
2) Some question related to telecom domain on which my project based on.
3) Write a code of ternary search means dividing given sorted array in to 3 parts every time and search the element.
Find out the complexity. Hw is it bettr than binary?
4) Given k sorted array of n element each. Sort them into a single sorted array.

jitna yad tha utna likh diya :)....some basic questions of c/c++ was dere. like storage class and some questions of structure

Wednesday, April 29, 2009

Decho Interview of Sandeep Jain

Hi,

This is my Interview Experience at Decho, Hope its helpful... :)


Round 1: One hour Aptitude test

It contained the usual apti questions like
- pipe
- ratio proportion
- seating/arrangements
- % related
- speed distance

It seems easy with the captions but there were few really tricky ones.

These two were different:

There is only one correct soultion to the following, what is it?
A) Ans is A
B) Ans is A or B
C) Ans is C or D
D) None of this

How many questions have you solved correctly?
A) All of them
B) None of them
C) All of them except this one
D) Only this one




Round 2: 30 Minutes Technical written

5 questions we had to do any 3

1) Reverse a Link List
void reverse(node **head)

2) Count the number of leaves in a binary tree.
This question was not that clear it seemed as if they wanted to know minimum & maximum number of leaves in a Binary tree with N nodes.

3) Write a function to Reverse the words in a sentence.
void reverse_words(char *sentence, int sentence_length);

For e.g.
Input: This is a book
Output: book a is This


4) Given a Binary tree, write a modify function that replaces a nodes value with the sum of the values of its children.
void modify(node *root);

5) There is a string, and a pair, count the occurrences of this pair in this pair.
E.g.: String = "abceabcdefqw", Pair = "ab"
int count_pairs(const string &str, const string &pair);




Round 3: First tech interview

Q) Tell me something about yourself
Q) About the project in Trilogy, He only wanted a basic introduction of the project
Q) I have to maintain an integer which can be in two states, i = a or i = b.
i.e. i can have only these two values. Write a code that toggles this value of i from a to b or vice versa. Without using if, switch, for, while, do-while, ternary.
I gave a XOR solution, but then he said do not use any XOR either.

Q) Write a function to find the first non-repeating character in a given char array.

Q) There are three ants sitting at the vertices of an equilateral triangle. They can only move along the edges of the triangle. If all of them have equal speed and all of them start moving at the same time. What is the probability of collision of any two ants?

Q) I have a group of people standing in a matrix form (i.e. rows & columns) I select a person A who is the tallest of the shortest of every column,
person B who is the shortest of the tallest of every row.
Out of A & B who has the chances of being taller than the other.

Q) What are const functions?
Q) How do you make a member variable modifiable even if the object itself is const?
Q) What are the ways in which you pass arguments to a function? (call-by-value, call-by-reference) Give examples and explain the working.
Q) I gave an e.g of using int type arguments. So now he asked What if are dealing with objects?
Q) When are copy constructors called? write a sample copy constructor.
Q) What is a singleton class? Write a sample.
Q) Why do we use virtual destructors?
Q) Suppose you created a class, can you prevent your users from using destructors?
Q) What happens when you use a static variable in a function? What if we have multiple threads facing race condition for that static variable?
Q) Where is the data that is used by a process stored? (he wanted details of storage in terms of local variables, global, static, dynamically allocated ones)
Q) Write a fully functional Queue class.




Round 4: Second tech interview

Q) Started with the Trilogy-project. Asked for a detailed description. What the project is, how it works, what have I done till now?
What kind of bugs I fixed? What was the biggest challenge during internship? etc etc... I spoke everything I could recall at that time.
Q) Write a function that will convert a binary tree into its mirror image.
Q) There is an underground electric wire from city A to city B, The wire has broken at some point. The only way to check the wire at any point is to dig that place and then check whether it is broken or not. Give an efficient way to do it, so that our time & cost is minimal.
I gave a solution(think a little, its easy) then he said, what if do not know the distance, we only know that wire starts from city A, and that it is broken at some point.
Q) Prisoners on a staircase with either red/blue hats. The one who tells the correct colour lives or he dies. Its a famous puzzle.
Q) Pirates puzzle, 5 Pirates, have 100 bucks. They follow a hierarchy all 5 being at different levels. The superior one decides how to distribute the money. Then there is a poll among the five, if there are more than 50% votes against the distribution the top most pirate is killed. Then the distribution has to be made by the 2nd pirate in the hierarchy and so on. Assuming that all pirates are really smart, greedy, and want to live as well. How would the leader distribute it.
Q) In a village there are 100 people & everone has a strange disease, all those who have this disease have a halo over their head. If anyone comes to know that he has the disease(by looking at his halo or if someone else tells him) he dies the next morning. i.e. Awareness of disease leads to death. :P
A magician, in an attempt to save them, cast a spell over the entire village. Because of which "NO one shall see his own halo, and no one shall tell anyone else about their Halo" NOW the questio is, For many days will they live?



Round 5: Third tech interview

Q) Write a recursive function to compute the number of binary 1's & 0's both.
Q) Write a function that removes extraneous spaces from a string. For e.g.
Input: "I______am_____a______Boy"
Output: "I am a Boy"
Input: "______I_____am_____a____________Boy____"
Output: "I am a Boy"

I gave them the code, but they insisted my code to have a fatal bug. & I kept disagreeing, finally they said, its correct telling me that they forgot to see the last line of code (which handled null)

Q) Why do we need multi-threading on a single processor? (He wanted the concept of DMA & I/O devices)
Q) There are 6 boxes numbered 1,2,3,4,5,6. Box 1 contains infinite balls of 1 kg. Box 2 contains balls of 2 kg and so...
However one of the boxes contains defective balls. All balls have the same defect and thus there weight is different than the expected weight. For e.g. in Box 3 we have all balls weighing 8 kg instead of 3 kg.
Given an electronic scale so that measure accurate weights of each, In how many least weighings can you find out the defective box, how many balls will you will take out from the boxes?



Round 6: The F-2-F with the General manager of Decho

Initially she did not ask any questions she just explained how the company works, what the project is, how the current project works etc etc. Then she asked me what I did or didn't understand. If I would like to ask any questions to her. This all seemed pretty good. Cause she made it appear as if I was selected. She also explained how Decho is a part of EMC^2 (It was acquired by EMC^2)
Then she told me that the HR will meet me next.



Round 7: HR round

- Tell me something about yourself starting from your school, Please skip the technical details.
- What about your family, fathers business, siblings etc etc.
- How did you get into this IT field, you already have a family business?
- Who are the people you met today? (I told her that in sequence :P)
- From the time you came to our office till now, what new have you learned?
- What was the best experience in Trilogy?
- What was the worst experience in Trilogy?
- Why not Aricent? Why not Nagarro?
- Why Bangalore & not NCR?
- She asked some resume related stuff, as well.
- What your strength? Weaknesses?
- (I answered being short tempered as a weakness) then why do you think you get angry?
- Why do you think people get angry?
- Next she wanted me to ask her questions, as much as I wanted to?

I asked her the following:
-- What do you think I should or must improve on?
-- What are the office timings? I hope its not a school.
-- I asked her about EMC^2 & how does EMC^2 effect Decho. What about recession's effect on EMC and thus on Decho?
-- How does the appraisals work? (Cause she said its the task of manager to check on the performance)
-- If the compnay provides cab facility or accomodation?

There were sone questions related to compensation as well, which I am not listing here... :P :P

And thats it...
Through with it... :)

All The Best to all of you.

Friday, April 17, 2009

Amazon Interview of Varun Maini


Telephonic Interview :

1) Explain ur current company project.He wanted to know in depth, at each step he said , can we go into more details of implementation.
2) You are given a very huge string ,u have to beautify it.
beautify means that wherever there are multiple spaces / tabs repace it with single space.Whenever there is a full stop make the next char in Upper case,
no characters except the start of new line should be in upper case except when they are enclosed in single/double quotes,
U have to do this all in a single traversal and const space.
3) Implement a stack so that push,pop and max would take O(1) time.(gave 4-5 approaches)
4) Given a date as 2001/10/02 its a palendrom , find the palendrom date that occured just before this.


Round 1: (focused just on coding)

1) given an array find three numbers whose product is maximum.

(NOTE : looks easy but dont be fooled , there could be -ve nos too !!!!
gave 3-4 approaches , finally gave code for the approach taking O(n) time and const space)

2) Given a binary tree , convert it into a doubly linked list where the elements in DLL will be in same order as inorder traversal of the tree.

3) Given a sorted array , rotate it from a given Kth index in best possible manner

4) given a sorted array that is rotated find the index from which rotation happened ( O(logn) soln )


Round 2 : (focused on coding and DS )

1) given an i/p string AAABBCCCAA , o/p = A3B2C3A2 etc .. requirements : single traversal of string and const memory

2) give me a data structure such that if there could be values between 1-1000 then u could do the following operation in o(1) time :

insert(x) , delete(x), giveAnyElement()

where 'giveAnyElement()' will return any element present in the Data Structure.

U can assume that memory is no issue .. just concentrate on O(1) time .

(My soln : take a array[3][1000] array wherein
for each of the 'i' index :
array [0][i] = a int having value 0 or 1 , where 0 means element not present , 1 = element is present
array [1][i] = index of next value in the list
array [2][i] = index of previous value in the list

Basically u need to implement a doubly linked list on in an array and u are done :)

3) given a linkedList where each node has two pointer fields next and Random
where next points to the next node of linklist , while random could point to any node in LL
so create a copy of the linkList.


Round 3 : (focused on Algo,DS and coding)

1) given a NxM matrix , where each array entry is a character, write a code that will find all the words that can be formed using elements in a row, oolumn and diagonal

2) given a binary tree , each node apart from left and right has a tail pointer attached to it , where each tail should point to a node which would
come to the right of the current node , if a inorder traversal of tree is done.
So u have to devise a O(n) algo to find out which all nodes have their tail pointers set incorrectly.

3) given a huge string of size n (where n = about one billion ), there are m strings each k characters long u have to find out all the occurences of these m strings
in a single traversal of the big string.

(soln started from naive string matching, then kmp,then sorting the m strings and using buckets,then using binary trees, tries, hashing etc .. )


Round 4 : (focused on my ability to Design )

1) u have a function where there is an infinite loop thats running and in that loop , getRandomNumber() is called, at any point of time i should be able to track
the maximum, minimum, second max , sum , mean ,median etc of the nos.

Also i should have the flexibility that i can add more features , ex i can also add feature to find mode of the nos found so far

more importantly :a) i should have the flexibility to 'Remove' any feature as and when i want
b) i should be able to change the implementation of any of max, minimum methods without needing any change in my class


(My soln : after a good long discussion , i used Observer Design Pattern)

2) what is the diff between interface and abstract classes
give real world examples for them.

3) What do u know about JDBC , what is the purpose of the driver, when u do a preparedStatement.execute() then what all happens

4) Discuss the Collections API , what all interfaces and concrete classes does it provide , if u had to create ur own Varun-collections API then what all interface
and abstract classes would u provide

5) U have to design a database schema denoting the entire recruitment process , wherein storing info about candidates , interviewers , the interview results etc ..

Round 5 : (foucussed on Algo and how efficiently can i convert my algo to code)

1) given a NxM matrix where each row has elements in sorted order , and each column has element in sorted order , u have to find a given no in O(n) time and no extra space
ex :
1 4 10
3 6 11
4 7 15
find if 7 is present or not .

2) Given n sorted arrays merge them into a single sorted array

3) If i give u an N then ur code should give me the no of distinct binary trees possible with N nodes
ex i/p = 3 o/p = 5

4) once again went back to first question , now its given that all the arrays are increasing continously
ie
1 4 10
12 16 20
24 30 35 now find if a given x is present of not



Round 6 : (Focussed on HR,Data Strcuture , Algo)

1) whats the best thing about trilogy
2) if u have to change something in trilogy what would that be
3) biggest challenge u faced there
4) biggest accomplishment
5) Why amazon , there are 100 of companies out there ???

6) if u have to design the algo for searching that would be used for google , then what algo are u going to use.

7) extension of 6th : u have a huge file and u enter some key words , now u need to find the closest set of characters that enclose the entire set of keywords.

ex : let String Be "ABAACAAABXYABX....BXAC.." where these A,B,C... are words (not a single characters)
suppose user enters the keywords A,B,C then ur answer should be "BXAC"


Round 7 : (DS, Algo , OS, Puzzles)

1) what all have u read in OS. Can u describe features of any OS.

(I told lot of things that i had read in Galvin , then i started to describe UNIX , giving details about inode, the kind of scheduling algo it uses, singal
mechanism it uses ,system call mechanism , the dual mode operations , the access control of files, talked about (datablock,superblock,inodeblock,bootblock)
talked about its shell and how can its functionality be easily extended etc ... )

2) in amazon we have millions of customers daily , if we wanted to give some gift to the customer who buy 3 or more items during the last 7 days , what DS and Algo
are u going to use to store and retrive this info

3) There is a file that has N lines
where 'i' th line says : "There are exactly i lines in the file which are false"

ie .. There are exactly 1 line in the file which is false
There are exactly 2 lines in the file which are false
..
..
There are exactly n lines in the file which are false

now u have to find out which of these n lines are true.

4) given a village with demons and a sleeping man, The man is always sleeping ,never wakes up. Now a demon can eat the sleeping man , but after that
he will fall asleep , any demon can eat another sleeping demon.
If demons are very smart and would always choose to stay alive than to eat the man and risk their lives.
so if initially there are 65 demons and 1 sleeping man ,, what would happen in the village ???

Adobe Interview of Varum Maini

Written Exam :

C/C++ :-

Ques 1.
Write setnum(x,p,y,n)
Dennis Ritchie question : set the n bits starting from position p in x with rightmost n bits of y.

Ques 2.
Write a program to find the depth of Binary Tree

Ques 3.
In Binary Search code, reduce the number of comparisons in while loop from two to one. Write the code.

Ques 4.
Difference between char arr[] = "string" and char *arr = "string".

Ques 5.
Implement int **my2DAllocate(int rows, int columns); to allocate memory for 2D array and return the int ** pointer.

Ques 6.
What are bit fields. Give example, when they are used.

Ques 7.
What are data break points. When do we use them.

Ques 8.
Write code to evaluate ReversePolish.
Input : 123+*
Output : 6

Ques 9.
Hex no. is given in string for (0x or 0X optional). Write code to get the integer value.



Engineering Paper :

Ques1:
For a String s
Head(s)= first char of s
Tail(s) = all the chars of s except head

I.e. is s=”abcd” , head(s)=”a” , tail(s)=”bcd”

So given concat(Head(s),Head(tail(tail(s))) = “ac” , which of the following could be s

abcd , aabc,acac , aaac


Ques 2.
Binary Search tree is given. Print all the possible routes from root to leaf.

Ques 3.
Give a Data Structure to denote a polynomial when :
a) polynomial is dense
b) polynomial is sparse

Ques 4.
U have a file that is much bigger than RAM , give an algo to sort the file.

Ques 5.

Int power(int base,int n)
{
if(n==0)
return 1;
else
{
int x = power(base,n/2);
if(n%2==0)
{
return x*x;
}
else{
return x*x*base;
}
}
}

if I call power(5,12) then how many multiplications will take place ?


Ques 6.
P1 : read the file
P2 : modify the file

Show how will u synchronize the process so that modify can happen only when no one is reading the file. Using constructs

Enter Critical Section :
Exit Critical Section :
Wait Event :
Signal Event

Ques 7.
Given code that did bubble sort and sorted an array in decreasing order. An array is given in sorted order, u have to find out that if the above algo is run on it .. then how many times would two array values be swapped.


Ques 8.
Given two binary tree, how will u find that they are isomorphic (that is at each level they are equal or are mirror image of each other)

Ques 9.
A rectangle is represented by two points P1(x1,y1) and P2(x2,y2) representing lower left and upper right corner.

So given two rectangles , find if they intersect.



Interview 1 :

1) A date is represented as yyyy/mm/dd ex : 2001/10/02 .
Now observe that the above date is a palendrom, so find out the palendrom date which came just before the above date.
(Hint : September dosn’t have 31 days !!!! )

2) given two stings s1 and s2 , s1 has some characters at the end which are same as some of s2’s starting characters ..
so u have to concatenate the strings so that the repeated portion occurs only once.

Ex : S1 = “ ABCDEFGHIJK”;
S2 = “GHIJKXYZ”;

O/p = “ABCDEFGHIJKXYZ”

3) given a big string , u enable a person to underline some characters , for example some body had underlined characters 3-6 and 10-14 and so on ..
suggest a Data structure which can record this info effeciently and can accomodate new underlines .
NOTE : a new underline could lead to updation of records for ex consider a underline that starts from 5-8 .. then above set would become 3-8 and 10-14
NOTE : a new underline could lead to MERGING of records for ex consider a underline 4-13 .. this would lead to 3-14 in above set.

4) arr[2][3][2]={1,2,3,4,5,6,7,8,9,10,11,12};
what is value of arr,*arr,**arr,***arr, arr+1 ,*arr+1 ,**arr+1,***a+1

5) Given a no N, find all prime nos from 1 to N. using the fastest approach possible.

Now the answer i gave for this question left him speechless ..
He was basically just looking for the soln where i store all the previously encountered primes in an array and just keep dividing my no with them to find if its prime or not
But because of my maths background i gave a answer which uses Fermat's Theorm and proved much faster than above approach and no extra memory reqd.

After that soln he kind of felt overwhelmed and the interview was over :D



Interview 2 :

1) Given M sorted arrays , each having K elements , merge them into a big sorted array of size MK in most efficient manner possible.
(Hint :- Coreman Question : Use a Heap)

2) If u have to desing ur own Operating System , what mechanism are u going to use for ur file system .

(I started with using continous blocks to store file , this lead to external fragmentation ..
so next i told of using linked approach , where in each block i also keep address of next data block
next moved to FAT system...
Finally came up with an indexed approach , where first datablock just stored pointers to rest of data blocks)

3) Implement a stack such that push,pop and max and min are obtained in O(1)

4) given an array[1...N] which have elements from range 1-N they have elements that are repeated any no of times.
So give all the approaches u can come up for to find the nos that are repeated.

(first O(n^2) approach : brute force
then sort and find out
then use and extra array of size n
then use a bit vector of size n
no extra memory , whenever u encounter a no go to that index and make the value -ve ....
and another couple of really fundoo algos were given )

5) How will u create ur own C++ library.

(told that i will create my classes and place all my implementations in it. and provide a header file which having the class , macro and typedef declarations.
He then asked that what approach would u use to avoid mentioning all private and protected functions from the '.h' file
After about 5 - 10 mins of discussion .. i gave the correct answer .. that i will create a class which has all my private and protected funtions .. and in my
original class i will just add a POINTER to that class (Note : Pointer and not object as if i use an object then i have to give my second class's declaration too
and so will land up at square 1 )

6) Create a singleton class in C++


Interview 3 :

1) given a link list , find if its a palendrom or not.
(I gave one soln , then he asked me to code a recursive one )

2) There is a rectangular table , u and ur friends have identical coins , so u place a coin on table,then ur friend places one (no overlap allowed) , in the end
there would be no space left on the table and the person who is not able to place his coin on the table looses.
So device an algo such that if u place the first coin , u will always win .

(Basically place the coin at the center (point of intersection of diagonals), then wherever the friends places a coin, place a coin at its mirror image across the diagonal,
so for all his coins u are able to place a coin, hence cancelling his every move, but u have a coin extra at the center and hence in the end u will win)

3) In a party there is X, X's wife Y along with A,B,C,D,E and F (where b is a's wife , d is c's wife and f is e's wife). So ppl meet and handshakes take place , its given
a husband dosnt shake hands with his wife. In the End X asks every1 else the no of handshakes that they had .. and all give different Answers !!!!!!
IF its given that X shook hands with A. Then u have to find if Y shook hand with A / B / either of them / none of them

4) Applications of Heap, implement heapsort

5) function to generate permutations of a string ( he told me to assume that all characters in string are different)

6) being in line with prev question , he told me to come up with a Data structure that given a string , find all anagrams of string.


Interview 4:

1) given a no x , convert it to binary and store it into a char array and return.

(Looks simple, but is not .. basically u need to take care how much memory u need to allocate the array , then if u are returning , should u create a array
or use malloc , then how should the calling function accept it as char * p = fun() or char p[] = fun()

He then changed some lines of code and said now what will happen and so on ..)

2) given two very big files , each having around 1 billion lines , u have to print all the lines that are common to both files

(gave nearly 10 different approaches :
brute force , create a binary tree of one file and then keep searching elements of other file in it,sort one file and do binary search , sort both and compare top two and proceed ,
sort and place the strings in buckets , buckets then gave way to B trees , then hashing , break file into small mangagable chunks and then proceed etc etc ..)

3) what is virtual memory and how would u use it in the previous question

4) given a N X M matrix , find out the total nos of rectangles that can be there.


5)
int p = 0x6000;
int *q = &p;

fun(int *r)
{
*r = *q;
}
int main()
{
int a = 0x5000;
fun(&a);
printf(a);
}

here he asked the o/p. then he made the following change

he replaced the int * r with char ** r , then asked me what would be the o/p. This really confused me, but i figured out the ans in about 2 mins .
then he replaced the char ** r with char *r, this looks simpler than pervious case , but believe me .. this is the toughest ,

here when we do *r = *q this would then lead to storage of 0x6000 % 255 to be stored in *r
also there is now the case of Endianess, if machine is little Endian then r has changed the Least Significant Byte of a else the Most Significant Byte.


HR round :

1) ur marks in 10,12,grad and mca
2) ur ranks in all the above
3) what all companies did u sit in during campus placements , out of them in how many did u get selected
4) what was ur rank in DU's MCA enterance
5) what would ur boss say about u
6) What is the best thing about Trilogy and whats the worst
7) Package , how much expected
8) Whats ur worst habbit
9) How is ur rapport with ur team in trilogy
10) Give me 5 reasons that seperates u from others so that i should select u
11) How do u rate ur performance in trilogy on a scale of 1-10