Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}

2) What's the expected value of X

3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:

1)

(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Probably one of the most popular CS Interview questions.

ReplyDeleteboolean delete(Node* node){

if(node->next==NULL) return false;

else{

node->val=node->next->val;

node->next=node->next->next;

return true;

}

}

If playing with the data part of the node is allowed, copying the next node into the current node and then deleting the next node will suffice.

ReplyDeleteAnother interesting question on Linked List,which I was asked recently for one of my Job interviews : You are given a linked list(the head pointer). One of the nodes in the linked list points to an earlier node in the list(a loop). Find that 'earlier' node to which this node points to. Time Complexity : O(n)

ReplyDeleteSpace Complexity O(1).

In the C code for the linked list, are you allowed access to the data?

ReplyDeleteIf so, copy the data for the next node to this node, and then delete the next node. (by setting the "next" pointer of this node (say n) to n->next->next)

If O(n) can't be done, then the only way I can think of is to move next node data to the current node and delete the next node. But you need to assume that there aren't other pointers to these nodes - else you are making some valid pointers (valid in the O(n) soln) invalid and vice versa which may not really be the right thing to do in the context of the program.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteLet the pointer to the node be point.Then the code is as follows:

ReplyDeletecurrent=point->next->next;point->info=point->next->info;

point->next=current;

Ankush has already given the correct solution.

ReplyDeleteHowever, just for technical details sake, we need to free the next node too using free(node->next)

So another possible solution might be(copying the rest of the code from ankush)

boolean delete(Node* node){

if(node->next==NULL) return false;

else{

node->val=node->next->val;

struct node *temp=node->next;

node->next=node->next->next;

free(temp);

return true;

}

}

All comments point to the correct solution, but Siddhartha's solution is most apt. Thanks.

ReplyDeleteOne point I would like to make:

If the pointer is the last element of the linked list, then is there no way to delete the last element in O(1).. or is there? In Siddhartha's code, "if(node->next==NULL) return false; " does not delete the node. Thanks

Verified my point with smarter people - All agree with me. So, we have O(1) solution provided the node is not the tail. If the node is a tail, we have O(n) algorithm.

ReplyDeleteThanks