Four people crossing the bridge optimally

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 is 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?

Sol:
When two people walk and their speeds are different then the time taken(cost) to cover some distance will be the time taken by slowest of the two.

first take 1, 2 to side2 cost = 2
get 2 back to side1 cost = 2
then take 5,10 to side2 cost = 10
get 1 back to side 1 cost = 1
get 1 and 2 back to side2 cost =2

total cost = 17

100 couples C cheats problem?

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?

Sol:
At the end of Cth day all of the cheats get killed if there are C cheats

Five Pirates gold coins division problem.

You have five pirates, ranked from A to E 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? (Assumption : If the top pirate is voted down and gets killed, then the remaining pirates retain their rankings and continue the game, with Pirate 4 now in charge etc.. 2) top pirate also have the voting right and he will not be killed if there is a tie in number of votes)

Ans: 98 coins with top pirate

This is a game theory problem which involves some reasoning.
Lets start to the solution as if there are only 2 pirates. In this case, the top-ranked pirate (Pirate B) would get 100 gold coins, and Pirate A wouldn't get any, because Pirate A has no way to vote down the plan.

Let's work backwards from there. Clearly, Pirate A doesn't want it to come down to just two people. So consider if there were three pirates. Then, Pirate A would accept even just one coin to avoid letting things get down to two people. Thus, if there were three pirates involved, Pirate C should offer Pirate A a single coin; Pirate A would agree because one coin is better than zero. Pirate B could not overrule this plan.

Lets say there are 4 pirates, Pirate B would accept even just one coin to avoid letting things get down to three pirates; if it got down to three, as we have shown above, Pirate B would get nothing. Thus, Pirate D could offer to keep 99 coins and pay Pirate B a single coin; Pirate A and Pirate C would get nothing, but they don't have enough votes to override the plan.

Coming to actual five pirates case , Pirate A and Pirate C are anxious to avoid letting things get down to four pirates, because then they'd get nothing. So if Pirate E offered Pirate A and Pirate C a single coin each, then they'd vote in favor of the plan, since one coin would be better than nothing.
So Pirate E keeps 98 coins for himself.


Generalized answer is
If there are odd number of pirates then
the number of coins with top pirate = total number of coins - number of odd numbers below the number.
else
the number of coins with top pirate = total number of coins - number of even numbers below the number.

Proff for above formulae can be established by following
In case of 6 pirates: Pirate F would have to offer a coin to Pirates B and D to satisfy everyone's self-interests.
In case of 7 pirates : Pirate G would have to offer a coin to Pirates A, C, and E.

audio resume,answers link?

Useful link with interview answers audios.
http://www.midemo.com/validator_online/rep/gads.php?HashCode=10ac8f04c270fbf0fc6bd1d975172f28&gclid=CLLTt-aikZACFQFeQgodLzEaAA

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?

prob of colliding is
= 1st and 2nd moving towards each other + 2nd and 3rd moving towards each other + 3rd and 1st moving towards each other
= (1/2)* (1/2) + (1/2)* (1/2) + (1/2)* (1/2) = 3/4

probability of not colliding = 1- 3/4 = 1/4

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?

For continuous clock where hours and minutes hands move continuously then the answer is 7.5 Minutes.
3.25* 30 - 15*6 = 7.5

For discrete clock where minutes hand moves after 60 secs and hours hand moves after 12 mins then the answer is 6 minutes.

Ratio of boys and girls.

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:

It doesn't matter how many kids a family has. The odds of having a boy or girl are always the same. So number of boys and girls in the village is same.

Ratio of boys and girls.

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:

50:50.

probability of a boy/girl is always 2 irrespective of the number of conditions.

for the above problem we can prove it with simple probability theory.

Lets assume P(b) be the probability of having a boy. P(g) be the probability of having a girl.

Total expectation of a boy is equal to (probability of having a boy at first instance + probability of having a girl then a boy + probability of having 2 girls followd by a boy + etc... )
E(b) = 1/2 + 1/2*1/2 + 1/2*1/2*1/2 + ......
it comes down to 1 ( infinite series sum = a/1-r = 1/2/1-1/2 = 1).

E(g) = 0 + 1/2 + 1/4 + 1/8....
it comes down to 1.

It means there are equal number of girls and boys in the village.

Number coding

Assume 9 is twice 5; how will you write 6 times 5 in the same system of notation

Solution:

9 is twice 5. So 5 is 4.5.
6 times 5 should be 6*4.5 = 27

Distance between trains

One train runs from A to B at 105 miles per hour; the other runs from B to A at 85 miles per hour. How far apart were the two trains 30 minutes prior to their crossing?

Solution:

Two trains are 95 miles apart 1/2 Hr before they crossed each other

Relative Speed of the trains = 85+105 = 190MPH

One hour before they crossed, they would have been 190 miles apart.

Distance between the trains 1/2 hr before they crossed would be 190/2 = 95miles

Probability of observing a car

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)?

probability of not observing a car in 30 mins = probabality of not observing a car in first 10 mins * not obs in next 10 mins * not obs in last 10 mins

lets assume observing a car in 10 mins = p

probability of not observing the car in 10 mins = 1-p

probability of not observing the car in 30 mins = (1-p)^3

so (1-p)^3 = 0.05

1-p = (0.05)^1/3.
p = 1- (0.05)^1/3.
p = 1- 0.37
p = 0.63.

How to check if the stack grows up or down?

