QuickBits-2: Convert flv to mp4

I had lot of flv video files and wanted to convert it to mp4 for my itouch. Here is the quick way. -f is to force the format to mp4.

$ ffmpeg -i file.flv -f mp4 file.mp4

If you have to convert all files in a folder. Here is the small script. It will convert all flv files to mp4 with the same name with extenstion to mp4.

for file in *.flv
do
ffmpeg -i "$file" -f mp4 "${file%.flv}.mp4
done

QuickBits-1: !$

some times u want to take argument from the previous command you gave

say for example

$ ls /user/ramz/dir1/dir2/dir3/

Now you want to cd to the directory you used in ls command. The quick way is

$ cd !$

- This is equivalent to cd /user/ramz/dir1/dir2/dir3
- !$ - Takes the last argument of previous command.

Segregate even and odd nodes in a Linked List

Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.

Examples:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Input: 8->12->10->5->4->1->6->NULL
Output: 8->12->10->4->6->5->1->NULL

// If all numbers are even then do not change the list
Input: 8->12->10->NULL
Output: 8->12->10->NULL

// If all numbers are odd then do not change the list
Input: 1->3->5->7->NULL
Output: 1->3->5->7->NULL

#include "linkedlist.h"
#include

NODE* createLL(int maxNode)
{
        int index;
        NODE* headNode=NULL;

        for (index = 0; index <= maxNode; index++)
        {
                headNode = addAtHead(headNode, rand()%100);
        }
        return headNode;
}

NODE* segregateEvenOdd(NODE* headNode)
{
        NODE* currentNode = headNode;
        NODE* lastNode = headNode;
        NODE* previousNode = NULL;
        int length = 0;

        /* Find lastNode and length */
        while(currentNode != NULL)
        {
                lastNode = currentNode;
                currentNode = currentNode->next;
                length++;
        }

        currentNode = headNode;
        while(length)
        {
                /* push OddNumber node to last */
                if (currentNode->data % 2 == 1)
                {
                        if (headNode != currentNode)
                        {
                                previousNode->next = currentNode->next;
                                lastNode->next = currentNode;
                                lastNode = currentNode;
                                currentNode->next = NULL;
                                currentNode = previousNode->next;
                        }
                        else
                        {
                                lastNode->next = headNode;
                                lastNode = headNode;
                                headNode = headNode->next;
                                currentNode->next = NULL;
                                currentNode = headNode;
                        }
                }
                else
                {
                        previousNode = currentNode;
                        currentNode = currentNode->next;
                }
                length--;
        }

        return headNode;
}

/* Driver program */
int main()
{
    NODE* headNode=createLL(10);

    printList(headNode);

        headNode = segregateEvenOdd(headNode);

        printList(headNode);
}

Write a C program to remove duplicates from a sorted linked list.

#include
#include "linkedlist.h"

#define LL_LIMIT 6
#define LL_DUP1 4

NODE* createLL()
{
        int index=LL_LIMIT;
        NODE* headNode = NULL;
        while(index > 0)
        {
                headNode = addAtHead(headNode, index);
                if (index == LL_DUP1)
                {
                        headNode = addAtHead(headNode, index);
                }
                index--;
        }
        return headNode;
}

int removeDupNode(NODE* headNode)
{
        NODE* dupNode;
        if (headNode == NULL)
        {
                printf("List is Empty\n");
                return 1;
        }

        while(headNode->next != NULL)
        {
                if(headNode->data == headNode->next->data)
                {
                        printf("Duplicate data is %d\n", headNode->next->data);
                        dupNode = headNode->next;
                        headNode->next = dupNode->next;
                        free(dupNode);
                }
                headNode = headNode->next;
        }
        return 0;
}

int main()
{
        NODE* headNode = NULL;

        headNode = createLL();

        displayAll(headNode);

        if(!removeDupNode(headNode))
        {
                displayAll(headNode);
        }
}

Find Middle of Linked List

#include
#include "linkedlist.h"

#define LL_LIMIT 6
int main()
{
    int midData;
    int index=LL_LIMIT;
    NODE* headNode=NULL;
    NODE* oneStepPtr=NULL;
    NODE* twoStepPtr=NULL;

    /* Create LL*/
    while(index > 0)
    {
        headNode = addAtHead(headNode, index);
        index--;
    }

    /* Display LL*/
    displayAll(headNode);

    oneStepPtr = headNode;
    twoStepPtr = headNode;

    /* Increment step pointers till the end */
    while(twoStepPtr != NULL &&
          twoStepPtr->next != NULL &&
          twoStepPtr->next->next != NULL)
    {
        oneStepPtr = oneStepPtr->next;
        twoStepPtr = twoStepPtr->next->next;
    }
    midData = oneStepPtr->data;

    printf("Middle of LL contains %d\n", midData);
    return 0;
}

