The Singleton Pattern

I'm not going to explain Singleton pattern. It's already nicely done in this article.
Once you have gone through that article. Feel free to experiment with code below.

using System;
namespace SingletonTest
{
    public class SingletonAlmostLazy
    {
        private static readonly SingletonAlmostLazy sObj = new SingletonAlmostLazy();

        // this ensures that type initialization will be done only when this class is referenced by 'SingletonAlmostLazy.XXX'
        // v4.0 onwards type initilization changed a bit (Don't exactly know what that is :) )
        // In < v4.0, type initialization may happen before as well - i.e, before the actual reference
        static SingletonAlmostLazy() { }
        private SingletonAlmostLazy()
        {
            Console.WriteLine("This is singleton constructor");
        }
        public static SingletonAlmostLazy Instance { get { return sObj; } }

        public static void DoSomething()
        {
            Console.WriteLine("Doing something in SingletonAlmostLazy");
        }
    }

    class SingletonFullLazy
    {
        private class SingletonHolder
        {
            internal static readonly SingletonFullLazy sObj = new SingletonFullLazy();

            // Lazy
            static SingletonHolder() { }
        }

        private SingletonFullLazy()
        {
            Console.WriteLine("This is singleton constructor");
        }

        public static SingletonFullLazy Instance { get { return SingletonHolder.sObj; } }

        public static void DoSomething()
        {
            Console.WriteLine("Doing something in SingletonFullLazy");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            SingletonAlmostLazy.DoSomething();
            Console.WriteLine("After SingletonAlmostLazy.DoSomething()");
            SingletonAlmostLazy obj = SingletonAlmostLazy.Instance;
            SingletonAlmostLazy obj2 = SingletonAlmostLazy.Instance;

            Console.WriteLine("Done with AlmostLazy...");
            Console.WriteLine("\n\n\n");

            //---------------

            SingletonFullLazy.DoSomething();

            Console.WriteLine("After SingletonFullLazy.DoSomething()");

            SingletonFullLazy o = SingletonFullLazy.Instance;
            SingletonFullLazy o2 = SingletonFullLazy.Instance;

            Console.WriteLine("Done with FullLazy...");
            Console.ReadLine();
        }
    }
}

Output:
This is singleton constructor
Doing something in SingletonAlmostLazy
After SingletonAlmostLazy.DoSomething()
Done with AlmostLazy...




Doing something in SingletonFullLazy
After SingletonFullLazy.DoSomething()
This is singleton constructor
Done with FullLazy...

Find all possible ways to sum numbers such that it sumes to N (order matters)

You are given a number N and a set of numbers. Find all possible ways to sum those numbers in the set such that total comes to N and order matters.

using System;
using System.Collections.Generic;

namespace Solutions
{
    public class NumbersSumToValueQuora
    {
        List<List<int>> findSetOfNumbers(List<int> numberList, int value)
        {
            return myHelper(numberList, value, new LinkedList<int>(), new List<List<int>>());
        }

        List<List<int>> myHelper(List<int> numberList, int remaining, LinkedList<int> currSet, List<List<int>> result)
        {
            if (remaining == 0)
            {
                result.Add(new List<int>(currSet));
                return result;
            }
            for (int i = 0; i < numberList.Count; i++)
            {
                int temp = numberList[i];
                int nVal = remaining - temp;
                if (nVal >= 0)
                {
                    numberList.RemoveAt(i);
                    currSet.AddLast(temp);

                    myHelper(numberList, remaining - temp, currSet, result);

                    currSet.RemoveLast();
                    numberList.Insert(i, temp);
                }
            }
            return result;
        }
        public static void HelperNumbersSumToValueQuora()
        {
            NumbersSumToValueQuora obj = new NumbersSumToValueQuora();

            List<List<int>> ans = obj.findSetOfNumbers(new List<int> { 1, 2, 3, 4, 5 }, 4);
            foreach (var slist in ans)
            {
                Console.WriteLine("{" + String.Join(", ", slist.ToArray()) + "}");
            }
        }
    }
}

2 Eggs and 100 floor building

This one was one of the widely discussed problems on the campus during my stay @ IIT Kharagpur.

Question:
You are given 2 eggs. Both eggs have same properties.
These 2 eggs are very strong. Just by dropping them on the floor they won't break.

