Friday, August 24, 2012

Adobe Written Test

Q1. Lowest Common Ancestor of a Binary Search Tree :
There’s only three cases you need to consider.
  1. Both nodes are to the left of the tree.
  2. Both nodes are to the right of the tree.
  3. One node is on the left while the other is on the right.
For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.
Therefore, using a top-down approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.
Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (max(p->data, q->data) < root->data)
    return LCA(root->left, p, q);
  else if (min(p->data, q->data) > root->data)
    return LCA(root->right, p, q);
    return root;
Q2. Given a string of 0's & 1's complement . Return a string which is its 2's complement . To calculate 2's complement :
  1. invert the bits
  2. Add 1
Code :

char * TwoComplement(char a[])
int l = strlen(a);
char *b = malloc(l);
for(int i=0;i<l;i++)
int carry=1;
for(int i=0;i<l;i++)
return b;

Q3:  GCD of two numbers using Recursion .

// a>=b
int gcd(int a,int b)
     return a;
     return gcd(b, a%b);

Q4 : A array of size (n-1) is filled with 1 to n numerals and only one of these r missing (no repetetion).Find the missing number in 1 traversal of array.

int find(int a[])
   int temp = 1;
   for(int i=1;i<=n;i++)
   for(int i=0;i<n-1;i++)
   return temp;

Q5 : Find half of a linked list in single traversal.

