Eligibility for CPM JKC

Eligibility for applying in CPM JKC???

• All ECE, CSC,ME, EEE, CSIT of B.Tech and B.E including MCA can apply for this CPM JKC.
• Only registered students can participate in the Placements of CPM JKC. 
  
• The candidate must have minimum aggregate mark of 65%.
• The candidate can register in 3rd year of his college.
• Its not compulsory to clear all the subjects in first attempt itself.

If you need any further information you can contact at mail them at ieg.admin@gmail.com

Ten Commands Every Linux Developer Should Know

http://www.linuxjournal.com/article/7330

C Interview Programs

1. Are expressions arr and *arr same for array of integers?
2. Are variables argc and argv are local to main?
3. Bitwise operator for checking whether particular bit is on or off?
4. Bitwise operator for putting on particular bit in number?
5. Bitwise operator for turning off particular bit in number?
6. Can Structure contain Pointer to itself?
7. Can there be at least some solution to determine number of arguments passed to variable argument list function?
8. Can we specify variable field width in scanf() format string? If possible how?
9. Can you dynamically allocate arrays in expanded memory?
10. Can you use function fprintf() to display output on screen?
11. Can you write function similar to printf()?
12. Describe about storage allocation and scope of global, extern, static, local and register variables?
13. Difference : Strings and Arrays?
14. Difference : Structure and Unions?
15. Difference : arrays and linked list?
16. Difference : enumeration and set of pre-processor # defines?
17. Difference : functions memmove() and memcpy()?
18. Difference : functions rand(), random(), srand() and randomize()?
19. Difference : main() in C and main() in C++?
20. Difference : pass by reference and pass by value?
21. Difference : strdup and strcpy?
22. Differentiate between for loop and while loop? it uses?
23. Does mentioning array name gives base address in all contexts?
24. Does there exist any other function that can be used to convert integer or float to string?
25. Does there exist any way to make command line arguments available to other functions without passing them asarguments to function?
26. Explain one method to process entire string as one unit?
27. How are Structure passing and returning implemented by complier?
28. How can called function determine number of arguments that have been passed to it?
29. How can we check whether contents of two structure variables are same or not?
30. How can we read/write Structures from/to data files?
31. How much maximum can you allocate in single call to malloc()?
32. How will you declare array of three function pointers where each function receives two ints and returns float?
33. If we want that any wildcard characters in command line arguments should be appropriately expanded, are we required to make any special provision? If yes, that?
34. In header file whether functions are declared or defined?
35. In header files whether functions are declared or defined?
36. Increase size of dynamically allocated array?
37. Increase size of statically allocated array?
38. Out of fgets() and gets() that function is safe to use and why?
39. Program : compare two strings without using strcmp() function.
40. Program : concatenate two strings.
41. Program : find Factorial of number.
42. Program : generate Fibonacci Series?
43. Program : interchange variables without using third one.
44. Program : s for String Reversal. same for Palindrome check.
45. Program : that employs Recursion?
46. Program : that uses command line arguments.
47. Program : that uses functions like strcmp(), strcpy(), etc.
48. To that numbering system can binary number be easily converted to?
49. Use bsearch() function to search name stored in array of pointers to string?
50. Use functions fseek(), freed(), fwrite() and ftell()?
51. Use functions memcpy(), memset(), memmove()?
52. Use functions randomize() and random()?
53. Use functions sin(), pow(), sqrt()?
54. Use qsort() function to sort array of structures?
55. Use qsort() function to sort name stored in array of pointers to string?
56. What advantages of using Unions?
57. What do functions atoi(), itoa() and gcvt() do?
58. What do ‘c’ and ‘v’ in argc and argv stand for?
59. What does error ‘Null Pointer Assignment’ mean and what causes this error?
60. What does static variable mean?
61. What is NULL Macro? Difference : NULL Pointer and NULL Macro?
62. What is NULL Pointer? Whether it is same as uninitialized pointer?
63. What is far pointer? where we use it?
64. What is linklist and why do we use it when we have arrays? – I feel correct answer should be linklist is used in cases where you don’t know memory required to store data structure and need to allocate is dynamically on demand.
65. What is maximum combined length of command line arguments including space between adjacent arguments?
66. What is near, far and huge pointers? How many bytes are occupied by them?
67. What is object file? How can you access object file?
68. What is pointer?
69. What is recursion?
70. What is similarity between Structure, Union and enumeration?
71. What is static identifier?
72. What is structure?
73. What is use of typedef?
74. When reallocating memory if any other pointers point into same piece of memory do you have to readjust these other pointers or do they get readjusted automatically?
75. Where are auto variables stored?
76. Where does global, static, local, register variables, free memory and C Program instructions get stored?
77. Write down equivalent pointer expression for referring same element a[i][j][k][l]?
78. advantages of using pointers in program?
79. advantages of using typedef in program?
80. bit fields? What is use of bit fields in Structure declaration?
81. declare following: array of three pointers to chars, array of three char pointers, pointer to array of three chars, pointerto function that receives int pointer and returns float pointer, pointer to function that receives nothing and returns nothing
82. detect loop in linked list?
83. differences between malloc() and calloc()?
84. differences between structures and arrays?
85. different storage classes in C?
86. dynamically allocate one-dimensional and two-dimensional array of integers?
87. enumerations?
88. implement substr() function that extracts sub string from given string?
89. macros? advantages and disadvantages?
90. obtain current time and Difference : two times?
91. obtain segment and offset addresses from far address of memory location?
92. print string on printer?
93. register variables? advantage of using register variables?
94. that function should be used to free memory allocated by calloc()?
95. that header file should you include if you are to develop function that can accept variable number of arguments?

Semaphore Vs Mutex

Semaphore owns the resource ownership whereas mutex doesn't.Means when the semaphore enters the critical section by setting the sem_flag as one but because of some means(lets say dead lock) it gets blocked inside the critical section waiting for another resource,which is being used by another process/thread.So now no other process can enter the  critical section ...almost deadlock..means no other process can unset the sem_flag to zero..=> implies the process which sets the lock/flag has to unlock the flag.No other process/thread has the permission to unlock..

On the other hand, mutex doesn't own the ownership means even if it gets blocked inside the crtitical region,any other process can enter the critical section.

1. A semaphore post (or basically unlock) can be performed by  a different thread. However, in the case of mutex, it should be unlocked only by the same thread.
2. A semaphore post is always remembered. In other words, a producer thread can signal an unlock even when no consumer thread is waiting for data. In this case, when a consumer thread comes up and tries to block on a call to sem_wait (or locking), it can proceed further and gain control of the semaphore (which had been signalled before by the producer thread). This does not happen with a mutex - any unlock from another thread is lost.

When Can I use select or Poll

 

If you have the packet flow very frequent at that time you can use poll()

 

If your packet arriving rate is somewhat slower in millisec then you can use select()

QuickSort Program in C

