programming Interviews

Citrix interview questions

2008-11-04T23:00:00.000-08:00

1)Explain an algorithm for path planning in a given map.

2)Write a code to find the shortest path in a given graph.

3)Write a code for minimal spanning tree

4)How do you find existence of a cycle in the given graph.

5)Explain OSI model.

6)How do you find out the sizeof an object in Java.

7)Given a byte, write a code to swap every two bits. [Using bit operators] Eg: Input: 10 01 11 01 Output: 01 10 11 10

8)Write a Shell code which takes in as input several files and replaces each occurance of word “Nishant” with word “reddy”.

9)What is VPN ?

10)What are TCP/IP protocol , Routing algorithms , P2P file sharing , Routing protocols.

11)Implement the above protocols in C.

Citrix Written exam

2008-11-04T22:59:00.000-08:00

11. Find the slope of the line joining the points (0,2) and (3, -2)
a. -4/3
b. ¾
c. -3/4
d. 4/3

12. Solve for x in x^3+3x^2+5x+9=6
a. -1
b. 1
c. -2
d. -3

13. 73 to the base x is equivalent to 51 to the base y. which of the following may be the possible values of x and y
a. 10, 12
b. 8, 16
c. 9, 13
d. 8, 12

14. Which of the following is independent of the operating system and machine architecture
a. linker
b. loader
c. compiler
d. debugger

15. Which of the following restricts a process to the memory allocated to it
a. stack pointers
b. memory allocation hardware
c. kernel
d. none of these

16. When a user logs out, what happens to the processes created by him?
a. they’ll be killed
b. aborted
c. hang
d. none of these

17. What is the output of
Main()
{
Struct node {
Int a;
Int b;
Int c;
};
Struct node a = {2,4,5};
Struct node *st;
St = &a;
Printf(“%d”, *(int *)st);
}
a. 2
b. 3
c. 7
d. 11

18. What is the output of
Struct outer{
Struct inner{
Int a = 10;
}
Int b = 5;
}
Main()
{
Struct inner new;
Printf(“%d”, new.a)
}
a. It will give a compilation error
b. 10
c. 5
d. 15earrange?blogID=9179416692752405527

19. Thrashing is solved by
a. increasing cpu bound processes
b. reducing the degree of multi-programming
c. increasing user processes
d. none of these

