Showing posts with label Algorithms. Show all posts
Showing posts with label Algorithms. Show all posts

Monday, July 23, 2012

Power of 2 or not ?

How to find a number is power of 2 or not ?


bool IsPowerOfTwo(unsigned long x)
{
    return (x != 0) && (x & (x - 1)) == 0);
}


Explanation:


The above function returns bool (true/false) and accepts one incoming parameter of type unsigned long (x, in this case). Lets take an example, that someone has passed value 4 to the function like:

bool b = IsPowerOfTwo(4);

Now replace each occurance of x with 4:

return (4 != 0) && ((4 & (4-1)) == 0); 


We already know (4 != 0) , so the evaluation of the expression is true.


((4 & (4-1)) == 0)  translates to:


((4 & (3)) == 0) 


But what exactly is  4&3 ? The binary representation of 4 is 100 and of 3 is 011. The & operation says that if both values are equal to 1, then the result is 1. Otherwise it is 0.

100
011

----
000


The result is simply 0. So we go back and look at what our return statement now translates to:

return (4 != 0) && ((4 & 3) == 0);

Which translates now to:

return true && (0 == 0);

return true && true;

We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.

Monday, July 16, 2012

Search in a Circular Sorted Array

Given a circular sorted array say A = { 2,3,4,5,6,7,8,9,0,1 }, find a number in it.

If the array is not circular, we can use binary search to find the key. But if the array is circular we don't know where is the starting point (pivot element). Obviously we can do a linear search to find the element. But if the input array is very large the worst case performance will be very bad. We can take advantage of the fact that the array is sort and use binary search algorithm to find the element in O(N log N).