void swap(int *a, int *b)
{
  int t=*a; *a=*b; *b=t;
}
void sort(int arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

Little Endian Big Endian OS

A beginner introduction to Endianness.

Introduction

A long time ago, in a very remote island known as Lilliput, society was split into two factions: Big-Endians who opened their soft-boiled eggs at the larger end ("the primitive way") and Little-Endians who broke their eggs at the smaller end. As the Emperor commanded all his subjects to break the smaller end, this resulted in a civil war with dramatic consequences: 11.000 people have, at several times, suffered death rather than submitting to breaking their eggs at the smaller end. Eventually, the 'Little-Endian' vs. 'Big-Endian' feud carried over into the world of computing as well, where it refers to the order in which bytes in multi-byte numbers should be stored, most-significant first (Big-Endian) or least-significant first (Little-Endian) to be more precise

• Big-Endian means that the most significant byte of any multibyte data field is stored at the lowest memory address, which is also the address of the larger field.
• Little-Endian means that the least significant byte of any multibyte data field is stored at the lowest memory address, which is also the address of the larger field.

For example, consider the 32-bit number, 0xDEADBEEF. Following the Big-Endian convention, a computer will store it as follows:

Figure 1. Big-Endian: The most significant byte is stored at the lowest byte address.

Whereas architectures that follow the Little-Endian rules will store it as depicted in Figure 2:

Figure 2. Little-endian: Least significant byte is stored at the lowest byte address.

The Intel x86 family and Digital Equipment Corporation architectures (PDP-11, VAX, Alpha) are representatives of Little-Endian, while the Sun SPARC, IBM 360/370, and Motorola 68000 and 88000 architectures are Big-Endians. Still, other architectures such as PowerPC, MIPS, and Intel�s 64 IA-64 are Bi-Endian, i.e. they are capable of operating in either Big-Endian or Little-Endian mode. [1].

Endianess is also referred to as the NUXI problem. Imagine the word UNIX stored in two 2-byte words. In a Big-Endian system, it would be stored as UNIX. In a little-endian system, it would be stored as NUXI.

Function	Purpose
ntohs	Convert a 16-bit quantity from network byte order to host byte order (Big-Endian to Little-Endian).
ntohl	Convert a 32-bit quantity from network byte order to host byte order (Big-Endian to Little-Endian).
htons	Convert a 16-bit quantity from host byte order to network byte order (Little-Endian to Big-Endian).
htonl	Convert a 32-bit quantity from host byte order to network byte order (Little-Endian to Big-Endian).

Linux is Little endian

Solaris is Big endian

A) Little-Endian is low emissions byte address in the low-memory, high emissions bytes in the memory address of the high end.
  B) is the Big-Endian emissions in the high-byte memory address low-, and low emissions in memory byte address the high end.
  C) network byte order: TCP / IP protocol layers byte sequence will be defined as the Big-

Little Endian To Big Endian Conversion

Convert "Little-Endian" to "Big-Endian"
This tip outlines two simple methods that help you to convert 

a number from the "little-endian" format to the 

"big-endian" format.

// 2-byte number
int SHORT_little_endian_TO_big_endian(int i)
{
    return ((i>>8)&0xff)+((i << 8)&0xff00);
}

// 4-byte number
int INT_little_endian_TO_big_endian(int i)
{
 return((i&0xff)<<24)+((i&0xff00)<<8) +

       ((i&0xff0000)>>8)+((i>>24)&0xff);
}

How to Use va_arg in C

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

int maxof(int, ...) ;
void f(void);

main(){
        f();
        exit(EXIT SUCCESS);
}

int maxof(int n args, ...){
        register int i;
        int max, a;
        va_list ap;

        va_start(ap, n args);
        max = va_arg(ap, int);
        for(i = 2; i <= n_args; i++) {
                if((a = va_arg(ap, int)) > max)
                        max = a;
        }

        va_end(ap);
        return max;
}

