Insertion Sort ( reverse)

 

Orginal insertion sort will sort elements from starting of the array. This program will sort the elements from end of the array.

/*Insertion Sort*/

#include<stdio.h>
void insertion(int A[], int n);
void print_array(int A[],int n);
main()
{
    int arr[]={7,6,5,4,2,3,1,8,10,9}; // Input Array

    int size = (int)(sizeof(arr)/sizeof(arr[0])); //Calculate size of array

    int itr ; // Iterator

    insertion(arr,size); // Insertion function

    print_array(arr,size);
}

void print_array(int A[], int n)
{
    int itr;

    // Printing array after sorting
    for(itr=0;itr<n;itr++)
    printf("%d ",A[itr]);
}

void insertion(int A[], int n)
{
    int i , j , key;
    for(j=n-1;j>=0;j--)
    {
        key=A[j];
        i=j+1;
        while((i<=n)&&(A[i]<key))
        {
            A[i-1]=A[i];
            i=i+1;
        }
        A[i-1]=key;
    }
}

Insertion Sort (orginal)

 

/*Insertion Sort*/

#include<stdio.h>
void insertion(int A[], int n);
main()
{
    int arr[]={7,6,5,4,2,3,1,8,10,9}; // Input Array

    int size = (int)(sizeof(arr)/sizeof(arr[0])); //Calculate size of array

    int itr ; // Iterator

    insertion(arr,size); // Insertion function

    // Printing array after sorting
    for(itr=0;itr<size;itr++)
    printf("%d ",arr[itr]);
}

void insertion(int A[], int n)
{
    int i , j , key;
    for(j=1;j<n;j++)
    {
        key=A[j];
        i=j-1;
        while((i>=0)&&(A[i]>key))
        {
            A[i+1]=A[i];
            i=i-1;
        }
        A[i+1]=key;
    }
}

Output:

1 2 3 4 5 6 7 8 9 10

 

Time Complexity: O(n^2)

GroupOn Telephonic Interview Questions

 

Questions will be simple. But, working code is MUST. Telephonic Interview over Skype. Writing code is mandatory.

Questions are

1. Program to print the elements in a tree vertically
2. Given an input tree. Program to create a new tree which is the mirror of an input tree.
3. Root to leaf path which is having the given sum
4. Given the output of runlength encoding. Construct the array
5. Array implementation of stack & queues
6. N-stacks implement in an single array.

IBM ISL Interview

 

This interview is for AIX testing position.

Round – 1 was around 2 hours. it includes C, datastructures, OS , multithreading , Linux, Shell.

1. Difference between process & threads
2. How the following system calls will work: fork , read, open , write.
3. Difference between open & fopen.
4. A program that creates a thread.
5. A program with multi thread
6. A program with  the implementation of thread join & synchronization.

OS concepts & linux
7. Fragmentation & types
8. Paging & type  of allocation
9. Scheduling
10. Process memory layout
11. Process states
12. Difference between zombie & orphan process
13. How to find zombie & orphan process in linux using commands.
14. uses of chown , chmod, df , free, top, /proc & some other linux admin commands.
15. question s in sed , awk , grep
16. pipe & examples
17. writing simple shell scripting programs

C programs
18. Program to reverse a string (with & without recursion)
19. Program to reverse a linked list
20. Program to add two numbers (in linked list)
21. program to sort the linked list (own logic)
22. function call by value, call by reference
23. program to swap bytes in an integer
24. questions in padding
25. questions in pointers

26. what is meant by system testing
27. what all testing i have done in previous experience

Round –2 : it was around half an hour. it consists of unix & shell questions.

1. System programming questions like, using a system call in a program
2. writing makefiles
3. shell script program;
Input: hello
Output: h  e  l l  0
4. some other simple shell script programs & some command functionalities in linux

Round – 3 : It was around half an hour. It is a HR + Manager round

1. some questions about testing
2. why leaving the old company
3. why IBM ISL
4. Other general HQ questions

Process (notes)

 

- a program in execution
- a process contains -> program counter, process stacks & data section.

- process memory layout

Command Line Aruguments

Stack

Stack grows down & Heap grows Up

Heap

Data section (includes BSS)

Text section

    CLA - command line arguments,stored at higher address
    stack - local variables & other info (return info,machine register) stored. In each recursive call, new stack frame is created.
    headp - dynamic memory allocation, shared to all process.
    BSS - Block started by symbol (uninitialized global data)
    data segment - initialized global variables
    text - contains machine instrucitons that cpu executes, shared across various instances of same program. (read only privileges, avoid rewriting)

- process states

    new - a process being created
    ready - instructions are executed
    waiting - waiting for some event
    running - waiting to be assigned to processor
    terminate(done) - process has finished

- zombie process – system is referencing the process even if process is  terminated.

- info associated with each process
    Process state
    Program counter
    CPU registers
    CPU scheduling information
    Memory-management information
    Accounting information
    I/O status information

- process queues - job , ready , device
- process scheduler
    - Long term (job) - selects which process to put in ready queue (frequent invoked - very fast)
    - Short term (cpu) - selects which process to execute & allocate CPU (infrequently invoked - very slow)
   
- context switch
    - switching from one process to another, system saves the state of the one process & load the state of new process

- processes can be independent or cooperating
- cooperating process need IPC - shared memory , message passing
    - advantage for co-operating process
        - info sharing
        - computation speedup
        - convenient
        - modularity

    - message passing
        - send /recieve
        - establish connection
        - blocking send / non-blocking
    - shared memory
        - producer consumer problem

Compilation steps of a C program

There are four steps

1. Preprocessing
2. Compilation
3. Assembling
4. Linker

STEPS	INPUT	OUTPUT	GCC
Pre Processing	source file	preprocessed output (removing all # defines & replacing macros)	gcc -E a.c output will be printed in console where we can see all the Macro are replaced.
Compilation	Preprocessed output file	Assembly language code	gcc -S a.c output will be in a.s file
Assembling	Assembly code	Machine code	gcc -c a.c output will be in a.o
Linker	Machine code	executable file	gcc a.c output will be a.out file