Approach:



  • Find the middle value of the input array a.
  • If a[0] < a[mid], then all values in the first half of the array are sorted.
  • If a[mid] < a[last], then all values in the second half of the array are sorted.
  • Take the sorted half, and check whether your value lies within it (key lies between the sorted half).

    • If so, binary search that half.
    • If it doesn't, it must be in the unsorted half. Take that half and repeat this process


     
    #include <iostream>
    #include <vector>
    #include <assert.h>
    
    template<typename T, typename type>
    int binary_search(const T& a, int left, 
                      int right, type key) {
    
        while (left <= right) {
            int mid = (right-left)/2 + left;
    
            // base case 1
            if (a[mid] == key)
                return mid;
    
            // mid less than key. Move to right
            if (a[mid] < key) {
                left = mid+1;
            }
            else {
                right = mid-1;
            }
        }
    
        return -1;
    }
    
    template<typename T, typename type>
    int circular_search(const T& a, int left, 
                        int right, type key) {
    
        // base case 1
        int mid = (right-left)/2 + left;
        if (a[mid] == key)
            return mid;
    
        // left array is sorted.
        if (a[0] < a[mid]) {
    
            if (key > a[left] && key < a[mid]) {
                return binary_search(a, left, mid-1, key);
            }
            else {
                return circular_search(a, mid+1, right, key);
            }
        }
        // right array is sorted
        else if (a[mid] < a[right]) {
            if (key > a[mid] && key < a[right])
                return binary_search(a, mid+1, right, key);
            else
                return circular_search(a, left, mid-1, key);
    
        }
    
        return -1;
    
    }
    
    template<typename T>
    void print(const T&a) {
        typedef typename T::const_iterator iterator;
        iterator start = a.begin();
        iterator end = a.end();
        for(; start!=end; ++start)
            std::cout << *start << " ";
        std::cout << std::endl;
    }
    
    int main() {
        typedef std::vector<int> Input;
        Input temp;
        int n =0;
        
        // get n from user
        std::cin >> n;
    
        for(int i=0; i<n; ++i) {
            temp.push_back(i*2);
        }
        Input data;
        data.resize(temp.size());
    
        // Rotate the input sequence
        std::rotate_copy(temp.begin(), temp.begin()+4, 
                         data1.end(), data.begin());
        print(data);
    
        // get key from user
        int key=0;
        std::cin >> key;
    
        int found = circular_search<Input, int>(data, 0, n-1, key);
        if (found)
        {
            assert(key == data[found]);
            std::cout << data[found] 
                      << " found @ pos " 
                      << found << std::endl;
        }
        else
            std::cout << key 
                      << " not found" 
                      << std::endl;
    
        return 0;
    
    }
    
    

    Friday, July 13, 2012

    Hamming sequence

    Hamming's Problem

    Hamming wants an efficient algorithm that generates the list, in ascending order, of all numbers of the form 2i3j5k for i,j,k at least 0. This list is called the Hamming sequence. The list begins like this:
    1 2 3 4 5 6 8 9 10 12 15 16 18 ...

    Brute force technique:

    Take the first number you haven't checked yet, divide it by 2's, 3's and 5's until you can't do that any more, and if you're left with 1, then the number should go on the list; otherwise throw it away and try the next number. So:
    • Is 19 on the list? No, because it's not divisible by 2, 3, or 5.
    • Is 20 on the list? Yes, because after we divide it by 2, 2, and 5, we're left with 1.
    • Is 21 on the list? No, because after we divide it by 3, we're left with 7, which isn't divisible by 2, 3, or 5.
    This obvious technique has one problem: it's unbelievably slow. The problem is that most numbers aren't on the list, and you waste an immense amount of time discovering that. Although the numbers at the beginning of the list are pretty close together, the 2,999th number in the list is 278,628,139,008. Even if you had enough time to wait for the brute-force algorithm to check all the numbers up to 278,628,139,008, think how much longer you'd have to wait for it to finally find the 3,000 number in the sequence, which is 278,942,752,080.

    Linear Solution:

    The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that:
    1) a[j]*2 > a[i - 1] and
    2) j is smallest possible.

    Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5)

     
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int main(void) {
      // get n from user
      unsigned n;
      cout <<"n: ";
      cin >>n;
    
      // list of ugly numbers
      vector <uint64_t> ugly;
      uint64_t x = 1;
      ugly.push_back(x);
    
      // index of next multiple
      unsigned i2 = 0, i3 = 0, i5 = 0;
    
      // value of next multiple
      uint64_t x2 = 2, x3 = 3, x5 = 5;
    
      // loop through ugly numbers
      for(unsigned a = 1; a < n; a++) {
    
        x = std::min(x2, std::min(x3,x5));
    
        ugly.push_back(x);
        if (x == x2) { i2++; x2 = ugly[i2] * 2; }
        if (x == x3) { i3++; x3 = ugly[i3] * 3; }
        if (x == x5) { i5++; x5 = ugly[i5] * 5; }
      }
    
      // return last ugly number found
      cout << x << endl;
      return 0;
    
    }
    

    Sunday, February 01, 2009

    Show that 2^n is O(n!)

    This is an interview question from MS.

    Answer:

    n! = 2*3*...*n >= 2*2*...*2 = 2^(n-1)

    Since 2^n <= 2*n! for all n, we have that 2^n = O(n!).

    Thursday, January 15, 2009

    Monday, January 05, 2009

    Arrange 0's & 1's

    Problem Statement:
    -------------------

    An array of size n among which there are n/2 0s and n/2 1s arranged in random order.
    Arrange all the 1s to left and all 0s to right but it needs to be
    stable i.e., the order of 1s and 0s in the i/p array should be maintained.

    Expected Complexity:
    --------------------------------
    O(N) with constant space.


    Pseudocode:
    --------------------

    1. Have two counters, count1 = 0 and count2 = (n/2)+1
    2. Traverse thru the array, if(arr[ i ] == 1) { arr[ i ] = count1++;} else { arr[ i ] = count2++ };
    3. At the end of the traversal, you have array filled with numbers 0 to n-1


    Now the problem reduces to sorting and array of n numbers which has elements from 0 to
    n-1 occuring only once which can be done in O(n).



    for(j = 0; j <= 1; j++)
    {
    for(i = 0; i<n; i++)
    {
    if(arr[ i ] != i)
    {
    swap(arr[ i ], arr[ arr[ i ] ]);
    }
    }
    }
    </pre>


    Note: j loop runs only twice irrespective on 'n' and has constant complexity. The order of this whole loop is 2*n = O(n).


    4. After the array is sorted, Again traverse thru the array and make elements arr[0] to
    arr[n/2] to '1' and arr[(n/2)+1] to arr[n] as '0'.


    Space complexity is constant and time complexity is O(step2) + O(step3) + O(step4) = n + 2n +n = 4*n = O(n).


    Solution #1 (Stable):
    ------------------------

    <pre name='code' class='cpp'>
    #include<iostream.h>

    int a[] = { 1,0,0,0,1,1,1,0,0,1};
    #define _SIZE sizeof(a)/sizeof(a[0])


    /* Helper Function */
    void printArray()
    {
    for(int i=0;i<_SIZE; ++i)
    cout<<a[i]<<" ";

    cout<<endl;
    }

    int main()
    {

    int countOne = 0;
    int countZero = (_SIZE)/2;
    int i = 0;

    /* Fill the array with numbers from 1 to N */
    for(i=0; i < _SIZE; ++i)
    {

    if(a[i] == 1)
    {
    a[i] = countOne;
    countOne++;
    }
    else
    {
    a[i] = countZero;
    countZero++;
    }
    }
    printArray();

    /* Swap the number and make it a sorted one */
    for(int j = 0; j< 2; ++j)
    {
    for(i=0; i < _SIZE; ++i)
    {
    if(a[i] != i)
    {
    int temp = a[i];
    a[i] = a[a[i]];
    a[temp] = temp;
    }
    }


    }


    printArray();

    /* Fill the 1st N/2 elements with 1 */
    for(i=0; i<_SIZE/2; ++i)
    a[i] = 1;


    /* Fill the last N/2 elements with 1 */
    for(i=_SIZE/2; i<_SIZE; i++)
    a[i] = 0;

    printArray();

    return 0;
    }

    </pre>


    Solution #2 (UnStable):
    -----------------------------------


    Here is a small variation of the quick sort to solve the same problem but this solution is not stable. So I prefer #1.


    <pre name='code' class='cpp'>
    #include<iostream.h>
    using namespace std;
    #define _SIZE sizeof(a)/sizeof(a[0])

    void swap(int *a, int l, int r)
    {
    cout<<"Swaping "<<l<<" "<<r<<endl;

    if(a[l] != a[r])
    a[l] ^= a[r] ^= a[l] ^= a[r];

    return;
    }


    bool compare_1_upper(int *a, int u, int p)
    {

    return (a[u] == p);
    }

    bool compare_1_lower(int *a, int l, int p)
    {
    return (a[l] < p);
    }


    bool compare_0_upper(int *a, int u, int p)
    {
    return (a[u] > p);
    }

    bool compare_0_lower(int *a, int u, int p)
    {
    return (a[u] == p);
    }

    bool (*funcPtr_upper)(int *, int, int) = 0;
    bool (*funcPtr_lower)(int *, int, int) = 0;

    void qPartition(int *a, int low, int upper)
    {
    int pivot = a[low];
    int l = low - 1;
    int u = upper + 1;
    if(a[low])
    {
    funcPtr_upper = compare_1_upper;
    funcPtr_lower = compare_1_lower;
    }
    else
    {
    funcPtr_upper = compare_0_upper;
    funcPtr_lower = compare_0_lower;
    }
    while(1)
    {
    while(funcPtr_upper(a, --u, pivot));
    while(funcPtr_lower(a, ++l, pivot));
    if(l<u)
    swap(a, l, u);
    else
    return;
    }
    return;
    }
    int a[] = { 1,1,1,1,1,0,0,1};
    void print()
    {
    for(int i=0; i< _SIZE; ++i)
    cout<<a[i]<<" ";
    cout<<"\n";
    }
    int main()
    {
    print();
    qPartition(a, 0, _SIZE - 1);
    print();
    return 0;
    }

    Monday, December 29, 2008

    XOR Linkedlist

    Problem:


    Implement a doubly linked list with a single pointer.


    Solution:


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

    /* pray that a long is the size of a struct link* */

    typedef unsigned long pointer;
    struct link
    {
    pointer next_prev;
    int payload;
    };

    typedef struct link link;
    link* add_data(int payload, struct link* list)
    {
    struct link * new_link = (struct link*)malloc(sizeof(link));
    assert(new_link);
    new_link->next_prev = (pointer)list;
    new_link->payload = payload;
    if (list != NULL)
    {
    list->next_prev = (pointer) list->next_prev ^ (pointer)new_link;
    }
    return new_link;
    }

    void walk_list(link *list)
    {
    struct link* prev = 0;
    while (list != NULL)
    {
    pointer next = ((pointer)prev) ^ list->next_prev;
    printf("%d ", list->payload);
    prev = (struct link*)list;
    list = (link*)next;
    }
    printf("\n");
    }

    int main(void)
    {
    link *l1 = add_data(1, NULL);
    link *l2 = add_data(2, l1);
    /* add something to the front ... */
    /* add something to the back ... */
    link *l3 = add_data(3, l2);
    link *l4 = add_data(4, l3);
    link *l5 = add_data(5, l4);

    /* walk from front to back */
    walk_list(l1);
    /* walk from back to front */
    walk_list(l5);

    return 0;
    }

    Dutch Nation Flag Problem

    Problem:

    Given an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.

    This is same as You have an array containing only '0's, '1's and '2's. Club same items together in single scan.

    Solution:

    <br />#include<iostream.h><br />#define _SIZE sizeof(a)/sizeof(a[0])<br />using namespace std;<br />void printArray(int *array, int size)<br />{<br />    for(int i=0; i<size; ++i)=""><br />        cout<<array[i]<<" ";<br />    cout<<endl;<br />    return;<br />}<br />void swap(int *a, int left, int right)<br />{<br />    if(a[left] != a[right])<br />    {<br />        a[left] ^= a[right] ^= a[left] ^= a[right];<br />    }<br />}<br />void reArrange(int *a, int length)<br />{<br />    int low, mid, high = length -1;<br />    low =0; mid = 0;<br />    while(mid <= high)<br />    {<br />        switch(a[mid])<br />        {<br />            case 0 :<br />                swap(a, low, mid);<br />                low++;<br />                mid++;<br />                break;<br />            case 1 :<br />                mid++;<br />                break;<br />            case 2 :<br />                swap(a, mid, high);<br />                high--;<br />                break;<br />            default:<br />                cout<<">>> Error \n";<br />        }<br />    }<br />}<br />int main()<br />{<br />    int a [ ] = { 1,1,1,0,1,2,2,1,0,2,1,2,0 };<br />    printArray(a, _SIZE);<br />    reArrange(a, _SIZE);<br />    printArray(a, _SIZE);<br />    return 0;<br />}<br /><br />

    Wednesday, December 24, 2008

    Search in the Matrix


    We a Matrix where every ROW and COL are sorted something like the below:

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

    Problem: give a number, you need to search whether it is there in the Matrix or not.

    Solution:

    The below solution's complexity is O(m+n) where m - ROW, n - COL

    <br />#include<iostream><br />using namespace std;<br />#define ROW 4<br />#define COL 5<br /><br />int Matrix[ROW][COL] = {<br />    { 1, 3, 5, 7,  9},<br />    { 2, 4, 6, 8, 10},<br />    {11,13,15,17, 19},<br />    {20,40,60,80,100}<br />};<br />bool isValid(int row, int col)<br />{<br />    if(row >= 0 && col < COL)<br />    {<br />        return true;<br />    }<br />    return false;<br />}<br />int main()<br />{<br />    int i = ROW-1;<br />    int j = 0; // Zeroth Column<br />    int searchItem = 0;<br /><br />    cout<<"enter the number to be searched: ";<br />    cin >> searchItem;<br /><br />    while(isValid(i, j))<br />    {<br />        if(Matrix[i][j]== searchItem)<br />        {<br />            cout<<"Item found @ ("<< i<<","<< j << ") :"<< searchItem<< endl;<br />            return 0;<br />        }<br />        else if (Matrix[i][j] > searchItem)<br />        {<br />            //go up, which means reduce the row<br />            i--;<br />        }<br />        else<br />        {<br />            // itea is lesser than the index, go right<br />            j++;<br />        }<br />    }<br />    cout<<"Item not found :("<< endl;<br />    return 0;<br />}<br />

    Tuesday, December 23, 2008

    Palindrome Number

    Check whether a number is palindrome or not ..


    #include<iostream>
    using namespace std;
    bool isPanlindrome(int n)
    {
    int rev = 0;
    int num = n;
    while(n)
    {
    rev = rev * 10 + (n%10);
    n = n /10;
    }
    if(num && num == rev)
    return true;

    return false;
    }
    int main()
    {
    int number = 0;

    cout<<"Enter the number: ";
    cin>>number;

    cout<<number<<" is Panlindrome ?."<< (isPanlindrome(number)? "Yes !!": "No :(!!");
    cout<<endl;
    return 0;
    }

    Monday, December 22, 2008

    String Manipulation

    Given a string : abbbccddddeee
    Encode it to : ab3c2d4e3


    #include<iostream>
    #include <strstream>
    #include<stdlib.h>
    #include<string.h>
    using namespace std;
    void convert(char *input)
    {
    char *start = input;
    char *s1 = input;
    char *s2 = input + 1;

    int len = strlen(input);
    int count = 0;
    char *end = start;
    while(--len && *s1 && *s2 )
    {
    while(*s1 && *s2 && len && *s1 == *s2)
    {
    ++count;
    s2++;
    --len;
    }
    if(count)
    {
    ostrstream str;
    str<<(count+1);
    *start = *s1;
    *++start = *(str.str());
    start = start + strlen(str.str()) - 1;
    count = 0;
    }
    else
    *start = *s1;
    start++;
    s1 = s2;
    s2++;
    }
    if(*s1 != *(s1-1))
    *start++ = *s1;
    *start = *s2;
    cout<<"Magic: "<<end<<endl;
    return;
    }
    int main()
    {
    char input[100];
    memset(input, 0, 100);
    cout<<"Enter the string: ";
    scanf("%s", input);
    cout<<"You entered: "<<input<<"!!\n";
    convert(input);
    return 0;
    }

    Thursday, December 18, 2008

    Array Rotation

    A[M][N] is an array rotated in anti clock wise that is A'[N][M]. then mapping A[j]=A'[ _ ][ _ ] in terms of M,N

    A
    1 2 3
    4 5 6

    A'
    3 6
    2 5
    1 4


    A[j]=A'[ _ ][ _ ] ??


    Solution:


    i' = N-j-1
    j' = i
    thus after rotation
    A'[i ][j] = A[N-j-1][ i]

    KMP string matching

     
     
    #include<iostream>
    
    void preProcess(int *kmpNext, 
                    const char *pattern) {
        int j = -1;
        int i = 0;
        kmpNext[i] = j;
        int len = strlen(pattern);
    
        while(i<len) {
            while(j >=0 && pattern[i] != pattern[j]) 
                j=kmpNext[j];    
    
            ++i;++j;
            kmpNext[i] = j;
    
            if (pattern[i] == pattern[j])
                kmpNext[i] = kmpNext[j];
            else
                kmpNext[i] = j;
        }
        
        return;    
    }
    
    void match(const char *str,
               const char *pattern,
               const int *pre) {
        int m = 0;
        int i = 0;
        int len = strlen(str);
        
        while(m+i < len) {
            if(str[m+i] == pattern[i]) {
                i++;
    
                if(i == strlen(pattern)) {
                    std::cout << "Match found at index: " 
                              << m << std::endl;
                }
            }
            else {
                m = m + i - pre[i];
                if(i > 0) {
                    i = pre[i];
                }
            }
        }    
        return;
    }
    
    void KMP() {
        char String [] = "abcabcabdewqabcabd";
        char pattern [] = "abcabd";
        
        int *pre = new int [strlen(pattern)+1];
        memset(pre, 0, (strlen(pattern)+1) * sizeof(int));
        
        /* Preprocess the table */
        preProcess(pre, pattern);
    
        for(int i =0; i<strlen(pattern)+1; ++i)
            std::cout << pre[i] << " ";
        std::cout << std::endl;
    
        /* Match the string */
        match(String, pattern, pre);
    
        delete pre;
        return;
    }
    
    int main() {
        KMP();
        return 0;
    }
    

    Matrix Filp

    Matrix Flip


    void BitFlip()
    {
    int c = 1;
    int r = 1;
    int i, j;

    print();
    for(i=0; i<5; ++i)
    r &= BitArray[0][i];

    for(i=0; i<5; ++i)
    c &= BitArray[i][0];

    for(i=1; i<5; ++i)
    {
    for(j=1; j<5; ++j)
    {
    if(! BitArray[i][j] )
    {
    BitArray[i][0] = 0;
    BitArray[0][j] = 0;
    }
    else
    {
    BitArray[i][j] = 0;
    }
    }
    }

    for(i=1; i<5; ++i)
    {
    for(j=1; j<5; ++j)
    {

    if(BitArray[i][0] && BitArray[0][j])
    BitArray[i][j] = 1;
    }
    }

    if(r == 0)
    for(i=0; i<5; ++i)
    BitArray[i][0] = 0;

    if(c ==0)
    for(i=0; i<5; ++i)
    BitArray[0][i] = 0;

    print();

    return;
    }

    Wednesday, December 17, 2008

    Max sum in the array

    #include<iostream>
    using namespace std;

    #define _SIZE sizeof(array)/sizeof(array[0])
    #define max(a,b) a>b ? a:b
    int main()
    {
        int array[] = { 0, 1, 2, -3, 5, 6, -5, 1, };
        int MaxSoFar = 0;
        int MaxCurrent = 0;
        for(int i = 0; i<_SIZE; ++i)
        {
            MaxCurrent = max(MaxCurrent+array[i], 0);
            MaxSoFar = max(MaxCurrent, MaxSoFar);
        }
        std::cout<<"Max sum in the array: "<< MaxSoFar<<"\n";
        return 0;
    }

    Thursday, December 04, 2008

    Find the start in the circular shifted array

    A sorted array, with over a million elements in it, is rotated clockwise. Find out the index where the sorted list starts.



    int find_index(int *a,int start,int end)
    {
    int mid = (start+end)/2;
    if (a[start] < a[mid] < a[end])
    return start;
    else if(a[start] > a[mid])
    return find_index(a, start, mid);
    else if(a[mid] > a[end])
    return find_index(a, mid, end);
    }

    Compute no of digits after '.' in float

    Compute the number of digits after '.' in a floating point number.

    e.g. if given 3.554 output=3
    for 43.000 output=0


    double no = 3.44;
    int count = 0;
    while(no!=((int)no))
    {
    count++;
    no=no*10;
    }
    printf("%d",count);

    Wednesday, December 03, 2008

    Reduce the comparisons in Binary Search

    Normally there will be 2 comparisons that will be made in Binary Search Algorithm like

    if(value > array[mid])
       low = mid
    else (value < array[mid])
       high = mid
    else (value == array[mid])
       found the value

    we have to reduce the number of comparisons made in the above code.

    #include <stdio.h>

    int array [ ] = { 0, 1,2,3,4,5,6,7,8,9 };
    int bin_search(int val)
    {
        int low=0;
        int high = sizeof(array)/sizeof(array[0]) - 1;
        int mid;
        while(low < high)
        {
                mid = (low+high)/2 ;
                if(array[mid]<val)
                   low = mid+1;
                else
                   high = mid;
        }
        if(array[low] == val)
        {
           return val; // found the value
        }
        else
           return -1; // not found
    }
    int main()
    {
        int i;
        for( i=0; i< 11; ++i)
                printf("Return: %d\n", bin_search(i));
       
        return 0;
    }

    Wednesday, June 11, 2008

    Swap two pointers

    Our task is to two pointers which is pointing to two objects. The problem is very simple and remember to use pointer to pointer concept. Without that it is just a pass by value to the function.


    #include<stdio.h&gt;
    void swap(int **firstPtr, int **secondPtr)
    {
    int *temp = *firstPtr;
    *firstPtr = *secondPtr;
    *secondPtr = temp;

    return;
    }

    int main()
    {
    int a = 10;
    int b = 20;

    int *aPtr = &a;
    int *bPtr = &b;

    printf("Before Swapping, Address : %x %x, Value : %d %d\n", aPtr, bPtr, *aPtr, *bPtr);
    swap(&aPtr, &bPtr);
    printf("After Swapping, Address : %x %x, Value : %d %d\n", aPtr, bPtr, *aPtr, *bPtr);
    }

    If you compile and see the result, the pointers would be swapped ..

    Tuesday, June 10, 2008

    Write your own tail -n implementation

    This is one of the question asked in Adobe to my friend. You need to implement your own tail function. read the man page for more information about tail command.

    I could able to think of two ways to solve the problem. [tail -n 10 filename ]

    Solution 1:

    Keep 2 pointers, 1st points to the start of the file, the 2nd points to the n+1 th line :

    if the file is not big enough [ less than n ] then dump the content of the file from the beginning to the end of the file and return
    else move the second pointer by one line and move the 1st pointer by one until the second reaches EOF. One the 2nd pointer reaches the end of the file, dump the content from where the 1st pointer currently pointing till the end of the file.

    This is one of the solution me and Arun discussed when I was there in Hyderabad. But there are lot of improvements that we can do in this and the companies expect such kind of answers (just for the interview sake)

    Problem: One of the biggest problem with the above solution is the performance. Both the pointers are reading the same content (2 times reading the same content). Since disk I/O is costly this is a real performance issue.


    Solution 2 :

    The next solution is instead of reading from the file twice, create a buffer to hold the content, read the file from the end of the file and dump it into the buffer, also keep track of the no of lines read so far from the end. Once the required no of lines read, print the content of the buffer from the end.


    My Implementation :


    #include <stdio.h&gt;
    #include <stdlib.h&gt;
    #include <string.h&gt;
    #include <sys types.h>
    #include <sys stat.h>
    #include <fcntl.h&gt;

    void tail(int lines, char *file_name)
    {
    struct stat file;
    int size = 0;
    char *ch = NULL;
    char *buf = NULL;

    FILE *fd = fopen(file_name, "r");

    if(fd == NULL)
    {
    printf("Not able to open the file : %s\n", file_name);
    return;
    }

    // Set the pointer to the end
    fseek(fd, 0, SEEK_END);

    // Find the size of the file
    size = ftell(fd);
    --size;

    // Allocate the buffer to hold the content
    ch = (char *)malloc(2);
    buf = (char *)malloc(80 * lines);
    memset(buf, 0, 80 * lines);

    char * start = buf;
    *buf++ = '\0';

    // Copy the file content from the end of the file in the reverse order into the buffer
    // Use fseek --> SEEK_SET to navigate the file from the back

    while(size && lines)
    {
    --size;
    fseek(fd, size , SEEK_SET);
    fread(ch, 1, 1, fd);
    *buf++ = *ch;
    if(*ch == '\n')
    lines--;


    }
    close(fd);

    // Print the content of the buffer
    while( start != buf)
    printf("%c", *buf--);

    printf("\n");
    return;
    }
    int main(int argc, char **argv)
    {
    if(argc != 3)
    {
    printf("Run exe file_name no_of_lines\n");
    return (-1);
    }

    char *file = argv[1];
    tail(atoi(argv[2]), file);

    return 0;
    }


    input file :cat ganesh
    1 Ganesh
    2 Vishnu
    3 Ramak
    4 Arun
    5 Jerome

    Output:

    # ./a ganesh 2

    4 Arun
    5 Jerome

    # ./a ganesh 4

    2 Vishnu
    3 Ramak
    4 Arun
    5 Jerome

    ./a ganesh 10
    1 Ganesh
    2 Vishnu
    3 Ramak
    4 Arun
    5 Jerome

    PS : Guys don't get envy that I wrote a big program for myself. I struggled a lot to make this program to work :-)