void f(void) {
        int i = 5;
        int j[256];
        j[42] = 24;
     

Sorting Program in C

/* sort.c */

/* Author    : Mr. Jake Rodriguez Pomperada,MAED-IT */

/* Date      :  March 19, 2009 Thursday */

/* Language  : C  */

/* Tool      :  Turbo C 2.0 */

/* Email     :  jakerpomperada@yahoo.com */

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

 main()

{

 int a[10],n=0,choice=0;

 int read_array(int []);

 while(1)

 {

   clrscr();

   printf("\t  ============================ ");

   printf("\n\t ======== MAIN MENU ========= ");

    printf("\n\t ============================ ");

   printf("\n\n\t 1> BUBBLE SORT");

   printf("\n\n\t 2> SELECTION SORT");

   printf("\n\n\t 3> INSERTION SORT");

   printf("\n\n\t 4> BUCKET SORT");

   printf("\n\n\t 5> SHELL SORT");

   printf("\n\n\t 6> EXIT");

   printf("\n\n\t ENTER YOUR CHOICE :=> ");

   scanf("%d",&choice);

   switch(choice)

   {

    case 1:n=read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           bubble_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 2:n=read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           select_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 3:n=read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           insert_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 4:n=  read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           bucket_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 5:n=  read_array(a);

           printf("\n\n\t THE ARRAY ELEMENTS ARE :: ");

           print_array(a,n);

           shell_sort(a,n);

           printf("\n\n\t THE SORTED LIST IS :: ");

           print_array(a,n);

           break;

    case 6: printf("\n\n\t\t THANK YOU FOR USING THIS SOFTWARE");

        printf("\n\n\t       Created By: Mr. Jake R. Pomperada, MAED-IT");

        exit(0);

   }

getche();

 }

}

int read_array(int a[])

{

 int n,i;

 printf("\n\n\t ENTER THE ARRAY LENGTH :: ");

 scanf("%d",&n);

 for(i=0;i<n;i++)

  {

   printf("\n\n\t ENTER THE ELEMENT [%d] :: ",i);

   scanf("%d",&a[i]);

  }

 return(n);

}

print_array(int a[],int n)

{

 int i;

 for(i=0;i<n;i++)

  printf("%d \t",a[i]);

}

 bubble_sort(int a[],int n)

{

 int i,j,temp;

 for(i=0;i<n-1;i++)

   {

    for(j=0;j<n-1;j++)

     if(a[j]>a[j+1])

      {

       temp=a[j];

       a[j]=a[j+1];

       a[j+1]=temp;

      }

    printf("\n\n\t PASS %d :: ",i+1);

    print_array(a,n);

    }

}

select_sort(int a[],int n)

{

 int i,j,temp;

 for(i=0;i<n-1;i++)

   {

    for(j=i+1;j<n;j++)

      {

       if(a[i]>a[j])

          {

           temp=a[i];

           a[i]=a[j];

           a[j]=temp;

          }

       }

    printf("\n\n\t PASS %d :: ",i+1);

    print_array(a,n);

   }

}

insert_sort(int a[],int n)

{

 int i,j,temp;

 for(i=1;i<n;i++)

  {

   temp=a[i];

   for(j=i-1;temp<a[j] && j>=0;j--)

     a[j+1]=a[j];

   a[j+1]=temp;

   printf("\n\n\t PASS %d :: ",i);

   print_array(a,n);

  }

}

 shell_sort(int a[],int n)

{

 int i,j,k,d,t,x,flag=0;

 int p=1;

 for(d=n/2;d>=1;d=d/2)

  {

   flag=0;

   for(j=0;j+d<n;j++)

    {

      for(k=j;k>=0;k=k-d)

      {

         if(a[k]>a[k+d])

         {

          t=a[k];

          a[k]=a[k+d];

          a[k+d]=t;

          flag=1;

         }

      }

    }

    if(flag==1)

    {

      printf("\n\n\t PASS %d ::",p++);

      for(x=0;x<n;x++)

          {

            printf("\t %d",a[x]);

          }

    }

  }

}

 bucket_sort(int a[],int n)

{

 int b[10][20],i,j,row,col,no,x,p=1;

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

 {

   initzerocol(b);

   for(j=0;j<n;j++)

    {

      row=returndigit(a[j],i);

      b[row][0]=b[row][0]+1;

      col= b[row][0];

      b[row][col]=a[j];

    }

   merge(a,b);

   printf("\n\n\t PASS %d ::",p++);

   for(x=0;x<n;x++)

     printf("\t %d",a[x]);

  }

}

 initzerocol(int b[][20])

{

 int i;

 for(i=0;i<10;i++)

  b[i][0]=0;

}

int returndigit(int no,int i)

{

 int k;

 for(k=1;k<i;k++)

  no=no/10;

 return(no%10);

}

 merge(int a[],int b[][20])

{

 int i,j,k=0;

 for(i=0;i<10;i++)

   for(j=1;j<=b[i][0];j++)

    {

      a[k]=b[i][j];

      k=k+1;

    }

 }

 /* End of Code */

Heap Sort

 

We've already looked at several O(n^2) sorting algorithms, bubble sort and selection and insertion sort. Now we turn to faster sorting algorithms that can sort in time proportional to O(n*log(n)) in the average and best case time, a significant speedup, as n, the number of items to sort, grows larger. It will also now be important to consider the space taken by an algorithm. The O(n^2) sorts did not require any space over and above what was needed to store the input. Some faster sorts require (or are much easier to understand when explained by using) additional storage. Sorting methods that do not require additional space are called "in place". This property is particularly useful when dealing with large data sets, and some algorithms that seem to require additional space can be made in place with a bit of work.

Perhaps the simplest of these algorithms is heap sort, which is based on the heap data structure. The first important thing to remember about heaps is that the top element of the heap is always "next" in order (either the next highest or next lowest, in the case of numbers). Think about the consequences of this fact -- if we take all of our input values and store them in a heap, and we remove one element at a time, we will remove these elements in sorted order. But how fast is doing this?
There are two factors at work: the time it takes to create a heap by adding each element and the time it takes to remove all of the elements from a heap. Fortunately, we have a guarantee that adding a single element to and removing a single element from a heap both take O(log(n)) time. As noted above, each of these operations takes place once for each element in the input. Consequently, the algorithmic efficiency of a heap sort is O(n*log(n)), rather good indeed.
There are, however, a few tradeoffs. First, heap sort will always take O(n*log(n)) time -- while this means that its worst-case efficiency is more robust than any algorithm previously discussed, it means that even the best case time is O(n*log(n)). As you may recall, bubble sort can be optimized so that it takes only O(n) time in the best case!
Moreover, the simple implementation of heap sort will require additional space sufficient to hold a heap of size n, meaning that you need at least double the amount of space for heapsort as you do for our previous sorts. And creating a heap may have other consequences, such as increasing the constant that is normally dropped in big-O notation. As a result, for small data sets, heap sort might not be the fastest choice!
A last consideration is that heap sort is not a "stable" sort in the sense that it doesn't preserve the original order of equal elements. This might matter if, for instance, you had a list of emails that you wanted to sort by date, and you also wanted to sort alphabetically by sender. One option would be to first sort the emails alphabetically, and then sort by the date received. A stable sort would keep the alphabetical order for emails sent on the same day; an unstable sort would not.
For instance, sorting the following list of names (already in alphabetical order)

From: example@example.com       Sent: 2/1/2005
From: john@example.com          Sent: 2/1/2005
From: smith@mit.edu             Sent: 1/2/2005
...

using heap sort might yield

From: smith@mit.edu             Sent: 1/2/2005
From: john@example.com          Sent: 2/1/2005
From: example@example.com       Sent: 2/1/2005
...

Note that john@example.com is now ahead of example@example.com, even though "john" should be after "example". A proper stable sort would never put john in front of example, choosing instead to preserve the original order

From: smith@mit.edu             Sent: 1/2/2005
From: example@example.com       Sent: 2/1/2005
From: john@example.com          Sent: 2/1/2005
...

In some applications (for instance, mail readers) this can be an important feature. (Note that it's somewhat complicated to sort by treating both name and date as one feature because in some cases you might want the sort names in reverse order and dates in ascending order.)
You might take some time to think about how you could implement a heap sort without using any additional memory.
Summary
Heap sort is a relatively simple algorithm built upon the heap data structure. A naive implementation requires additional space, but it is possible to do a heap sort in place. Heap sort has guaranteed O(n*log(n))) performance, though the constant factor is typically a bit higher than for other algorithms such as quicksort. Heap sort is not a stable sort, so the original ordering of equal elements may not be maintained.
If you want more details on implementation, you can go here to get the source code for a heap and heap sort implementation.

Quicksort

 

by Jakub Bomba (axon)
When deciding on the best sorting algorithm we often look at its worst-case running time, and base our decision solely on that factor. That is why beginning programmers often overlook quicksort as a viable option because of its T(n^2) worst-case running time, which could be made exponentially unlikely with a little effort. In fact, quicksort is the currently fastest known sorting algorithm and is often the best practical choice for sorting, as its average expected running time is O(n log(n)).

Quicksort, like mergesort, is a divide-and-conquer recursive algorithm. The basic divide-and-conquer process for sorting a subarray S[p..r] is summarized in the following three easy steps:

Divide: Partition S[p..r] into two subarrays S[p..q-1] and S[q+1..r] such that each element of S[p..q-1] is less than or equal to S[q], which is, in turn, less than or equal to each element of S[q+1..r]. Compute the index q as part of this partitioning procedure
Conquer: Sort the two subarrays S[p...q-1] and S[q+1..r] by recursive calls to quicksort.
Combine: Since the subarrays are sorted in place, no work is needed to combing them: the entire array S is now sorted.

Before a further discussion and analysis of quicksort a presentation of its implementation procedure below:

QUICKSORT(S, P, r)
1 If p < r
2 	then q <- PARTITION(S, p, r)
3		QUICKSORT(S, p, q-1)
4		QUICKSORT(S, q+1, r)

note: to sort the whole array S, the initial parameters would be: QUICKSORT(S, 1, length[A])

PARTITION(S, p, r)
1 x <- S[r]
2 i <- p-1
3 for j <- p to r-1
4	do if S[j] <= x
5		then i <- i+1
6			swap S[i] <-> S[j]
7 swap S[i+1] <-> S[r]
8 return i+1

Quicksort's running time depends on the result of the partitioning routine - whether it's balanced or unbalanced. This is determined by the pivot element used for partitioning. If the result of the partition is unbalanced, quicksort can run as slowly as insertion sort; if it's balanced, the algorithm runs asymptotically as fast as merge sort. That is why picking the "best" pivot is a crucial design decision.

The Wrong Way: the popular way of choosing the pivot is to use the first element; this is acceptable only if the input is random, but if the input is presorted, or in the reverse order, then the first elements provides a bad, unbalanced, partition. All the elements go either into S[p...q-1] or S[q+1..r]. If the input is presorted and as the first element is chosen consistently throughout the recursive calls, quicksort has taken quadratic time to do nothing at all.
The Safe Way: the safe way to choose a pivot is to simply pick one randomly; it is unlikely that a random pivot would consistently provide us with a bad partition throughout the course of the sort.
Median-of-Three Way: best case partitioning would occur if PARTITION produces two subproblems of almost equal size - one of size [n/2] and the other of size [n/2]-1. In order to achieve this partition, the pivot would have to be the median of the entire input; unfortunately this is hard to calculate and would consume much of the time, slowing down the algorithm considerably. A decent estimate can be obtained by choosing three elements randomly and using the median of these three as the pivot.

Short Example of a Quicksort Routine (Pivots chosen "randomly")

Input: [13 81 92 65 43 31 57 26 75 0]
Pivot: 65
Partition:  [13 0 26 43 31 57 begin_of_the_skype_highlighting              13 0 26 43 31 57      end_of_the_skype_highlighting]  65  [ 92 75 81]
Pivot: 31  81  
Partition: [13 0 26]  31  [43 57]  65  [75]  81  [92]
Pivot: 13
Parititon: [0]  13  [26]  31  [43 57]  65  [75]  81  [92]
Combine: [0 13 26]  31 [43 57]  65  [75 81 92]
Combine: [0 13 26 31 43 57 begin_of_the_skype_highlighting              0 13 26 31 43 57      end_of_the_skype_highlighting]  65  [75 81 92]
Combine: [0 13 26 31 43 57 65 75 81 92]

Summary
Quicksort is a relatively simple sorting algorithm using the divide-and-conquer recursive procedure. It is the quickest comparison-based sorting algorithm in practice with an average running time of O(n log(n)). Crucial to quicksort's speed is a balanced partition decided by a well chosen pivot. Quicksort has the advantage of sorting in place, and it works well even in virtual memory environments.

Merge Sort

Merge sort is the second guaranteed O(nlog(n)) sort we'll look at. Like heap sort, merge sort requires additional memory proportional to the size of the input for scratch space, but, unlike heap sort, merge sort is stable, meaning that "equal" elements are ordered the same once sorting is complete.

Merge sort works using the principle that if you have two sorted lists, you can merge them together to form another sorted list. Consequently, sorting a large list can be thought of as a problem of sorting two smaller lists and then merging those two lists together. For instance, if you have the list

1 9 7 6

you could divide it into two lists,

1 9
and
7 6

Once those two lists are sorted:

1 9
and
6 7

They could be merged back together easily by starting at the left end of each list and then picking the smaller value. This process is illustrated below for those who find a visual approach helpful:

New list: 1
9
and
6 7

New list: 1 6
9
and
7

New list: 1 6 7
9
and
empty list

New list: 1 6 7 9

Here's the key to merge sort: once you've broken the problem in a problem of sorting and then merging two smaller lists, you can then apply merge sort to each of those smaller lists. This is a recursive process, so it will need a base case. Specifically, once we've reached a single element array, we know it's sorted (it has only one element, which must be in the right position) and we can just merge it with its neighbor to produce a new, sorted two-element array. This array, again, can be recombined with a neighbor, and so on until the entire array is sorted.
Merge sort is also our first divide-and-conquer sort. The term divide and conquer refers to breaking the problem into simpler sub-problems, each of which is then solved by applying the same approach, until the sub-problems are small enough to be solved immediately.
Merge sort guarantees O(nlog(n)) complexity because it always splits the work in half. In order to understand how we derive this time complexity for merge sort, consider the two factors involved: the number of recursive calls, and the time taken to merge each list together.
First, let's consider the number of recursive calls, as this will shed some light onto our understanding of the list merge operation. Each recursive call will either be a base case, or will result in two future recursive calls. The first call starts off by making two calls; each of those makes four, and so forth. What does this sound like?
If you thought,"a binary tree", then you're absolutely right. An easy way to visualize merge sort is as a tree of recursive calls. To save a bit of space, I will use m(lower, upper) to indicate merge sort called from element lower to element upper. For instance, m(0, n-1) would be the merge sort call for an array of size n in C/C++.

                        m(0, 3)
                      /        \
                     /          \
                    /            \
               m(0, 1)         m(2, 3)
              /       \        /      \
             /         \      /        \
       m(0, 0)     m(1, 1) m(2, 2)     m(3, 3)
                  

So we see that for an array of four elements, we have a tree of depth three. Now let's say we doubled the number of elements in the array to eight; each merge sort at the bottom of this tree would now have double the number of elements -- two rather than one. This means we'd need one additional recursive call at each element. This suggests that the total depth of the tree is log(n) + 1, the number of times we need to halve the number of elements in the array to reach the base case.
Now, what about the amount of work done at each recursive call? At first, you might think that every merge in the tree should equate to O(n) time, but this is incorrect. At each level, the number of elements is being dramatically reduced; at the bottom branch, it is certainly not taking O(n) time to perform a non-operation. At the level where the results of the base case are being merged (at depth 1 in the above tree), each merge sort call is merging exactly half the list. At the root node is the only time the entire list is merged together at a single node.
As a result, it makes more sense to think about merge sort in terms of the number of operations performed on a single level of the tree. At each level, a total of n operations take place, and there are log(n) + 1 levels; consequently, the overall time complexity is O(n * log(n)).
Moreover, merge sort is stable -- so long as you break ties by picking from the correct list, equal elements will always end up in the same order as before. Specifically, if you split an array into a left half and a right half, you would break ties in favor of the left half, as it precedes the right half. This allows equal elements to stay ordered across merge operations.
The downside of merge sort is that it usually does require a scratch array to store the the results of a merge. In place mergesort with arrays is a complex problem beyond the scope of this discussion. On the other hand, when dealing with linked lists, merge sort can be outstanding because no scratch space is needed. As an exercise, try implementing merge sort for linked lists without using any extra space save for a few extra variables.
Implementation Here is a find a sample implementation of merge sort. The code is a bit too long to post here, but you should check it out and notice one important feature: the scratch space is only allocated once. Malloc, free and other memory allocation routines (e.g., new and delete in C++) are typically fairly slow. As a consequence, reallocating the scratch space for every recursive call would be time prohibitive and would significantly increase the constant factor of merge sort.
Summary Merge sort is a fast, stable sorting routine with guaranteed O(n*log(n)) efficiency. When sorting arrays, merge sort requires additional scratch space proportional to the size of the input array. Merge sort is relatively simple to code and offers performance typically only slightly below that of quicksort.

Insertion Sort

Insertion sort does exactly what you would expect: it inserts each element of the array into its proper position, leaving progressively larger stretches of the array sorted. What this means in practice is that the sort iterates down an array, and the part of the array already covered is in order; then, the current element of the array is inserted into the proper position at the head of the array, and the rest of the elements are moved down, using the space just vacated by the element inserted as the final space.
Here is an example: for sorting the array the array 52314 First, 2 is inserted before 5, resulting in 25314 Then, 3 is inserted between 2 and 5, resulting in 23514 Next, one is inserted at the start, 12354 Finally, 4 is inserted between 3 and 5, 12345

Selection sort

Selection sort is the most conceptually simple of all the sorting algorithms. It works by selecting the smallest (or largest, if you want to sort from big to small) element of the array and placing it at the head of the array. Then the process is repeated for the remainder of the array; the next largest element is selected and put into the next slot, and so on down the line.

Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort, and can be better than a modified bubble sort.
Here is the code for a simple selection sort:

	for(int x=0; x<n; x++)

	{

		int index_of_min = x;

		for(int y=x; y<n; y++)

		{

			if(array[index_of_min]<array[y])

			{

				index_of_min = y;

			}

		}

		int temp = array[x];

		array[x] = array[index_of_min];

		array[index_of_min] = temp;

	}

	

The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).

