Ant and Spider Problem

Given a cube. A ant is placed in a corner and cannot move. A spider starts from the opposite corner, and can move along cube edges in any direction (x,y,z) with probablity 1/3. What is the expected number of steps for this spider to get to the ant?

Let x represent the expected number of moves it takes to reach the ant when the spider is one move away (i.e., at any one of the three vertices of the cube adjacent to the ant). Let y represent the expected number of moves it takes to reach the ant when the spider is two moves away, and let z represent the expected number of moves it takes to reach the ant when the spider is three moves away (at the opposite vertex on the cube).

Then z = 1 + y, since after the first move, the spider will be one move away. From this point, there is a (2/3) chance that the spider will move to a vertex adjacent to the ant and there is a (1/3) chance he will move back to his starting position, Thus, y = 1 + (2/3)x + (1/3)z.

Similarly, x = 1 + (1/3)(0) + (2/3)(y). This system of 3 equations with 3 unknowns has solution z=10, y=9, and x=7. So, it will take 10 steps to reach the ant, on average, from the spider's initial position.

7 Bucket and Poison Problem

There are 7 buckets with water, and one of them is poisoned. You have infinite number of flies, and if you put a fly in poisonous bucket, it will take seven days to die. You need to send your friend a non-poisonous bucket in 1 week, and also you need to find out which bucket is poisoned. How many least number of flies you need to it? and how do you do it?

1) One answer would be, You need one fly for this.

How?  You put the fly in any one of the bucket, and if it dies in one week then it is the poisonous one, and send any one of the other 6 to your friend, and if fly does not die, then its non-poisonous, and you need to send this to your friend and since you have sent to your friend in one week, now take your time and repeat to find out which has the poison with the same fly.

2) Since first answer may be ridiculous, the second answer would be using 3 flies.

How? You need to number the buckets from 1 to 7 in binary and then assign one bit for each flies, and dip the fly in those buckets which has the corresponding bit set in the bucket number in binary, after seven days, if the fly dies consider it as 1 otherwise 0, and get the binary number for bucket which contains the poison.

Classic 25 Horse Problem

Classic 25 horse problem,
25 Horses,
Have a 5 horse track,
No stopwatch,
How many races are required to determine the 3 fastest horses?

Answer : 7 Races

And here goes why? 

1. we have 5 races for 25 horses that 5 horses on a team, define each team as a, b, c, d, e.
2. carry a best horse race for each team first place, define them as a.1,b.1,c.1,d.1,e.1
3. assume prior best horse race 's top 3 places are a.1 b.1 c.1 , so we know the fastest horse is a.1
4. we only need to take last race to know who are second and third quickest horse.
5. The horses that participate in this race are b.1 b.2 a.2 a.3 c.1 , this race 's top 2 places are 2nd and 3rd quickest horses

Search two numbers from array to make a sum

You have a array of random numbers and you are given a number k. Find the 2 elements in the array which sum up to k.

e.g: If my array is {2,5,3,1,8,7,5,4} and k=6.

Then 2 numbers that sum up to 6 are 5 and 1.

step 1: sort the array //O(n.log(n))

arr=2,5,3,1,8,7,5,4 --> 1,2,3,4,5,5,7,8

//size=8

step 2:

i=0, j=7

if a[i]+a[j]==K //done

if a[i]+a[j] > K //j--

if a[i]+a[j] < K //i++

repeat step2, till it reaches mid point //O(n)

Probability

Probability question: Persons A and B go shopping together. Say person A spent X amount of money and B Y. What is the probability that the sum total of their purchases [i.e. X+Y] has 0 cents [i.e. is a whole number]. ?

Answer : The person A can have cents in the range of 0 to 99, and same with the case B. Thus they have 100 cases each, and total number of cases is 100x100. Out of them the cases of our interest is (0, 0) (1,99), (2, 98), (3, 97) ... (99. 1) is 100. So the probability is 100/10000 = 1/100.

Count 45 minutes using rope

Given 2 non-uniform ropes (each burns down in 1hr, but not uniformly), how to measure 45 mins?