Node hasLoop(Node *head) {
  Node *slow = head, *fast = head;
  while (slow && fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  return slow;

Q6: Reverse a doubly linked list

void reverse(struct node **head)
     struct node *temp = NULL;  
     struct node *current = *head;
     while (current !=  NULL)
       temp = current->prev;
       current->prev = current->next;
       current->next = temp;              
       current = current->prev;
     if(temp != NULL )
        *head = temp->prev;

Monday, January 9, 2012

CodeSprint 2 : Coin Tosses

[20 points]
You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads. What is the expected number of additional tosses needed until you get N consecutive heads?
Input:The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.
Output:Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places.
Sample Input:4
2 0
2 1
3 3
3 2
Sample Output:6.00
Sample Explanations:If N = 2 and M = 0, you need to keep tossing the coin until you get 2 consecutive heads. It is not hard to show that on average, 6 coin tosses are needed.
If N = 2 and M = 1, you need 2 consecutive heads and have already have 1. You need to toss once more no matter what. In that first toss, if you get heads, you are done. Otherwise, you need to start over, as the consecutive counter resets, and you need to keep tossing the coin until you get N=2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0
If N = 3 and M = 3, you already have got 3 heads, so you do not need any more tosses.
Constraints:1 <= T <= 100
1 <= N <= 1000
0 <= M <= N
This problem is a Mathematical Expectation problem
Mathematically, for a discrete variable X with probability function P(X), the expected value E[X] is given by Σ xiP(xi) the summation runs over all the distinct values xthat the variable can take.

eg. find number of coin flips for getting a single head.
Let Expected number of coin flips for getting a head is x
a. If the first flip is the head, then we are done. The probability of this event is 1/2 and the number of coin flips for this event is 1. 
b. If the first flip is the tails, then we have to start over.The probability of this event is 1/2 and the expected number of coins flips now onwards is x. But we have already wasted one flip, so the total number of flips is x+1.
 this gives ,
x = (1/2)(1) + (1/2) (1+x)
Solving, we get x = 2. 

similarly for n consecutive heads ,
a. if 1st , 2nd , 3rd or nth flip gives tail then we have to start all over again.
b. else we are done
a  & b gives , x = (1/2)(x+1) + (1/4)(x+2) + ... + (1/(2^k))(x+k) + .. + (1/(2^N))(x+N)  + (1/(2^N))(N)
 we get x = 2N+1-2 .
let En be the probability for n consecutive heads  means
In order to obtain n consecutive heads, we must first obtain n − 1 consecutive heads, followed by:
  • with probability ½, a further head; or
  • with probability ½, a tail, after which we must obtain n consecutive heads.
It follows that En = ½(En−1 + 1) + ½(En−1 + 1 + En), from which En = 2En−1 + 2. which also give En = 2N+1-2  .

 Now as per given problem we already have M number of heads therefore let rest number of coin flips required be x.
let k =N-M be the consecutive heads required.
a. if 1st , 2nd , 3rd or kth flip gives tail then we have to start all over again ie. to find n consecutive heads.
b. else we are done
which gives
y =  (1/2)(x+1) + (1/4)(x+2) + ... + (1/(2^k))(x+k)  + (1/(2^(N-k)))(k)
and x = 2N+1-2.
solving this gives , 
y = 2N+1 - 2M+1

java code : 

import java.math.BigInteger;
    import java.util.Scanner;
    public class Solution {
          public static void main(String[] args) {
            Scanner a = new Scanner(;
            int t= a.nextInt();
                int n=a.nextInt();
                int m = a.nextInt();
            BigInteger b = BigInteger.valueOf(2).pow(n+1);
           BigInteger c= BigInteger.valueOf(2).pow(m+1);
Python one :
t = int(raw_input())
while t :
    n, m = map(int, raw_input().split())
    k = 2**(n+1)-2**(m+1)
    print '.'.join(map(str,[k,"00"]))
    t = t-1

Wednesday, November 9, 2011

Fun Facebook : Tag Someone with different word/text

A little trick with on Facebook to tag anyone with a different name/word. just follow these steps :

Step 1 :
find the profile id of the person by visiting their profile 
if url looks like ,

then id = 1097061819 

else if
url is , then find profile id by adding graph in place of www.

step 2 :
 Copy and Paste the below code in your status or comment box
@@[0:[person id:0: Any text you like Here]]
@@[0:[1097061819:0: This person is awesome]]

Tuesday, August 30, 2011

Access mediafire , megaupload in India

Rapidshare , Mediafire and other file sharing sites are blocked in india . Video lovers who watches their favorite videos or likes to share interesting clippings on file sharing sites such as Rapidshare, Mediafire, Megaupload, Hotfile, Fileserve and more will not be able to do so henceforth in India. When they tried to access such file sharing websites, there will be an error message “this site has been blocked as per instructions from Department of Telecom (DOT).

If you want to bypass the DOT blocked file sharing websites in India, you can use these methods:

Thursday, August 4, 2011

Dutch National Flag Problem

Given `N' objects coloured red, white or blue, sort them so that objects of the same colour are adjacent, with the colours in the order red, white and blue.
The technique to solve this problem is three way partitioning ie representing Red with 0 , White with 1 and Blue with 2 . The variables are lo , mid , hi .
lo = 1st position where value is not 0 .
hi = 1st position from end where value is not 2 .
mid = position past lo where value is not 1 .
sourcecode :

Wednesday, August 3, 2011

Worth Sharing ...

i just couldn't resist sharing this...

Curriculum Vitae

Any Finally ...
Stay Motivated
Ten Commandments for Peace of Mind

10 reasons why Computer is better than GirlFriend :)

Got it from a blog.. worth sharing :P . Anyway this one gives me hope :D

1.) It doesn’t talk back to you. At best it beeps or gives you the silent treatment.

2.) It provides you with more information than any girl will ever know.

3.) When you upgrade you know the costs up front.

4.) You can stare at tons of other girls and your computer will never get mad at you.

5.) You can shut her down whenever you get tired of her.

6.) Troubleshooting your computer is much easier than your GF.

7.) Your computer holds many valuable bits of information about your past and still likes you.

8.) You can press your computers buttons without any worry of repercussions.

9.) Your computer won’t sleep with your best friend or cheat on you.

10.) Your computer will cost a lot less than any girlfriend!

And this one is too funny :
There are basically 7 TYPES OF GIRLS :
  1.   HARD DISK Girls: Remember everything forever....
  2.   RAM Girls: Forgets about you the moment you go away from her.
  3.   SCREENSAVER Girls: Just for looking.
  4.   INTERNET Girls: Difficult to access.
  5.   SERVER Girls: Always busy when needed.
  6.   MULTIMEDIA Girls: Makes horrible things looks beautiful.
  7.   VIRUS:These type of girls are normally called ‘WIFE’ once enters in your system don’t let you free even after format..

Total Pageviews