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

Total Pageviews