OS Puzzle: Can it happen?

Consider two different threads are running the same piece of code below. When it will print the following ?

1. x is 7
2. x is 8
3. x is 9
4. x is 10

shared int x; 
x = 10; 
while (1) 
{ 
 x = x - 1; 
 x = x + 1; 
 if (x != 10) 
  printf(“x is %d”,x) 
}

Effective Endian conversion in x86

Instead of Using the bit shift operators, we can use the assembly instruction bswap provided by x86 systems.
I am using the EAX Register for manipulation because it is the same register used for returning value. So i dont need any extra instruction to move my variable to EAX register

Embedded: Edge vs Level Triggered Interrupts

S.No	Edge Triggered Interrupts	Level Triggered Interrupts
1	Can cause high spurious Interrupts (if there is no signal proper filters, but can be avoided with filters)	Minimal Spurious Interrupts
2	If the Pulse is very short it needs dedicated HW to detect it	It is easy to detect the Level triggered Interrupts
3	From H/W Perspective more gates and complex to implement	Less gates required and Less complex to implement
4	Not good for Interrupt Sharing. As if we dont clear the interrupt immediately it will cause other device interrupt to get lost. (But can be avoided if we clear the interrupt immediately)	Good for Interrupt sharing with devices.
5	No Lockup problem	If there is any interrupt without the handler to clear it will cause the whole system to Lockup
6	While Processing the interrupt first Clear the interrupt and then process	Process the interrupt and then Clear. (or else may get the same interrupt again)

Verdict:  Edge Triggered Interrupts are preferred.

QuickBits-12: Bash Shortcuts for Geeks

 

These are some of the shortcuts that i use ...

Command Editing Shortcuts

• Ctrl + a – go to the start of the command line
• Ctrl + e – go to the end of the command line
• Ctrl + k – delete from cursor to the end of the command line
• Ctrl + u – delete from cursor to the start of the command line
• Alt + d – delete to end of word starting at cursor (whole word if cursor is at the beginning of word)
•  Ctrl + w – delete from cursor to start of word (i.e. delete backwards one word)

 

Command Recall Shortcuts

• Ctrl + r – search the history backwards
• Ctrl + g – escape from history searching mode
• Ctrl + p – previous command in history (i.e. walk back through the command history)
• Ctrl + n – next command in history (i.e. walk forward through the command history)
• Alt + . – use the last word of the previous command
• Ctrl + o -  This command is my favourite. If you hit CTRL+o after picking a command from your history, the command is executed, and the next command from history is prepared on the prompt.
•  

Command Control Shortcuts [Not a Bash Feature]

• Ctrl + l – clear the screen
• Ctrl + s – stops the output to the screen (for long running verbose command)
• Ctrl + q – allow output to the screen (if previously stopped using command above)
• Ctrl + c – terminate the command
• Ctrl + z – suspend/stop the command
•  

Bash Bang (!) Commands

• !! - run last command
• !blah – run the most recent command that starts with ‘blah’ (e.g. !ls)
• !$ – the last word of the previous command (same as Alt + .)
• !* – all of the previous command except for the first word (e.g. if you type ‘ls foo foo/bar foo/bar/foo‘, then !* would give you ‘foo foo/bar foo/bar/foo‘)
• ^^ - If you type a command and run it, you can re-run the same command but substitute a piece of text for another piece of text using ^^ (e.g.: if you run 'ls this/is/cool/stuff' and if you do '^cool^geek' then it will run 'ls this/is/geek/stuff'. It replaces only the first occurance)
• !!:gs/search/replace/ - It is same as previous except it replaces all occurance

 Tricks with ~/.inputrc

• Put this in your ~/.inputrc

"\e[A": history-search-backward
"\e[B": history-search-forward
"\C-p": history-search-backward
"\C-n": history-search-forward

Type something, then pressing Ctrl-p(or Ctrl-n) will initiate the search in the history with the already typed text as prefix

•  

QuickBits-11: Giving User Input to cmd through file

Lots of user developed commands requires user input for "if you want to continue ... [y/n]" . If you want to automate this

For example: If mycommand requires user input saying 'y' then add 'y' to the arguments.txt file.

cat arguments.txt - | mycommand

Now your mycommand will not ask for user input. It takes it from the file arguments.txt

QuickBits-10: Highlight a word in Emacs buffer