Find the Loop in the linked list and remove the loop from it

int detectLoop(NODE* headNode)
{
       NODE* oneStepPtr = headNode;
       NODE* twoStepPtr = headNode;
       int isLoop = 0;

       while(twoStepPtr != NULL
                 && twoStepPtr->next != NULL
                 )
       {
               oneStepPtr = oneStepPtr->next;
               twoStepPtr = twoStepPtr->next->next;

               if (twoStepPtr == oneStepPtr)
               {
                       isLoop = 1;
                       break;
               }
       }
       return isLoop;
}

/* Call only when loop exists */
void removeLoop(NODE* headNode)
{
       /* find Loop Node */
       NODE* oneStepPtr = headNode;
       NODE* twoStepPtr = headNode;
       NODE* loopNode = headNode;

       while(twoStepPtr != NULL
             && twoStepPtr->next != NULL
            )
   	{
       	oneStepPtr = oneStepPtr->next;
       	twoStepPtr = twoStepPtr->next->next;

       	if (twoStepPtr == oneStepPtr)
       	{
                       loopNode = oneStepPtr;
           		break;
       	}
   	}


       /* Find  loopLength */
       NODE* currentNode = loopNode;
       int loopLength = 0;
       while (currentNode != loopNode
                  || loopLength == 0)
       {
               loopLength++;
               currentNode = currentNode->next;
       }


       /* Offset headNode by loopLength */
       currentNode = headNode;
       NODE* offSetNode = NULL;
       NODE* tailNode = NULL;
       int offSetLength = 0;

       while(offSetLength < loopLength)         {                 tailNode = currentNode;                 currentNode = currentNode->next;
               offSetLength++;
       }
       offSetNode = currentNode;


       /* find tailNode, when currentNode and offSetNode meets, but one */
       currentNode = headNode;
       while(offSetNode != currentNode)
       {
               tailNode = offSetNode;
               offSetNode = offSetNode->next;
               currentNode = currentNode->next;
       }

       tailNode->next = NULL;
}

Write a recursive approach to reverse a link list.

void recursiveReverse(NODE** headNode)
{
        NODE* firstNode;
        NODE* restOfNodes;

        if(headNode == NULL)
        {
                printf("List is Empty\n");
                return;
        }

        firstNode = *headNode;
        restOfNodes = firstNode->next;

        if (restOfNodes == NULL)
        {
                return;
        }

        recursiveReverse(&restOfNodes);

        firstNode->next->next = firstNode;
        firstNode->next = NULL;

        *headNode = restOfNodes;
}

Write a program to return the nth node from the end of a linked list.

#include "linkedlist.h"
#include

#define LL_LIMIT 10

/* Create LL */
NODE* createLL()
{
        int index=0;
        NODE* headNode = NULL;
        while(index <= LL_LIMIT)
        {
                headNode = addAtHead(headNode, ++index);
        }
        return headNode;
}

/* get Nth Node from Last */
int getNthNodeLast(NODE* headNode, int nodeNum)
{
                NODE* currentNode1 = headNode;
                NODE* currentNode2 = headNode;
                int count = 0;

                while(currentNode1 != NULL)
                {
                                count++;
                                currentNode1 = currentNode1->next;
                                if(count > nodeNum)
                                {
                                                currentNode2 = currentNode2->next;
                                }
                }

                return currentNode2->data;
}

/* Driver program to test above functions */
int main()
{
                NODE* headNode = NULL;
                headNode = createLL();

                displayAll(headNode);
                printf("3rd Node is %d\n", getNthNodeLast(headNode, 3));
}

Write a C program to remove duplicates from a sorted linked list.

#include
#include "linkedlist.h"

#define LL_LIMIT 6
#define LL_DUP1 4

NODE* createLL()
{
        int index=LL_LIMIT;
        NODE* headNode = NULL;
        while(index > 0)
        {
                headNode = addAtHead(headNode, index);
                if (index == LL_DUP1)
                {
                        headNode = addAtHead(headNode, index);
                }
                index--;
        }
        return headNode;
}

int removeDupNode(NODE* headNode)
{
        NODE* dupNode;
        if (headNode == NULL)
        {
                printf("List is Empty\n");
                return 1;
        }

        while(headNode->next != NULL)
        {
                if(headNode->data == headNode->next->data)
                {
                        printf("Duplicate data is %d\n", headNode->next->data);
                        dupNode = headNode->next;
                        headNode->next = dupNode->next;
                        free(dupNode);
                }
                headNode = headNode->next;
        }
        return 0;
}

int main()
{
        NODE* headNode = NULL;

        headNode = createLL();

        displayAll(headNode);

        if(!removeDupNode(headNode))
        {
                displayAll(headNode);
        }
}

Find Middle of Linked List