Answer : Take one rope connect both ends. Ignite the connection point and one end of the other rope at the same time. When the looped rope burns out, it is 30 mins. Then ignite the unburned end of the remaining rope. When the remaining rope burns out, it is another 15 mins. So it is 45 mins.

Three Orange Boxes

Three boxes, one with apples, one with oranges, one with a mix of apples and oranges, all the boxes are labeled incorrectly, you can pick up just one fruit. How do you tell which box has what fruit?

Answer : All the labels are incorrect, so pick a fruit from the box labeled mixed box. That will tell you if its the apple or orange box, because its not mixed. The other labels are also incorrect, so the box labeled with the fruit you picked will be the box containing just the other type of fruit. The remaining one will be the mixed box.The second box cant be mixed fruit box because then the third box will be labelled correct which is not the case 

where is volatile variables stored in memory layout ?

The storage of a variable is not decided based on if it is volatile or not. It can be anywhere as is the case with normal variable. So the variable may be on stack,heap or in the data section of executable, depending on how it gets defined. The volatile qualifier just tells the compiler that this variable may change in ways that are not apparent to you, it can be changed at any point of time, for example is hardware registers (variables mapped to h/w registers). So compiler disables any optimizations such as caching on this variable.

Volatile is type qualifier not a storage class specifier.

Find binary of a Number

Write a function to print the binary value of the number passed to it, and function should not use any variables other than the parameter passed to it.

Answer : We need to use recursion for this, and here is my version of the C code for the same

#include <stdio.h>

void printBinary(int k)
{
    if(k != 0)
    {
        printBinary(k/2);
    }
    printf("%d", k%2);
}
void main(void)
{
    int k = 4561;
    printBinary(k);
}

Array manuplation

Given a array of random integers, sort the odd elements in descending order and even numbers in ascending order. Optimize for time complexity.
e.g. for i/p (1,4,5,2,3,6,7) O/p = (7,5,3,1,2,4,6)

Answer :
We can solve this by doing a simple bubble sort, with the below logic

1. if first number and second number are odd >> compare and exchange >> push lower odd to first
2. if first is odd and second is even >> no exchange >> we want odd in the first
3. if first is even and second is also even >> compare and exhange >> push higher even number to last
4. if first is even and second is odd >> always exchange >> since we want odd numbers first

Here is the complete solution in C

#include <stdio.h>

int a[] = {1,4,5,2,3,6,7};
int len = 7;

void main(void)
{
    int i,j, temp;
    for(i = 0; i < len-1; i++)
    {
        for(j = 0; j< len-1; j++)
        {
         if( a[j] %2  != 0) 
         {     // first odd number
             if(a[j+1] % 2 != 0) 
             {   
                 // second odd number
                 if(a[j] < a[j+1]) 
                 {
                     temp = a[j+1];
                     a[j+1] = a[j];
                     a[j] = temp;
                 }
             }
             else 
             {     // second even number 
                 //do nothing
             }
         }
         else 
         {     // first even number
             if(a[j+1] % 2 != 0) 
             {   
                 // second odd number
                 // always interchange
                 temp = a[j+1];
                 a[j+1] = a[j];
                 a[j] = temp;
             }
             else
             {
                 // second even number
                 if(a[j] > a[j+1])
                 {
                     temp = a[j+1];
                     a[j+1] = a[j];
                     a[j] = temp;
                 }
             }
         }
        }
    }
    for(i=0; i<len; i++)
    printf("%d ", a[i]);
}

Find the Odd ball

You are given 80 balls and out of which only 1 has more weight than other 79. also, you are given weighing machine which can weigh any number of balls of 2 sets( 40 40 or 25 25 etc) at one time

Answer:
Assume the ball we need to find is X. Divide into 3 groups, A (27 balls), B (27 balls), C (26 balls)

Step 1: Weight A vs B, whichever is heavier has X. If equal, then C has X. If C has X, choose a random ball in A and put into C so that C has 27 balls.