If you have used Source Insight for code browsing, you would have used its word hightlight feature.You can highlight the word under cursor, in your file you are browsing using shift+f8.

You can do the same in Emacs, by adding this to your .emacs file

 
(defun is-word-highlighted ()
  (interactive)
  (let ((face (or (get-char-property (point) 'read-face-name)
                  (get-char-property (point) 'face))))
   (if (facep face) (if (face-equal face "hi-yellow") t nil) nil)))

(defun toggle-highlight-word ()
(interactive)
(setq sym (current-word))
(if (is-word-highlighted) (unhighlight-regexp sym) (highlight-regexp sym)) 
)

(global-set-key [S-f8] 'toggle-highlight-word)

QuickBits-9: Search String in files

1. To search for a string/regular expression in all files in a folder

grep -H "string" * 

This will print the matching line.
-H is for printing the matching filename.

2. To search for a string/regular expression in all files in a folder + subfolders

grep -H "string" * -r

3. To search for a string in all files of certain type

find . -name "pattern" -exec grep -H "string" {} \;



grep -H "string" $(find . -name "pattern")

Example: To find string "main" in all .c file

find . -name "*.c" -exec grep -H "main" {} \;



grep -H "main" $(find . -name "*.c")

QuickBits-8: Remove Duplicate Lines in a File

To Remove duplicate lines in a file and print it

 cat filename | sort | uniq  

sort will sort the lines and
uniq will remove adjacent duplicate lines.

To count the number of repetition of each line

 cat filename | sort | uniq -c

QuickBits-7: Convert .a file to .so file

.a files are just archive of .o object files. You need to just extract the files from the archive and package them as a shared object (.so).

ar -x myarchive.a



gcc -shared -Wl,-soname,mysharedlib.so *.o -o mysharedlib.so

QuickBits-6: Search and Kill Process

Many a times we need to find a process and kill it. The best way to Find a process is

Search

 pgrep -l [pattern] 

-l will list the name of the process or else only pid will be displayed. pgrep searches for the match in any part of the name including the arguments to the command.

Example:

 pgrep -l work



output

217 kworker/u:3

218 kworker/u:4

219 kworker/u:5

863 NetworkManager

900 ./a.out work

Search & Destroy

 pkill [pattern]

It will find and kill all the process that matches the Pattern.

QuickBits-5: Searching for previous commands

How to search and run the same command in bash ?

1. Up / down arrow keys [ good for previous few commands ]

2. Type ctrl+r and type any part of the command including its arguments. Bash will find and run it for you. Keep pressing ctrl+r until u find the right command.

Say you have run the following command sometime back

cd /myfolder/personal/secret/

you can search by typing ctrl+r and typing secret. Bash will find this command for you.

QuickBits-4: sshfs

If you have ssh access to another PC and you want to access the folder of that PC the best way is to ssh mount that.

 sshfs username@hostname:/folder /mountfolder 

With this command the the /folder on the ssh host is mounted locally to /mountfolder. And you can access it as local folder.

To unmount the mounted folder

 fusermount -u /mountfolder 

QuickBits-3: Vim diff

Most often when you are working in shell you want to find diff between two files and merge them. vimdiff is very good utility.

 vim -d file1 file2 

Keyboard Shortcuts:

ctrl+w ctrl+w - switch windows
do                                - diff obtain
dp                                - diff put
[c                                - previous difference
]c                                - next difference
:diffupdate                       - diff update ;)
:syntax off                       - syntax off
zo                                - open folded text
zc                                - close folded text

A Boolean Array Puzzle

Input: A array arr[] of two elements having value 0 and 1

Output: Make both elements 0.

Specifications: Following are the specifications to follow.
1) It is guaranteed that one element is 0 but we do not know its position.
2) We can’t say about another element it can be 0 or 1.
3) We can only complement array elements, no other operation like and, or, multi, division, …. etc.
4) We can’t use if, else and loop constructs.
5) Obviously, we can’t directly assign 0 to array elements.

void changeToZero(int a[2])
{
   a[ a[1] ] = a[ !a[1] ];
}

int main()
{
   int a[] = {1, 0};
   changeToZero(a);

   printf("arr[0] = %d \n", a[0]);
   printf("arr[1] = %d ", a[1]);
   getchar();
   return 0;
}

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;
}