Bubble sort

 

The simplest sorting algorithm is bubble sort. The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted. Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array, the most exchanges that will be necessary is equal to the length of the array. Here is a simple example:
Given an array 23154 a bubble sort would lead to the following sequence of partially sorted arrays: 21354, 21345, 12345. First the 1 and 3 would be compared and switched, then the 4 and 5. On the next pass, the 1 and 2 would switch, and the array would be in order.
The basic code for bubble sort looks like this, for sorting an integer array:

	for(int x=0; x<n; x++)

	{

		for(int y=0; y<n-1; y++)

		{

			if(array[y]>array[y+1])

			{

				int temp = array[y+1];

				array[y+1] = array[y];

				array[y] = temp;

			}

		}

	}

Notice that this will always loop n times from 0 to n, so the order of this algorithm is O(n^2). This is both the best and worst case scenario because the code contains no way of determining if the array is already in order.
A better version of bubble sort, known as modified bubble sort, includes a flag that is set if an exchange is made after an entire pass over the array. If no exchange is made, then it should be clear that the array is already in order because no two elements need to be switched. In that case, the sort should end. The new best case order for this algorithm is O(n), as if the array is already sorted, then no exchanges are made. You can figure out the code yourself! It only requires a few changes to the original bubble sort.

Comparison of sorting algorithm

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Even a perfectly sorted input requires scanning the entire array
Insertion Sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	In the best case (already sorted), every insert requires constant time
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Constant	Instable	By using input array as storage for the heap, it is possible to achieve constant space
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Depends	Stable	On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Constant	Stable	Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.

