• RSS
  • Facebook
  • Twitter

Knowledge is Power.

  • Who you are ?

    Working on machines without understanding them ? Then you should be here..

  • Where you are ?

    Geographical location should not become a barrier to Share our knowledge.

  • What do you do ?

    Puzzles and Interview question are intended to be discussed here.

    Sunday, October 27, 2013

    Know Thy Complexities!

    Hi there!  This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science.  When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them.  Over the last few years, I've interviewed at several Silicon Valley startups, and also some bigger companies, like Yahoo, eBay, LinkedIn, and Google, and each time that I prepared for an interview, I thought to msyelf "Why oh why hasn't someone created a nice Big-O cheat sheet?".  So, to save all of you fine folks a ton of time, I went ahead and created one.  Enjoy!
    Good Fair Poor

    Searching

    Algorithm Data Structure Time Complexity Space Complexity
    Average Worst Worst
    Depth First Search (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)
    Breadth First Search (BFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)
    Binary search Sorted array of n elements O(log(n)) O(log(n)) O(1)
    Linear (Brute Force) Array O(n) O(n) O(1)
    Shortest path by Dijkstra,
    using a Min-heap as priority queue
    Graph with |V| vertices and |E| edges O((|V| + |E|) log |V|) O((|V| + |E|) log |V|) O(|V|)
    Shortest path by Dijkstra,
    using an unsorted array as priority queue
    Graph with |V| vertices and |E| edges O(|V|^2) O(|V|^2) O(|V|)
    Shortest path by Bellman-Ford Graph with |V| vertices and |E| edges O(|V||E|) O(|V||E|) O(|V|)

    Sorting

    Algorithm Data Structure Time Complexity Worst Case Auxiliary Space Complexity
    Best Average Worst Worst
    Quicksort Array O(n log(n)) O(n log(n)) O(n^2) O(n)
    Mergesort Array O(n log(n)) O(n log(n)) O(n log(n)) O(n)
    Heapsort Array O(n log(n)) O(n log(n)) O(n log(n)) O(1)
    Bubble Sort Array O(n) O(n^2) O(n^2) O(1)
    Insertion Sort Array O(n) O(n^2) O(n^2) O(1)
    Select Sort Array O(n^2) O(n^2) O(n^2) O(1)
    Bucket Sort Array O(n+k) O(n+k) O(n^2) O(nk)
    Radix Sort Array O(nk) O(nk) O(nk) O(n+k)

    Data Structures

    Data Structure Time Complexity Space Complexity
    Average Worst Worst
    Indexing Search Insertion Deletion Indexing Search Insertion Deletion
    Basic Array O(1) O(n) - - O(1) O(n) - - O(n)
    Dynamic Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
    Singly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
    Doubly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
    Skip List O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
    Hash Table - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
    Binary Search Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
    Cartresian Tree - O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
    B-Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
    Red-Black Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
    Splay Tree - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
    AVL Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

    Heaps

    <!-- heapify
    Heaps Time Complexity
    Heapify Find Max Extract Max Increase Key Insert Delete Merge
    Linked List (sorted) -

    O(1)
    O(1)
    O(n)
    O(n)
    O(1)
    O(m+n)

    Linked List (unsorted)
    -
    O(n)
    O(n)
    O(1)
    O(1)
    O(1)
    O(1)
    Binary Heap
    O(n)
    O(1)
    O(log(n))
    O(log(n))
    O(log(n))
    O(log(n))
    O(m+n)
    Binomial Heap
    -
    O(log(n))
    O(log(n))
    O(log(n))
    O(log(n))
    O(log(n))
    O(log(n))
    Fibonacci Heap
    -
    O(1)
    O(log(n))*
    O(1)*
    O(1)
    O(log(n))*
    O(1)

    Graphs

    Node / Edge Management Storage Add Vertex Add Edge Remove Vertex Remove Edge Query
    Adjacency list O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)
    Incidence list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
    Adjacency matrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)
    Incidence matrix O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)

    Notation for asymptotic growth

    letter bound growth
    (theta) Θ upper and lower, tight[1] equal[2]
    (big-oh) O upper, tightness unknown less than or equal[3]
    (small-oh) o upper, not tight less than
    (big omega) Ω lower, tightness unknown greater than or equal
    (small omega) ω lower, not tight greater than
    [1] Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST n log n (Omega n log n) and NO MORE THAN n log n (Big O n log n).SO
    [2] f(x)=Θ(g(n)) means f (the running time of the algorithm) grows exactly like g when n (input size) gets larger. In other words, the growth rate of f(x) is asymptotically proportional to g(n).
    [3] Same thing. Here the growth rate is no faster than g(n). big-oh is the most useful because represents the worst-case behavior.
    In short, if algorithm is __ then its performance is __
    algorithm performance
    o(n) < n
    O(n) ≤ n
    Θ(n) = n
    Ω(n) ≥ n
    ω(n) > n

    Big-O Complexity Chart

    "Big -->

    Friday, August 23, 2013

    "Query end" state in MySql appears to consume a lot of time which becomes a bottleneck for insert operations.

    I had written a stored Procedure in Mysql which implements a cursor to iterate over the rows of a table. This cursor worked well on my machine but it took a lot of time in the live environment (POC setup).

    Initial culprit seemed to be the hardware but after analysing the procedure with "show processlist", I found that every insert would used to get stuck at query insert state.

    Incase any of you guys come across similar issue, you can edit your my.cnf file (I think my.ini for windows) and change this

    innodb_flush_log_at_trx_commit = 1
    to
    innodb_flush_log_at_trx_commit = 0 or innodb_flush_log_at_trx_commit = 2.

    This will drastically improve the performance but it also prohibits the innodb engine to serve ACID properties.

    After reading some forums I found that the above parameter can be changed if you are ready to incur a loss of one statement in case of system crash(not Mysql) or power failure.

    Monday, July 29, 2013

    Hello Guys,

    As a newbie on online Coding contests, I was initially fed-up with 1000000007.I hardly understood the logic behind it.

    Some guys give an hint that "its the first 10 digit prime..", so what ?
    There were 2 questions in my mind.
    1) Why only a prime.
    2) Why not 2nd or 3rd prime

    Instantly I got an partial answer from myself for the first question, A prime because we need (ans % Prime) as the actual answer, so the o/p should be unique.

    But, there was a lot behind that word Prime in this case (Explained later)

    The 2nd question what still open, but lately I understood that 1000000007 is easy to represent as 10^9+7. Any greater Prime would have served the purpose but this was easy to write. Infact some times we find the 2nd 10 digit prime which is again easy to represent 1000000009.

    This would have been very well understood by everyone now.


    Coming to the actual point.

    All of us might have noticed that 1000000007 comes only when our answers are expected to be very large, more commonly when we implement combinations n(c,k) or nCk.

    The combination formula is n!/(r!(n-r)!).


    We are asked mod operation with 1000000007 for 2 reasons,
    1) Obviously, so as to restrict our answer to 10 digit and
    2) Help us with large multiplications and divisions.

    Did u read Division ? yes !!!

    We must know that (%) is distributive over multiplication,addition etc, but not over division.
    So, how to do large divisions ?

    There`s a theorem known as "Fermat's little theorem".
    It say`s that (A/B) % MOD = ((A % MOD)*(B^(MOD-2) % MOD))%MOD (You can refer wiki for actual theorem)

    Now, we can see that, Fermat's theorem essentially convert all our division to multiplication.So we can use our mod (%) operation.

    If you have any issues/queries, please comment the same... I will try my best to answer it.


    Sunday, July 28, 2013


    Problem Statement

    A company organizes two foreign trips for its employees yearly. Aim of the trip is to increase interaction among the employees of the company and hence company wants each of his employee to see new people on the trip and not even a single person with whom he has worked in past. Therefore it is a rule in company that in any of the trips, all the employees should be new to each other and no two of them should have worked together in past.

    Given the work history of each employee (which people he has worked with sometimes in past), you have to tell whether all of the employees can be accommodated within trips without violating the above rule or not. Each employee is given a unique integer ID by which they are recognized. You can also assume that each employee has worked with at least one other employee in past.

    Note: No employee can be in both trips and every employee must be part of one trip.

    Examples

    Example: 

    i) Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past.

    ii) Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no way possible to have two trips satisfying the company rule and accommodating all the employees.
    ==========================================================================
    This is an old Question on Techgig, but lets discuss it as we are finding it difficult to approach the problem.
    Well, I had solved this question few months back and scored just 90. Unable to 100 (Maybe I am missing a corner case, not sure though).
    I can`t recollect the exact thought process of mine towards this problem but I will explain the final approach used by me.
    As per the question, they are giving us the set of employees who have worked with each other. So lets keep a mapping of the employees who have worked with each other.
    Then, if an employee has worked with someone, check for all combinations of employee such that the intersection should not be marked as "1" (i.e worked with each other)

    Here is the code : (Fetches only 90)


    #include
    #include

    char* emp_violating(int input1,char* input2)
    {
        int i=0,j=0,k=0;
        int a=0,b=0;
        int map[input1+1][input1+1];
        int cnt[input1+1];
        for(i=0;i<=input1;i++)
        {    for(j=0;j<=input1;j++)
                map[i][j]=0;
                cnt[i]=0;
        }
        while(1)
        {
            while(*input2 != '(') 
        {input2++;}
            input2++;
            while(*input2>='0' && *input2<='9')    /*For more than 1 digit numbers*/
            {
                a=a*10 + (int)*input2++ - '0';
            }
            while(*input2 != ',') 
            input2++;
            input2++;
            while(*input2>='0' && *input2<='9')    /*For more than 1 digit numbers*/
            {
                b=b*10 + (int)*input2++ - '0';
            }
            map[a][b]=1;map[b][a]=1; /*Mark that both guys have been with each other*/
            cnt[a]++;cnt[b]++; /*Increment the count to identify that they have been to a picnic. This can also just set to be dirty*/
            input2++;
            if(*input2!=',')
            break;
            a=0;b=0;
        }

        for(i=1;i<=input1;i++)
        {
            if(cnt[i]>1)
            {
                for(j=1;j<=input1;j++)
                {
                    for(k=j+1;k
                    {
                        if(map[i][j]==1 && map[i][k]==1)
                        {
                            if(map[j][k]==1) return "no";
                        }
                    }
                }    
            }
        }
        return "yes";
    }

    int main() /*Driver*/
    {
        char *a="(10,2),(2,3),(3,4)";
        printf("%s\n",emp_violating(10,a));
        return 0;
    }



    Monday, July 15, 2013


    Problem Statement

    In a family party, people are playing the musical pillow game in which people sit in a circle. Starting from the first person, they transfer the pillow to the person to their left. For simplicity, we’ll assume that people are assigned an integer tag from 1 to n(which is the total number of people) in the clockwise manner, so that during the game pillow is passed in the increasing sequence of. When game starts, a song is played and the person with the pillow at the end of the song, is eliminated and game starts again till there is only one person is left, which is declared as the winner of the game.
                                                    You are give total number of people playing the game and the duration of the song in seconds. If game starts with pillow being put on a table & person1 (person with tag number 1)picking it up(at the end of first second [time], pillow will be with person1) and each person takes one second to transfer the pillow to the next person, you have to tell which person (tag number) which will win the game.

    Examples

    Example 1: Let there are 5 people and duration of the song is 2 seconds(every second person present in the clockwise manner will be eliminated) then people will be eliminated in the following order: 2,4,1, 5 and person with tag 3 will be the winner.

    Example 2: If there are 11 people in the beginning of the game, and song duration is 4 seconds then people will be eliminated in following order: 4,8,1,6,11, 7, 3,2,5, 10 and winner will be the person with tag no. 9.
    ==============================================================================

    Dont know why they called it as a medium level problem after that Bitonic problem (Easy level) which ruined a couple of days of my life.. :(

    Lets come to the problem, its a very easy problem to solve. A new programmer would face only one problem i.e to start the loop from first position when we reach the end of our sequence.

    Here`s the logic :
    i) First we declare an array with the number of persons (input1) and fill it with 0.

    ii) Then, as the games starts and a person gets out, that position is to be marked as 1. Because while the next round this position needs to be ignored as the person is already out.

    ii) Continue till only a single person remains.

    The tricky point here is, how to traverse through the loop. The answer to this is, just maintain a flag which is updated only when we encounter a 0 at that position in the array else just move on until flag becomes equal to input2. In case, we reach the end of array, start from 1 again without resetting the flag.

    If you have doubts or you want the source code for reference the comment below with your email address.

    EDIT: Just learnt to find that this is called as "Josephus Problem" and a recursive solution can be written for it.

    Monday, July 8, 2013


    Problem Statement
    You are given a set of positive integers. your task is to solve partition problem.

    Lets define the partition problem.

    Partition problem is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the elements in S1 equals the sum of the elements in S2.

    Example 1:
    array[] = {1, 5, 11, 5}
    Output: Yes
    This array can be divided into to subsets {1, 5, 5} and {11} these two have equal sum.

    Example 2: 
    array[] = {1, 5, 3}
    Output: No
    This array cant be divided into two subsets of equal sum.

    ===============================================================================

    The level set was easy but this was really a nice question, took half hour to code it.. :P

    Well, Most of us get the answer just by reading the question... "Divide the array such that sum of each partition is equal", but as soon we we try to write the code, out mind keeps wondering "how the hell do I implement this ?"

    I thought for some time and then realized that, The worst case of forming the partitions for N element is; One partition of 0 elements and the other of N elements, but this wont help us.

    Now lets move forward in the same line. One partition of N-1 elements and the other of 1 element.This is our first step.

    This can be easily achieved with a for loop. But, the problem is, there are many different ways for selection 2 partitions each of N-1 and 1 elements respectively. To be precise they are N ways.

    First thing to be taken care of is to cover all the N ways. Next, every time the partition should be increase and decrease respectively keeping in mind all the cases.

    Here is the code,

    #include
    #include

    char* partition(int input1[])
    {
               int i=0,n,total=0,loop,round,s1=0;
               while(input1[i]>-1)
               {
                    if(input1[i]==0)return "Invalid";
                    total+=input1[i++];
               }
               n=i;
               round=0;
               while(round < N)
               {
                    loop=round;
                    for(i=0;i<=round-1;i++)
                    s1=s1+input1[i];
                    while(loop < round)
                   {
                       s1=s1+input1[loop];
                       if(s1==(total-s1))return "Yes";
                       s1=s1-input1[loop];
                       loop++;
                   }
                   s1=0;
                   round++;
                }
                return "No";
    }


    Let me know if you have any doubts.


    Problem Statement

    Rahul is playing a very interesting game. He has N disks ( each of equal radius). 
    Every disk has a distinct number out of 1 to N associated with it. Disks are placed one over other in a single pile.

    Rahul wants to sort this pile of disk in increasing order from top to bottom. But he has a very very special method of doing this. In a single step he can only choose one disk out of the pile and he can only put it at the top. 

    Rahul wants to sort his pile of disks in minimum number of possible steps. So help Rahul in doing so. So don't have to show the actual steps just answer the minimum number of possible steps to sort the pile so that that Rahul can check whether he is doing his work right or wrong

    ===============================================================================

    This was a very easy question, but Some of us found it difficult.

    Here goes the explanation,

    If you write it down on a paper then you will notice that We first track the highest numbered disk and then just move the disks with the decreasing number on top of it.

    For example lets take 3 4 5 1 2  as the numbering. 

    Here, since 5 is the highest number I will move only 2 and then 1 on top of it, so the ans comes as 2. 

    There are two steps to solve this problem
    1) First find the max element. then,
    2) Find (P) the number of elements before the max element which are in increasing order. Total-1-P is the ans.

    This logic fetches 100 ont Techgig.

    If anyone wants the code then just give a comment.
    Problem Statement
    You are given an array A[] containing n positive integers. Lets define Bitonic subsequence. A subsequence of array A[] is called Bitonic if it is first strictly increasing and then strictly decreasing. Your task is to find the length of largest bitonic subsequence given an array.

    Note- A sequence sorted in increasing order is considered as Bitonic with decreasing part as empty. Similarly, A sequence sorted in decreasing order is also considered as bitonic with increasing part as empty

    How many of you guys have got the solution for this problem ?

    Well, I have got the logic which work perfect but unfortunately It doesn`t fetch 100 on the Techgig compiler. The problem is not with my Code/Loigc but the problem is Techgig`s definition for Bitonic subsequence. Which can be found here

    Techgig say that the sequence should be strictly increasing and then decreasing where as it can be either way and that too in circular fashion.

    If you refer the previous link we can see that


    3 5 8 9 7 4 2 1
    5 8 9 7 4 2 1 3


    both are bitonic such that 2nd sequence can be converted to first by a circular shift.

    Lets, come to the basic question on Techgig and see how to implement a logic for it.

    I am considering a sequence for example given below.
    9,10,1,3,5,8,2,1,7,5,3,1

    Here starts the actual logic :-
    As we want an subsequence which is first increasing and then decreasing let find the increasing numbers.
    We will be going number by number.

    step 1 : Consider 9, It is the first number so directly put it into a list(Array)
                 9 (List)

    step 2: next is 10, since 10 is greater and 9, put it into same list
                9,10

    step 3: 1, since 1 is less than 10 and we are searching for increasing number, we will create a new list
               9,10
               1
               At this point, If we had any numbers less then 1 in the previous list then those needed to be first      i inserted in the new list and then 1. But we didnt have any here

    step 4: Once we have more than 1 list, every new number has to be checked with the last number of that list and if the new number is greater then it has to be appended to that list. The next number is 3,first check in the previous list if 3 is greater than the last number if it. In our case we have 10 as the last number so we need not append 3.
    Now, 3 is greater than 1, so just append it.
               9,10
               1,3

    Repeat the above steps, we get
              9,10
              1,3,5,8
              1,2
              1,7
              1,5
              1,3
              1
    These are the various lists which we get. Now we can see here that 2nd list has the largest length. But that wont help us, because it may happen the there is not decreasing subsequence for it or may be some other list has a decreasing sequence of greater length.

    Hence, once these lists are formed we perform a similar process for decreasing lists.

    The important thing to keep in mind is the position(in input1[]) of last number in our lists.Because, we need to find the decreasing sequence only after that position.

    For example, lest take our first list 9,10 and try to find the various decreasing sequences for it.

    step 1 :1
    step 2: 1
               3

    step 3: 1
               3

               5   


    step 4: 1
               3

               5
               8

    step 5: 1
               3,2

               5,2
               8,2
    step 6: 1 
               3,2,1
               5,2,1
               8,2,1

    step 7: 1 (Important)
               3,2,1
               5,2,1
               8,2,1
               8,7

    step 8: 1 (Important)
               3,2,1
               5,2,1
               8,2,1
               8,7,5,3,1

    Now, we can see that for increasing order 9,10; we have a decreasing order 8,7,5,3,1 of length 5, so 5+2=7 is the length of this Bitonic.

    Similarly, we can find the decreasing sequences for other lsit`s generated in part I and check the largest length.


               
    Hope this was helpful. There may be other logic for the implementation but this was my own from scratch.
    Also, this can be modified for the circular sequence.

    If anyone want the code for this just put a comment below, and I would share the same.