Step 2: After step 1, we determine which group has X, and the group size is 27. Divide into 3 smaller groups, each of size 9, and repeat the same procedure.

In short, we have, 80 -> 27 -> 9 -> 3 -> 1, 4 steps in total to find X.

In general , if there are n balls , log_3(n) is the answer, or find out how many powers 3 should be raised to cross the total number of balls

Sub Strings

write a code for which input is a string and set of characters acting as delimiters. Cut the given string where ever delimiters occur and return all the set of sub strings. For eg: given string abbcdeffghujsb and delimiter set:c,g,j hen output should be: abb, deff, u, sb

Answer goes as below

char delimiter[] = {'c', 'j' , 'f'};

void get_sub_str(const char *str, char *dl, int dn)
{
    char temp[1024];
    int i, j, len = 0;
    int ssu = 0; // sub string update
    for(i=0; str[i]!='\0'; i++)
    {
       for(j=0; j<dn; j++)
       {
           if( str[i] == dl[j])
               ssu = 1;
       }
       if(ssu == 1)
       {
           temp[len] = '\0';
           printf("%s\n", temp);
           len = 0;
           ssu = 0;
           i++;
       }
       temp[len] = str[i];
       len++;
    }
}

Signed and Unsigned

1. What is the output of the following program

main() {
    unsigned int a = 10;
    int b = -19;
    puts((a+b)>0? "Positive":"Negative");
}

Answer : Positive
Explanation : When signed and unsigned arithmetic is done, signed is converted to unsigned and result will be unsigned, ANSI C standard.

Linked List Example

Recently I was recalling my linked list concepts, and I found that I know the concepts, but when programming I am missing something. So I thought I should do it once again, so I made a simple program, which can add / delete elements from linked list. here it is for your reference.

shetty.h, this file contains the basic type definitions required.

#ifndef __SHETTY_H_
#define __SHETTY_H_

typedef struct le {
    int ld;
    le *next;
} le;

typedef struct lh {
    le *next;
} lh;

#endif // __SHETTY_H_

Shetty.cpp, this file contains all the functionality required to add or delete from the linked list. The comments are self explanatory.

#include "shetty.h"
#include "malloc.h"
#include "stdio.h"

lh list;

/********************************************
** This function adds an element to Linked
** list, the head to list and element to be
** added is given as params.
** lst - pointer to the head of the list
** ld  - an integer data, u can change this
**       to whatever type you want to.
********************************************/
void add_list(lh *lst, int ld)
{
    le *element;
    le **tmp;
    element = (le *) malloc (sizeof(*element));
    element->ld = ld;
    element->next = NULL;

    tmp = &(lst->next);
    while(*tmp!=NULL)
        tmp = &((*tmp)->next);
    *tmp = element;
}

/********************************************
** This function removes an element from the
** Linked list
********************************************/
void remove_list(lh *lst, int ld)
{
    le **tmp, **prev;
    le *deleted;

    tmp = &(lst->next);
    prev = tmp;
    while(*tmp!=NULL)
    {
        if((*tmp)->ld == ld)
        {
            deleted  = (*prev)->next;      
            (*prev)->next = (*tmp)->next;
            free(deleted);                  
        }
            prev = tmp;
            tmp = &((*tmp)->next);
    }
}

/**************************************
** Display the list to see elements
**************************************/
void disp_list(lh *lst)
{
    le **tmp;
    tmp = &(lst->next);
    while(*tmp!=NULL)
    {
        printf("%d\t", (*tmp)->ld);
        tmp = &((*tmp)->next);
    }
    printf("\n");
}
int main(void)
{
    list.next = NULL;
    add_list(&list, 25);
    add_list(&list, 30);
    disp_list(&list);
    add_list(&list, 45);
    disp_list(&list);
    add_list(&list, 55);
    disp_list(&list);
}

Here, only one thing is important in dealing with linked list. i.e we need to get the address of the next pointer in a temp variable, and then change this variable with different address as we traverse the list. We should not modify any of the pointers in the list while traversing, unless we want to add or delete from the list.