Sorting Programs in C

Sorting in general refers to various methods of arranging or ordering things based on criterias (numerical, chronological, alphabetical, heirarchial etc.). In Computer Science, due to obvious reasons, Sorting (of data) is of immense importance and is one of the most extensively researched subjects. It is one of the most fundamental algorithmic problems. So much so that it is also fundmental to many other fundamental algorithmic problems such as search algorithms, merge algorithms etc. It is estimated that around 25% of all CPU cycles are used to sort data. There are many approaches to sorting data and each has its own merits and demerits. This article discusses some of the common sorting algorithms.

Bubble Sort
Bubble Sort is probably one of the oldest, most easiest, straight-forward, inefficient sorting algorithms. It is the algorithm introduced as a sorting routine in most introductory courses on Algorithms. Bubble Sort works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is "bubbled" to the end of the list whereas the smaller values sink to the bottom. It is similar to selection sort although not as straight forward. Instead of "selecting" maximum values, they are bubbled to a part of the list. An implementation in C.

void BubbleSort(int a[], int array_size)
{
     int i, j, temp;
     for (i = 0; i < (array_size - 1); ++i)
     {
          for (j = 0; j < array_size - 1 - i; ++j )
          {
               if (a[j] > a[j+1])
               {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
               }
          }
     }
}

A single, complete "bubble step" is the step in which a maximum element is bubbled to its correct position. This is handled by the inner for loop.

for (j = 0; j < array_size - 1 - i; ++j )
{
     if (a[j] > a[j+1])
     {
          temp = a[j+1];
          a[j+1] = a[j];
          a[j] = temp;
     }
}

Examine the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)

8 6 10 3 1 2 5 4 } pass 0
6 8 3 1 2 5 4 10 } pass 1
6 3 1 2 5 4 8 10 } pass 2
3 1 2 5 4 6 8 10 } pass 3
1 2 3 4 5 6 8 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7

The above tabulated clearly depicts how each bubble sort works. Note that each pass results in one number being bubbled to the end of the list.

Selection Sort
The idea of Selection Sort is rather simple. It basically determines the minimum (or maximum) of the list and swaps it with the element at the index where its supposed to be. The process is repeated such that the nth minimum (or maximum) element is swapped with the element at the n-1th index of the list. The below is an implementation of the algorithm in C.

void SelectionSort(int a[], int array_size)
{
     int i;
     for (i = 0; i < array_size - 1; ++i)
     {
          int j, min, temp;
          min = i;
          for (j = i+1; j < array_size; ++j)
          {
               if (a[j] < a[min])
                    min = j;
          }

          temp = a[i];
          a[i] = a[min];
          a[min] = temp;
     }
}

Consider the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)

8 6 10 3 1 2 5 4 } pass 0
1 6 10 3 8 2 5 4 } pass 1
1 2 10 3 8 6 5 4 } pass 2
1 2 3 10 8 6 5 4 } pass 3
1 2 3 4 8 6 5 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7

At pass 0, the list is unordered. Following that is pass 1, in which the minimum element 1 is selected and swapped with the element 8, at the lowest index 0. In pass 2, however, only the sublist is considered, excluding the element 1. So element 2, is swapped with element 6, in the 2nd lowest index position. This process continues till the sub list is narrowed down to just one element at the highest index (which is its right position).

Insertion Sort
The Insertion Sort algorithm is a commonly used algorithm. Even if you haven't been a programmer or a student of computer science, you may have used this algorithm. Try recalling how you sort a deck of cards. You start from the begining, traverse through the cards and as you find cards misplaced by precedence you remove them and insert them back into the right position. Eventually what you have is a sorted deck of cards. The same idea is applied in the Insertion Sort algorithm. The following is an implementation in C.

void insertionSort(int a[], int array_size)
{
     int i, j, index;
     for (i = 1; i < array_size; ++i)
     {
          index = a[i];
          for (j = i; j > 0 && a[j-1] > index; j--)
               a[j] = a[j-1];

          a[j] = index;
     }
}

Examine the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)

8 6 10 3 1 2 5 4 } pass 0
6 8 10 3 1 2 5 4 } pass 1
6 8 10 3 1 2 5 4 } pass 2
3 6 8 10 1 2 5 4 } pass 3
1 3 6 8 10 2 5 4 } pass 4
1 2 3 6 8 10 5 4 } pass 5
1 2 3 5 6 8 10 4 } pass 6
1 2 3 4 5 6 8 10 } pass 7

The pass 0 is only to show the state of the unsorted array before it is given to the loop for sorting. Now try out the deck-of-cards-sorting algorithm with this list and see if it matches with the tabulated data. For example, you start from 8 and the next card you see is 6. Hence you remove 6 from its current position and "insert" it back to the top. That constitued pass 1. Repeat the same process and you'll do the same thing for 3 which is inserted at the top. Observe in pass 5 that 2 is moved from position 5 to position 1 since its < (6,8,10) but > 1. As you carry on till you reach the end of the list you'll find that the list has been sorted. It didn't take a course to tell you how to sort a deck of cards, did it; you prolly figured it out on your own. Amazed at the computer scientist in you ? ;)

Heap Sort
Heap sort algorithm, as the name suggests, is based on the concept of heaps. It begins by constructing a special type of binary tree, called heap, out of the set of data which is to be sorted. Note:

• 
  
  A Heap by definition is a special type of binary tree in which each node is greater than any of its descendants. It is a complete binary tree.
  
  
• 
  
  A semi-heap is a binary tree in which all the nodes except the root possess the heap property.
  
  
• 
  
  If N be the number of a node, then its left child is 2*N and the right child 2*N+1.

The root node of a Heap, by definition, is the maximum of all the elements in the set of data, constituting the binary tree. Hence the sorting process basically consists of extracting the root node and reheaping the remaining set of elements to obtain the next largest element till there are no more elements left to heap. Elemetary implementations usually employ two arrays, one for the heap and the other to store the sorted data. But it is possible to use the same array to heap the unordered list and compile the sorted list. This is usually done by swapping the root of the heap with the end of the array and then excluding that element from any subsequent reheaping.

Significance of a semi-heap - A Semi-Heap as mentioned above is a Heap except that the root does not possess the property of a heap node. This type of a heap is significant in the discussion of Heap Sorting, since after each "Heaping" of the set of data, the root is extracted and replaced by an element from the list. This leaves us with a Semi-Heap. Reheaping a Semi-Heap is particularily easy since all other nodes have already been heaped and only the root node has to be shifted downwards to its right position. The following C function takes care of reheaping a set of data or a part of it.

void downHeap(int a[], int root, int bottom)
{
     int maxchild, temp, child;
     while (root*2 < bottom)
     {
          child = root * 2 + 1;
          if (child == bottom)
          {
               maxchild = child;
          }
          else
          {
               if (a[child] > a[child + 1])
                    maxchild = child;
               else
                    maxchild = child + 1;
          }

          if (a[root] < a[maxchild])
          {
               temp = a[root];
               a[root] = a[maxchild];
               a[maxchild] = temp;
          }
          else return;

          root = maxchild;
     }
}