20. If t` is the reverse of t then what is the reverse of trs
a. s’r’t’
b. srt
c. t’r’s’
d. t’rs’

Citrix Interview questions

2008-11-04T22:28:00.000-08:00

Posted: 04 Nov 2008 07:44 AM CST

1. What is the output of this statement ?
Printf(“%d”,printf(“%d %d”,2,2) & printf(“%d %d ”, 2, 2));
a. 22222
b. 22221
c. It will give an error during compilation

2. What is the output of this code snippet


main()
{        int *p[10];
        printf("%d %d\n",sizeof(*p),sizeof(p));
        }

3. Function inlining is best used when
a. In a small recursive function
b. In large function where number of variables used is small
c. In a large function where there are many loops and number of variables used is small
d. None of these

4. If there is a large quantum in round robin it will be equivalent to
a. First come first serve
b. Shortest job first
c. Least recently used
d. None of these

5 . which of the following will lead to starvation
a. Fifo
b. Shortest job first
c. Round robin
d. Least recently used

6 . if the address space is 192.168.36.16/28 which of the following is the broadcast ip
a. 192.168.36.0
b. 192.168.36.1
c. 192.168.36.255
d. 192.168.36.31

7. if there are 9 yellow balls, 3 red balls and 2 green balls. What is the probability that the second ball picked is yellow given the first ball is yellow
a. 8/13
b. 9/13
c. 8/14
d. 9/14

8. How many processes are created in this snippet?
Main()
{
Fork();
Fork() && fork () || fork ();
Fork ();
}

a. 15
b. 19
c. 21
d. 27
e. 31

9. which of the following is TRUE about the declaration const char * p
a. the pointer cannot be changed but the value to which it points can be changed
b. the value is constant but the pointer can be changed
c. neither the value nor the pointer can be changed
d. none of these

10. If F and L are the pointers to the first and last elements in a linked list, then which of the following operations is dependent on the length of the list?
a. delete the first element in the list
b. insert a new element as a first element
c. delete the last element of the list
d. add a new element at the end of the list

Its Avishkar 08 Time at MNNIT Allahabad

2008-09-06T17:43:00.000-07:00

Avishkar is the annual techno-management symposium of MNNIT Allahabad. Avishkar hosts a galaxy of events aimed at boosting the technological and managerial skills inherent in today's youth. It provides them with an opportunity to showcase their innovative ideas as well as learn and implement new skills in the fields of technology and management.

Apart from events Avishkar also hosts a series of guest lectures and workshops by eminent personalities from the industry and the academia. The latest edition of the festival is scheduled to be held from 17th September – 19th September 2008.

please don't miss it .

Check out the site : www.avishkar.mnnit.ac.in

Don't miss the Online Programming Cont est

NETAPP interview questions MNNIT Allahabad

2008-09-06T17:40:00.000-07:00

NETAPP-AUGUST 2008 MNNIT ALLAHABAD
---------------------------------------------------
1.WRITTEN-1:30 min
--------------------------------------------------
(Courtesy Utsav Kumar Goyal)
it consisted of 4 sections.
1st section was quantitative aptitude. questions on pipe-cistern,work,percentages,profit loss etc.,

2nd section was c. this was the easiest of all as nearly all questions were from test ur c skills...but all good questions only.

3rd section was ADA.. i.e algorithms. questions were mixed easy as well as hard. some basic questions like a tree is given wat is inorder traversal. some complex questions like the complexity. there were even questions on Graphs.

4th section was Systems. questions were tricky. questions on race conditions.segmentation faults.code was given and race condition wat is final output.
int a[100];
for(i=0;i<=100;i++) a[i]=i; wat will happen?? questions on signals....
------------INTERVIEW- -----------

The written was followed by interviews. 1st- it was 20-25 min interview. mostly on c and systems(my aoi) questions
1)THEY ASKED A CODE FROM C SECTION.
char *func(char *p)
{
p=p+3;//change local variable
return p;
}
main()
{
char *y="HELLO";
y=func(y);//although call by value but u end up changing original variable
printf("%d",y);
}
ans:LO now he asked is this call by value or call by reference.this is tricky because u end up changing ptr y. although this is call by value. this is because u r returning value and storing in same variable y.
2)then wat is difference in file pointer and file descriptor.(read K-R unix interface chapter).
3)i give u a 512 mb ram. wat will be there in it??

2nd interview 2 puzzles

1- u have a scooter. and 3 tyres. each tyre has a max life of 1 yr. wat is the max tym u can run ur scooter.
ans: 1.5 yrs 1-6 nnths 1,2 tyre replace 1st with 3rd after 1 yr 2nd finished. so replace it by 1st after 1.5 yrs total tyre=0:
2-u r given a disk. half black half white. its rotating. u have to make sum system using sensors etc. so that a computer can tell the direction in which the disc is rotating.

3-He asked me about the question from the written paper about race conditions and segmentation fault. this discussion went on and on.
what is segmentation fault?? who gets to know that there is segmentation fault. i said kernel. i said it sends a SIGSEGV signal. if u have a[100] array wat will happen when u assign a[102]?? ok now if i have a[100] and b[100] wat will happen now when i acess a[102]??? the correct answrs were ...there are segment registers in hardware..they give an exceptions to kernel which then generate SIGSEV...........read M.J Bach for furthur reference.
so all in all the interview was Fucked..... :(

3rd interview)

Ist question on project. around 10 mins on that. then write a code that will for sure generate segmentation fault.write a code to delete any node in a link list. with all test cases and boundary conditions.(easy stuff)

4th) Hr-- why u want to join netapp,about urself... i was the last person to be interviewed so this was very short interview.

Solid Core Interview Questions at MNNIT (NIT Allahabad)

2008-09-04T18:10:00.000-07:00

SOLIDCORE: R&D AUG-2008 MNNIT(Courtesy -Utsav Kumar Goyal)
WRITTEN- 1hour
------------
18 objective type questions to be solved in 1 hr. Questions were too good, most of them were from Probability ,permutations and combinations.(this pattern may nt repeat. pls dont take it for granted)

-----------------------
1st Interview 1.5 hours
-----------------------
-->>why do u wanna join solidcore??

--->>c questions having compiler related issues.
1.wat is output

i=0;
printf("%d",i++,++i);
or
while(i)
printf("%d",i++);
or
i=i++ + ++i;
or
i=i++*i++; etc. etc.

---> area of interest: mine was ds+os...wat book u study for ds...my answer sartaj sahni and herbert

schildt...
what about tenenbaum??.....mine answer i studied queues and stacks from it.

--->ur aoi is ds..wat was the code u liked the most interesting??
mine ans: i developed a rat and maze prob. that i liked most...on this there was a ques in written

about a square grid 9*9 in wat max ways can u reach from one corner to other.u can only move down or

right.
ans: at each square u can have only 2 moves down(say 0) or right(say 1)..total moves in any path =16
so make make all possible permutations of 8 1's and 8' 0s...
they asked me to write a code for it.

--->write a code for inorder traversal using recursion(easy haan??)...ok now remove the left

recursion only....good now remove the right recursion only....

--->print a matrix helically..code

--->write a standard string reversal function...code
some other ques i don't remember

FEEDBACK:GOOD! :) BUT U CODE SLOW :(

---------------------
2nd Interview 1 hours
---------------------
--->about urself

--->what is deadlock,livelock,spinlock,conditions for deadlock,mechanism for synchronisation,virtual

memory etc etc. i.e all basic stuff.

--->area of interest os-so wat is malloc...is malloc a system call...wat it returns (explained brk

sys call etc. )?? ..how does free() gets to know that how many bytes it has to free(read ritchie

unix interface chapter)..

--->what is segmentation faults??who gets to know that seg fault occurs

--->what are system calls??
--->what is need of system calls??
--->when process swithes mode what happens??

--->what is difference in file pointer and filedescriptor...??discussed a lot on this
--->why do u need to close a file??(i gave funde like a file can have max. desc. fixed etc.)
--->what is page fault??
--->who brings in the page when page fault occurs...

process makes MMU bring the page ...who is in between??
--->write a code to check if a no. is palindrome

--->a puzzle:u have 100 coins on a table 80 tails up and 20 heads up. u are blindfolded. u have to

split these in two heaps not necessary of equal size so that they have equal number of tails.u can't

make out a coin is heads up or tails up by feeling it or smelling it :P :)

Yahoo interview questions at NIT Allahabad

2008-08-31T13:40:00.000-07:00

Yahoo questions:

Written Round :

1) diff betwn char *p char p[]

2) min no of comparision to find min and max in an array on n elements

3)least common ancestor code was given you should identify what it was

4)question on recursion

main()
{
int n=5;
fun(n);
}

fun(int n)
{
if( n = 0 )
return 0;
else
fun(n-1);
}

5)

for(i=0;i<10;i++);
{
printf("%d",i);
}

6)

for(i=0;i<10;i++)
{
for(j=0;j<100;j++)
{
//do somthing
}
}
for(i=0;i<100;i++)
{
for(j=0;j<10;j++)
{
//do something
}
}

which is fast ?

7) shell script to print the total disk usage in a directory

8) can 2 users have same uid and explain the file ownership and process ownership if it is possible

9) command to find the network delay between 2 hosts

10) what is SUID bit

......

Programming round :
unix profile:

1) Given a master node computer and many slave computers you have to monitor the given parameters like disk usage , memory usage , cpu usage and alert the master node if they cross a paticular threshold

2) given a direcotry in host computer and another directory in a remote computer implement rsync between those two

ds profile:

3) create a simple database using file . your database should support basic operatins like insert , remove , query ( most imp ) .

4) implement the grep command in C . your program should handle basic regular expressions like * , . , ^ , $

Interview :

1) write a program to remove blank spaces from a file

2) using sed print last 10 lines from a file

3) what is the techincal differences between windows and linux

4) what is a daemon and what are the steps to be followed for creating a daemon

5) sql queries ..( dont remember )

6) regular expressions

7) about project

8) gave 2 puzzles one was to join 9 points uisng 4 lines and another was simple related to areas

Microsoft interview questions round 5

2008-08-30T19:57:00.001-07:00

Programming round
Problem:
Input: s= “aaabbbaacc”
Output s=”a3b3a2c2”
1) You are given an ambiguous problem, just a single string one statement and what is
the output. Ask as many questions as you can ask to get a clear idea about the problem.
2) Write the complete program for that problem.
3) Generate the test cases and verify them.
Answer:
Possible questions can be asked.
1) Weather the input and output are in the same variable?
2) Suppose you have only one element at a time like (abc) what should be
the output weather (a1b1c1) or (abc). In first case the size of the string is increased, so of
we use the same variable to store the output, it may access memory out of the allotted
memory for the array?
3) What if digits are there in the input string?
Those who didn’t satisfy them where taken one more round and puzzles where asked for
them. (The person who didn’t ask any question for the above problem was given to the
next round).

microsoft interview questions round 4

2008-08-30T19:56:00.000-07:00

Puzzle round
1) There are 25 horses which runs at different speed, and you have to find out the top
three horses, in one race you can race not more than 5 horses, find the no. of races
required minimum.
Answer: 7 races
2) Question about compiler (Phases of compiler, storage of variables of different scope
and difference between stack and heap)
(Const, static and other types)

Microsoft interview questions round 2

2008-08-30T19:55:00.000-07:00

Interview round
3 panels (2 technical panels, asking to write programs and 1 panel asking to solve
puzzles)
1) Write a program which prints the last n lines from a file. You are given only one file
pointer fp.
I was asked to write all possible solutions in different ways. (I gave him 8 to 9 solutions
for that problem).
You can travel a file only once and you can use extra memory space.
Use a circular queue. (Best solution)
2) What is virtual memory?
3) What is address space?
4) Two processes are communicating through a socket on the same machine, in one
program you are storing a string and passing the address of that string to other program
through socket and the other program is printing the value at that address, what is the
value printed
Ans. (Different string)

Microsoft interview questions round 2

2008-08-30T19:54:00.002-07:00

Different problems were given to different persons.
*1) You are given an Array of N size. It contains 0s and 1s only. You have to arrange all
0s before all 1s (In the program you can’t travel more than one. Try to minimize the
complexity).
e.g. Don’t swap the numbers just assign the other one to the element.
2) Verify whether a given tree is a Binary Search Tree or Not. Write the function for it.
*3) You are given two sorted link list A and B, merge them into single list without using
a 3rd link list (i .e. Merge both link lists into A).
*4) Find the angle between 2 different hand of the clock at any given time. Write the
proper code.
5) Now the minute hand of the clock is made 10 faster. Find the angle between them at
any given time. E.g. At 3 o’clock the minute hand will be at 2 and the hour hand will be
at 3.

Microsoft interview questions Round 1

2008-08-30T19:54:00.001-07:00

1) Simple program having a function with a static variable, and the function calculates
the sum of the digits passed to that, and stores it in the static variable (little bit modified
sum), find the output.
Int main()
{
printf(“%d\n”,fun(1234));
printf(“%d\n”,fun(1234));
}
int fun(int num)
{
static int s;
while(num)
{
s = s+ num%10;
num = num/10;
if(s>=10)
s= s%10;
}
return s;
}
2) Consider the following code...
char* fun(char *str)
{
char array[1024];
int i =strlen(str);
strcpy(array,str);
array[i]='\n';
return array;
}
find out the bugs in the code.(Memory Leak).
1) Array is a local variable.(it will be deleted after the function returns, Memory leak)
2) The size of the array is fixed.
3) A matrix is rotated as given in the figure; find the relation between the two matrix’s.
Find A’[i][j]=A[__][__]
4) Write a function that takes a single link list as input and an integer n , the function
deletes all the nth nodes in the link list.
For example if n=3 means delete 3rd, 6th, 9th ... nodes from the list.
5) Write all the test cases for the above program and what errors will u take into account?
6) You are given a document; write the algorithm for the function that counts the no. of
occurrences of words in the document. Suppose you are provided with the function
GetNextWord() which provides you the next word in the document and advances the
pointer by one word.
1) What data structure will you use for the given problem?
2) Write the algorithm for the function?
3) What is the complexity for your program?

Microsoft interview questions round 3

2008-08-30T19:50:00.000-07:00

A hi-funda tech round that I have ever been in. The atmosphere was tense; it was
just 2 minutes before the interview that I came to know that this was going to be
technical. I had expected atleast the last round to be HR
1) Code a string tokenizer
char* strtok(char* str, char* delimiter). Give me all the test cases.
Managed this nicely, felt I was the best coder on earth!
2) Give me a function which will print the all possible permutations (words)
of a sequence of digits pressed while SMSing on a mobile phone.
Remember SMSing: 2=abc, 3=def,...9=wxyz. If the input is “239”, output should
be:
adw
adx
ady
...
...
cfz
You got it right? Please imagine my situation when I was told to code this in ten
minutes. On top of it all, I hadn’t gone through string permutation recursion the
last night. (Last night - 18th night - was spent only on OS, after the shocker of a
semaphore in the first round -18th evening. Not one OS question came in 2nd and
3rd rounds – on 19th morning- though ).
As usual, started coding with int main() {... when he cautioned me to think of an
algo first and then code. Wrote in some code, which would never compile. But I
love explaining my algos. Gave him a gist of my thought process, but he was
barely happy. That guy is a compiler himself as one of my friends had told me.
He could make out any error faster than a compiler!
BTW, the best part was this. As I started writing my code on paper, he started
typing something on his laptop faster than my writing speed. After 8 mins, he
stopped to ask me if I had finished and to have a look at his output for the same
code. I was happy that I had completed 1/4th of my code!

Thank you for the guy sharing this info

microsoft interview questions round 2

2008-08-30T19:49:00.000-07:00

This was the best round of interview I've ever had in my short life so far. It was
partly non-tech which was a welcome change. The guy who took this is a bigshot
at Windows kernel as I learnt only later.
1) He gave me a Math puzzle, walked me through the answer. Though I
hardly had any idea about the answer at the beginning, he kept giving me
so many hints that the answer became obvious to me. Now, the question
was to generalize this and give an algorithm to solve.
I don’t have to the patience to type the whole question, but it was on N bags
containing infinite balls of equal weight (1 kg each), with M (not given) bags
containing only defective balls (900 g each). With just one weighing on an
electronic balance, find out which M bags have defective balls.
Hint: My answer was that picking 1+2+3+...+i+...+n balls from each ith bag would
lead to a linear dependency problem, and the equations can’t be solved.
(Remember Determinant != 0 to solve simultaneous equations?). So the best
series would be a linearly independent 1+2+4+...+2^(i-1)+...2^(n-1).
2) He has installed an expensive, state-of-the-art parking lot system on MG
Road in Bangalore (wish there was one ). It parks one car every 2
seconds and returns it to the user, when he swipes his card. I am hired as
for testing this system (which made it obvious that I might be hired for
testing in MS). Question is whether I am ready to accept the challenge and
get him profits.
He wanted me to use words like capacity, protection & security, user interface
and “stress testing” (remember sitting in my Software Engineering class). I used
all these words, and he was happy!

Microsfot interview questions round 1

2008-08-30T19:48:00.000-07:00

1) Discuss all the test cases for problem 2 in your answer paper. Does your code
work for all these cases? If not modify them on the spot.
(The interviewer kept staring at my pen for really long. Thankfully I didn't
become self-conscious, since I hate people seeing my answer as I am writing )
Initially, with full enthu, I threw some obscure test cases, only later to realize that
my code doesn’t handle any of those.
2) Convert the same code to a recursive one now!
(I was like "Oh My God!" But then, after some ten minutes with the interviewer
carefully scanning every of my letters, had something to show on the paper. He
smiled at the end of it all ☺)
3) Your favorite topic in the class?
I wanted to say none, since I just wanted to get out of the room, but somehow
i managed to say OS and DSA. He started drilling me on Semaphores and
Monitors. Could somehow manage, though I hadn't touched OS book since IBM
Extreme Blue interview last sem ☺. Thankfully, I managed to divert his attention
form coding Dining Philosophers' problem! Shouldn't I be proud of that?
Please remember: Skill to divert the interviewer's attention from the stuff you
don't know to the stuff you know is important. This works wonders as it did to
me. And no one expects you to know everything. So, got through round 1.

MS interview questions

2008-08-30T19:43:00.000-07:00

Selection process: 1 C-Apti + 3 rounds of interview
C-Aptitude TEST (5 q, 1:15 hrs)
1) What's the output?
#include
e(int n)
{
if(n>0)
{
e(--n);
printf("%d", n);
e(--n);
}
}
main()
{
int a=5;
e(a);
printf("%d",a);
}
Ans: 0120301401205

It's damn difficult to follow the stack trace unless you are patient, which I wasn't.
Please remember, all those who made it to the interview round had written
correct answer to this question. Though, I'm not sure if I included the last but one
0. I might have since I made it to the interview round.

2) Write a C code to swap the positions of two consecutive words in a sentence.
Eg: "ramu is good boy"
"is ramu boy good"
Discuss the elegance of your algorithm.
Ans: I wrote a code with O(n) time and O(1) space complexity. This impressed them in the interview, since many had used up a temporary space.
Think a bit and you will get the answer yourself.
3) Provide all the test cases for int atoi(char*) function in C.
Ans: Please try to give all possible test cases including NULL string,
arbitrarily huge string etc. For those of you Java freaks, this function works
similar to Integer.ParseInt().
4) Correct all the code defects in a given piece of code.
Ans: I don't remember the whole code, but it had some strings without '\0' at the
end etc. Was very easy to correct. (The cheapest one so far.☺)
5) Write a function bool isBST(Tree* root) which takes a binary tree as
input and says whether it's a binary search tree or not.
(D E Shaw had asked this just the previous evening. So had little problem
finishing it off in 2 min! )

Hughes systique

2008-08-18T22:39:00.000-07:00

Networking company ,package 4.0

written was lil lengthy , one apti paper(30 Questions in 45min ,questions were good ) and one technical

in technical dey covered almost all subjects like OS,networking,java,c,c++

interviews:

2 technical interviews there was no HR (in my coll,there is no guarantee that it will be same every where).

1st round:

tell me about urself [:P]

1 .i told i love to work in Linux , so dey asked about all those distributions that i m familiar wih,like wats the difference between fedora and ubuntu,
wat are the technical differences apart from GUI.
have u done any big projects in linux, i told writing simple device drivers [:P].

den jumped to C

2 .why size of int depends on the machine architecture (a lil bit discussion continued on that [:(])
den wats the best sorting algo and y ?
den to C++

3. y c++ ?

encapsulation

4. virtual functions, base class pointer,derived class pointer,biding references.
a reference is defined as private variable in a class. den he told me to write a constructor . asked me how the initialition is done for the reference (a lil bit discussion).

shell scrpting

5. find all those files that are modified since yesterday [:P]

and some more in shell scripting

den networking

6. wat happens when we enter www.google.com ( i told all those how the DNS is resolved , gave an example of our college website [:P])
7. y http protocol [:P]
8. RPC how it works ?

DBMS

9. SQL query
10. Normalization
and a lil discussion

OS

11. Dead lock avoidance,bankers algorithm
Sheduling, the best sheduling algo ?

haan thank god dey didn't ask IMP ,Environtment and ecology all those :P hehe ..

Second round

some other guy took this time

he was very very cool and friendly

12. tell me about urself
same here i love to work in linux
13. he asked y like that ?

14. some kernel questions
grep ,pipe,command line mode in VIM (how to copy line, replace some pattern)

15. write a code to implement memcpy() function

it was only for 20 mins

finally got through yaar [:P] [:D]

courtesy geek interview yahoo model

2008-07-15T11:44:00.000-07:00

1. In a village in each family they give birth to children till they get a boy. IF girl child they try again. What is the ratio of boys to girls.
2. 2n+1 numbers in a list except for 1 num all had duplicates, how to find duplicate in O(n)
3. In 1000 wine bottles stack 10 are poisoned given 10 rats what is the minimum number of tries to find the poisoned one. Rat dies once it licks the poisoned wine.
4. Write 1,3,6,4 using +,-,*,/ to get 24 (no repeat of numbers)
5. Which is the DS used in dictionary mode in mobile (t9)
6. Which is DS used for chess program...to predict move each and every time..
7. There are $1070 dollars how to split them into bags such that asked for any denomination from $1 to $1070 , u must b able to give without opening bag...

Another paper:
1. First fit issues...
2. Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements
3. Prog: given Numerator & Denominator.... print 0.3333333333 as .(3) 0.123123 as .(123)

Yahoo interview Questions

2008-07-14T20:26:00.000-07:00

1)Design a data structure such that given a stream of numbers, you can find the maximum of the numbers at any point and also all the numbers.

2)Given an array of 1s and 0s arrange the 1s together and 0s together in a single scan of the array. Optimize the boundary conditions.

3)Find the common ancestor of two given nodes in a binary tree, how do you exploit the properties of a given BST for the same problem.

4)Given a function getsort(data),that sorts the data given. The function sorts in place and does not use any extra memory. How do you validate the function with respect to 1)it sorts 2) it does not use extra memory

5)Explain the Traveling Salesman problem? What is an NP-complete problem? What is the Hamiltonian cycle problem?

6)Find out the least common ancestor in a binary tree.

Yahooooo

2008-06-29T21:55:00.001-07:00

A modified insertion sort uses binary search to find the position of insertion. What would be the improvement in order realized?

class a{};
main()
{
count <<>
}
What is the output?

The linked list size is unknown and it is very large. Find out the N th element from the back end.

What happens in the following code?
char x[10],y[10];
x=y;

Design a stack which supports push, pop, min and max operations in O(1).

Design an NFA to accept a string of 0s and 1s.

Given a balanced BST tree, write a function to replace the root with a node that belongs to the original tree.

Explain what this function does


char *mystrcpy(char *s)
{
char des=char [MAXLEN];
char * t=des;
while(*s)
{
*++t=*++s;
}
return t;
}

Given that you have a server hit by around 400 million users, and you have log files that contain the user ids of all of them. How do you find the frequency of login of each user. (The log files are very huge!!)

Explain Polymorphism, Encapsulation, Inheritance, operator overloading?

Deshaw

2008-06-29T18:37:00.000-07:00

Question1: Differentiate HTTP and HTTPS

Question2: Discuss ACID properties of a database system.

Question3: Given a table Employee with only one field: Names, report all names with multiple entries.

Question4:Given two sequences s1,s2 and another sequence s3, find if s3 is formed by interleaving s1 and s2.[Example: s1:abcd s2:bcaa s3:abbccdaa].

Question5: If a class B is inherited from a class A, B has a function foo which is also in A, how do you call foo function in A??

Question6: If a class B is inherited public from a class A, what all the variables that can be accesses and those that cannot be.

Question7: List out the additional features of C++ over C when the latter is already available as a good programming language?

Question8: Can classes,protected variables or other features in C++ be implemented using C?

Question9: Define Deadlock

Question20:Given a multi-threaded program How can you make it run on a system that supports only a single thread execution?

Question11:What are the Differences between a const char * and char const *?

Question12:What are the Differences between a reference variable and pointer variable in C++?

Question13What is a register variable and what are the limitations on it? What is an automatic variable?

Question14What are the Differences in memory allocation in array and pointer(stack and heap)?

Question15Find the missing element in a sorted array in most optimum running time (O(log n))

amazon

2008-06-21T02:42:00.000-07:00

1. How would you find the second largest element in an array using minimum no of comparisons?

2. Write a C program for level order traversal of a tree?

3. You are given: 3 types of vehicles: Motorbike, Car, and a special type of car for the handicapped.
3 types of parking: Motorbike parking, Car parking, handicapped car parking.

Motorbikes and cars can only park in their designated parkings, while the handicapped cars can park either in their own parking or the regular car parking.
How would you model this as classes? Explain your methods.

4. Given 2 tables: Employee(Employee_Name,Dept_No) Department(Dept_No, Dept_Name)

Write an SQL query which outputs all the employees, and their department nos and names, including all those departments which have no employees working for them.

6. Explain about Inodes?

7.Give a Linux shell command to find all files in a directory which contain ip addresses.

8. Given a table Employee which has columns name and salary, write an SQL query to find the employee with the second highest salary.

9. Given a table of Player which contains Sno and player name, write a query which finds all possible Table Tennis doubles pairings.

10.Given a string A, and a string B, and a dictionary, how would you convert A to B in the minimum no of operations, given that:

i) All the intermediate words must be from the dictionary

ii) An ‘operation’ is defined as:

a) Delete any character from a string ex dog → do

b) Insert any character into a string ex cat → cart

c) Replace any character in the string with another ex cat → cot

Amazon ..!!!

2008-06-10T01:27:00.000-07:00

1.Given a string,find the first un-repeated character in it? Give some test cases

2.You are given a dictionary of all valid words. You have the following 3 operations permitted on a word:

a) Delete a character

b) Insert a character

c) Replace a character

Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)

3.Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.

4.What is a C array and illustrate the how is it different from a list.

5. What is the time and space complexities of merge sort and when is it preferred over quick sort?

6. Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.

7. Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.

8.Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.

9. Given an array of size n ,containing every element from 1 to n+1, except one. Find the missing element.

Amazon latest interview Questions

2008-06-03T20:40:00.000-07:00

1. How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same

2. Explain polymorphism citing an example.

3. What are the 4 basics of OOP?

4. Define Data Abstraction. What is its importance?

5. Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Eg.

i) 3 2 7 10 should return 13 (sum of 3 and 10)

ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

6. Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can’t pass the value k to any function also.

7.You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?

8.Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.

9.Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.

10.Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren't present.

Google interview Questions

2008-05-31T14:37:00.000-07:00

GOOGLE PAPER - JAN 2005

Google Placement Paper and Sample Paper

1. Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed.

WWWDOT - GOOGLE = DOTCOM

This can be solved through systematic application of logic. For example, cannot be equal to 0, since . That would make , but , which is not possible.

Here is a slow brute-force method of solution that takes a few minutes on a relatively fast machine:
This gives the two solutions
777589 - 188106 == 589483
777589 - 188103 == 589486

Here is another solution using Mathematica's Reduce command:
A faster (but slightly more obscure) piece of code is the following:

Faster still using the same approach (and requiring ~300 MB of memory):

Even faster using the same approach (that does not exclude leading zeros in the solution, but that can easily be weeded out at the end):

Here is an independent solution method that uses branch-and-prune techniques:

And the winner for overall fastest:

2. Write a haiku describing possible methods for predicting search traffic seasonality.

MathWorld's search engine
seemed slowed this May. Undergrads
prepping for finals.

3. 1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
What's the next line?

312211. This is the "look and say" sequence in which each term after the first describes the previous term: one 1 (11); two 1s (21); one 2 and one 1 (1211); one 1, one 2, and two 1's (111221); and so on. See the look and say sequence entry on MathWorld for a complete write-up and the algebraic form of a fascinating related quantity known as Conway's constant.

4. You are in a maze of twisty little passages, all alike. There is a dusty laptop here with a weak wireless connection. There are dull, lifeless gnomes strolling around. What dost thou do?

A) Wander aimlessly, bumping into obstacles until you are eaten by a grue.
B) Use the laptop as a digging device to tunnel to the next level.
C) Play MPoRPG until the battery dies along with your hopes.
D) Use the computer to map the nodes of the maze and discover an exit path.
E) Email your resume to Google, tell the lead gnome you quit and find yourself in whole different world [sic].

In general, make a state diagram . However, this method would not work in certain pathological cases such as, say, a fractal maze. For an example of this and commentary, see Ed Pegg's column about state diagrams and mazes .

5. What's broken with Unix?

Their reproductive capabilities.

How would you fix it?

6. On your first day at Google, you discover that your cubicle mate wrote the textbook you used as a primary resource in your first year of graduate school. Do you:

A) Fawn obsequiously and ask if you can have an autograph.
B) Sit perfectly still and use only soft keystrokes to avoid disturbing her concentration chetanasinterview.com
C) Leave her daily offerings of granola and English toffee from the food bins.
D) Quote your favorite formula from the textbook and explain how it's now your mantra.
E) Show her how example 17b could have been solved with 34 fewer lines of code.

7. Which of the following expresses Google's over-arching philosophy?

A) "I'm feeling lucky"
B) "Don't be evil"
C) "Oh, I already fixed that"
D) "You should never be more than 50 feet from food"
E) All of the above

8. How many different ways can you color an icosahedron with one of three colors on each face?

For an asymmetric 20-sided solid, there are possible 3-colorings . For a symmetric 20-sided object, the Polya enumeration theorem can be used to obtain the number of distinct colorings. Here is a concise Mathematica implementation:

What colors would you choose?

9. This space left intentionally blank. Please fill it with something that improves upon emptiness.

For nearly 10,000 images of mathematical functions, see The Wolfram Functions Site visualization gallery .

10. On an infinite, two-dimensional, rectangular lattice of 1-ohm resistors, what is the resistance between two nodes that are a knight's move away?

This problem is discussed in J. Cserti's 1999 arXiv preprint . It is also discussed in The Mathematica GuideBook for Symbolics, the forthcoming fourth volume in Michael Trott's GuideBook series, the first two of which were published just last week by Springer-Verlag. The contents for all four GuideBooks, including the two not yet published, are available on the DVD distributed with the first two GuideBooks.

11. It's 2PM on a sunny Sunday afternoon in the Bay Area. You're minutes from the Pacific Ocean, redwood forest hiking trails and world class cultural attractions. What do you do?

12. In your opinion, what is the most beautiful math equation ever derived?

There are obviously many candidates. The following list gives ten of the authors' favorites:

1. Archimedes' recurrence formula : , , ,
2. Euler formula :
3. Euler-Mascheroni constant :
4. Riemann hypothesis: and implies
5. Gaussian integral :
6. Ramanujan's prime product formula:
7. Zeta-regularized product :
8. Mandelbrot set recursion:
9. BBP formula :
10. Cauchy integral formula:
http://www.ChetanaS.com
An excellent paper discussing the most beautiful equations in physics is Daniel Z. Freedman's " Some beautiful equations of mathematical physics ." Note that the physics view on beauty in equations is less uniform than the mathematical one. To quote the not-necessarily-standard view of theoretical physicist P.A.M. Dirac, "It is more important to have beauty in one's equations than to have them fit experiment."

13. Which of the following is NOT an actual interest group formed by Google employees?
A. Women's basketball B. Buffy fans C. Cricketeers D. Nobel winners E. Wine club

14. What will be the next great improvement in search technology?

Semantic searching of mathematical formulas. See http://functions.wolfram.com/About/ourvision.html for work currently underway at Wolfram Research that will be made available in the near future.

15. What is the optimal size of a project team, above which additional members do not contribute productivity equivalent to the percentage increase in the staff size?
A) 1 B) 3 C) 5 D) 11 E) 24

16. Given a triangle ABC, how would you use only a compass and straight edge to find a point P such that triangles ABP, ACP and BCP have equal perimeters? (Assume that ABC is constructed so that a solution does exist.)
This is the isoperimetric point , which is at the center of the larger Soddy circle. It is related to Apollonius' problem . The three tangent circles are easy to construct: The circle around has diameter , which gives the other two circles. A summary of compass and straightedge constructions for the outer Soddy circle can be found in " Apollonius' Problem: A Study of Solutions and Their Connections" by David Gisch and Jason M. Ribando.

17. Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

The following Mathematica code computes the difference between [the cumulative number of 1s in the positive integers up to n] and [the value of n itself] as n ranges from 1 to 500,000:
http://www.ChetanaSinterview.com
The solution to the problem is then the first position greater than the first at which data equals 0:

which are the first few terms of sequence A014778 in the On-Line Encyclopedia of Integer Sequences.

Checking by hand confirms that the numbers from 1 to 199981 contain a total of 199981 1s:

18. What is the coolest hack you've ever written?

While there is no "correct" answer, a nice hack for solving the first problem in the SIAM hundred-dollar, hundred-digit challenge can be achieved by converting the limit into the strongly divergent series:

and then using Mathematica's numerical function SequenceLimit to trivially get the correct answer (to six digits),

You must tweak parameters a bit or write your own sequence limit to get all 10 digits.

19. 'Tis known in refined company, that choosing K things out of N can be done in ways as many as choosing N minus K from N: I pick K, you the remaining.

This simply states the binomial coefficient identity .

Find though a cooler bijection, where you show a knack uncanny, of making your choices contain all K of mine. Oh, for pedantry: let K be no more than half N.

'Tis more problematic to disentangle semantic meaning precise from the this paragraph of verbiage peculiar.

20. What number comes next in the sequence: 10, 9, 60, 90, 70, 66, ?

A) 96
B) 1000000000000000000000000000000000\
0000000000000000000000000000000000\
000000000000000000000000000000000
C) Either of the above
D) None of the above

This can be looked up and found to be sequence A052196 in the On-Line Encyclopedia of Integer Sequences, which gives the largest positive integer whose English name has n letters. For example, the first few terms are ten, nine, sixty, ninety, seventy, sixty-six, ninety-six, . A more correct sequence might be ten, nine, sixty, googol, seventy, sixty-six, ninety-six, googolplex. And also note, incidentally, that the correct spelling of the mathematical term " googol" differs from the name of the company that made up this aptitude test.

The first few can be computed using the NumberName function in Eric Weisstein's MathWorld packages:

A mathematical solution could also be found by fitting a Lagrange interpolating polynomial to the six known terms and extrapolating:

21. In 29 words or fewer, describe what you would strive to accomplish if you worked at Google Labs.

MS intern

2008-05-31T14:28:00.000-07:00

Hi all

1)wap to merge 2 BSTs without using malloc.
2)wap to eliminate all the duplicates of an array with order preserving in o(n) time.you can use extra space.
eg. for aabbccccdddeeabcd
the answer should be abcde

3)given a 2D array of only 0's and 1's.Find an algorithm for converting all the rows and columns of elements which are 1 to 1 without using extra space.

for ex. if a[2][3]=1 then every element of 3rd row and 4th column should be set to 1

(plz notice that these are bits)

4) given 2 sorted linked lists,wap to find the intersection of these lists and preserve these intersections as a separate list.Don't use malloc.

5) wap to traverse a 2d array of bits in a spiral order.Don't include floating point computations/multiplication/division operations.

6)wap to insert a node in a sorted circular linked list in most efficient time.

rest was some discussion on projects and general talk.

Cool Question from Yahoo!

2008-05-30T22:55:00.001-07:00

Yahoo question - Friendship Graph of Orkut

Given the relationship graph of friends in orkut suppose the immediate friend list is stored in file sytem of database,
1) What algorithm you will use to find all unique 2nd level friends of a given user
2) Given 2 users give an algorithm which tells whether they are connected through common friends or not.
3) The solution should have optimum memory usage & running complexity.

The question has been discussed in the community but could not find any thread which has solved it.

Amazon interview Questions

2008-05-30T22:52:00.001-07:00

Q.1: Given a string construct a new string containing the occurrences of unique characters in it. You can
assume that only a-z & A-Z appear in the string with 'a' being different from 'A'. Also the letters in the output string must be in the order of their occurrence in the input string.
e.g. for the string "ThunderBirdFirefox" you must return the string "T1h1u1n1d2e2r3B1i2F1f1o1x1".

Q.2: Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

Q.3: Given a set of 1 Trillion integers on hard disk, find the smallest 1 million of them. You can fit at most 1 million integers in memory at a time. State the fastest solution you can think of.

Q.4: There is a matrix of integers where every row and every column is sorted. How will you find whether a given number exists in the matrix? (Just present the pseudo code).

Q.5: There are N people in a room and one of them is a celebrity. Everybody knows at least the celebrity while the celebrity knows no one. You enter the room to find the celebrity. You are only allowed to pick a person, point to another person, and ask whether the first person knows the second one. How will you find the celebrity in minimum number of questions?

Amazon off campus

2008-05-27T22:41:00.001-07:00

Design a 7 sided dice from a 5 sided dice i..e given a dice which will give results in the range of 1-5 how do you get results in the range of 1-7 from the same dice.

In other words, given random5 impelement random7 using random5. I searched community but could not understand the logic. If anyone can give a try

Link List addition

2 integers r given in the form of link lists.
eg..14567..is tored as..1->4->5->6->7->nul
how to add 2 such integers..assume..there sum is in integer range
IMP..use single link lists and not doubly linklists..
al exixtings solutions r have been done using doubly link lists..
and also plssss..us e rcursion...
this was asked in amazon off campus

Lets discuss

2008-05-27T00:14:00.000-07:00

google telephonic interview question

given an input n write a code to generate all possible parenthesizations
for ex if n=3
then print

((()))
(())()
()()()
(()())
()(())

Crazy google

2008-05-15T21:01:00.000-07:00

How many golf balls can fit in a school bus?

Solution: The point of the question isn't to see how golf balls you think are in the bus, but to see what your deduction skills are like. Do you just make a random guess or try to cop out by saying a lot, or do you actually try to come up with a legitimate answer by going through a logical series of steps.

You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?

Solution:You simply jump out. As you are scaled down, the ratio of muscle mass to total mass remains the same. Potential energy is given by E = mgh. So, if E/m is unchanged (where E is the energy expended in expanding your leg muscles, and m is your mass), then h is unchanged. Mini-me jumps as high as me. This is the reason why grass-hoppers can jump about as high as people.

How much should you charge to wash all the windows in Seattle?

Solution:As crazy as it might sound, questions like these demonstrate your ability to think through a complex problem with little or no information. They expect you to take an educated guess. Most of the time you can ask them questions like - how many buildings are there in Seattle.

How would you find out if a machine’s stack grows up or down in memory?

Solution:Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0.

Explain a database in three sentences to your eight-year-old nephew.

Solution:A database is like a file cabinet. The files, or data, is stored in it and can be arranged in categories. But unlike an actual file cabinet, you can do a lot more cool stuff with a database like being able to make it accessible through the internet.

How many times a day does a clock’s hands overlap?

Solution:The Hour hand and Minute hand would be meeting exactly 11 times in 12 hours (Hour hand would have taken 1 clockwise round and Minute hand would have taken 12 clockwise rounds, so 12 - 1 = 11 rounds).

result: First time hour and minute hands overlap will be 12 Hours / 11 = 01:05:27.27. So at this time only hour and minute hands would be overlapping and second hand will not be any near to them. Similarly for 2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th and 10th overlap of hour and minute hand the Second hand wont be any nearby. So all 3 hands (hour, minute and Second) overlap only 2 times i.e. (0:0:0 and 12:0:0).

Also we all know when we get our watches repaired, normally the repairman overlaps all the three hands to 12.

If we are considering that the second hand is not present, then the rest two overlaps 22 times in 24 hours.

There again is a catch, if we check the angles by which the hour hand and minute hand moves.

The second hand moves 6 degree in a second. In that time the minute hand will move 6/60 degrees. and the hour hand will move 6/(60*12) degrees. now taking these things in the considerations. if we check the positions of the hour and minute hand in terms of angle from the marker 12, for our first rendezvous time, i.e. 01:05:27.27 sec.
first thing that comes to my mind is that, there is fraction in the seconds. So that time can’t be measured. there will be no exact overlap. now lets calculate the angles:

1 hour 5 mins and 27 seconds = 3600 + 5*60 + 27 = 3927 seconds.

angle of hour hand = 3927 * 6/(60*12) = 32.725 degree.
angle of minute hand = 3927 * 6/60 = 392.7 degree
subtracting 360 degree from it we get - 32.7 degree.

So at 01:05:27 both hands don’t overlap. Now for 01:05:28 :
Angles : hour hand - 32.73333
minute hand - 32.8
so obviously they dont meet at 01:05:28 either.

So they overlap at 12:00 and 24:00 only. So the answer is 2 only.

You have to get from point A to point B. You don’t know if you can get there. What would you do?

Solution:Utilizing a “learn as you go” approach and applying collected knowledge and data along the way is the best way to proceed. Let’s break this down farther.

Determine the amount of time you have to go from point A to point B. Spend the initial 20% of that time making a 360° search with the largest circumference possible with the in the time you have allowed.

During that time, ask people, look for maps, clues, collect data, and knowledge. At the end of the initial 360° search take an objective look at all the information you have obtained and you calculate the risk of failure you are willing to live with. Create a plan and a strategy based on your assessment of where you believe point B to be. Then you proceed on implementing your plan with predetermined intervals of reassessment and strategy improvements.

This is the best chance you have reaching point B if you don’t know if you can get there.

Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

Solution:Let’s suppose there are
a set of attributes of each shirt you are interested in: e.g. sleeve length, color, buttons (no buttons, fully button, partially buttoned from collar to chest level).
Let’s say the closet is a simple wall closet with a single closet rod running the entire length of closet. On the left you put all the short sleeve shirts, and on the right the long sleeve shorts. You separate then long and short sleeve sides with a specially marked coat hanger. Then you separate each group into no buttonoed, partially buttoned, and fully button, using more specially marked hangers. Then each sub group is separated into colored and monochrome sub-sub-groups (specially marked hangers aren’t needed for separators unless you are color blind) Then each colored group is sorted left to right according to the color spectrum: ROYGBIV: red, orange, yellow, green, blue, indigo, violet. Each monochrome ggroup is sorted left to right: white on the left, black on the right, and shades of grey in the middle, the darker greys on the right, the lighter on the left.

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Solution:1. There is only one cheat husband
- If it is so then 99 wives knew it before. So the cheated wife got the idea from queen that her husband is cheating. So she will kill him. Next morning every wife will know there is no cheat husbands anymore.

2. There are more than one cheat husbands

- In this case, all of the wives already had the idea prior to queen's information. Its just that the cheated wives knew the count which is one less than what the non-cheated wives' knew - thats all. i.e. if there were 2 cheat husbands then their wives knew the count is 1 and others knew its 2. So the queen just repeated the info saying "at least 1". Same goes to 2,3,4...100 cheat husbands. So in this case no wife kills her husband.

In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?

Solution:From pure probability,we get the expected number of girls born to be 1/2 with that of boys being 1.So the ratio is 2:1

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

Solution:If the chance to see the car is 10 percent per minute, the first minute you have 10% chance, the second minute you have 10% of 90% = 9% (so total 19%), the third minute 10% of 81% (= 8,1%, total 27,1 %) ......
As the chance for 30 minutes is 95 percent, the chance for 1 minute is 9.5% and for 10 minute 63.1 %.

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)

Solution:7.5 degrees (the hour hand is 1/4th of the way between 3 and 4, the angle measure of that is 360/12 = 30 degrees between hours / 4 = 7.5 degrees).

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it�s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

Solution:1 and 2 cross, taking 2 minutes, 1 goes back carrying the flashlight total=3 minutes. 5 and 10 cross, taking 10 minutes totaltime now= 13 minutes, 2 goes back,total time now = 15 minutes. 1 and 2 cross again, taking 2 minutes making it 17 minutes.

You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?

Solution:No.

How many piano tuners are there in the entire world?

Solution:1) At first list out all the piano manufacturing companies in the world.
2) Then look into their purchase records and find out the piano purchasers information.
3) i) If the purchase is made by an individual or a house hold then the piano is played at best case by all the people of the house.
ii) Else if the piano is purchased for school then list out the students that opted the piano course in their music curriculum.
iii) If the piano is purchased by a Church then count the no of major or minor events of the church and count the piano users.
sum up all the numbers to get more or less accurate piano users count.

You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

Solution:choose 6 balls and weigh 3 against 3
- if they weigh the same, you have another weighing for the remaining 2 balls and you can find the heavier one
- if they don’t weigh the same, from the group of 3 which was heavier, choose any 2 balls and weigh them:
- if they weigh the same, the remaining ball is the heavier one; otherwise you just found the heavier one by weighing the 2 chosen balls.

You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

Solution:The highest ranked pirate gets 98 gold coins
---Two pirates get 1 gold coin each
---The other 2 pirates get nothing.

Google Latest interview Questions

2008-04-30T19:57:00.000-07:00

Google Interview Questions ::

Total there are five Technical Interviews followed by Management round.

So here are the questions.

Google Interview Round 1 ::

What is the Space complexity of quick sort algorithm? how do find it?

Solution: Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that
* in-place partitioning is used. This requires O(1).
* After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.
The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.

However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.

What are dangling pointers?

Solution: A dangling pointer is a pointer to storage that is no longer allocated. Dangling pointers are nasty bugs because they seldom crash the program until long after they have been created, which makes them hard to find. Programs that create dangling pointers often appear to work on small inputs, but are likely to fail on large or complex inputs.

Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

Solution:The simple recurrence relation governing this problem is f(N)=f(N-1) +f(N-2)(why?),which is a fibonacci sequence.
Nth state can be arrived directly by taking 2 step movement from N-2 or 1 step from N-1.Remember N-2 -> N-1 -> N is not a direct path from N-2th state to Nth state.Hence the no of solutions is no of ways to reach N-2th step and then directly taking a 2 jump step to N + no of ways to reach N-1th step and then taking 1 step advance.

You are given biased coin. Find unbiased decision out of it?

Solution:Throw the biased coin twice.Classify it as true for HT and false for TH.Both of these occur with probability=p*(1-p),hence unbiased. Ignore the other 2 events namely HH and TT.

On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.

Google Interview Round 2 ::

You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.

Solution:
The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array.

Sum of first N natural numbers=N*(N+1)/2

and S=N*(N+1)/2 - K.Now putting this other way around we get K=N*(N+1)/2 -S !!

Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.

We solve this problem by solving 2 essential equations.

They are X+Y=N*(N+1)/2 -S---------->(1)

X*Y=N!/P-------------------(2) where S and P are the cumulative sum and product of the array entries.

You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.

Solution:
The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution.

Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z

Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.

Questions on my project please be prepare well about your project

How do you search for a word in a large database.
How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'.

Google Interview Round 3 ::

You have given an array. Find the maximum and minimum numbers in less number of comparisons.

Solution:
only 3n/2 comparisons are necessary to find both the minimum and the maximum. To do this, we maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, however, at a cost of two comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then compare the smaller to the current minimum and the larger to the current maximum, at a cost of three comparisons for every two elements.

You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).

Solution:All the numbers are positive to start with.Now, For each A[i], Check the sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a repetition if it's negative.Finally all those entries i,for which A[i] is negative are present and those i for which A[i] is positive are absent.

Google Interview Round 4 ::

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.

       Ex: A="abcd" B="xyz" C="axybczd". answer is yes.

Solution:


bool test(A,B,C)

{

i=j=k=0;

while(k < i ="=" j ="=">

The above algorithm doesn't work when C[k]=A[i]=B[j], essentially throwing one in to a dilemma whether to accept the character from A or B.

Given two sorted arrays A and B.

Find the intersection of these arrays A and B.

Solution:The intersection can be found by using a variation of merge routine of the merge sort.

If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?

Solution:In this case for each entry of smaller array,we can run a binary search routine on the larger one to know its presence.

Google Interview Round 5 ::

If you get into Google, which products are you going to work on?
What is TCP, UDP. what is reliability, unreliability, give examples of these?

Solution:
Click Here To Read About TCP
Click Here To Read About UDP
Click Here To Read About Reliability

What is http protocol?

Solution:
Click Here To Read About HTTP
How does Google search engine works?
What is indexing, what is the input and output to it. how Google does that?

Yahoo interview Questions

2008-04-13T15:38:00.000-07:00

Yahoo Telephonic Round:

Design classes for the following problem. (C++)

A Customer Can have multiple bank accounts A Bank account can be owned by multiple customers When customer logs in he sees list of account, on clicking on an account he sees list of transactions.

Solution :

Customer class, Account class, Transaction class
Customer class contains an array of pointers to the account classes
Account class contains an array of pointers to its owner customer classes
Account class also contains an array of transactions associated to it.
Transaction class contains id or pointer the customer who did that transaction
In customer class write a function with prototype

for (i in Accounts )
{
cout << i.AccountName << endl;
}
cin >> id;
for(i in Accounts[id].transactions )
{
cout << i.TransDetails << endl;
}

Yahoo Interview Round 1:

How to call a C++ function which is compiled with C++ compiler in C code?

Solution: The C++ compiler must know that f(int,char,float) is to be called by a C compiler using the extern "C"construct:

The extern "C" line tells the compiler that the external information sent to the linker should use C calling conventions and name mangling (e.g., preceded by a single underscore). Since name overloading isn't supported by C, you can't make several overloaded functions simultaneously callable by a C program.
```
// This is C++ code
// Declare f(int,char,float) using extern "C":
extern "C" void f(int i, char c, float x);
...
// Define f(int,char,float) in some C++ module:
void f(int i, char c, float x)
{
  .....
} 
```
When you deliver your C++ headers and C++ library of a class (what all can you change in the class so that application using your class does not need to recompile the code)
How do you initialize a static member of a class with return value of some function?
Solution :

Static data members are shared by all object instances of that class. Each class instance sees and has access to the same static data. The static data is not part of the class object but is made available by the compiler whenever an object of that class comes into scope. Static data members, therefore, behave as global variables for a class. One of the trickiest ramifications of using a static data member in a class is that it must be initialized, just once, outside the class definition, in the source file. This is due to the fact a header file is typically seen multiple times by the compiler. If the compiler encountered the initialization of a variable multiple times it would be very difficult to ensure that variables were properly initialized. Hence, exactly one initialization of a static is allowed in the entire program.

Consider the following class, A, with a static data member, _id:
```
  
 //File: a.h
  class A
  {
     public:
     A();
     int _id;
  };