Instantiate a local variable in main function(caller) and instantiate another local variable in callee function. Compare both the addresses. If address of local variable declared in main in less than the address of local variable in function(callee) then the stack is growing towards higher address.
Here is the Program which does this:
int main()
{
int localinmain;
CheckStackGrowth(&localinmain);

}

void CheckStackGrowth(int *localinmain)
{
int localinfunction;
if(localinmain < &localinfunction)
printf("Stack is growing downwards.\n");
else
printf("Stack is growing upwards.\n");


}

Interview With Google.

Recently I have attended telephonic Interview with Google for the post of Sr. S/W Engineer in their internal application team. Someone named XYZ called me from their Mountainview office. It was around 10:30 PM (was already feeling sleepy). He started with asking me something about my previous projects and asked most challenging work i have done so far. Then he asked me about the languages i am comfortable with.
Then he asked whether i have used Microsoft Excel. Then he asked me the logic to convert column headers in excel sheet to numbers. Something like (A->1, B->2.......Z->26, AA->27 ....). Given the column header it should return the number mapping to it.
My answer was to use the number system with base 26. Store the column header in a string and extract each character and do ch-'A'+1(ascii diff) to get the index value corresponding to the number and multiply it with 26 ^(character positon -1) and add it to the result.

He accepted the answer and asked me to write the code for the same. I have written it in C and dictated it to him on phone. He then asked me to calculate the complexity of the same. I gave both the space and time complexity of my algorithm.

Next he asked me the logic to find the Square root of the number without using Square root function.

I gave him the numerical method answer... (Thank god i still remember some of my numerical method classes which i attended 8 years back). My answer was something like below.

double guess = num/2, oldguess = 0;
while(guess != oldguess) {
oldguess = guess;
guess = (num/guess + guess)/2;
}
return guess;

He was happy with my answer and asked me about the possible test cases i will have for it.
I gave him 0,1, negative numbers and numbers out of double range.. etc..............
He said excellent.
During the course of interview he was saying only few words like sounds good, make sense, excellent etc..

He then said he is done from his side and enquired whether i have any questions for him.
After one hour i got a chance to make him talk.... so i don't want to miss this opportunity and asked him about the kind of work they do ? Their work culture? etc... (even though i know answers from them.. :-))

He replied back saying G is a great company and talked about 20% time which we can use for personal projects... blah..blah .. blah...

Next day i got a call from their HR asking for my time for the onsite inerviews.....

Will keep posting my further rounds here.. .. do let me know the feedback..

incrementing void pointer?

Will the following program execute?void main()
{
void *vptr = (void *) malloc(sizeof(void));
vptr++;
}


Output of this program depends on the compiler।
1) If you are using a ANSI C or C++ compiler then you cannot take the sizeof(void) and you cannot increment a void* pointer. So, you will get the follwoing errors.

ANSI C++ forbids taking the sizeof a void type.
ANSI C++ forbids incrementing a pointer of type `void *'

NOTE: Try this with CC compiler under unix

2)If you are using gcc compiler then sizeof(void) will return 1.
so one byte will be allocated and when u try to increment the void* pointer it will be incremented by one byte.

NOTE: output as seen in gdb;
(gdb) p sizeof(void)
$1 = 1
(gdb) p vptr
$5 = (void *) 0x13030
(gdb) n
4 vptr++;
(gdb) p vptr
$6 = (void *) 0x13031

Is the size of an Integer Platform Dependent or Architecture Dependent?

platform dependent means based on operating system architecture.
ie in some of 32 bit OS, the size of int is 2byte and in some of 64 bit OS, the size of int is 4 byte. It also varies based on the compiler used.
Example: in VC++ it is 4byte and in TC++ it is 2 byte

How can I test whether my system’s byte order is big endian or little endian.?

Little endian and Big Endian refer to the layout of byte in which the data is stored.

Big endian : Stores most significant data of information from the base address.
Little Endian : Stores from least significant data from the base address.

let us take an example :

I want to store 14 in an integer on a 32bit machine.

in the binary pattern the number is represented as 1110.
If the same is to be stored in a 32bit alignment.

Big Endian stored it like :

0000-0000 0000-0000 0000-0000 0000-1110

Little Endian stores it like :
0000-1110 0000-0000 0000-0000 0000-0000

So the following program might help you in knowing whether your machine is of Little-Endian or Big Endian Architecture.

void main()
{
int i = 1;
char *c = (char *)&i;

if ( *c == 1 )
{
cout<<" LITTLE ENDIAN";
}
else
{
cout<<" BIG ENDIAN";
}
}

When the processor wakes up after power on, it goes to a particular memory location. What is that memory location called?

When power is switched on , the CPU wakes up and makes chipset(mostly intel bases ones) to look for top 16 bytes of the first MB of the MEMORY where BIOS code is placed in compressed format.

NOTE: Additional info about booting process.

Then CPU decompress the BIOS code and BIOS code will get system settings (remember the BIOS settings we set at boot time in ROM BIOS) from chipset registers.Then BIOS configures the memory and copies BIOS code to RAM (shadowing). Then all the controller(SCSI,N/w cards,video card) BIOSes are shadowed. After this PCI bus gets initialized and basic devices required for computer to boot are given Interrupts and DMA channels.
After this we will see that memory counting screen which we get after starting our system.

Then BIOS executes the bootloader to load MBR(Master Boot record). Then Interrupt vector is created and OS is loaded.BIOS will be deactivated once OS gets loaded.