In the above function, both root and bottom are indices into the array. Note that, theoritically speaking, we generally express the indices of the nodes starting from 1 through size of the array. But in C, we know that array indexing begins at 0; and so the left child is

child = root * 2 + 1
/* so, for eg., if root = 0, child = 1 (not 0) */

In the function, what basically happens is that, starting from root each loop performs a check for the heap property of root and does whatever necessary to make it conform to it. If it does already conform to it, the loop breaks and the function returns to caller. Note that the function assumes that the tree constituted by the root and all its descendants is a Semi-Heap.

Now that we have a downheaper, what we need is the actual sorting routine.

void heapsort(int a[], int array_size)
{
     int i;
     for (i = (array_size/2 -1); i >= 0; --i)
     {
          downHeap(a, i, array_size-1);
     }

     for (i = array_size-1; i >= 0; --i)
     {
          int temp;
          temp = a[i];
          a[i] = a[0];
          a[0] = temp;
          downHeap(a, 0, i-1);
     }
}

Note that, before the actual sorting of data takes place, the list is heaped in the for loop starting from the mid element (which is the parent of the right most leaf of the tree) of the list.

for (i = (array_size/2 -1); i >= 0; --i)
{
     downHeap(a, i, array_size-1);
}

Following this is the loop which actually performs the extraction of the root and creating the sorted list. Notice the swapping of the ith element with the root followed by a reheaping of the list.

for (i = array_size-1; i >= 0; --i)
{
     int temp;
     temp = a[i];
     a[i] = a[0];
     a[0] = temp;
     downHeap(a, 0, i-1);
}

The following are some snapshots of the array during the sorting process. The unodered list -

8 6 10 3 1 2 5 4

After the initial heaping done by the first for loop.

10 6 8 4 1 2 5 3

Second loop which extracts root and reheaps.

8 6 5 4 1 2 3 10 } pass 1
6 4 5 3 1 2 8 10 } pass 2
5 4 2 3 1 6 8 10 } pass 3
4 3 2 1 5 6 8 10 } pass 4
3 1 2 4 5 6 8 10 } pass 5
2 1 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7
1 2 3 4 5 6 8 10 } pass 8

Heap sort is one of the preferred sorting algorithms when the number of data items is large. Its efficiency in general is considered to be poorer than quick sort and merge sort.

Difference between Macro and Inline

http://www.geekinterview.com/question_details/23831

STL Standard Template Library C++

http://www.cplusplus.com/reference/stl/

http://www.cplusplus.com/reference/algorithm/

Important C Networks Interview Quesitons

Questions in Brocade R&D

1. explain about function ptr
2. height of the tree
3. order of the tree (types of traversal)
4. tell me about structure padding
5. explain about hash function
6. what is static variable
7. difference between global variable and static variable
8. virtual memory segments
9. Rip convergence time with several topologies
10. what is HA
11. difference between HA and pizzabox stacking
12. differnce between sll and dll
13. average case of quick sort
14. binary search
15. why we need double ptr
16. rope lighting puzzle
17. why ARP?
18. smaphore?
19. diffrence between RIP and OSPF
20. question about DCB
21. question about CN

Infinite Solution (comm net ) Interview Questions

How many Collisions Domains are there in a switch ?
Ans : That is equal to the Number of Ports in the Switch

How many Broadcast Domains are there in a switch ?
Ans : Only One

How can we Increase the Number of Broadcast Domains ? How ?

Ans : yes, Vlans

What is the Upper Limit for the Number of Vlans in a switch ?
Ans:4096 (2 ^ 12 =4096) 12 bits

How RSTP is Different from STP ?

How Distance Vector Routing Differs from Link State Routing ?

Which Converges Faster RIP or OSPF ?

Why PTP when we have NTP ?

Why NTP cant Achieve Nano Second Sync ?

Explain what you know about OSPF ?

Explain a bug you fixed ?

What are the Data structures you Know ?

when will you use typedef ?

how will you copy an array to another ?