```
The initialization of a static member is done similarly to the way global variables are initialized at file scope, except that the class scope operator must be used. Typically, the definition is placed at the top of the class source file:
```
   // File: a.cc
  int A::_id;
```
Because no explicit initial value was specified, the compiler will implicitly initialize _id to zero. An explicit initialization can also be specified:
```
// File: a.cc
int A::_id = 999;
```
In fact, C++ even allows arbitrary expressions to be used in initializers:
```
      // File: a.cc
  int A::_id = GetId();    
```
How can one application use same API provided by different vendors at the same time?
If you are given the name of the function at run time how will you invoke the function?
Solution :
- Compile your program with --export-dynamic on the gcc command line
- Link with -ldl (dynamic library handling, needed for dlopen and dlsym
- Call dlopen() with a null parameter, meaning you aren't loading symbols from a file but from the current executable
- Call dlsym() with the name of the function you'll be calling. Note that C++ modifies function names, so If you're trying this with C++, you'd have to either declare this function as extern "C", or figure out what name the function has after compiling. (On unix, you could run nm -s on the object file for this).
- If dlsym() returns non-null, use the returned value as a function pointer to invoke your function.

Yahoo Interview Round 2:

When will you use shell script/Perl ahead of C/C++?
How does yahoo handles billions of requests, does it create a thread per request or a process?
How does HTTP works?

Solution :HTTP Is a request-response protocol.

For example, a Web browser initiates a request to a server by opening a TCP/IP connection. The request itself comprises o a request line, o a set of request headers, and o an entity. The server sends a response that comprises o a status line, o a set of response headers, and o an entity. The entity in the request or response can be thought of simply as the payload, which may be binary data. The other items are readable ASCII characters. When the response has been completed, either the browser or the server may terminate the TCP/IP, or the browser can send another request.
How to count number of unique music titles downloaded from a log file which contains an entry of all music title downloaded?
What is the difference between COM and CORBA?

Solution :COM is linked to Microsoft CORBA to UNIX,Moreover, COM objects require installation on the machine from where it is being used .CORBA is ORB (Object request broker) , and also its a specification owned by OMG, which is open. Not owned by a company. So we cannot say that it only belongs to Unix. Corba servers can run on windows NT, and CORBA clients can run on Unix.
What is web service?

Solution :Web Service is defined as "a software System to support interoperable Machine to Machine interaction over a network." Web services are frequently just Web APIs that can be accessed over a network, such as the Internet, and executed on a remote system the requested services.

I got only these two Rounds as of now, if I get any more I will post them here. If you have attended yahoo interview please share your experience and questions with us. You can mail them at kchaitanyya@gmail.com or you can comment here.Solutions for rest of questions will be provided later.if you know any of the questions which are unsolved please comment the solution. we will include.

Cisco Networking specific interview Questions

2008-04-13T15:35:00.001-07:00

What is a wildcard mask, and how is it different from a netmask?
How do you configure a Cisco switch or router? What are the steps needed?
How would I place an interface into trunking mode?
How do you shutdown an interface on a router or switch?
What is VTP?
What is VMPS?
What is SPAN/RSPAN?
What is flow/netflow?
What is TACACS? Radius?

Microsoft inrerview Questions

2008-04-13T15:29:00.000-07:00

First interview Questions

If the Fibonacci series is 1,2,3,5,8,13,..... then 10 can be written as 8 + 2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101. Got it??
The Question was, given n, I need to get all possible representations of n in Fibonacci Binary Number System.
as 10 = 8 + 2 ==> 10010
also 10 = 5 + 3 + 2 ==> 1110

I have a file in which there are supposed to be 4 billion numbers, starting from 1 to 4,000,000,000 but unfortunately one number is missing,i.e there are only 3,999,999,999 numbers, I need to find the missing number. In this question he asked me concepts like fopen, what will be the size of such a file and how such a big file will get loaded into RAM,and also concepts of logical/virtual/physical memory and memory paging.

I have an array consisting of 2n+1 elements. n elements in it are married, i.e they occur twice in the array, however there is one element
which only appears once in the array. I need to find that number in a single pass using constant memory. {assume all are positive numbers}

Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7

There is a temple, whose premises have a garden and a pond. It has 4 idols, each of Ram, Shiv, Vishnu and Durga. The priest plucks x flowers from the garden and places them in the pond. The number of flowers
doubles up, and he picks y flowers out of them and goes to offer it to Lord Ram. By the time he reaches to the pond, he finds the remaining flowers also have doubled up in the meantime, so he again picks up y from
the pond and goes to Lord Shiv.This process is repeated till all the Gods have y flowers offered to them, such that in the end no flower is left in the pond. Find x and y.

Second :

Asked About My Btech Final year Project. Design your own compiler that does trace back optimization.Give hypothetical test cases for your compiler.

There is a central server and some clients connected to it. All the changes made to data occur at the server, and all the clients have just read access.
You have two options:-
1. Push :- The server keeps pushing data to the clients.
2. Pull :- The client keeps requesting the server to send data.

What are the advantages and disadvantages of each type.Design a system which uses both the push as well as pull strategy.

Implement atof function.Write solid secure code only.

Third interview :

a) What is your CGPA?

b )What are your immediate goals?

c) What are your long term goals?

d) And some more questions on academics.

Find the first unrepeated character in a string of English language in O(n).

Simple questions on Probability.

Difference between a 32-bit OS and a 64-bit OS. Some questions on address space and fetch cycles/ Instruction Set of a processor.

Microsoft interview Questions

2008-04-13T15:28:00.000-07:00

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). Full points are given for the solution bearing efficiency O(log n). Partial points for the efficiency O(n).

Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) . Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters.

Given that, there are 2 linked lists L1 and L2. The algorithm finds the intersection of the two linked lists. i.e' "L1 intersection L2 " ( similar to intersection of 2 sets ). Write all the possible test cases involved in the above given problem.

Amazon intern Interview Questions

2008-04-13T15:22:00.001-07:00

Amazon Internship Interview Round 1

There are two urns A and B and an equal number of red balls and blue balls.How do u place the balls in the urns such that the probability of picking up the red ball is greater?

Two trains enter at the opposite sides of a tunnel of length L with speeds 'V'. A particle enters the tunnel at the same time with a speed 'v' and it vibrates in the tunnel[i.e. if it reaches the end of the tunnel then it comes back]. What is the position of the particle by the time the 2 trains meet?

Write an sql query to sort a table according to the amounts in a row and find the second largest amount.

How do you kill a process?

What is the functionality of a top command?

Given an array of size n+1 which contains all the numbers from 1 to n.Find the number which is repeated in O(n) time.How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?

Design a datastructure to represent the movement of a knight on a chess board

Write an algorithm to traverse a knight covering all the squares on a chessboard starting at a particular point.

Amazon Internship Interview Round 2

Why do you like to work with us?

What work are you expecting?

Tell me about any of your experience

Amazon standard Questions

2008-04-13T15:19:00.001-07:00

What are the major differences between C and C++?

What are the differences between new and malloc?

What is the difference between delete and delete[?

What are the differences between a struct in C and in C++?

What are the advantages/disadvantages of using #define?

What are the advantages/disadvantages of using inline and const?

What is the difference between a pointer and a reference?

When would you use a pointer? A reference?

What does it mean to take the address of a reference?

What does it mean to declare a function or variable as static?

What is the order of initialization for data?

What is name mangling/name decoration?

What kind of problems does name mangling cause?

How do you work around them?

What is a class?

What are the differences between a struct and a class in C++?

What is the difference between public, private, protected, and friend access?

For class CFoo { }; what default methods will the compiler generate for you>?

How can you force the compiler to not generate them?

What is the purpose of a constructor? Destructor?

What is a constructor initializer list?

When must you use a constructor initializer list?

What is a:
* Constructor?
* Destructor?
* Default constructor?
* Copy constructor?
* Conversion constructor?

What does it mean to declare a...

* member function as virtual?
* member function as static?
* member variable as static?
* destructor as static?

Can you explain the term "resource acquisition is initialization?"

What is a "pure virtual" member function?

What is the difference between public, private, and protected inheritance?

What is virtual inheritance?

What is placement new?

What is the difference between operator new and the new operator?

What is exception handling?

Explain what happens when an exception is thrown in C++.

What happens if an exception is not caught?

What happens if an exception is throws from an object's constructor?

What happens if an exception is throws from an object's destructor?

What are the costs and benefits of using exceptions?

When would you choose to return an error code rather than throw an exception?

What is a template?

What is partial specialization or template specialization?

How can you force instantiation of a template?

What is an iterator?

What is an algorithm (in terms of the STL/C++ standard library)?

What is std::auto_ptr?

What is wrong with this statement?
std::auto_ptr ptr(new char[10]);

It is possible to build a C++ compiler on top of a C compiler. How would you do this?

Basic Questions

* What is a friend, and why do you need it?
* If this doesn't compile, why didn't it (or will it compile?) Don't show comments, which explain the problem.


template  void HashTable <>::dummy()
{
K* k = NULL;
Hashable* h = k; // If this fails to compile, it's because
// K is not derived from Hashable.
}

* This will loop forever. Why? Will it really loop forever? (Answer: Base:func() does not call Base::func(). Base: is just a label, so the line always will call Derived::func() until it runs out of stack space)


class Base {
  public:
      Base() {}
      virtual void func() { /* do something */ }
};


class Derived : public Base {
public:
  Derived() {}
  virtual void func()
  {
Base:func();
/* do something else */
  }
};

main()
{
Derived d;
d.func();    // Never returns!
}

More advanced questions:

* What is a vtbl ?
* What is RTTI and why do you need it?
* How do I specialize a template? Give an example.

To separate sheep from goats (for those claiming C++ Guru status):

* What is a partial template? Why would you use one?
* How to I create a binary functor in the STL?

Given the following code:


class A;
class B;

class C {
  A* a_;
  B* b_;

  public:
};

Implement a copy constructor and assignment operator for C. A sample solution is something like:


class C {
A* a_;
B* b_;

void swap(C& rhs) { rhs.a_ = a_; rhs.b_ = b_; }

public:

C(const C& rhs) {
  auto_ptr<> a(new A(rhs.a_));
  auto_ptr<> b(new B(rhs.b_)):

      delete a_;
  delete b_;

  a_ = a.release();
  b_ = b.release();
}

C& operator=(const C& rhs) {
  C temp(rhs);
  temp.swap(*this);
  return *this;
}
};

What is wrong with this class, assuming that this is its complete interface?



class C {
char *p;
public:
C() { p = new char[64]; strcpy(p, "Hello world"); }
~C() { delete p; }

      void foo() { cout << "My ptr is: '" << p << "'" << endl; }
};

Since this has an overtly programmed destructor, the member wise semantics for destruction are not good enough; therefore, they are not good enough for copy and assignment either. But, the copy ctor and op= are not programmed, so we will have some serious trouble.

Gradual hinting: what happens when we make a copy? [correct answer: pointer is copied]. Now, the original goes out of scope, what happens to the copy? [pointer dangles]. How would you fix it?

[also, that delete p should be delete[ p since p was allocated with the array new]

Assuming that swap() and copy construction are part of your interface for class C, what's the cookie-cutter pattern for operator= that uses them?

answer:


C& C::operator=(const C &rhs) {
if (this != &rhs) {
  C tmp(rhs);
  this->swap(tmp);
}
return *this;
}
]]

Yahoo interview Questions

2008-04-13T15:17:00.001-07:00

1) There is a n x n grid of 1's and 0's. Find the i , where i is the row
containing all 1's and all 0's(except the intersection point). Should do
it in less than 25 comparisons
..
2) Use 2 stacks to implement a queue. Followed up with making the
access to the Data structure concurrently.

3) C++ question was good, implement a c++ class such that it allows us
to add data members at runtime.

4)Implement a transaction manager in a database server. The discussion
involved a lot of stuff about transaction logs.

5) How do you tune an application. Creating indexes.

6) Some SQL performance tuning questions on creating indexes.

7) can you write a foo() in c? If so how can u do it?

8) vector implementation questions.

9) Almost everyone asked about my language.(except ppl who attended my talk).

Microsoft interview Questions IDC

2008-04-12T19:33:00.000-07:00

First Interview:

The interviewer initially asked me all about my internship project and my role in that.

1. Given an Ellipse class can you derive a Circle class from it?
What all methods would you include in the circle class and what all in
ellipse?
Design a class of curve from which Circle and Ellipse can be inherited.

2. This contained series of questions on C++.

* What are virtual functions? Why are they used? Give examples.
* What are pure virtual functions and abstract classes? When do we use it?
* Where are virtual functions stored in the memory? How does the object knows that the virtual function to be called is from base class or derived class?
* What is VTable (virtual table) and what does it do?
* Few more similar questions that I am not able to remember.

3. These were also series of Questions mostly on OS skills:

* What are DLLs? Why do we use them?
* How does DLL work? Can anybody call methods written in DLLs ?
* What are static and shared Library? Which is fast and why?
* Questions about paging, loading, linking etc.
* Concept of 32-bit OS, virtual memory, inter-process communication etc.
* Few more similar questions that I am not able to remember.

4. Given a BST (Binary search Tree) how will you find median in that?

Constraints:

* No extra memory.
* Function should be reentrant (No static, global variables allowed.)
* Median for even no of nodes will be the average of 2 middle elements and for odd no of terms will be middle element only.
* Algorithm should be efficient in terms of complexity.

Write a solid secure code for it.

Second Interview:

Again, the interviewer asked me about my internship project and my role etc stuff.

1) He gave me a question that suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the no is divisible by 3 or not, how will you do that?

I was bit confused. I asked him that how are we getting the stream? Then he told me that you take a function signature as:

char getStreamBit();

which will return you the bit character (either '1' or '0') one by one. Also in the end he asked me to write the code of my algorithm on the board.

2) Then he asked me if I have any questions? I asked about 2-3 questions.

He was in hurry, so he left after that.

First and Second interview together lasted for JUST 1 hour and 45 minutes.

Third Interview:

Again, he too asked me about my internship project, implementation, my role etc.

1. Modified 2 color sort problem i.e. you are given an array of integers containing only 0s and 1s.You have to place all the 0s in even position and 1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and without taking extra memory (modify the array in-place).

For Example :

Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1}

Write a solid secure code for it.

2. You are given a Linked List and a function declaration as node* KReverse(node* head, int k);

KReverse is a function that reverses the nodes of a Linked List k at a time and then returns the modified Linked List.

For Example

Linked List : 1->2->3->4->5->6->7->8->9->10->11

For k = 2

Return Value: 2->1->4->3->6->5->8->7->10->9->11

For k = 3

Return value: 3->2->1->6->5->4->9->8->7->10->11

Write a solid secure definition for the function KReverse.

Constraints:

* If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is.
* You have to retain the memory address of the nodes without modifying it i.e. you can't just interchange the values in the nodes.
* No extra memory allowed.

He tested some of his inputs with the code I wrote.

The third interview lasted for about little more than 1.5 hrs and in the end he also offered me some fruits (Apple, Guava etc) and asked me about my college etc.

Fourth Interview:

I had my fourth interview too.

1. Initially he asked me about my earlier interviews. Who were your interviewers, how did you perform etc. things. I told him that in my first interview I just made a small mistake writing code (median of BST under constraints) for one of the case. So he asked me to complete my code for that case too and write solid secure code only.

He was very very particular about the code rather than the problem solving aspect for this question. He was basically checking my concepts about pointers, memory allocation etc things in whole interview and my way of writing code.

2. Suppose you are passing a string to a Formatter function. Get the formatted news feed output string such that

* There should be one sentence per line.
* There shouldn't be any spaces i.e. the line shouldn't be blank.

For example:

Input String:

". ....West Indies reached the final of DLF series. .Lalu was invited
to IIM-A once again. . .. .. . Microsoft unveils Zune, an ipod killer. .
. . . "

Output String:

"West Indies reached the final of DLF series.
Lalu was invited to IIM-A once again.
Microsoft unveils Zune, an ipod killer."

Design and write solid secure code for the Formatter Function.

As I said earlier, he was very particular about the code. This is where you need to follow all the standards, convention and check for the test cases. He just wanted to check my concepts about the pointers, memory allocation, OS etc stuff and of course the logic proposed by me for this particular problem(and questions like how much extra memory do you need for the output
string, how can you reduce that etc, complexity etc things)

He then asked me to give some of the test cases for the input string.

In between, he kept me asking questions like what if type int(32 bit) is replaced with type int64 (64bit). What modifications will you make to your code. Questions about double pointers, segmentation fault, all conceptual questions again!

Then he asked me about my interests. Why should we hire you etc HR questions. If you have any questions etc. stuff

Microsoft interview Questions

2008-04-12T19:30:00.000-07:00

1. Given a Parent -Child binary tree ,build the child -sibling version of it? Minimize the space requirements wherever possible.

2. Given a binary tree build a linked list of all its nodes such that the nodes of a level appear before the nodes of the next level?

3. Given an infinite stream of bits with the bits being appended at the highest significant position. give an algorithm to to say whether the number formed by using the sequence of bits that had been processed till then, is divisible by 3 or not?

4. Given a string S of words and no of character per line m ,with m being greater than the longest word in S,print S in a set of lines so that each line contains no more than m characters and no word split between 2 lines.

5. Given an expression remove the unnecessary brackets in it with out creating an ambiguity in its execution.
input output
ex1: (a+(b)+c) a+b+c
ex2: (a*b)+c a*b+c

6. Propose a tree based data structure to identify a node with nth rank with maximum efficiency .

7. Given a string S of alphabets and 2 characters a,b find the minimum distance between instances of them such that position of a <= position of b.

8. Given an array of size n with first l positions filled with characters and a string s ,replace all the instances of ’%’ with this string s,given that the length of the array is sufficient to handle these substitutions.
input output
eg: abcdef%ghi%—— and “ppp” abcdefpppghippp
1. Given a binary tree verify whether it is a binary search tree or not?
2. Write a C code to merge 2 binary search trees and do the same 2 merge linked lists.How is the former different when compared to the later.(Discuss the issues)

Google interview Questions

2008-04-12T19:17:00.000-07:00

Google telephonic Interview

Asked about my project. Prepare well to answer any type of questions that may arise in your project.They will just ask to explain about any one of the projects listed in your resume.

In a plane, n points are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Now
given these n points.Find the maximum number of collinear points.

Write the code for finding the min of n number.
```
I gave:

for(i=0;i
```
Given that n numbers are from random sampling how many times (probability) does
the line (i) be executed

Google Interview Round 2:

What is Bottom up parsing and what is top down parsing?

What is a symbol table?

There is a portal with two billion users registered. If you store all the 2 billion users in a conventional databases it will take more time to retrieve the data about a particular user when that user tries to login. How do you handle this situation to make sure that the user gets the response quickly.

There are 8 identical balls. One of them is defective. It could be either heavier of lighter. Given a common balance how do you find the defective ball in least number of weighings.

You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why?

Asked me about all the details of hash table and heaps.

Write code for finding number of zeros in n!

Google Interview Round 3 :

Write C++ class for the game Connect Four. [Connect Four (also known as Plot Four, Four In A Row, and Four In A Line) is a two-player board game in which the players take turns in dropping discs into a seven column grid with the objective
of getting four of one's own discs in a line.]

Given a stack and an input string of 1234.At any point you can do anyone of
the follow

i. take the next input symbol and Enque.
ii. you can pop as many as you can. When ever you
pop an element it will be printed
  (you cannot pop from an empty stack)

Give an example of one permutation that this data structure cannot generate.
```
For Example:

1234 is input.

First push all 1,2,3,4 on to stack and pop all.
output will be 4321.
```
It means that this data structure can generate 4321.

Question 2 was pretty easy right? Now do again the same question but the
data structure and input are different


Input: 12345
Data Structure: Deque ( Doubly Que )

Note: Deque is a data structure into which you can do enque
and deque from both sides.Some thing like this
__________________________________
enque ---> <----enque dequeue <---- ----->dequeue
__________________________________

Classic Egg Puzzle Problem

You are given 2 eggs.You have access to a 100-store building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-store building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Google Interview Round 4 :

Given n non overlapping intervals and an element. Find the interval into which this element falls.

Worst case is take all intervals one at a time and see whether the element lies in the interval or not.It will take O(n). So please give a solution that will do better than O(n).

Now given that the n intervals are overlapping then how do you solve? The interviewer was concentrating more on the complexities (running, memory ..)

Write code for Random Sort?


Algorithm  is explained:

Given an input array of size n. Random sort is sampling
a new array from the given array and check whether the
sampled array is sorted or not. If sorted return else
sample again. The stress was on the
code.

Google Interview Round 5:

This is Manager Round

Tell me an achievement that you have done in your non academics

Tell me about one of your project

Take a feature of C++ and tell me how you have implemented it in one of your project

By taking one of your project as example tell me how you have taken care of software engineering where you would have handled more data

There is a routine already written to find the subtraction of two sets ( set A - set B) . Write test cases for testing it.Tell me how do you test the test cases you have written?

There is a printed book. The page numbers are not printed. Now the printing of page numbers is being done separately. If the total number of digits printed is 1095 then how many pages does the book have?

Google Interview Questions

2008-04-12T19:13:00.000-07:00

Round -1

What is the Space complexity of quick sort algorithm? how do find it?
What are dangling pointers?
Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.
You are given biased coin. Find unbiased decision out of it?
On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.

Round -2

You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.
You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
Questions on my project please be prepare well about your project
How do you search for a word in a large database.
How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'.

Round -3

You have given an array. Find the maximum and minimum numbers in less number of comparisons.
You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).

Round -4

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
```
       Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
```
Given two sorted arrays A and B.

Find the intersection of these arrays A and B.
If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?

Round -5

If you get into Google, which products are you going to work on?
What is TCP, UDP. what is reliability, unreliability, give examples of these?
What is http protocol?
How does Google search engine works?
What is indexing, what is the input and output to it. how Google does that?

Google Top Interview Puzzles

2008-04-09T10:14:00.000-07:00

1) There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

2) There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).

3) Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.

4) You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.

Note: Some position may be blank in the game। So your data structure should
consider this condition also.

5) You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

6) How do you put a Binary Search Tree in an array in a efficient manner.

Hint :: If the node is stored at the ith position and its children are at
2i and 2i+1(I mean level order wise)Its not the most efficient way.

7) How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

Note :: You should not use use any extra space. i.e sorting Binary Search Tree
and storing the results in an array and listing out the fifth element.

8 )Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn

9) Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.

10 )Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?

11 )How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

12) Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you do the same ?

13) Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?

14)Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code

15 )You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?

16)Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?

17) Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?

18) Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

19) Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

20) Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

21) Given an array,

i) find the longest continuous increasing subsequence.

ii) find the longest increasing subsequence.

22) Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

23) Write a function to find the middle node of a single link list.

24 )Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

25) Implement put/get methods of a fixed size cache with LRU replacement algorithm.

26 ) You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

Please give a solution in O(n) time complexity

27 )Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

You can discuss these puzzles in comments.if you have any more Google which are interesting and frequently asking in interviews comment it, i will add to the above 27 puzzles.

Deshaw interview questions

2007-08-17T01:38:00.000-07:00

1)What is the number of zeros of the product of the first 100 numbers ?

2)A report has 20 sheets each of 55 lines and each line consists of 65 characters. If this report is to be retyped with each sheet having 65 lines and each line of 75 characters wht will be the reduction percent in the pages ?

(a) 22.5 % (b) 35 (c) 25 (d)none
Ans: 25

3)A man driving the car at twice the speed of auto oneday he was driven car for 10 min. and car is failed. he left the car and took auto to goto the office .he spent 30 min. in the auto. what will be the time take by car to go office?
(a) 25 (b) 30 (c) 35 (d) none
Ans: 25

4)Write code for initializing one dimentional and two dimentional array in a C Program?
Ans: I am sure you know this!

5)What is the difference between AWT & Swing?
Ans: Swing is written in Pure Java
AWT components use native code and controls has OS specific look and feel

6)If a number is choosen between 100 and 999 including these numberrs what is the provbabilty that the number selected does not contain a 7 is?
Ans: 18/25 (Check once!)

7)What command is used for knowing our own computer's IP address
Ans: ifconfig - for MAC and LINUX
ipconfig for windows

8)How many no of 4x1 muxes are required for making a 16x1 mux?
Ans: Five

9)Minimum number of IP addresses requiered for a router?
Ans: Two

Sasken Interview questions

2007-08-17T01:05:00.001-07:00

1)I am running a windows based application.While running the script on QTP ,The Application pop-up an Error Message as "object Disabled" in two different scenarios

Scenario 1-->The Application pops-up a Message for Max Session Reached(as the application is set to hold 2 sessions and if it crosses the pre-defined limit then the error message pops-up)

Scenario 2-->When Network connectivity is disabled the Application screen gets greyed out in colour with no operation possible.

Now though Exception handling features in QTP ,we need to do the following For Scenarion 1-->Through Exception handling we need to just accept the Message pop-up in the Application and and resume with the call function as is for Scenario 2--> Through Exception Handling featutes on QTP we need to shut down the client , restart the client and resume the call functions as it is

Note: The Application returns an Error Message as "object disabled" in both the cases i.e for pop-up message and when the Apllication getting greyed out due to Network failure how can we enhance the script in such a way that for the same error message retured by the application in two different and how to handle them????

2)What is the ethernet interface? Wand when we can use? How to connect the host systems to target system

3)What is the difference between ArrayList and Vector?

Ans: ArrayList is not synchronized while Vector is Synchronized.

4)How to test the MMS application?

5)What is regression testing?

Cisco interview questions

2007-08-15T07:32:00.000-07:00

1)What is Recovery Testing

Ans: In software testing, recovery testing is the activity of testing how well the software is able to recover from crashes, hardware failures and other similar problems.

2)Which layer is responsible for determining if sufficient resources for the intended communication exists?
* Application
* Network
* Session
* Presentation
* Transport

Ans:The Application layer of the OSI model is where users communicate to the computer. The Application layer is responsible for identifying and establishing the availability of the intended communication partner and determining if sufficient resources for the intended communication exist.

3)What are the 2 functions of the Data Link Mac layer?
* Handles access to shared media
* Manages protocol access to the physical network medium
* Provides SAPs for higher level protocols
* Allows multiple devices to uniquely identify one another on the data link layer

Ans: Handles access to shared media and Allows multiple devices to uniquely identify one another on the data link layer

4)Describe End to End network services: (Choose all that apply)
* Best Route selection
* Accomplished Segment by Segment, each segment is autonomous
* Flow Control & Data Integrity
* Best efforts packet delivery

Ans: Accomplished Segment by Segment, each segment is autonomous and Flow Control & Data Integrity (Not sure! Double check!)

5)Which of the following provide correct information about a protocol at the transport layer of the OSI model?
* UDP - Provides Connectionless datagrams service
* TCP - Provides Connection Oriented Services
* SMTP - Provides Mail Exchange
* IP - Route determination
* FTP - Transfers of Files

Ans: UDP - Provides Connectionless datagrams service and TCP - Provides Connection Oriented Services

6)Which layer is responsible for providing mechanisms for multiplexing upper-layer application, session establishment, and tear down of virtual circuits?
* Session
* Network
* Physical
* Transport
* Application
* Presentation

Ans: Transport Layer

7)Which of the following are logged when IP access list logging is enabled?
* source address
* protocol
* source port
* destination address
* access list number
* destination port

8)What?s the default CDP holdtime in seconds for Cisco routers?
* 30 seconds
* 180 seconds
* 90 seconds
* 60 seconds

Ans: 180 Seconds

9)Which two of the following protocols are used at the Transport layer?
* ARP
* UDP
* ICMP
* RARP
* TCP
* BootP

Ans: TCP and UDP

10)Choose three reasons why the networking industry uses a layered model:
A* It facilitates systematic troubleshooting
B* It allows changes in one layer to occur without changing other layers
C* It allows changes to occur in all layers when changing one protocol
D* It clarifies how to do it rather than what general function to be done
E* It clarifies what general function is to be done rather than how to do it

Ans: A, B, and E

11)Which layer is responsible for identifying and establishing the availability of the intended communication partner?
* Application
* Presentation
* Transport
* Session
* Network

Ans: Application

12)What is TACACS? Radius?

Ans: Terminal Access Controller Access-Control System (TACACS) is a remote authentication protocol that is used to communicate with an authentication server commonly used in UNIX networks. TACACS allows a remote access server to communicate with an authentication server in order to determine if the user has access to the network.

RADIUS: Remote Authentication Dial In User Service (RADIUS) is an AAA (authentication, authorization, and accounting) protocol for controlling access to network resources. RADIUS is commonly used by ISPs and corporations managing access to Internet or internal networks across an array of access technologies including modem, DSL, wireless and VPNs.

13)What is flow or netflow?

Ans: NetFlow is an open but proprietary network protocol developed by Cisco Systems to run on Cisco IOS-enabled equipment for collecting IP traffic information.

14)What is SPAN or RSPAN?

Ans: Switched Port Analyzer. Remote Switched Port Analyzer. You can monitor traffic flowing to a port from another port.

15)What is VMPS?

Ans: The VLAN Membership Policy Server ( VMPS ) makes it possible to use a client/server architecture to manage dynamic VLAN based on the MAC addresses.
When someone connects to a port, the client switch connects it to server VMPS to know if this MAC address can be connected to this port.

Cisco

2007-08-15T07:09:00.000-07:00

Continued ...

SOFTWARE SECTION

1. The starting location of an array is 1000. If the array[1..5/...4] is stored in row major order, what is the location of element [4,3]. Each word occupies 4 bytes.

Ans: 1056 (Check it out for yourself!)

2. In a tertiary tree, which has three childs for every node, if the number of internal nodes are N, then the total number of leaf nodes are?

Ans: (2N+1)

3. Explain the term "locality of reference" ?

Ans: In computer science, locality of reference, also called the principle of locality, is the term applied to situations where the same value or related storage locations are frequently accessed. There are three basic types of locality of reference: temporal, spatial and sequential:

Temporal locality -
Here a resource that is referenced at one point in time is referenced again soon afterwards.
Spatial locality -
Here the likelihood of referencing a storage location is greater if a storage location near it has been recently referenced.
Sequential locality -
Here storage is accessed sequentially, in descending or ascending order.

4. What is the language used for Artificial Intelligence

Ans: lisp

5. What is the character set used in JAVA 2.0 ?

Ans: Unicode

6. char a =0xAA ;
int b ;
b = (int) a ;
b = b >> 4 ;
printf("%x",b);

What is the output of the above program segment ?

Ans: fffffffa

7. struct s1 { struct { struct { int x; } s2 } s3 }y;
How does one access x in the above given structure definition ?

Ans: Compilation failes as ";" is missing immediately after declaration of the strcuture variables s2 and s3.

Otherwise, we can access x like this: y.s3.s2.x

8. Why there is no recursion in Fortran ?

Ans. There is no dynamic allocation.

9. What is the worst case complexity of Quick sort?

Ans. O(n²)

10. What will be sequence of operating system activities when an interrupt occurs ?

Ans: Most modern general purpose microprocessors handle the interrupts the same way. When a hardware interrupt occurs the CPU stops executing the instructions that it was executing and jumps to a location in memory which either contains the interrupt handling code or an instruction branching to the interrupt handling code. This code usually operates in a special mode for the CPU, interrupt modeand, normally, no other interrupts can occur in this mode. There are exceptions though; some CPUs rank the interrupts in priority and higher level interrupts may happen. This means the first level interrupt handling code must be very carefully written and it often has its own stack which it uses to store the CPU's execution state (all of the CPU's normal registers and context) before it goes off and fully handles the interrupt. Some CPUs have a special set of registers that only exist in interrupt mode and the interrupt code can use these registers to do most of the context saving it needs to do. When the interrupt has been handled, the CPU's state is restored and the interrupt is dismissed. The CPU will then continue to doing whatever it was doing before being interrupted. It is important that the interrupt processing code is as efficient as possible and that the operating system does not block interrupts too long.

Source: http://www.science.unitn.it/~fiorella/guidelinux/tlk/node81.html

11. In a sequential search, what is the average number of comparisons it takes to search through n elements ?

Ans: (n+1)/2.

12. What is the size of the array declared as double * X[5] ?

Ans. 5 * sizeof ( double * )

13. A binary search tree with node information as 1,2,3,4,5,6,7,8 is given. Write the result obtained on preorder traversal of the binary search tree ?

Ans : (Not sure!)

14. If size of the physical memory is 2³²-1, then what is the size of the virtual memory ?

15.

S -> A0B
A-> BB0
B-> AA1
How many strings of length 5 are possible with the above productions?

16. (3*4096+15*256+3*16+3). How many 1's are there in the binary representation of the result?

Ans. 10 ( 16179 = 11111100110011)

17. In memory mapped I/O how is I/O is accessed ?

Ans: uses the same address bus to address both memory and I/O devices, and the CPU instructions used to access the memory are also used for accessing devices.

18. What is the use of ALE in 8085 ?

Ans: To latch the lower byte of the address.

19. If the logical memory of 8 X 1024 is mapped into 32 frames, then the number of bits for the logical address are____ ?

Ans. 13

20. Context free grammar is useful for which purpose ?

21. In ternary number representation, numbers are represented as 0,1,-1.(Here -1 is represented as 1 bar.) How is 352/9 represented in ternary number representation?

22. There are processes which take 4,1,8,1 machine cycles respectively. If these are executed in round robin fashion with a time quantum of 1, what is the time it take for process 4 to complete ? Ans. 9

23. The minimum frequency of operation is specified for every processor because......
a)for interfacing slow peripherals
b)dynamic memory refreshing.
c)to make compatible with other processor.

24. For linked list implementation , which search is not applicable ?

Ans: Binary search.

25. Each character is represented by 7 bits, 1 bit is used to represent error bit and another bit for parity. If total number of bits transmitted is 1200 bits, then what is the number of symbols that can be transmitted ?
Ans: 133

26. Explain set associativity of cache ?

27. Write the postfix form of the following expression . A+[[(B+C)+(D+E)*F]/G]

28. What is the function of the linker?

29. void f(int y)
{
struct s *ptr;
ptr = malloc (sizeof (struct)+99*sizeof(int));
}

struct s{
int i;
float p;
};

when free (ptr) is executed, then what will happen?

30. To concatenate two linked lists strings, the order is O(1) is obtained for what kind of list?

31 main()

{ fork();

fork();

printf("hello");

}

How many times it will print hello?

32. char A[5,6] How many bytes it requires?

33. Bridges are used in which layer?

34 .Bigendian means

a)lower byte stored in lower address

b)lower byte stored in higher address

one of these is correct.u can verify in Any micro processor book.

35 main()

{ j=0

for(i=0;i<10;i++)>

{

j+=i;

}

what is the value of i & j at the end of the loop

ans: 10,46

Cisco

2007-08-15T06:22:00.000-07:00

PAPER 28 JULY

Basic Digital Section

1. In order to find out stack fault of a three input nand gate how many necessary input vectors are needed ?

2. What is parity generation ?

3. A nand gate becomes ___ gate when used with negative logic ?

4. What is the advantage of cmos over nmos ?

5. What is the advantage of syncronous circuits over asynchronous circuits ?

6. What is the function of ALE in 8085 ?

7. A voice signal sample is stored as one byte. Frequency range is 16 Hz to 20 Hz. What is the memorysize required to store 4 minutes voice signal?

8. What will the controller do before interrupting CPU?

9. In a normalised floating point representation, mantissa is represented using 24 bits and exponent with 8 bits using signed representation. What is range ?

10. The stack uses which policy out of the following-- LIFO, FIFO, Round Robin or none of these ?

11. Where will be the actual address of the subroutine is placed for vectored interrupts?

12. Give the equivalent Gray code reprasentation of AC2H.

13.What is the memory space required if two unsigned 8 bit numbers are multiplied ?

14. The vector address of RST 7.5 in 8085 processor is _______.
Ans. 003C (multiply 7.5 by 8 and convert to hex)

15. Subtract the following hexadecimal numbers--- 84₁₆ - 2A₁₆

16. Add the following BCD numbers--- 1001 and 0100

17. How much time does a serial link of 64 Kbps take to transmit a picture with 540 pixels.

18. Give the output when the input of a D-flip flop is tied to the output through the XOR gate.

19. Simplify the expression AB + A( B + C ) + B ( B + C )

20. Determine the logic gate to implement the foolowing terms--ABC, A+B+C

21. Implement the NOR gate as an inverter.

22. What is the effect of temperature on the I_cb in a transistor

23. What is the bit storage capacity of a ROM with a 512*4 organisation?

24. What is the reason of the refresh operation in dynamic RAM's ?

25. Suppose that the D input of a flip flop changes from low to high in the middle of a clock pulse.Describe what happens if the flip flop is a positive edge triggered type?

26. How many flip flops are required to produce a divide by 32
device ?

27. An active HIGH input S-R latch has a 1 on the S input and a 0 on the R input. What state is the latch in?

28. Implement the logic equation Y = C^BA^ + CB^A + CBA with a multiplexer. (where C^ stands for C complement)

29.Equivalent Gray code reprasentation of AC2H.

30. What does a PLL consist of ?

Google interview questions

2007-08-15T06:09:00.000-07:00

1)Write a command to find all of the files which have been accessed within the last 30 days.

Ans: find / -type f -atime -30 > outputfile.txt

2)write an assembly code which can call function in a loop with al value from 0 to 9.

3)Given one ip address, find out which contry

4)what is the hexidecimal number of 4100?

5)how to estimate the disk access time? e.g. the time between read one byte and another byte in the disk.

6)class foo { public: static int func(const char*& p) const; }; This is illegal, why?

7)value = 0xabcd; for (loop = 1; (value >> 1) & 1 loop & 1; loop++) { foo(); if (loop & 1) value >>= 1; } how many times is foo() executed?

8)You have a sheet cake. There is a rectangular piece missing from the inside of the sheet cake. The location of the missing piece is arbitrary. I was told I could assume I had the means to make the cuts. How do you divide the sheet cake into 2 even proportions with 2 cuts?

9)What is the difference between Set_window() and _set_window ()?

10)It's 2PM on a sunny Sunday afternoon in the Bay Area. You're minutes from the Pacific Ocean, redwood forest hiking trails and world class cultural attractions. What do you do?

11)In your opinion, what is the most beautiful math equation ever derived?

12)What will be the next great improvement in search technology?

13)What is the optimal size of a project team, above which additional members do not contribute productivity equivalent to the percentage increase in the staff size?

14)Given a triangle ABC, how would you use only a compass and straight edge to find a point P such that triangles ABP, ACP and BCP have equal perimeters? (Assume that ABC is constructed so that a solution does exist.)

Adobe Questions

2007-08-15T04:51:00.000-07:00

ADOBE PALCEMENT PAPER ON 3rd SEPTEMBER 2006 AT MUMBAI

Written Test
1) Wap to reverse a linked list and sort the same.

2) Given two integers A & B. Determine how many bits required to convert
A to B. Write a function int BitSwapReqd(int A, int B);

3) Write an algorithm to insert a node into sorted linked list. After inserting,
the list must be sorted.
4) Without using /,% and * operators. write a function to divide a number by 3.
itoa() function is available.

5) Wap to swap two integer pointers.

6) Write a funcn int round (float x) to round off a floating point num to int.

7) write an ALP to find sum of First n natural numbers using the following Instructions

LDA num ; load Accumulator with num
DCR R ; decrement Register R
INR R ; increment Register R
MOV x,y ; move the contents of register y into register x
JZ label ; jump to label if A=0
DJNZ label; Decrement & Jump if A <> 0
you can use B & C registers in addition to A register

8) Prove that a tree is BST. What is height of a tree?

Sun Microsystems

2007-08-15T04:35:00.000-07:00

1)How many ways can a thread be used?
2)What is multithread synchronizing ?
3)In which way does a Primitive data type is passed ?
4)What happens when a main method is declared as private?
5)Is there any need to import java.lang package?
6)What is multithread synchronizing ?
7)Find the error in the following program struct point {struct point *next; int data; } x; main() {int...data; } x; main() {int i; for(x=p;x!=0;) x=x->next,x++; freelist(x); } freelist(x) {free(x); return }
8)Which data structure gives efficient search? A. B-tree B. binary tree C. array D. linked list
9)Give the output of the following program main() {char *p='a'; int *i=100/*p; } what will be the value of *i= 1
10)Give the output of the following program main() {int ret; ret=fork();ret=fork();ret=fork();ret=fork(); if(!ret) printf("sun"); else printf("solaris");

Sun Microsystems

2007-08-07T08:18:00.000-07:00

SUN MICROSYSTEMS PAPER - DEC 2005

60 questions 60 marks

Everything is multiple. BEWARE OF NEGATIVE MARKING .

Section 1 : Operating systems 20 questions

Section 2 : Technical programming 25 questions

Section 3 : Aptitude 15 Questions

Section 1 : Operating Systems

Study all the unix commands & some basic networking concepts like DHCP, Dynamic NAT, RARP, ARP, UDP, DNS. Unix : Grep, sed, basic perl program whose o/p is to be predicted. Pipes. You can expect some nasty & tricky questions !. But this section is kool not to worry too much.

Section 2 : Programming part

C programs & Java programs. The programs seems to be easy but bcoz of the Negative marking (0.5) we have to be very clear. No bluffing ok! The programs are easy. Programs were on Fork, PID, Basic C syntax, Basics of Java, Exception handling, Inheritance, Strings, Cast conversion, Object linking etc

Section 3 : Aptitude

Most of the questions can be found from other placement papers like Sonata, TCS, Caritor. Nothing to worry much. But again you have to be very confident about the answers.

The cut-off marks are not told & will be decided by the evaluators at that time. Only 3 out of some 50 candidates got through. The next rounds are technical interview followed by HR interview. This interview call was purely on referral basics. So not much competitors & really a good chance of getting thru !. Do well & good luck !

Questions:

# main()

{

int _=10;

printf("%d",_);

}

# If you have developed an microprocessor by name JUGGI, how would you account for the JVM ?

a) Write/ Develop a new JVM by going through the SUN standards

b) Implement the same JVM that's in windows , linux as JVM is platform independent.

c) Leave it to the SUN to write it for you

d) Need not write anything

# Which server would you use to configure or set up a new IP address in Linux

a) DNS b) DHCP c) TCP d) blah blah blah .....

# Three friends divided some bullets equally. After all of them
shot 4 bullets the total no.of remaining bullets is equal to that of
one has after division. Find the original number divided. [Infosys paper & IBM]

a) 20 b) 22 c) 18 d) 19

# A cube object 3" * 3" * 3" is painted with green in all the outer surfaces. If the cube is cut into cubes of 1"*1"*1", how many 1" cubes will have at least one surface painted. [Caritor]

a) 8 b) 26 c) 27 d) None of the above

# What is the protocol used for getting the physical address by supplying
IP address of a node ? [Wipro]
[i] ARP [ii] RARP [iii] BOOTP [iv] DHCP

# How can a process be started automatically in UNIX ? [MBT]

a) CRONTAB b) INITTAB c) CONTROL d) FORK

# Flow chart problem [Satyam]

let the value of N be 10
divide N by 10 to give quotient (Q) remainder(R)
diff=R-Q
if diff=1 then 6
go to step 7
display the value of N
add 1 to N
if N <100>

a) 11,12,13,,14.. b)12,23,34,..... c)21,32,4,354...... d) none

# What is the output of the Program? [Sasken]
#define SQ(x) x*x
main()
{
int a=SQ(2+1);
printf("%d",a);
}

a) 5 b) 6 c) 7 d) None of the Given Answers

# There N stations on a railroad. After adding X stations on the rail route 46 additional tickets have to be printed. Find N and X. [Sify]

a) x=2 and N=11 b) x=2 and N=12 c) x=2 and N=13 d) x=3 and N=11

# How is an Non-maskable interrupt handled

a) The current program is executed & then handles the NMI

b) Handles the NMI first & then continues with the execution

c) Handles the interrupt based on the priority

d) Ignores the interrupt & continues with the program.

# Problems like

If QWERT means 2513678397849 what does [some word] equal to ?

# Simple program on fork system call

# Simple problems on inheritance [Java]

# Simple string assignment problems

# If 8 butts of cigarette make 1 cigarette then how many will 64 butts make ?

Ans : 8

# ICMP is used where

a) ICMP supports packets containing error, control, and informational messages.

b) The Ping / Command execution.

c) a&b both

PAPER 2

1. For the following program.

struct XXX
{int a;
float b;
char *s;
}X;

If optimization :X not used in compiler then unused
bits_________________.
Give your assumption_______________.

2. Give the output of the following program

struct XXX
{int a:6;
float b:4;
char s;
}structure;

size of (structure);

3. Class used for the multiple inheritence in JAVA_________________

(a) anonymous class
(b) inner class
(c) abstract class
(d) none

4. XDR fixes in which part of OS1 stack.

5. LDAP is____________service protocol.

6. Given definition for a function which returns a array of pointers

with argument of int*.

7. Give a function declaration with no arguments which refers a two
dimensional array

8. Pick up the correct function declaration.

1. void *[] name();
2. void int[][] name();
3. void ** name();
4. none of the above.

9. Give the difference between monolithic and microlithic kernal:

a. monolithic large
b. microlithic used in embedded systems.
c. none.

10. rPC coresponds to_______________in OSI stack.

11. Find the no.of page faults using LRU stack.

eg.3 4 4 6 7 8 1 2 .. ..

12. The inorder representation of a tree 41523 and preorder is 24513
Draw it?

13. When does a stack member will be initialised

(a) when object is created
(b) when object is initialised.
(c) doesnot depend on object.
(d) none.

14. Number of CPU in a multiprocess is contrassed by

(a) RISC nohere of CPU
(b) memory
(c) both (a) and (b)
(d) None of the above

15. Give the output of the following program

main()
{char *s;
s="hot java";
strcpy(s,"solarrs java")

}

16. Give the output of the following program

main()
{printf("hot java");
fork()
exit(0);
}

(i). When redirected to a screen what will be printed.
(ii). When redirected to file what will be printed.

17. Give the output of the following program

main()
{int ret;
ret=fork();ret=fork();ret=fork();ret=fork();
if(!ret)
printf("sun");
else
printf("solaris");

18. Give the output of the following program

main()
{char *p='a';
int *i=100/*p;
}

what will be the value of *i= 1

19. Which data structure gives efficient search

1 B-tree
2 binary tree
3 array
4 linked list

20. Find the error in the following program

struct point
{struct point *next;
int data;
}
x;

main()
{int i;
for(x=p;x!=0;)
x=x->next,x++;
freelist(x);
}

freelist(x)
{free(x);
return
}

21. Mutex and _________are similar locking mechanisms.

22. A complex question on pointers and functions.

23. SNMP and SMIP transport layer protocols for TCP/IP&OSI.

24 UNIX: difference between select and poll

Yahoo Questions

2007-08-06T19:39:00.000-07:00

1. In a village in each family they give birth to children till they
get a boy. IF girl child they try again. What is the ratio of boys to
girls.

2. 2n+1 numbers in a list except for 1 num all had duplicates, how to
find duplicate in O(n)

3. In 1000 wine bottles stack 10 are poisoned given 10 rats what is
the minimum number of tries to find the poisoned one. Rat dies once it
licks the poisoned wine.

4. Write 1,3,6,4 using +,-,*,/ to get 24 (no repeat of numbers)

5. Which is the DS used in dictionary mode in mobile (t9)

6. Which is DS used for chess program...to predict move each and every
time..

7. There are $1070 dollars how to split them into bags such that asked
for any denomination from $1 to $1070 , u must b able to give without
opening bag...

Another paper:

1. First fit issues...

2. Algorithm to partition set of numbers into two s.t. diff bw their
sum is min and they hav equal num of elements

3. Prog: given Numerator & Denominator.... print 0.3333333333 as .(3)
0.123123 as .(123)

Sasken

2007-08-06T19:34:00.000-07:00

Off Campus Written Test conducted at Bangalore
The test comprises of 2 sections:
1. Technical ( C ) & Technical Subject- 60 mins, 60 questions
2. Logical Reasoning.. - 30 mins,17 questions....

==> Questions in C were mostly from "pointers in c" and "test ur C skills" by Yeshwant Kanetkar... C questions based on command line arguments, data structure ( BST, tree traversals). All the questions were like " what is the output of the following program segment" and in many questions 3rd and 4th choices were (c) compilation error and (d) compilation, warning, runtime error.... Heard they are asking abt- ptr, string, arr, preprocessor, data structures etc.. C test was pretty ok pass by value, pass by reference etc. questions were asked The general test was pretty tough, they ask u fourier transforms,harmonics,Barkhuasen criterion,virtual memory,Whether FIFO is better than LRU etc. 4 questions were from fourier transforms the duration was 60 mins and no negative marking

C basics 10 questions ,very easy.Given a program and asked the output-type questons.from pointers 3-4 questions are there. 2)reg subject:very very easy:some from digital(on nand gates. Jk flip flop),from Information theory and coding,some from Micro processors.

In Logical Reasoning all the 17 questions were paragraphs (argument) of 5 to 6 sentences...five sentences (choices) will be given below and questions were asked like " which of the five if true will weaken or supports the argument above .." :- R. S. Agrawal LR is sufficient

SASKEN PAPER HELD ON 9th AUG at 2:30pm
--------------------------------------------------------------

The questions were like this.
------------------------------
The text consists of two parts
1) C test
2) CSE01 Test
Duration: 1hr
---------------------------------------------------------------
1) C test -10 questions- Some questions were as follows, remember only a few.
a) What is the parameter passing mechanism to Macros Called?
b) void func(int x,int y)
{
x=3;
y=2;
}
main()
{
int i;
func(i,i);
print(i);
}
If the output must be 2 what is the parameter passing mechanism called?
c) which of the following code will swap the two numbers? -3 choices was given
d) which of the following is illegal for the program?
main()
{
char const *p='p';
}
1)p++ 2) *p++ 3)(*p)++ 4) all
e) what is the output of the following program
void print(int ** arr)
{
print("0 %f, 1 %f, 2 %f ",arr[0][0],arr[0][1],arr[0][2]);
}
main()
{
int a[][]={ {1,2,3},
{4,5,6}
}
int ** arr=a;
print(arr);
arr++;
print(arr);
}
f) which of the following code swaps the two numbers.
- 4 choices were given
g) if the string " this is a " is present in the code of a function such as 'void func(void)' where
will the variable stored in the memory.
a) in the stack b) heap c) code or text segment as per implementation d) created when func is called, stored in function stack space and destroyed as it goes out .

2) CSE01-15 questions
In this section there was question from LD-gates, JK flip flop, sampling rate and few other
then there was a few from OS - don't remember the questions.

INTERVIEW

In the interview, they asked about Stacks, Queues, Linked lists, Binary Trees.

Few questions I remember are:
1) If u have a linked list library, how do u design stack and queue using it; write pseudocode.
2) What are static variables and functions?
3) Write code in C to count the number of 1s in a character (1byte).
4) What is pre-order, post-order, in-order; write code to print post-order.
5) Can u construct a binary tree given its inorder and postorder details. Is it neccessary or sufficient to construct tree. Asked an example to do in both ways.
6) If recursion is not used to print post order, what other data structure u use
(ans: Stack).
7)Can u use stack always in place of recursion?
(ans: Yes)
8) What are meta characters?
9) Write a piece of code to insert a node in a linked list.
10) About malloc.
11) About Operating System - Semaphores
12) About Computability (eg:- finding infinite loop), Complexity of algorithms
13) What does compiler and assembler do?

They asked grep command in Linux. How do u search '\n', using grep, in a file.
They may ask some other commands if u say u r familiar and recently been using linux.
About Networks? OSI reference model.
what does transport layer do?
TCP belongs to which layer?
IP belongs to which layer?
Where is error correction done?
What is a connection oriented/ connection less transmission?
What is meant by reliable transmission protocol? why is it called so?
What is flow control and where it is done?
About ur project?
Asked me expalin about the project in brief.
If u don't know anything, say it sincerely. U cannot bluff them. I too spoke to them sincerely.
They were cool. U need not get tensed. They won't attack you. Just they want to know ur hold about the subject.

Next Paper
NOTE : Answer May Not be Accurate So Get An Idea of Questions.

What is the value of X after this execution
x = 0;
begin
parbegin
y = x;
x = x+1;
parend
parbegin
z =x;
x = z+1;
parend
end

a:1
b:0
c:2
d:1 or 2

2. Comparision of LRU and FIFO
a. FIFO IS always better
b. FIFO is always worst
c. FIFO is sometimes better
d. NOthing can be said.
ANS :D

3. How many minimum no of NAND GATES ARE required for construction of X-OR gate
6 7 5 8
ANS : 5 (but the correct answer is 4 ) if 4 is present that is correct answer otherwise 5

4. If each counter has time delay of 15 n sec. Then what is the max time to change the state of 4 bit
synchronus counter
a. 60
b.15
c. 120
d. none
ans : 15

5. There is ADC of freequency 1 MHz. How much time it will take to convert a message stream of 6 bit
ans : 6 Micro Sec

6. What is Baukshna's criteria for sustaining freequency.
some fk is given that( Iam not clear)
fk > 1
fk <1 fk ="0">
none

7. which of the following is wrong:
ans : WCW is a context free language.where w is word formed by sequence of alphabets.

8. find odd man out
LISP -Functional language
PROLOG - logic programming
C - imperative
ans : c- imperative. Iam not sure ask ur brother.
Fourier analysis 4 questions.

===============================

How macros are called
a. Call by name
b. Call by refernce
c. Call by value
ans : call by name.

2. fun( int x, int y){
x =3;
y =2;
}
main(){
int i;
fun( i,i);
printf("%d",i);
}

if the value is 2 then the calling mechanism
a. Call by name
b. Call by refernce
c. Call by value
ans : call by reference

3. fun(int i){
static int j =0;
x = x+j; j++
return ;
}
main(){
int x = 2;
I had not remembered the question exactly. but the essence is J will retain the value between successive function calls.

4.
cout <<>
Syntax error.

5.
main(){
int z=10,x=6,y=7;
( z ? x:y) =8;
}
ans : the statement does nothing. all values are same.

6. "This is a sting.."
It is string in a function. Where it will be stored.
a. stack
b.global heap
c. Data ro text segment.
d. none
c. Data or Text segment

7. One question i doent remember that Double pointer is given
for that my answer is : Segmentation error

8.fun( int x, int y){
int temp;
temp =x;
x =y;
y = temp;
}

main(){
int i =3,j =4;
fun(i,j);
printf("%d,%d",i,j);
}
ans : 3 4 (that means the values doesnot change)

}
}

) C test -10 questions- Some questions were as follows

I remember only a few.

a) What is the parameter passing mechanism to Macros Called?

b) void func(int x,int y)
{
x=3;
y=2;
}
main()
{
int i;
func(i,i);
print(i);
}

If the output must be 2 what is the parameter passing mechanism called?

c) which of the following code will swap the two numbers? -3 choices was given
d) which of the following is illegal for the program?
main()
{
char const *p='p';
}
1)p++ 2) *p++ 3)(*p)++ 4) all
e) what is the output of the following program
void print(int ** arr)
{
print("0 %f, 1 %f, 2 %f ",arr[0][0],arr[0][1],arr[0][2]);
}
main()
{
int a[][]={ {1,2,3},
{4,5,6}
}
int ** arr=a;
print(arr);
arr++;
print(arr);
}

f) which of the following code swapps the two,numbers.
- 4 choices were given

g) if the string " this is a " is present in the code of a function such as 'void func(void)' where
will the variable stored in the memory.
a) in the stack b) heap c) code or text segment as per implementation d) created when
func is called, stored in function stack space and destroyed as it goes out .

PAPER 2

1.
What is the output of the Program?

main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int *p=a;
int *q=&a[9];
printf("%d",q-p+1);
}
Ans: 10
2.
main()
{
int i=6;
int *p=&i;
free(p);
printf("%d",i);
}
Options:
a. No Error.
b. Free can't be used for p,
c. Compiler Error.
d. In printf we should use *p instead of i.

Ans: A
3.
What is the output of the Program?

main()
{
int i=5;
i=!i>3;
printf("%d",i);
}
Ans: 0

4.
What is the output of the Program?

main()
{
int a[10];
3[a]=10;
printf("%d",*(a+3));
}
Ans: 10
5.
int (*p[10]) ();

In above declaration what type of variable is P?
Ans: P is array of pointers that each points to
a function that takes no arguments and returns
an int.
6.
What is the output of the Program?
struct emp
{
int a=25;
char b[20]="tgk";
};
main
{
emp e;
e.a=2;
strcpy(e.b,"tellapalli");
printf("%d %s",e.a,e.b);
}
Ans: Compile Error.
7.
What is the output of the Program?
main()
{
int a=5;
const int *p=&a;
*p=200;
printf("%d",*p);
}

Ans: Compile Error.
8.
What is the output of the Program?
#define SQ(x) x*x
main()
{
int a=SQ(2+1);
printf("%d",a);
}

Ans: 5.
9.
What is the output of the Program?

main()
{
struct t
{
int i;
} a,*p=&a;
p->i=10;
printf("%d",(*p).i);
}

Ans: 10
10.
This program will be Compiled? [Yes/No]
zzz.c file
----------
/* This is zzz.c file*/
/*printf("tellapalli");*/
abc.c file
----------
main()
{
#include"zzz.c"
printf("Tellapalli");
}
Ans: Yes

CSEA01 Test

I haven't remembered the Qs.I has forgotten Qs.
They has given 5Q in OS,3Q in DM,2Q in ATFL,1Q in DLD,
1Q in CO,1Q in MP 1Q in DS,1Q in CN.

While(Fresher)
printf("ALL THE BEST");

SASKEN paper on 20th september(shreds,kochi)

C questions

1.Consider the following declaration:-
char const *p = 'd';
Which of the following is not a permissible operation
(a) *p++
(b) ++p
(c) (*p)++
(d) All
2.What is the output of the following code:-
void print_arr(float **p)
{
printf(" 0 %f 1 %f 2 %f\n",p[0][0],p[0][1],p[0][2]);
}
void main()
{
float arr[2][3] = {{0,1,2},{3,4,5}};
float **fl_arr;
fl_arr = (float *)arr;
print_arr(fl_arr);
fl_arr++;
print_arr(fl_arr);
}
(a)
(d)segmentation fault
3.What is the output of the following code:-
#define putchar (c) printf("%c",c)
void main()
{
char s='c';
putchar (s);
}
(a) c
(b) 99
(c) Compilation error
(d) Execution error
4.What is the output of the following code:-
void main()
{
printf("%d",printf("ABC\\"));
}
(a) ABC\\
(b) 1
(c) ABC\4
(d) ABC\3
5.What is the output of the following code:-
int compute(int n)
{
if(n>0)
{
n=compute(n-3)+compute(n-1);
return(n);
}
return(1);
}
void main()
{
printf("%d",compute(5));
}
(a) 6
(b) 9
(c) 12
(d) 13
6.What is the output of the following code:-
void main()
{
int i;
for(i=0;i<3;i++)>
{
int i=100;
i--;
printf("%d..",i);
}
}
(a0..1..2..
(b)99..98..97..
(c)100..100..100..
(d)99..99..99..
7.What is the output of the following code:-
void main()
{
int a[]={9,4,1,7,5};
int *p;
p=&a[3];
printf("%d",p[-1]);
}
(a)6
(b)1
(c)7
(d)Error

8.What is the output of the following code:-
void main()
{
int a[]={10,20,30,40,50};
int *p;
p= (int*)((char *)a + sizeof(int));
printf("%d",*p);
}
(a)10
(b)20
(c)30
(d)40
9.Which code will run faster
for(i=0;i<100;i++)>
for(j=0;j<10;j++)>
a[i][j]=0;
OR
for(j=0;j<10;j++)>
for(i=0;i<100;i++)>
a[i][j]=0;
(a)First code
(b)Second code
(c)Same
(d)Compiler and hardware dependent
Answers(Only those which are sure)
1.(c)
3.(c)
4.(c)
5.(b)
6.(d)
7.(b)
8.(b)
Aptitude
1.How many 2 digit numbers are there which have 8 as
the unit number in it's square.
(a)3
(b)None
(c)2
(d)1
2. B is 8km East of A. C is 6km North of B. D is 12km
East of C. E is 16km North of D.
What is the distance b/w A and E.
(a)20km
(b)22km
(c)18km
(d)30km
3. x+y = z
Then
(a)...
(b)y(c)...
4. 2Then which is the greatest
(a) (x^2)y
(b) 5xy
(c) x(y^2)
(d) 5(x^2)y/12
5. A is taller than B, D is taller than D, D is
shorter than E.Then which of the following is correct.
(a) C is taller than E
(b) A is taller than C
(c) D is shorter than A
(d) B is shorter than C
6.A small passage was given and 4 options which
summarizes it was given.The best was to be chosen.
7.Another passage was given and 4 inference was given
and correct was to be chosen.This one is very easy.
8.Which of the following is a parellogram:-
(a)130,50,130,50(angle in deg)
(b)120,30,130,20
(c)90,90,90,90
(d)a & c
9. In the following series (an - 1)^2, 1 is the first
term.Which are the next three
(a)1,3,4
(b)0,3,6
(c)0,1,2
(d)0,1,0
Answers

1.(b)
2.(d)
3.(b)
4.(c)
5.(c)
8.(d)
9.(d)
Computer science

1.Deadlock occur when
(a)Some resources are held up by some process.
(b)...
(c)...
(d)None of these
2. A prefix __expression can be equal to a postfix
__expression reversed only if
(a)It is left associative
(b)It is commutative
(c)It is right associative
3.How many lines will be printed in the following
Pascal pgm
[I don't remember the Pascal version,so I am giving C
version]
void print(int n)
{
if(n>0)
{
print(n-1);
printf("%d",n);//println(n) in Pascal version.
print(n-1);
}
}
(a)3
(b)7
(c)15
(d)31
4.Maximum number of nodes in a tree with n levels.
(a)2^(n-1)
(b)(2^n)-1
(c)2^(n-1) - 1
5.Complete graphwith n nodes have
(a)n-1 edges
(b)n(n-1)/2

6.If d is the degree of a node in a graph and n is
number of vertices then number of edges in that graph
is
(a)Edi^n
(b)0.25Edi
(c)0.5Edi
7.A grammar was given and 4 strings was given and the
one which was not possible was to be chosen.
8.A problem related to ethernet in which a station
sending a frame is of p probablity.There are m
stations to send pckts.4 option was given.It was a
mathematical kind of question related to probablity.
9.Which of the following layer in the OSI model does
error handling
(a)Data link
(b)Network
(c)Transport
(d) a & c
10.A network problem in which Data rate,Propagation
delay,and distance was given and it was to find how
many packets will be in the line.
Choices where
(a)5000
(b)Not possible to find with given data
(c)1000
Answers(Not very sure about all the answers)

1.(d)
2.(b)
3.(c)
4.(b)
6.(c)
9.(d)
10.(a)
Interview [For CS students]

There is Tech as well as HR interview. Tech interview
is the important one.
Tech interview questions

They will ask about the project.They will ask general
questions about it and most probably will not go into
the implementation part of it.So one must have a
general idea about the project done.
Interview is mainly based on Data Structures.Some
questions are as follows:-
- What is a tree,its application,order for
insertion,deletion and traversal with worst case
analysis.
- What is a graph,its application.
- Height of a tree
- Balanced tree and how to balance a tree
- Minimum Spanning Tree
- Dijikstra's, Prim algorithms
- Define a structure for a linked list.
- Binary search and its analysis
- Heap sort and its analysis
- What is a heap and its application
- Cache and its working
- Memory(IO mapped)
- Recursive fns and types, its adv and disadv.
- Compiler(grammar)
*****C debugging questions like
(1)What is the problem with the following code
int * f(int a)
{
int i;
i=a;
return(&i);
}
Ans-> We can't return address of auto variable as it
is allocation is made in stack which is deallocated
when the function returns.
(2)
a.h b.c c.c d.c
int i=0 #include"a.h" #include"a.h" extern int
i;void main{.....}
| | |
b.o c.o d.o
Compilation Phase
Linked to get exe.
Will there be any problem in any phase.If yes then
where and what?
In linking phase as there will be multiple declaration
of i.
*****You will be told to write some code like
(1)To find string length by using recursive function.
(2)To find fibonaci series by using recursive
function.
(3)To write code for malloc so that allocation may be
made fastly.
(4)Write a fn prototype which return a pointer which
points to an array of 10 ints.
HR Interview
------------
- Introduce yourself
- Why should we take you
- What you know about Sasken and etc.

Adobe interview questions

2007-08-06T19:17:00.000-07:00

-write an O(log2(N)) algorithm to find X^N
-rotate an array using reverse fn....
-height of a tree,
-finding second largest number in an array
-questions using finite automata
- write a pgm to find whether a m/c is little endian or big endian
- print a number in hexadecimal format without using sprintf
- optimise the computations in the recursive "nth fibonacci number" algo without using iteration(fairly simple)
"Instead of using return(fib(n-2)+fib(n-1)), use init lofib=0,hifib=1, start with n=2,lofib=hifib;hifib=fib;fib=lofib+hifib"
-given any number say 12, find the next multiple of 8 eg 16 using bit-wise manipulations.
-exchange the integers in a matrix across the secondary diagonal(or non-major diagonal)

deshaw

2007-07-19T20:04:00.000-07:00

PROGRAMMING

1. To display the contents of a executable file the following
command can be used
(a) cat (b) od (c) vi (d) ed ans : b

2. Assume the current directory contains 10 files and does'nt
contain 'temp'. What will be the output of the follwing
commands?
$ls > temp
$wc -l temp
(a) 9 (b) 10 (c) 11 (d) undefined. ans : b *c

3. If one wants the output of one command( command1) to be
printed inthe printer as well as to be added to another file
(outfile) which one of the following is a currect command
he can give?
(a) $command1 >>outfile|tee lpr
(b) $tee -a command1 | lpr
(c) $ command1 | tee outfile | lpr
(d) $ command | tee -a outfile |lpr ans : d
(4) In the shell program set -x will cause
A. Execution of the commands in the background
B. Execution of the commands in verbose mode
C. Exit from the shell program.
D. Exit from the shell program after executing the next command
ans:b

(5) ACL in UNIX refers to
A. Acces Control List
B. Action Control List
C. Application Command Language
D. Advanced C lanuage
ans a:

(6) The command echo*
A. will print * on the screen
B. will print contents of all the files in the current
directory
C. will list the files in the current directory
D. will print the contents of all shell variables
ans c:

(7) ls || date will
A. print the name of the files in the current directory
B. print today's date and time
C. (A) followed by (B)
D. none of the above
ans : a

(8) The built-in shell variable $$ refers to
A. printing numbers in dollar format
B. proces id_ of last command
C. proces id_ of last background command issued
D. proces-id of current shell
ans :d

(9) dd is mainly used for
A. dealing with raw, unformated data, whatever the source
B. dealing with data dictionary
C. deleting a directory
D. none of the above
ans :d

(10) vis in UNIX is
A. a command that takes only one input
B. a command for deleting strange or unwanted charectors that
may have crept into files.
C. points non-printable characters in understandable format
D. all of the above

(11) Which of the following is true regarding the UNIX
(i) Multiuser Operating System
(ii)Multitasking Operating System
(iii) Real timing Operating System
A. i only B. i and ii only C. i and ii and iii only
D. i and ii
ans : a

(12) ln command is used to
A. link object codes into a executable code
B. give two names to the same file
C. set line numbers for the file
D. none of the above
ans : b

(13) nohup command is used for
A. protecting the execution of programmes from aborting when
hangup signal is received
B. changing the execution priority of the programes
C. not hanging up of the modem
D. disconnecting a node from the system
ans : a

(14) SCCS is a
A. Tool for maintaining large programmes in a production
environment
B. Communication Protocol
C. Shell Programming Language
D. String processing utility
ans : a

(15) Which one of the following is true as long as UNIX is
concerned
A. One can do programming in C only
B. It can support terminals capable of printing only uppercase
characters
C. The text files are sorted as it is in MS-DOS
D. None of the above
ans: d

(16) Inside vi editor to replace the string 10/$$/92 with
10/$$/92 globally the following command can be used
A. :1,$ s/\/10\/\$\/94/10\/\$\$\/92/g
B. :1,$ s/\/10\/\$\/94/10\/\$\/$92/
C. :s10/$$/92/10/$$/92/g
D. :1,$ s/\/10\/$\/94/10\/$$\/92/g
**** ans : d

(17) The ed command without any argument
A. will print the current working directory
B. will make the home directory as current directory
C. will ask for the directory to be used as the current
directory
D. will go to the previous directory

(18) nice command is used
A. to increase/decrease execution priority of a command
B. to compress a file
C. to run a programme at latter time
D. to set the key board responce slower
ans : a

(19) What will be the output of the following command sequence
$ x='I am x'
$sh
$echo $x
A. I am x B. Blank line C. x D. None of the above
ans :b

(20) The command tr a-z 0-9 < x
A. converts all the digits to lowercase alphabets
B. converts all the lowercase alphabets to digits
C. will give syntax error
D. none of the above
ans :d

Deshaw

2007-07-19T20:00:00.000-07:00

APTITUDE PART

(1)A man bought two horses for Rs.924 each and sold one horse for
15% profit and the other for 15% loss.What is the net gain?

(2) Two pumps fill atank in 20 hrs. One pump fills the same
tank 10hrs. faster than the other pump. In what time the
other pump fills the tank?

(3) X men in Xhrs/day finish a work in x days. Y men in y hours
per day finish the work in
(a) X**2/Y**2 (b)X**3/Y**2 (c) Y**2/X**2 (d) Y**3/X**2

(4)8 men + 2 boys finish a work in 16 days.
2 men + 5 boys finish a work in 20 days. 8 men and 8 boys
finish the same work in how many days?

(5)A & B are two trains, travell from X & Y stations to Y & X
stations after crossing each other A takes 4 hrs.48 mins. to
reach Y station. B takes 3hrs.20 mins. to reach X station.
The speed A is 45kmph. Speed of B is ?

DESHAW

2007-07-19T19:53:00.000-07:00

Write the programs for the following problems in C.

1. Swap two variables x,y without using a temporary variable.

2. Write algorithm for finding the GCD of a number.

3.Write a program for reversing the given string.

4. The integers from 1 to n are stored in an array in a random
fashion. but one integer is missing. Write a program to find the
missing integer.

Ans): Hint : The sum of n natural numbers is = n(n+1)/2.
if we subtract the above sum from the sum of all the
numbers in the array , the result is nothing but the
missing number.

5. Some bit type of questions has been given on pointers asking to
to find whether it is correct from syntax point of view. and if
it is correct explain what it will do. (around 15 bits).

6. For the following C program

#define AND &&
#define ARRANGE (a>25 AND a<50)
main()
{int a = 30;
if (ARRANGE)
printf("within range");
else
printf("out of range");
}

What is the output?

7. For the following C program

#define AREA(x)(3.14*x*x)
main()
{float r1=6.25,r2=2.5,a;
a=AREA(r1);
printf("\n Area of the circle is %f", a);
a=AREA(r2);
printf("\n Area of the circle is %f", a);
}

What is the output?

Ans. Area of the circle is 122.656250
Area of the circle is 19.625000

8. What do the following statements indicate. Explain.

int(*p)[10]

int*f()

int(*pf)()

int*p[10]

Refer to:
-- Kernighan & Ritchie page no. 122
-- Schaum series page no. 323

9. Write a C program to find whether a stack is progressing in forward
or reverse direction.

10. Write a C program that reverses the linked list.

Thinkers

2007-07-19T00:56:00.001-07:00

How are M&Ms made?
If you had a clock with lots of moving mechanical parts, you took it apart piece by piece without keeping track of the method of how it was disassembled, then you put it back together and discovered that 3 important parts were not included; how would you go about reassembling the clock?
If you had to learn a new computer language, how would you go about doing it?
You have been assigned to design Bill Gates bathroom. Naturally, cost is not a consideration. You may not speak to Bill.
What was the hardest question asked of you so far today?
If MS told you we were willing to invest $5 million in a start up of your choice, what business would you start? Why?
If you could gather all of the computer manufacturers in the world together into one room and then tell them one thing that they would be compelled to do, what would it be?
Explain a scenario for testing a salt shaker.
If you are going to receive an award in 5 years, what is it for and who is the audience?
How would you explain how to use Microsoft Excel to your grandma?
Why is it that when you turn on the hot water in any hotel, for example, the hot water comes pouring out almost instantaneously?
Why do you want to work at Microsoft?
Suppose you go home, enter your house/apartment, hit the light switch, and nothing happens - no light floods the room. What exactly, in order, are the steps you would take in determining what the problem was?
Interviewer hands you a black pen and says nothing but "This pen is red."

Applications

2007-07-19T00:55:00.001-07:00

How can computer technology be integrated in an elevator system for a hundred story office building? How do you optimize for availability? How would variation of traffic over a typical work week or floor or time of day affect this?
How would you implement copy-protection on a control which can be embedded in a document and duplicated readily via the Internet?
Define a user interface for indenting selected text in a Word document. Consider selections ranging from a single sentence up through selections of several pages. Consider selections not currently visible or only partially visible. What are the states of the new UI controls? How will the user know what the controls are for and when to use them?
How would you redesign an ATM?
Suppose we wanted to run a microwave oven from the computer. What kind of software would you write to do this?
What is the difference between an Ethernet Address and an IP address?
How would you design a coffee-machine for an automobile.
If you could add any feature to Microsoft Word, what would it be?
How would you go about building a keyboard for 1-handed users?
How would you build an alarm clock for deaf people?

Algorithms

2007-07-19T00:54:00.001-07:00

What's the difference between a linked list and an array?
Implement a linked list. Why did you pick the method you did?
Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.
Describe advantages and disadvantages of the various stock sorting algorithms.
Implement an algorithm to reverse a linked list. Now do it without recursion.
Implement an algorithm to insert a node into a circular linked list without traversing it.
Implement an algorithm to sort an array. Why did you pick the method you did?
Implement an algorithm to do wild card string matching.
Implement strstr() (or some other string library function).
Reverse a string. Optimize for speed. Optimize for space.
Reverse the words in a sentence, i.e. "My name is Chris" becomes "Chris is name My." Optimize for speed. Optimize for space.
Find a substring. Optimize for speed. Optimize for space.
Compare two strings using O(n) time with constant space.
Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
Count the number of set bits in a number. Now optimize for speed. Now optimize for size.
Multiple by 8 without using multiplication or addition. Now do the same with 7.
Add numbers in base n (not any of the popular ones like 10, 16, 8 or 2 -- I hear that Charles Simonyi, the inventor of Hungarian Notation, favors -2 when asking this question).
Write routines to read and write a bounded buffer.
Write routines to manage a heap using an existing array.
Implement an algorithm to take an array and return one with only unique elements in it.
Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Now speed it up. Now test it.
Implement an algorithm to print out all files below a given root node.
Given that you are receiving samples from an instrument at a constant rate, and you have constant storage space, how would you design a storage algorithm that would allow me to get a representative readout of data, no matter when I looked at it? In other words, representative of the behavior of the system to date.
How would you find a cycle in a linked list?
Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
The following asm block performs a common math function, what is it?
```
cwd xor ax, dx
sub ax, dx
```
Imagine this scenario:
I/O completion ports are communictaions ports which take handles to files, sockets, or any other I/O. When a Read or Write is submitted to them, they cache the data (if necessary), and attempt to take the request to completion. Upon error or completion, they call a user-supplied function to let the users application know that that particular request has completed. They work asynchronously, and can process an unlimited number of simultaneous requests.
Design the implementation and thread models for I/O completion ports. Remember to take into account multi-processor machines.
Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.
Write a function to print all of the permutations of a string.
Implement malloc.
Write a function to print the Fibonacci numbers.
Write a function to copy two strings, A and B. The last few bytes of string A overlap the first few bytes of string B.
How would you write qsort?
How would you print out the data in a binary tree, level by level, starting at the top?

Riddles

2007-07-19T00:52:00.000-07:00

Why is a manhole cover round?
How many cars are there in the USA? (A popular variant is "How many gas stations are there in the USA?")
How many manhole covers are there in the USA?
You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?
One train leaves Los Angeles at 15mph heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?
Imagine an analog clock set to 12 o'clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?
You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of a red marble being picked? What are the exact odds of getting a red marble using your scheme?
Pairs of primes separated by a single number are called prime pairs. Examples are 17 and 19. Prove that the number between a prime pair is always divisible by 6 (assuming both numbers in the pair are greater than 6). Now prove that there are no 'prime triples.'
There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.
Suppose you had 8 billiard balls, and one of them was slightly heavier, but the only way to tell was by putting it on a scale against another. What's the fewest number of times you'd have to use the scale to find the heavier ball?
Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?
You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?
The SF Chronicle has a word game where all the letters are scrambled up and you have to figure out what the word is. Imagine that a scrambled word is 5 characters long:

How many possible solutions are there?
What if we know which 5 letters are being used?
Develop an algorithm to solve the word.

There are 4 women who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. What is the order required to get all women across in 17 minutes? Now, what's the other way?
If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?
If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.

Google,Microsoft interview questions collection

2007-07-12T22:41:00.000-07:00

1).You have to get from point A to point B. You don’t know if you can get there. What would you do?

2).Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

3).What method would you use to look up a word in a dictionary?

4).Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announce that at least one husband has been unfaithful. What happens?

5).You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?

6).How do you cut a rectangular cake into two equal pieces when someone has already taken a rectangular piece from it? The removed piece an be any size or at any place in the cake. You are only allowed one straight cut.

Google,Microsoft interview questions collection

2007-07-12T22:38:00.000-07:00

1)Explain the significance of "dead beef".

2) Write a C program which measures the the speed of a context switch on a UNIX/Linux system.

3) Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

4) Describe the algorithm for a depth-first graph traversal.

5) Design a class library for writing card games.

6) You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

7) How are cookies passed in the HTTP protocol?

8) What is the size of the C structure below on a 32-bit system? On a 64-bit?

struct foo {
     char a;
     char* b;
};

8) Design the SQL database tables for a car rental database.

9) Write a regular expression which matches a email address.

10)Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

11) You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

12) Explain how congestion control works in the TCP protocol.

Google interview questions

2007-07-12T22:34:00.000-07:00

1) ."You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?"

2)."How would you find out if a machine's stack grows up or down in memory?"

3)."Explain a database in three sentences to your eight-year-old nephew."

4).How many gas stations would you say there are in the United States?"

Swap 2 variables without using a third variable

2007-07-09T02:22:00.000-07:00

Here goes my solution:


int a = 5;
int b = 8;

a = b - a;
b = b - a;
a = a + b;

printf("After swapping ...a= %d and b= %d ",a,b);

Remove Duplicates from a list in PERL

2007-07-08T06:52:00.000-07:00

There is one simple and elegant solution for removing duplicates from a list in PERL


           @array = (2,4,3,3,4,6,2);
            my %seen = ();
            my @unique = grep { ! $seen{ $_ }++ } @array;
            print "@unique";

And here goes a bit more detailed solution


            @array = (2,4,3,3,4,6,2);
            my @unique = ();
            my %seen   = ();

             foreach my $elem ( @array )
             {
                    next if $seen{ $elem }++;
                    #print "\n".$elem." ".$seen{ $elem }++;;
                    push @unique, $elem;
              }
              print "@unique";

"$seen{ $elem }++" - This expression returns 1, if the element that is being pushed in to the hash table is already seen. You go through each element and skip the ones you've seen before. We use a hash %seen to keep track. The first time the loop sees an element, that element has no key in %Seen . The next statement creates the key and immediately uses its value, which is undef, so the loop continues to the push and increments the value for that key. The next time the loop sees that same element, its key exists in the hash and the value for that key is true (since it's not 0 or undef), so the "next statement" skips that iteration and the loop goes to the next element.

Find all the pairs in an array .... that sum up to particular number.

2007-07-08T05:11:00.000-07:00

Here goes my version .... implemented in Java. This program runs only on java 1.5


import java.util.*;
class findPairs
{
    public static void main(String[] args)
    {
        int a[] = new int[10];
        int index = 0;
        /* Java 1.5 specific code .... replace this with a simple array if you don't want to take input from console */
        Scanner sc =  new Scanner(System.in);
        String str = null;
        System.out.println("Enter array input");
        while(!(str=sc.next()).equals("quit")) {
            a[index] = Integer.parseInt(str);   
            index++;
        }
        sc =  new Scanner(System.in);
        System.out.println("Enter the number");
        int findNumber = Integer.parseInt(sc.next());

        int start = 0;
        int end = index-1;
        while(start <= end) {
            //System.out.println("Now  "+a[start]+" "+a[end]+"findNumber= "+findNumber);
            if(a[start]+a[end] < findNumber)
                start++;
            else if(a[start]+a[end] > findNumber)
                end--;
            else if(a[start]+a[end] == findNumber) {
            System.out.println("\npair is "+a[start]+" "+a[end]);
                end--;
                start++;
           
            }
        }
    }
}

This can also be implemented using a simple hash table like data structure. But certainly has lot of limitations.

Are you an aspiring "Googler"!!!

2007-07-07T23:11:00.000-07:00

Are you an aspiring Googler? Want to join Microsoft, Yahoo or Amazon soon after completing your graduation? Are you an experienced developer looking for a change?

Know Java, C/C++? Know Binary Trees and Are you good at solving puzzles? Have an aptitude for solving tough problems in Computer Science?

The Best way to conquer any thing is "Know Your Enemy(or friend? :) )" -

Do you see Google Jobs ad at the top of this page ..... go to their jobs web site ..... read the job profile .... know what they are looking for a specific position and gear up your preparation!!!

Its the same for any company, you are interested in!!!

Focus!!! Focus!!! Don't get deviated!!!

I wish you "Good Luck"!!

Remove a file named "-f"

2007-07-07T21:14:00.000-07:00

Already started thinking about the solution!!! Wait ......... Wait ........

First of all, Can you create a file named "-f" on a Unix Based System? Think about it!!!

You cannot create it with "vi" Command... Know the reason ???? "-f" is a flag in Unix Based Systems for commands like "vi" and "rm". So you can create a file with another name and rename it to "-f" .....

Now ..... How do you remove this file ???? Do you know that ........ "-f" is flag for "rm" command which forces the removal of a file or folder supplied to the "rm" command as argument ......

So you can't do something like this .....


          rm -f

So what's the solution ....... Have you ever heard about "Absolute and Relative Paths"???

Absolute Path: A path relative to the root directory. Its first character must be the pathname seperator like "/".


Example:    /home/praveen/practice/

Relative Path: A path relative to the working directory. Its first character can be anything but the pathname separator.


Example:  questions/myprogram.java

So .... got it?

HeHe ....

OK ...... Answer is:

say your file with name "-f" is in /home/praveen/practice and your current directory is also the same.

rm /home/praveen/practice/-f

or

rm ../-f

Got it? Comments?

Know Answer to "The Question" already????

2007-07-07T20:47:00.000-07:00

Know answer to the question your interviewer is asking?? Don't start shouting the answer even before your interviewer finishes with the question!!!

Here goes a list of few tips I know!!!

1. Listen to the question intently (you may want to smile ....... don't that!!)

2. Look a bit tensed(repeat with me .... "A BIT" not more than that nor less than that!!!)

3. Think think think ...... (at least try to pretend yaarr!!! )

4. Ask questions ....... (You can ask more questions ..... if you know the answer already!!! HeHeHe ...)

5. Then ...... do a bit of :ghoting (you know that eh??? hehehe ...)

6. Then slowly read out your solution ........

I wish you "ALL" -----"Good Luck!!!"

Do you have some more tips to add ..... you are most welcome Buddy!!!

Have to write code during the interview????

2007-07-07T20:27:00.000-07:00

Here goes one of the mistakes my friend made in the 2nd round of his interview ......

Can you write a program for finding nth Fibonacci number? Am I kidding? Off course you can!!! I know that!!! But the gotcha here is this ......

If you are an experienced person, preparing for interviews .... you are mostly likely be asked to write code (repeat with me 'WRITE CODE' not pseudo code or algorithm!). Don't forget to write the exact running version and read out to the interviewer. Don't forget to read out the semicolons at the end of every statement. Because, as you read out the code, your interviewer is typing the code and will execute it after you finishing to read out!! Seems at the max you are allowed to make just 2 mistakes. Also, in a hurry to finish it off fast, don't use more variables than required!!!

Here goes my version of recursive and non recursive versions of finding the Nth fibonacci number!!
(The code is written in Java)


class Fibonacci
{
    public static void main(String[] args)
    {
        int num = 5;
        System.out.println("Answer from recursive version"+fibRecursive(num));
        System.out.println("Answer from non recursive version"+fibNonRecursive(num));
    }

    public static int fibNonRecursive(int number) {
        int sum = 0;
        if(number == 0)
            return 0;
        else if(number == 1)
            return 1;
        else {
            int a = 0; // fib value when number is 0
            int b = 1; // fib value when number is 1
            int count = 0;
            while(count < number-1) {
                sum = a + b;
                a = b;
                b = sum;
                count = count + 1;
            }
        }
        return sum;
    }

    public static int fibRecursive(int number) {
       
        if(number == 0)
            return 0;
        else if(number == 1)
            return 1;
        return fibRecursive(number-1)+fibRecursive(number-2);
    }
}

Can you minimize the number of variables I am using in the non recursive version? Your comments are welcome!!

PHP Interview questions from YAHOO

2007-07-07T04:51:00.000-07:00

1. What is the difference between foo() & @foo()?

2. How do you debug a PHP application?

3. What does === do? What’s an example of something that will give true for ‘==’, but not ‘===’?

4. How would you declare a class named “myclass” with no methods or properties?

5. How would you create an object, which is an instance of “myclass”?

PHP Interview questions from YAHOO

2007-07-07T04:50:00.000-07:00

1. Which of the following will not add john to the users array?


$users[] = ‘john’;
array_add($users,’john’);
array_push($users,‘john’);
$users ||= ‘john’;

2. What’s the difference between sort(), assort() and ksort? Under what circumstances would you use each of these?

3. What would the following code print to the browser? Why?


$num = 10;
function multiply(){
   $num = $num * 10;
}
multiply();
echo $num;

4. What is the difference between a reference and a regular variable? How do you pass by reference & why would you want to? 5. What functions can you use to add library code to the currently running script?

Yahoo interview question

2007-07-07T04:29:00.000-07:00

1) What is the basic difference you find between a shell script and perl?

2)what is mutation testing?

Amazon interview questions

2007-07-06T01:33:00.000-07:00

1)How would you find the nth to last element in a linked list?

2) Explain algorithm to shuffle cards

3)Coding: Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function?

4)You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers?

5) How would you detect a repeated element in an integer array.

6) Write a function to smooth out stock fluctuations.

7) Given two sets, Write a function to provide the union of them.

8) Design an algorithm to calculate the most user viewed pages

9) Design an algorithm to find duplicates in an array.

10) Design an algorithm and write code to serialize a binary tree.

11) Design an algorithm and write code to find two numbers in an array whose sum equals a given value

12) count bits in an integer.

13)Given two binary trees, find whether or not they are similar.

14)assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability.

15)You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level.

Google,Microsoft interview questions phase-3

2007-07-06T01:13:00.000-07:00

1) Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.

2)You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.

3)Design a web server that serves the Google homepage.

What are the requirements.
Design a multi threaded web server that uses shared memory instead of disk access.
Design a work load balancer for their data centers.
Design a DNS server that returns the IP address of a data center that has the best connectivity relative to your IP.

Google,Microsoft interview questions phase-2

2007-07-06T00:52:00.000-07:00

1)What is the best and worst time for the operation 'equals'
How do you spedup the 'equals' operation
Write a function (and dictate it to your interviewer) that reverse the order of words in a sentence. The final algorithm should work in-place!! E.g.: "This is a sample" --> "sample a is This"

2)Trade offs between a multi threaded and single threaded implementation ?
N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?

3)There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers.

4)Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort,Shell,Radix,Heap

If you had a million integers how would you sort them and how much memeory would that consume?

5)Describe an alogrithm to find out if an integer is a square?

6)How would you determine if adwords was up and running and serving contextual content ?

7)Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.

8)Implement division (without using the divide operator, obviously).

9)You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.

Google,Microsoft interview questions phase-1

2007-07-06T00:47:00.000-07:00

1)Write an algorithm for Soduku puzzle

2)What method would you use to look up a name in a dictionary?

3)How would you find out if a machine's stack grows up or down in memory?

4)Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

5) Describe the algorithm for a depth-first graph traversal.

6)Design a class library for writing card games.

7)You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

8)You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

9)Given a number, describe an algorithm to find the next number which is prime.

10)what is the best and worst performance time for a hash tree and binary search tree?

MaximumSumSubsequence Problem - implemented in Java

2007-07-05T03:11:00.000-07:00

My Solution:


class MaxSubSequence
{
 public static void main(String args[]) {
  MaxSubSequence mss = new MaxSubSequence();
  System.out.println("\n\nMax Value is "+mss.maxsubsequence(new int[]{-1,-2,-3,-4,-5,1}));
 }
 
 int maxsubsequence(int intArr[])
 {
      int  beginIndex    = 0;
   int  endIndex      = 0;
   int  curValue      = intArr[0];
   int  maxValue      = curValue;
   int  maxBeginIndex = 0;
   int  maxEndIndex   = 0;
   int number = intArr.length;

   for (int i = 1; i < number; i++)
   {
    curValue += intArr[i];
    
    if (curValue > maxValue)
    {
     maxValue = curValue;
     endIndex = i;

     maxBeginIndex = beginIndex;
     maxEndIndex   = endIndex;
    }

    if (curValue <= 0)
    {
     beginIndex = i+1;
     endIndex   = i+1;
     curValue   = 0;
    }
   }
   
   System.out.print(" \n\n ");
   for(int i=maxBeginIndex;i < maxEndIndex+1;i++)
    System.out.print(intArr[i]+" ");
  return maxValue;
 }
};

Imagine coming up with this solution on phone ... A lady called him at 10.30 PM in the night from Google's US office. So prepare well. :-) I wish you all "All The Best".

Find if a number is a "Power Of 2"

2007-07-05T00:39:00.000-07:00

Just one line of code does everything :)


import java.util.*;
class PowerOf2 
{
 public static void main(String[] args) 
 {
  int num = 5;
  System.out.println("Is this number power of 2? "+((num!=0)&&(num & (num-1))==0));
 }
}

Any comments?

Atoi - implemented in Java

2007-07-05T00:06:00.000-07:00

My Solution:


class Atoi 
{
 public static void main(String[] args) 
 {
  //System.out.println("Change the value of str to see program's behavior for various inputs");
  String str = "123.25";
  boolean isValid = true;
  boolean isFloat = false;
  char ch[] = str.toCharArray();
  int sum=0;
  double fraction=0;
  int count = str.substring(0,str.indexOf('.')).length();
  int fracCount = 1;
  for (int i=0;i  {
   if(ch[i] == 46)
   {
    isFloat = true;
    continue;
   } 
   
   if(isFloat) {
    if(isNum(ch[i])) {
     fraction+= (ch[i]-48)*(1/(Math.pow(10,fracCount++)));
    } else {
     System.out.println("Sorry .... not a valid number");
     isValid=false;
     break;
    }
    continue;
   }
   else {   
    if(isNum(ch[i])) {
     sum+= (ch[i]-48)*Math.pow(10,--count);
    } else {
     System.out.println("Sorry .... not a valid number");
     isValid=false;
     break;
    }
   }
  }//end of for loop
  if(isValid)
  System.out.println("Value is"+(sum+fraction));
 }//end of main

 public static boolean isNum(char ch) {
  if(ch>=48 && ch<=57)
   return true;
  else 
   return false;
 }
}

Any comments?

A small Java program for "Array Rotation"

2007-07-04T23:56:00.000-07:00

My Solution:


class ArrayRotate 
{
 public static void main(String[] args) 
 {
  int a[] = {1,2,3,4,5};
  int count=0,k=0,j=0;
  for(int i=0;i<5;i++) {
   
   int first = a[0];
   k=0;
   j=0;
   System.out.println("\n");
   
   while(k < a.length) {
    j++;
    if(j >= a.length) {
     a[k] = first;
     System.out.print(a[k]+" ");
    } else {
     a[k] = a[j];
     System.out.print(a[k]+" ");
    }
    
    k++; 
   }//end of While

  }//end of for loop
 }//end of function main
}//end of class ArrayRotate

Any Comments?

Solution for the question - "How do you find, if a machine is big endian or little endian?"

2007-07-04T23:36:00.001-07:00

My Solution is this:


#include 
int main()
{

       int i = 1;
       char *p= (char *)&i;
       

       if(*p == 1)
         printf("Little Endian");
       else
         printf("Big Endian");

return 0;
}

Any comments?

Google interview questions

2007-06-30T08:34:00.000-07:00

One of my best friends has undergone Google interview process while I was at home during holidays. Following are his first phone interview questions. He hasn't signed on NDA, so I can share this information with U all.

1. Quick sort average and worst case time complexity

Ans - Avg -- O(nlogn)
Worst -- O(n^2)

2. what is the value of 2^12 = 4 * 1024 = 4096

3. Order the following operations - Fastest Operation - first

a. Read CPU register
b. Disk Seek
c. Context Switch
d. Read from main memory

My Answer is - a,d,c,b
(Correct me, If I am wrong!!!)
4.How will you find your system is Bigendian or small endian?
5.Reverse a singly linked list

Microsoft Interview Questions

2007-06-23T01:44:00.001-07:00

1) * If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

Answers -- Fill 5 quart pile using full 3 quart pile, stop when 5 quart is filled (second time), now you have 1 quart left in the 3 quart pile, empty 5 quart pile and fill it with the remaining 1 quart, and another full 3quart pile makes the 5 quart pile with 4 quart!!!!

2) if you are on a boat and you throw out a suitcase, will the level of water increase?

3) On an average, how many times would you have to open the Seattle phone book to find a specific name?

4) There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner. What is the probability that they don't collide?

5) If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?

Let us Rank

2007-06-22T09:03:00.000-07:00

what is your Dream company ??????????????????????

hii
please quote your dream company as a comment so that we can rank the company present in the hearts of the many people..

Thank you

Question regarding a string Class

2007-06-21T22:07:00.000-07:00

1)What do you need when you instantiate a string

2)What is the best and worst time for the operation 'equals'

3)How do you spedup the 'equals' operation

what is the best and worst performance time for a hash tree and binary search tree?

2007-06-21T22:04:00.000-07:00

what is the best and worst performance time for a hash tree and binary search tree?

Answer: Best is O(c), worst is O(log n)

Order the functions in order of their asymptotic performance

2007-06-10T12:34:00.000-07:00

Order the functions in order of their asymptotic performance

1) 2^n
2) n^Googol ( 10^100)
3) n!
4) n^n

Answer:
1)n^(whatever constant)
2)2^n
3)n! (==> n^n / e^n )
4)n^n

Tips, tricks and questions to crack Microsoft, Yahoo and Google programming interviews

2007-06-10T11:51:00.000-07:00

Hope the information presented here will help you all in cracking Microsoft, Yahoo and Google interviews. The one and only way to crack these interviews is to prepare well and be confident during the interviews. They are stressing very much on Data Structures and Algorithms during interviews. Prepare well and read out the code to them during interviews, they will be happy and you will have a high paying job!!!

I wish you good luck!!!

cheers,
Calvin