They have a limit - in a way - if they are dropped from a particular height or more, then they will break.
With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped ? meaning - find minimum number of drops by which we can find the lowest floor at which an egg will break when dropped.

Understanding the problem and some experimentation:

As it is said in the problem both the eggs have same properties - meaning - if  egg#1 starts to break (let's say) at building 25 then egg#2 will also follow the same behavior.

Trial 1:
now let's say, we choose 25th floor to drop the 1st egg.
If, 1st egg breaks when dropped from 25th floor, then we have to start from 1st floor for 2nd egg (to find out exactly from which floor that egg starts to break).
in worst case we will end up dropping from floor 1 to (25-1). So, total number of attempts will be 1+24 = 25 in this case.
But, what if 1st egg does not break at 25th floor ?
Trial 2:
let's say, we split 100 floors in 10 chunks.
1-10, 11-20, 21-30, ..., 91-100

We start from 10th floor.
If egg breaks, then we start from floor 1-9. Total= 1+9 = 10.
If egg does not break, then in worse case - let's assume egg actually starts breaking at 99th floor.
This way it comes to
1(for 10th floor) +
1(for 20th floor) +
1(for 30th floor) +
... +
... +
1(for 90th floor) +
1(100th floor egg breaks) +
9 (to check if on 91st to 99th floor egg breaks or not)
Total : 10 + 9 = 19 attempts to just figure out that the egg actually starts breaking from 99th floor.

Trial 3:
Why don't we use binary search ?
For binary search we have to start at 50th floor. worst case will require 50 trials  which is not optimal as our trail#2 requires only 19 attempts.

Correct Approach:

We just saw that our previous attempts did give some clues.

Now, let's assume that we start from floor x ; then if egg breaks at floor x then we have to try 1 to (x-1).
Can we choose (starting floor) x such that irrespective of egg breaks or not, x is actually the optimal floor to begin with ?

Example,
let's assume that x = 20.
So,
Attempt#1, drop egg from floor 20 (egg does not break)
Attempt#2, drop egg from floor 39  [ (20 + ( 20-1)) - so if egg does not break, and we know that 20 is the optimal attempts. so we have to choose 39th floor. so if at 39th floor egg breaks (we have already wasted 2 attempts at this moment) we know that we can start from 21st to 38th floor to check if egg breaks or not]
...
...
so on...

I hope, you get the idea behind the previous example.

Now, let's get to the core logic..
Let's assume that x is our optimal floor number to start dropping the egg.
so, using this, if egg breaks or not we should be able to figure out ( using next (x-1) attempts ) that from which floor egg starts to break.

worse case analysis...
x (egg to be dropped from xth floor - egg does not break) +
x-1 (egg to be dropped from (x+x-1)th floor - egg does not break) +
x-2 (egg to be dropped from (x+x-1+x-2)th floor - egg does not break)
... +
... +
3 + 2 + 1 = x(x+1)/2

These all attempts should cover all 100 floors.

so, our equation looks like this ( x . (x+1) ) / 2 <= 100
and x = 13.65 ~ 14
Hence, 14th floor should be the floor we should start dropping the 1st egg and hence our optimal attempts are 14 !

---
This equation does give us a generalized formula for n number of floors.
x.(x+1)/2 = n

My todo question is: Can we have a generalized formula for M eggs and a building with N floors ?

Answer - Which one is faster ?

The question asked on my post which-one-is-faster. 

Here is the answer to that question.
If we consider compare and increment part, it becomes clear that which one is faster and how ?

Compare :
Problem -1 has (10000*11)+10001 = 120001 comparisons
Problem-2 has (10*10001)+11 = 100021 comparisons
Delta = 120001 – 100021 = 19980

Increment:
Prblem-1 has (10000*10)+10000 = 110000 increments
Problem-2 has (10*10000)+10 = 100010 increments
Delta = 110000-100010 = 9990
So problem-2 is faster !!

Find power(n, exp) efficiently

I will discuss three approaches to find power(n, exp). power(n, exp) is defined as
power(2, 4) = 2 * 2 * 2 *2 = 16.


Iterative approach:
Space Complexity = ;
Time Complexity =
   

    result=1;
    for(i=1 ; i<=exp ; i++) {
        result *= n;
    }
    printf("Iterative method: [%d]\n", result);

Divide and Conquer / Recursive approach:

While finding power(2, 20), we know that .
i.e, .
It means that we can find solution for power(n, exp/2) and multiply that value with it again.
...
temp = power(n, exp/2);
power(n, exp) = temp * temp;
...
That is how we can avoid recomputing power(n, exp/2) TWO times.
Space Complexity = [ Used in Stack, while running the program ] ;
Time Complexity = O(log n)

int rec_pow(int n, int exp) {
    int subsoln;
    if (exp==1) {
        return n;
    }

    subsoln = rec_pow(n, exp/2);
    if (exp & 1) {
        // If exp is odd number.
        return n * subsoln * subsoln;
    }


    return subsoln * subsoln;
}

Exponentiation by Squaring / (log n) Iterative Method:
Refer: Wiki: Exponentiation by Squaring
It seems Art of Computer Programming, Volume 2: Semi numerical Algorithms by Donald Knuth ( his books are generally Juggernaut ) has discussed this method in detail. You may refer it ( I have not yet ).



This approach is implementation of the equation shown above.
Space Complexity = O(1) ;
Time Complexity = O(log n)

This code will work only for exp > 0.

    result=1;
    while(exp) {
        if (exp & 1) { // If exp is odd number.
            result *= n;
        }
        exp >>= 1;
        n *= n;
    }
    printf("Exponentiation by Squaring method: [%d]\n", result);

Which one is faster ?

Just found something interesting !!

Problem – 1

for(i=1 ; i<=10000 ; i++){
    for(j=1 ; j<=10 ; j++){
        // Compute A
    }   
}

Problem – 2

for(j=1 ; j<=10 ; j++){
    for(i=1 ; i<=10000 ; i++){
        // Compute A
    }
}

Which one is faster ? Are they both same ?

** Compute A for both takes same time

Print nodes in a Binary Tree [ Level wise ]

There are more then one ways to achieve this. But, the theme is to do BFS. Here is one of them. It is self-explanatory.

#include<stdio.h>
#include<stdlib.h>

struct node{
    int data;

    struct node* left;
    struct node* right;
};

struct node* queuePtr[100];
int front,end;

struct node* getNode () {
    struct node *t = (struct node*) malloc(sizeof(struct node));
    t->left = t->right = NULL;

    return t;
}

void print_BST_levelwise () {
    while (front < end) {
        if (queuePtr[front] != NULL) {
            if (queuePtr[front]->left == NULL && queuePtr[front]->right == NULL) {
                front++;
                continue;
            }
            //if (queuePtr[front]->left != NULL) {
                queuePtr[end++] = queuePtr[front]->left;
            //}
            //if (queuePtr[front]->right != NULL) {
                queuePtr[end++] = queuePtr[front]->right;
            //}
        }
        front++;
    }

    //Done with BFS... Now print
    int i,j,c;
    for(i=0 ; i<end ; i++) {
        if (queuePtr[i] != NULL) {
            printf("%d, ", queuePtr[i]->data);
        } else {
            printf("null, ");
        }
    }
    printf("\n\nLevelwise printing\n");
    c=-1;
    for(i=0 ; i<end ; ) {
        c++;
        printf("Level [%d]:\t\t", c+1);
        for(j=0 ; j<(1<<c) ; j++) {
            if (queuePtr[i] != NULL) {
                printf("%d, ", queuePtr[i]->data);
            } else {
                printf("null, ");
            }
            i++;
        }
        printf("\n");
    }
}

int main () {
    struct node* n1 = getNode();
    struct node* n2 = getNode();
    struct node* n3 = getNode();
    struct node* n4 = getNode();
    struct node* n5 = getNode();
    struct node* n6 = getNode();

    n1->data = 1;
    n1->left = n2;
    n1->right = n3;

    n2->data = 2;
    n2->left = n4;
    n2->right = n5;

    n3->data = 3;
    n3->left = NULL;
    n3->right = n6;

    n4->data = 4;
    n5->data = 5;
    n6->data = 6;


    /*  
        How does the Tree look ?


                                     1
                                   /   \
                                  2     3
                                /   \     \
                               4     5     6

    */

    front=end=0;
    queuePtr[end++] = n1;
    
    print_BST_levelwise();
    free(n1);
    free(n2);
    free(n3);
    free(n4);
    free(n5);
    free(n6);

    return 0;
}