Ans : i said MEMCPY , but he said there is one more way ?
i dont know :(

How will you copy Structures ?

use MEMCPY, Assign Individually (if Pointers and Strings are present we have to copy them Individually)
or use assignmnet s1=s2;

what ## operator how it is used in Macros ?

Ans : ?????

How will you find a number is a power of 2 ?

x&(x-1)  ==0

Explain me steps in Reversing a Linked list 2 ptr Approach ?

CISCO interview questions....

1. Conditions for ports to get aggregated.
2. Is the below arithmetic operations allowed on pointers.
int *a, *b, *c;
c= a+b;
c= a-b;
3. Write a pgm to determine the length of a string without using counters.
4. Write a pgm to swap the first and last character of a string.
5. Explain MRP. Use of MVRP.
6. Pkt format. How 4k VLANS get encoded  in MRPPDU .
7.  What are the three most important things done in a switch when a VLAN is configured?
8 . Explain the VLAN path creation and data traffic forwarding using MVRP.
9.  LLDP specific questions.
10. Process creation in linux.
11. How MRP task gets created in ISS.
12. Will LA work over layer 3 ports.
13. Explain woirking of STP. How root bridge and ports are getting selected.
14. PNAC related questions (in fact they asked all the protocols that was written in the resume.)
15. HA related qns. Qns related to the usage of Gracious ARP.
16. What will happen if a malicious user is sending control packets at a high rate to the switch. How to handle such a scenario.
17. Some questions related to CPU performance..
18. What are the different storage classes?
19. Why shld a variable be declared as static. (Need for static variables)
20. Qns on register storage class. When will a variable be declared as register.
21. What will happen if a programer declares the storag type of 100 local variables as register.
2 2. Whats the format of function with variable argument list? Most commonly used function that has variable argument.
2 3. How will the compiler know the number of arguments in a function with variable arguments.
24. Some more questions on variable argument list.
25. Qns on packet flow. Explain the flow that occurs when a packet is received on a port.
2 6. Type of message posting mechanism used.
27. Different data structures that I have used. What is the criteria for choosing a particular data structure.
28. Debugging tools that I have used.
29. What is the approach taken while writting the test plan.
30. Software life cycle model used in the project.
31. How the RTM is prepared.
32. Difference between access port and trunk port.
33. What will happen if one port in a port channel is access port and other is trunk?
3 4. Definition of Hashing.
35. What is hash function?
36. How the collision in Hashing is handled?
37. Some general questions on RB Tree like how it is balanced.
3 8. What will happen if the tree is not balanced.

Brocade interview questions.

Courtesy: Abishek

 

Requesting Prabu to share his part.

1> Most of the questions were on IGMP protocol (60-70 %) (Data Structure, Interaction with BCM , Timer involved)
2> need of Check Sun in TCP Fiels
3> Need of Check Sum in IP Files
4> Whuch checksum keep on chanfing on differnt hop ?
5> How Learning happens for Tag/Untag Packets
6> How Multicast entry arte programmed in BCM?
7> Differnce in Multicast Table for Mac and IP Based Snooping
8> What is ARP and RARP ?
9> Where is RARP protcol works ?
10> How Routing works ( 3 nodes are there what will packets format at each node ?)

Questions in C
===========
1> What will happen if we call the function recursively ?
2> What is the o/p when two pointers are substracted ?
3> If we are given two pointer p and p+1 can we find out type of poiner ?
4> what is differnce betwwem macro and inline function
5> Define a macro for calculating square
6> O/p of following
char *a= "hello",
a[0] = 'b'
printf ("\r %s \n", a);

7> Differnet Type of Memory (Stack Heap, ...)
8> What are the sequence happen when a function is called ?
9> what haapen when a local variable is returend from the function ?

OS
====
1> What are pthreads ?
2> Differnce between thread and process ?
3> How OS Schedules differnt threads ?
4> Need of Semaphore in Multi Thread Application ?
5> Differnt element of Process Table
6> Differnce betwwem malloc and calloc

Programs to Write
================

1> An Array of 20 elements is defined and initialized with 0
Some of them are initilaized to 1 for eg: a[3] =1 , a[7] = 1 a[8] =1 a[9] =1 and a[20] = 1;
Output should be 3,7-9,20

2> Program to Display information from Single Link List in Sorted Order.

Sl. No. Team/Project    Experience (in years)
               Development     SQA
1       SGSN    5 to 10 1 to 5
2       MME/LTE 3 to 5  1 to 5
3       Automation              1 to 5
4       PDSN            1 to 5
5       Diameter        3 to 11 1 to 5
6       In-line Services        4 to 7  1 to 5
7       IMS     1 to 5  1 to 5
8       ASNGW   8 to 12         1 to 5
9       Femto CDMA              1 to 5
10      AAA     1 to 6
11      ICSR    5 to 10
12      TPO     3 to 6
13      Tools   3 to 9

 

 

 

 

 

 

I would be the greatest sinner in the world, if I do not mention about Muthuraj before starting this mail. Had not for Muthu, I would have packed may bags and headed to destination after the first round itself. Hail Muthu for starting this mail chain

{Do curse Prabu for not sharing anything}. ?

O.K. Jokes Apart, I attended interview with Juniper Networks B’lore. I am keeping my fingers crossed for the result (I am hoping for some good news, please do pray for me). It consisted for five rounds of face-to-face interview. Earlier I had done with a round of telephonic and the questions have been shared already in the mail chain. It consisted of all the flavors in the interview, Protocols, C, Pgming, OS (?) & Attitude test. Sure, it was a very nice experience.

1.  First round was more of C basics and Protocols
2.  What is the difference between RSTP and MSTP?
3.  Explain RSTP
4.  Explain MSTP
5.  Draw a topology and explain RSTP
6.  Explain the MAC address table build-up in a network
7.  How does it learn?
8.  What is the difference between switching and Routing? (Hail Chezhian)
9.  Were you involved in any design? I explained PTP (should have chosen something else)
10. Why you chose this?
11. I explained PTP
12. Explain PTP and population of DS
13. How your design is useful in the packet flow?
14. Write a pgm to delete a node in DLL
15. What are the types of vbles?
16. Explain static
17. explain extern
18. why static vble value is never lost?
19. what is life-time and scope for all the variables?
20. and many such
21. Second round was again PB and C
22. What is PB?
23. Explain PB
24. Explain PBB
25. Explain a typical scenario of usage of PB
26. Why we need to use CEP and CNP?
27. What is the need for two different types of Ethertypes?
28. Can we achieve the same without difference ethertypes? (This and other PB, STP related stuff were mere discussion)
29. Write a pgm to do strcpy
30. write a pgm to do strcpy even if addresses overlap (I forgot this)
31. some wrong C code he wrote and he asked to spot the error
32. Stack and heap memory , text, BSS…. Asked everything ?
33. Then the third round. This time it was simple
34. Pgm to delete a node in doubly Olar linked list (need 2 take care of boundary conditions)
35. Pgm to do in-order Tree without usage of recursion
36. pgm to find whether number is power of 2 or not? (only one bit will be set)
37. And other logical questions
38. What you learnt in support? (I told soft skills and he was happy)
39. Finally he told HR will meet me (naan kooda mudichutangalaonu nimbi okkanthdu irundhaen)
40. now started the anti climax
41. One more fellow came and blasted everything in OS. I told him I am not that well in OS and am trying to learn.
42. Asked how 2 processes communicate. I told abt shared memory and message queues.
43. Then pgm to find a loop in SLL. I did not do well for this one
44. Pgm to find strcmp
45. Then more questions on C and other OS related stuff.
46. How does sizeof work? ( I said don’t know, he asked me to guess. Then I told probably, this is fn, it declares an instance of vble inside provided as input and finds the amt of memory occupied… reaction was “Out-of-box”. “Idharku thanae asaipattai Balakumara ?]
47. Then final rnd. This was more of Attitude determining round
48. How wuld u test ATM
49. What are the features u like to have in ATM
50. Postman Problem (Just they determine the attitude)
51. Red balls, white balls story
52. Then he explained what the BU is about and what they are doing and abt the growth of their BU. He also told about the protocols to be developed in the coming years.
53. Sari, anadhu ayipochunu nannum 2 questions kaetaen ?

 

 

 

Some more questions for Juniper ?

1.  Explain your current project
2.  How do you handle packet processing?
3.  What kind of mech is used b/w various threads in the project?
4.  What is a binary tree?
5.  What is a RBTree?
6.  Explain RBTree Traversal Algorithm
7.  Explain Tree Balancing
8.  What is Spanning Tree
9.  Explain overview of MSTP
10. Explain various timers in MSTP
11. Can timers be optimized in MSTP
12. Is MSTP implementation resource efficient with all these timers?
13. What is VSTP?==> The Answer VLAN Spanning Tree Protocol.. and is equivalent to PVRST. I did not know this ? shame on me
14. Explain the data structure implementation in current proj
15. Why you choose this one?
16. Any performance parameters considered?
17. Explain the difference b/w MACROs & inline functions
18. What are the storage classes in C?
19. Explain what is meant by "extern"?
20. What does the compiler do when it sees something as extern?
21. How can u achieve the functionality of extern without using it?
22. What is meant by 'static'?
23. what does the compiler do when it sees something as 'static'
24. More questions on malloc
25. what is stack memory and what is heap memory
26. Roughly draw the stack for a function
27. And more questions in C. I forgot
I forgot to attach the questions that asked by Huawei.
Please find thye below.

1. write a function to find the ethernet packet is IP packet or not?
2. write a pgm to find the little endifan and big endian.
3. write a program to convert the HTONL, NTOHL, NTOHS and HTONS.
4. write a program to multiply n with 32? This is one mokkai question?
5. Tell about the VLAN tag format.
6. Draw the ethernet packet?

Today I have attended the force 10 networks interview.
These are the questions asked by them.

1. Delete a node in the double linked lidt.
2. Reverse a linked list. - I used rescursive fun to delete.
3. How to find a given number is multiple of 2 without using shift operator, div and mod operator.
4. Asked questions on GARP.
5. At what base we are choosing the data structure.
6. How many number of nodes in level L. Write a generic formula to find it.
7. One puzzle.

I have completed 5 face to face interview of Juniper. Here are the questions asked to me.
I hope this will helpful for attending the Juniper.

Totally i had 7 rounds of Interview. This is the marathon interview i faced first in my life. But it was very interesting, enjoyable and lead you to learn lot of things.

First 2 rounds are telephonic, questions are

Round 1) Basic C concepts like storage classes, malloc related questions.
Round 2) Whatever we specified in our resume.

Round 3 - Round 7 (Face to Face)

These rounds can be a mixed of C, Data structures and OS.
1. Program to find the little endian or Big endian.
2. Multiplication using bitwise operators.
3. RB tree traversal.
4. Delete a node from double linked list. Should take care of all boundary conditions.
5. Consider you are having the SLL of data 1,3,5 and you are having the new node as 2. We have insert the node 2 in between the 1 and 3 but you have given the pointer of node 3. possible or not?
6. Set the nth bit program.
7. what is the difference between the MACROs and functions.
8. Advantage and disadvantage of MACROs.

Puzzles:
--------
1. Postman problem. write the strategy to deliver the mails faster.
2. Ratio of red marbles and white marbles in red box and white box.