#include
#include "linkedlist.h"

#define LL_LIMIT 6
int main()
{
    int midData;
    int index=LL_LIMIT;
    NODE* headNode=NULL;
    NODE* oneStepPtr=NULL;
    NODE* twoStepPtr=NULL;

    /* Create LL*/
    while(index > 0)
    {
        headNode = addAtHead(headNode, index);
        index--;
    }

    /* Display LL*/
    displayAll(headNode);

    oneStepPtr = headNode;
    twoStepPtr = headNode;

    /* Increment step pointers till the end */
    while(twoStepPtr != NULL &&
          twoStepPtr->next != NULL &&
          twoStepPtr->next->next != NULL)
    {
        oneStepPtr = oneStepPtr->next;
        twoStepPtr = twoStepPtr->next->next;
    }
    midData = oneStepPtr->data;

    printf("Middle of LL contains %d\n", midData);
    return 0;
}

Stack using One Queue

Implement a stack using a queue. The operations need not be neccesarily O(1).

#include "queueimplll.h"

typedef struct queue QUEUE;
typedef struct queue_node QUEUE_NODE;

int queuepush( QUEUE *q1, int val)
{

        /* In an empty Q, push the val straight*/
        if (q1->first == 0 &&
        q1->last == 0)
        {
                enqueue( q1, val);
                return 0;
        }

        /* enQ val*/
        if (enqueue(q1, val))
        {
                printf("ERROR: enqueue q2\n");
        }


        /* deQ, enQ by 1 short of QLength*/
        int first_value;
        int qlength = queue_length(q1) - 1;
        while(qlength--)
        {
                dequeue(q1, &first_value);
                enqueue(q1, first_value);
        }

        return 0;
}

/*Driver Program*/
int main()
{
        QUEUE queue1;
        int index;

        init_queue(&queue1);

        for (index = 10; index <= 100; index += 10)
        {
                queuepush( &queue1, index);
        }

        int value = 0;
        index = 0;
        while (!queue_empty_p(&queue1))
        {
                dequeue( &queue1, &value);
                printf("%d : %d\n", index++, value);
        }
}

Stack using two queues

Implement a stack using two queues. The operations need not be neccesarily O(1).

#include stdio.h
#include "queueimplll.h"

typedef struct queue QUEUE;
typedef struct queue_node QUEUE_NODE;

int queuepush( QUEUE *q1, QUEUE *q2, int val)
{

        /* If first queue is empty, enqueue  val straight away*/
        if (q1->first == 0 &&
        q1->last == 0)
        {
                enqueue( q1, val);
                return 0;
        }

        /* Enqueue val into second queue*/
        if (enqueue(q2, val))
        {
                printf("ERROR: enqueue q2\n");
        }

        /* Move (deQ, enQ) from q1 to q2 */
        int first_value;
        while (!queue_empty_p(q1))
        {
                dequeue(q1, &first_value);
                enqueue(q2, first_value);
        }

        /* Move (deQ, enQ) from q2 to q1*/
        while (!queue_empty_p(q2))
        {
                dequeue(q2, &first_value);
                enqueue(q1, first_value);
        }
        /* q1 is ready to be poped up*/

        queue_empty_p(q2);
        return 0;
}

/* Driver program */
int main()
{
        QUEUE queue1, queue2;
        int index;

        init_queue(&queue1);
        init_queue(&queue2);

        /* Push into queue1 */
        srand(time(NULL));
        for (index = 0; index <= 100; index++)
        {
                queuepush( &queue1, &queue2, (rand() % 100) + 1);
        }

        /* Pop from queue1*/
        int value = 0;
        index = 0;
        while (!queue_empty_p(&queue1))
        {
                dequeue( &queue1, &value);
                printf("%d : %d\n", index++, value);
        }
}

Queue with two stacks

Implement a queue using two stacks. The operations need not be neccesarily O(1).

/* Include Stack Implementation (using Array)*/
#include "stackimplarray.h"

void queuepush(STACK* st1, STACK* st2, int val)
{
        /* If first stack is empty, push the value straight down */
        if (st1->size == 0)
        {
                st1->items[st1->size++] = val;
                return;
        }

        /* Pop all elements of first stack
           and push it into second stack */
        while(st1->size != 0)
        {
                push(st2, pop(st1));
        }

        /* Push value onto second stack */
        push(st2, val);

    /* Pop all elements of second stack
           and push it into first stack */
        while(st2->size != 0)
        {
                push(st1, pop(st2));
        }
}


/* Driver code to test above functions*/
int main()
{
        STACK stack1, stack2;
        int i;
        for(i=1; i<=10; i++)
        {
                queuepush(&stack1, &stack2, i * 100);
        }

        while(stack1.size != 0)
        {
                printf("%d\n", pop(&stack1));
        }
}