Subject: RE: Juniper interview questions

My Experience

1 ) Void function1 (int x)
{
int couter = 0;

while(x)
{
   counter ++;
   x = x & (x-1);

}
/* What this piece of code is doing */
}

2 ) Reverse a Linked List
--> i fillowed 3 pointer Approach
---> why are you using Three Pointers ?

3) Linked List Problem , The Interviwer Created his own Problem
--> For solving the problem i need to use Circular linked lists
---> using malloc

4) Three Puzzles

http://firstclassthoughts.co.uk/puzzle/the_burning_rope_problem_iq_test.html

http://onepuzzleaday.blogspot.com/2007/08/23-august-2007.html

5) I am getting a vlan 100 tagged packet in my switch , explain step by stepwhat will happen ?

6) about PTP (IEEE 1588)

7) About PTP (IEEE 1588) State machine

8)  RSTP , MSTP , STP what do you know abt these protocols

9)  Explain Project in your Resume

10) Tell me abt yourself

 

 

I forgot to attach the questions that asked by Huawei.
Please find thye below.

1. write a function to find the ethernet packet is IP packet or not?
2. write a pgm to find the little endifan and big endian.
3. write a program to convert the HTONL, NTOHL, NTOHS and HTONS.
4. write a program to multiply n with 32? This is one mokkai question?
5. Tell about the VLAN tag format.
6. Draw the ethernet packet?

C Malloc multi dimension Dynamic allocation

#include<stdio.h>
int main()
{
    char ***p;
    int i,j,r,c;
    r = 10, c = 12;
    p = (char ***) malloc(r * sizeof(char**));
    for(i=0;i<r;i++) {
        p[i] = (char **) malloc (c * sizeof(char *));
        for(j=0;j<c;j++) {
            p[i][j] = (char *) malloc(10);
        sprintf(p[i][j],"%d:%d",i,j);
            printf("%s\t",p[i][j]);
        }
        printf("\n");
        }       

// Cleanup
    for(i=0;i<r;i++) {
        for(j=0;j<c;j++) {
            free(p[i][j]);
        }    
        free(p[i]);
    }
    free(p);
}

C++ Dynamic allocation

#include<iostream>
int main()
{
    char ***p;
    int i,j,r,c;
    r = 5, c = 4;
    p = new char**[r];
    for(i=0;i<r;i++) {
        p[i] = new char*[c];
        for(j=0;j<c;j++) {
            p[i][j] = new char[strlen("Arun") +1];
            strcpy(p[i][j],"Arun");
            cout<<p[i][j]<<"\t";
        }    
        cout<<"\n";
    }
// Cleanup
    for(i=0;i<r;i++) {
        for(j=0;j<c;j++) {
            delete p[i][j];
        }    
        delete p[i];
    }
    delete p;

}

BSS Memory

BSS means Block Started by Symbol

UNIX linkers produce uninitialized data segments. The segments that contain the program code and data are called text segments. These segments contain initialized data. The objects in the Block Started by Symbol segment contain only a name and size but not the value.

Memory Leak Finding Script

while true
do
echo "---------------------------------" >> /tmp/mem_usage
date >> /tmp/mem_usage
ps aux >> /tmp/mem_usage
sleep 60
done

Pthread Code

#include <stdio.h>
#include <pthread.h>
void * start
(
void * arg
)
{
printf( "I am a thread!\n" );
return NULL;
}
int main( int argc, char ** argv )
{
pthread_t thread;
pthread_attr_t attr;
pthread_attr_init( & attr );
pthread_attr_setdetachstate( & attr, PTHREAD_CREATE_JOINABLE );
pthread_create( & thread, & attr, & start, NULL );
pthread_join( thread, NULL );
return 0;
}

BSS Memory Segment

# The BSS segment also known as Uninitialized data  starts at the end of the data segment and contains all uninitialized global variables and static variables that are initialized to zero by default. For instance a variable declared static int i; would be contained in the BSS segment.

# The heap area begins at the end of the BSS segment and grows to larger addresses from there. The Heap area is managed by malloc, realloc, and free, which may use the brk and sbrk system calls to adjust its size (although, note that the use of brk/sbrk and a single "heap area" is not required to fulfil the contract of malloc/realloc/free; they may also be implemented using mmap to reserve potentially non-contiguous regions of virtual memory into the process' virtual address space). The Heap area is shared by all shared libraries and dynamically loaded modules in a process.

Linux Directory Structure and Meaning

Parts of a Unix directory tree. See the FSSTND standard (File system standard)

/            Root
|---root        The home directory for the root user
|---home        Contains the user's home directories
|    |----ftp        Users include many services as listed here
|    |----httpd
|    |----samba
|    |----user1
|    |----user2
|---bin            Commands needed during bootup that might be needed by normal users
|---sbin        Like bin but commands are not intended for normal users.  Commands run by LINUX.
|---proc        This filesystem is not on a disk.  Exists in the kernels imagination (virtual).  This directory
|    |            Holds information about kernel parameters and system configuration.
|    |----1        A directory with info about process number 1.  Each process
|                has a directory below proc. 
|---usr            Contains all commands, libraries, man pages, games and static files for normal
|    |            operation.
|    |----bin        Almost all user commands.  some commands are in /bin or /usr/local/bin.
|    |----sbin        System admin commands not needed on the root filesystem.  e.g., most server
|    |            programs.
|    |----include    Header files for the C programming language.  Should be below /user/lib for
|    |            consistency.
|    |----lib        Unchanging data files for programs and subsystems
|    |----local        The place for locally installed software and other files.
|    |----man        Manual pages
|    |----info        Info documents
|    |----doc        Documentation for various packages
|    |----tmp
|    |----X11R6        The X windows system files.  There is a directory similar to usr below this
|    |            directory.
|    |----X386        Like X11R6 but for X11 release 5
|---boot        Files used by the bootstrap loader, LILO.  Kernel images are often kept here.
|---lib            Shared libraries needed by the programs on the root filesystem
|    |----modules     Loadable kernel modules, especially those needed to boot the system after
|             disasters.
|---dev            Device files for devices such as disk drives, serial ports, etc.
|---etc            Configuration files specific to the machine.
|    |----skel        When a home directory is created it is initialized with files from this directory
|    |----sysconfig     Files that configure the linux system for networking, keyboard, time, and more.
|---var            Contains files that change for mail, news, printers log files, man pages, temp files
|    |----file
|    |----lib        Files that change while the system is running normally
|    |----local        Variable data for programs installed in /usr/local.
|    |----lock        Lock files.  Used by a program to indicate it is using a particular device or file
|    |----log        Log files from programs such as login and syslog which logs all logins,
|    |            logouts, and other system messages.
|    |----run        Files that contain information about the system that is valid until the system is
|    |            next booted
|    |----spool        Directories for mail, printer spools, news and other spooled work.
|    |----tmp        Temporary files that are large or need to exist for longer than they should in
|    |            /tmp.
|    |----catman    A cache for man pages that are formatted on demand
|---mnt            Mount points for temporary mounts by the system administrator.
|---tmp            Temporary files.  Programs running after bootup should use /var/tmp.

Nice Article For Volatile Memory

http://www.netrino.com/node/80

 

http://www.cognitus.net/html/tutorial/usingVolatile.html

memory allocate free tracking

void *mmalloc(size_t size)
{
G_inUse += size;
return malloc(size);
}

void mfree(void *p)
{
size_t *sizePtr=((size_t *) p)-1;
G_inUse -= *sizePtr;
free(p);
}

Here if we request 10 bytes of memory, malloc will allocate 11 byte(for ex: address is 2000 means 1999 will have size of the alloceated memory)