How Does The INTERNET works?

 How Does The INTERNET works?

Even though the Internet is still a young technology, it's hard to imagine life without it now. Every year, engineers create more devices to integrate with the Internet. This network of networks even extends into space. But what makes it work?
To understand the Internet, it helps to look at it as a system with two main components. The first of those components is hardware. That includes everything from the cables that carry terabits of information every second to the computer sitting in front of you.
Other types of hardware that support the Internet include routers, servers, cell phone towers, satellites, radios, smartphones and other devices. All these devices together create the network of networks. The Internet is a malleable system -- it changes in little ways as elements join and leave networks around the world. Some of those elements may stay fairly static and make up the backbone of the Internet. Others are more peripheral.
These elements are connections. Some are end points -- the computer, smartphone or other device you're using to read this may count as one. We call those end points clients. Machines that store the information we seek on the Internet are servers. Other elements are nodes which serve as a connecting point along a route of traffic. And then there are the transmission lines which can be physical, as in the case of cables and fiber optics, or they can be wireless signals from satellites, cell phone or 4G towers, or radios.
All of this hardware wouldn't create a network without the second component of the Internet: the protocols. Protocols are sets of rules that machines follow to complete tasks. Without a common set of protocols that all machines connected to the Internet must follow, communication between devices couldn't happen. The various machines would be unable to understand one another or even send information in a meaningful way. The protocols provide both the method and a common language for machines to use to transmit data.

A Matter of Protocols

You've probably heard of several protocols on the Internet. For example, hypertext transfer protocol is what we use to view Web sites through a browser -- that's what the http at the front of any Web address stands for. If you've ever used an FTP server, you relied on the file transfer protocol. Protocols like these and dozens more create the framework within which all devices must operate to be part of the Internet.
Two of the most important protocols are the transmission control protocol (TCP) and the Internet protocol (IP). We often group the two together -- in most discussions about Internet protocols you'll see them listed as TCP/IP.
What do these protocols do? At their most basic level, these protocols establish the rules for how information passes through the Internet. Without these rules, you would need direct connections to other computers to access the information they hold. You'd also need both your computer and the target computer to understand a common language.
You've probably heard of IP addresses. These addresses follow the Internet protocol. Each device connected to the Internet has an IP address. This is how one machine can find another through the massive network.
The version of IP most of us use today is IPv4, which is based on a 32-bit address system. There's one big problem with this system: We're running out of addresses. That's why the Internet Engineering Task Force (IETF) decided back in 1991 that it was necessary to develop a new version of IP to create enough addresses to meet demand. The result was IPv6, a 128-bit address system. That's enough addresses to accommodate the rising demand for Internet access for the foreseeable future [source: Opus One].
When you want to send a message or retrieve information from another computer, the TCP/IP protocols are what make the transmission possible. Your request goes out over the network, hitting domain name servers (DNS) along the way to find the target server. The DNS points the request in the right direction. Once the target server receives the request, it can send a response back to your computer. The data might travel a completely different path to get back to you. This flexible approach to data transfer is part of what makes the Internet such a powerful tool.
Let's take a closer look at how information travels across the Internet.

Packet, Packet, Who's Got the Packet?

In order to retrieve this article, your computer had to connect with the Web server containing the article's file. We'll use that as an example of how data travels across the Internet.
First, you open your Web browser and connect to our Web site. When you do this, your computer sends an electronic request over your Internet connection to your Internet service provider (ISP). The ISP routes the request to a server further up the chain on the Internet. Eventually, the request will hit a domain name server (DNS).
This server will look for a match for the domain name you've typed in (such as www.howstuffworks.com). If it finds a match, it will direct your request to the proper server's IP address. If it doesn't find a match, it will send the request further up the chain to a server that has more information.
The request will eventually come to our Web server. Our server will respond by sending the requested file in a series of packets. Packets are parts of a file that range between 1,000 and 1,500 bytes. Packets have headers and footers that tell computers what's in the packet and how the information fits with other packets to create an entire file. Each packet travels back up the network and down to your computer. Packets don't necessarily all take the same path -- they'll generally travel the path of least resistance.
That's an important feature. Because packets can travel multiple paths to get to their destination, it's possible for information to route around congested areas on the Internet. In fact, as long as some connections remain, entire sections of the Internet could go down and information could still travel from one section to another -- though it might take longer than normal.
When the packets get to you, your device arranges them according to the rules of the protocols. It's kind of like putting together a jigsaw puzzle. The end result is that you see this article.
This holds true for other kinds of files as well. When you send an e-mail, it gets broken into packets before zooming across the Internet. Phone calls over the Internet also convert conversations into packets using the voice over Internet protocol (VoIP). We can thank network pioneers like Vinton Cerf and Robert Kahn for these protocols -- their early work helped build a system that's both scalable and robust

Data Structures Most frequently asked Questions

19. What is a data structure? What are the types of data structures? Briefly explain them

The scheme of organizing related information is known as ‘data structure’. The types of data structure are:
Lists: A group of similar items with connectivity to the previous or/and next data items.
Arrays: A set of homogeneous values
Records: A set of fields, where each field consists of data belongs to one data type.
Trees: A data structure where the data is organized in a hierarchical structure. This type of data structure follows the sorted order of insertion, deletion and modification of data items.
Tables: Data is persisted in the form of rows and columns. These are similar to records, where the result or manipulation of data is reflected for the whole table.

20. Define a linear and non linear data structure.

Linear data structure: A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. Ex: Arrays, Linked Lists
Non-Linear data structure: Every data item is attached to several other data items in a way that is specific for reflecting relationships. The data items are not arranged in a sequential structure. Ex: Trees, Graphs

21. Define in brief an array. What are the types of array operations?

An array is a set of homogeneous elements. Every element is referred by an index.
Arrays are used for storing the data until the application expires in the main memory of the computer system. So that, the elements can be accessed at any time. The operations are:
- Adding elements
- Sorting elements
- Searching elements
- Re-arranging the elements
- Performing matrix operations
- Pre-fix and post-fix operations

22. What is a matrix? Explain its uses with an example

A matrix is a representation of certain rows and columns, to persist homogeneous data. It can also be called as double-dimensioned array.
Uses:

- To represent class hierarchy using Boolean square matrix
- For data encryption and decryption
- To represent traffic flow and plumbing in a network
- To implement graph theory of node representation

23. Define an algorithm. What are the properties of an algorithm? What are the types of algorithms?

Algorithm: A step by step process to get the solution for a well defined problem.
Properties of an algorithm:
- Should be written in simple English
- Should be unambiguous, precise and lucid
- Should provide the correct solutions
- Should have an end point
- The output statements should follow input, process instructions
- The initial statements should be of input statements
- Should have finite number of steps
- Every statement should be definitive
Types of algorithms:
- Simple recursive algorithms. Ex: Searching an element in a list
– Backtracking algorithms Ex: Depth-first recursive search in a tree
– Divide and conquer algorithms. Ex: Quick sort and merge sort
– Dynamic programming algorithms. Ex: Generation of Fibonacci series
– Greedy algorithms Ex: Counting currency
– Branch and bound algorithms. Ex: Travelling salesman (visiting each city once and minimize the total distance travelled)
– Brute force algorithms. Ex: Finding the best path for a travelling salesman
– Randomized algorithms. Ex. Using a random number to choose a pivot in quick sort).

24. What is an iterative algorithm?

The process of attempting for solving a problem which finds successive approximations for solution, starting from an initial guess. The result of repeated calculations is a sequence of approximate values for the quantities of interest.

25. What is an recursive algorithm?

Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repletion is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.

26. Explain quick sort and merge sort algorithms.

Quick sort employs the ‘divide and conquer’ concept by dividing the list of elements into two sub elements.
The process is as follows:
1. Select an element, pivot, from the list.
2. Rearrange the elements in the list, so that all elements those are less than the pivot are arranged before the pivot and all elements those are greater than the pivot are arranged after the pivot. Now the pivot is in its position.
3. Sort the both sub lists – sub list of the elements which are less than the pivot and the list of elements which are more than the pivot recursively.
Merge Sort: A comparison based sorting algorithm. The input order is preserved in the sorted output.
Merge Sort algorithm is as follows:
1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Other wise, divide the unsorted list into 2 lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, combine (merge) both the lists back into one sorted list.

27. What is Bubble Sort and Quick sort?

Bubble Sort: The simplest sorting algorithm. It involves the sorting the list in a repetitive fashion. It compares two adjacent elements in the list, and swaps them if they are not in the designated order. It continues until there are no swaps needed. This is the signal for the list that is sorted. It is also called as comparison sort as it uses comparisons.
Quick Sort: The best sorting algorithm which implements the ‘divide and conquer’ concept. It first divides the list into two parts by picking an element a ’pivot’. It then arranges the elements those are smaller than pivot into one sub list and the elements those are greater than pivot into one sub list by keeping the pivot in its original place.

28. What are the difference between a stack and a Queue?

Stack – Represents the collection of elements in Last In First Out order.
Operations includes testing null stack, finding the top element in the stack, removal of top most element and adding elements on the top of the stack.
Queue - Represents the collection of elements in First In First Out order.
Operations include testing null queue, finding the next element, removal of elements and inserting the elements from the queue.
Insertion of elements is at the end of the queue
Deletion of elements is from the beginning of the queue.

29. Can a stack be described as a pointer? Explain.

A stack is represented as a pointer. The reason is that, it has a head pointer which points to the top of the stack. The stack operations are performed using the head pointer. Hence, the stack can be described as a pointer.

30. Explain the terms Base case, Recursive case, Binding Time, Run-Time Stack and Tail Recursion.

Base case: A case in recursion, in which the answer is known when the termination for a recursive condition is to unwind back.
Recursive Case: A case which returns to the answer which is closer.
Run-time Stack: A run time stack used for saving the frame stack of a function when every recursion or every call occurs.
Tail Recursion: It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.

31. Is it possible to insert different type of elements in a stack? How?

Different elements can be inserted into a stack. This is possible by implementing union / structure data type. It is efficient to use union rather than structure, as only one item’s memory is used at a time.

32. Explain in brief a linked list.

A linked list is a dynamic data structure. It consists of a sequence of data elements and a reference to the next record in the sequence. Stacks, queues, hash tables, linear equations, prefix and post fix operations. The order of linked items is different that of arrays. The insertion or deletion operations are constant in number.

33. Explain the types of linked lists.

The types of linked lists are:
Singly linked list: It has only head part and corresponding references to the next nodes.
Doubly linked list: A linked list which both head and tail parts, thus allowing the traversal in bi-directional fashion. Except the first node, the head node refers to the previous node.
Circular linked list: A linked list whose last node has reference to the first node.

34. How would you sort a linked list?

Step 1: Compare the current node in the unsorted list with every element in the rest of the list. If the current element is more than any other element go to step 2 otherwise go to step 3.
Step 2: Position the element with higher value after the position of the current element. Compare the next element. Go to step1 if an element exists, else stop the process.
Step 3: If the list is already in sorted order, insert the current node at the end of the list. Compare the next element, if any and go to step 1 or quit.

35. What is sequential search? What is the average number of comparisons in a sequential search?

Sequential search: Searching an element in an array, the search starts from the first element till the last element.
The average number of comparisons in a sequential search is (N+1)/2 where N is the size of the array. If the element is in the 1st position, the number of comparisons will be 1 and if the element is in the last position, the number of comparisons will be N.

36. What are binary search and Fibonacci search?

Binary Search: Binary search is the process of locating an element in a sorted list. The search starts by dividing the list into two parts. The algorithm compares the median value. If the search element is less than the median value, the top list only will be searched, after finding the middle element of that list. The process continues until the element is found or the search in the top list is completed. The same process is continued for the bottom list, until the element is found or the search in the bottom list is completed. If an element is found that must be the median value.
Fibonacci Search: Fibonacci search is a process of searching a sorted array by utilizing divide and conquer algorithm. Fibonacci search examines locations whose addresses have lower dispersion. When the search element has non-uniform access memory storage, the Fibonacci search algorithm reduces the average time needed for accessing a storage location.

Data structure interview questions

1. What is Data Structure?

- Data structure is a group of data elements grouped together under one name.
- These data elements are called members. They can have different types and different lengths.
- Some of them store the data of same type while others store different types of data.

2. Which data structure is used to perform recursion?

- The data structure used for recursion is Stack.
- Its LIFO property helps it remembers its 'caller'. This helps it know the data which is to be returned when the function has to return.
- System stack is used for storing the return addresses of the function calls.

3. Does the Minimal Spanning tree of a graph give the shortest distance between any 2 specified nodes?

- No, it doesn’t.
- It assures that the total weight of the tree is kept to minimum.
- It doesn't imply that the distance between any two nodes involved in the minimum-spanning tree is minimum.

4. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?

- A heterogeneous linked list contains different data types in its nodes. We can not use ordinary pointer to connect them.
- The pointer that we use in such a case is void pointer as it is a generic pointer type and capable of storing pointer to any type.

5. Differentiate between PUSH and POP?

- Pushing and popping refers to the way data is stored into and retrieved from a stack.
- PUSH – Data being pushed/ added to the stack.
- POP - Data being retrieved from the stack, particularly the topmost data.

6. When is a binary search algorithm best applied?

- It is best applied to search a list when the elements are already in order or sorted.
- The list here is searched starting in the middle. If that middle value is not the correct one, the lower or the upper half is searched in the similar way.

7. How do you reference all the elements in a one-dimension array?

- This is done using an indexed loop.
- The counter runs from 0 to the array size minus one.
- Using the loop counter as the array subscript helps in referencing all the elements in one-dimensional array.

8. What is Huffman’s algorithm?

- It is used in creating extended binary trees that have minimum weighted path lengths from the given weights.
- It makes use of a table that contains frequency of occurrence for each data element.

9. What is Fibonacci search?

- It is a search algorithm that applies to a sorted array.
- It uses divide-and-conquer approach that reduces the time needed to reach the target element.

10. Which data structure is applied when dealing with a recursive function?

- A recursive function is a function that calls itself based on a terminating condition.
- It uses stack.
- Using LIFO, a call to a recursive function saves the return address. This tells the return address to the calling function after the call terminates.

11. How does dynamic memory allocation help in managing data?

- Dynamic memory allocation helps to store simple structured data types.
- It can combine separately allocated structured blocks to form composite structures that expand and contract as required.

12. What is a bubble sort and how do you perform it?

- Bubble sort is a sorting technique which can be applied to data structures like arrays.
- Here, the adjacent values are compared and their positions are exchanged if they are out of order.
- The smaller value bubbles up to the top of the list, while the larger value sinks to the bottom.

13. How does variable declaration affect memory allocation?

- The amount of memory to be allocated depends on the data type of the variable.
- An integer type variable is needs 32 bits of memory storage to be reserved.

14. You want to insert a new item in a binary search tree. How would you do it?

- Let us assume that the you want to insert is unique.
- First of all, check if the tree is empty.
- If it is empty, you can insert the new item in the root node.
- If it is not empty, refer to the new item’s key.
- If the data to be entered is smaller than the root’s key, insert it into the root’s left subtree.
- Otherwise, insert it into the root’s right subtree.

15. Why is the isEmpty() member method called?

- The isEmpty() member method is called during the dequeue process. It helps in ascertaining if there exists any item in the queue which needs to be removed.
- This method is called by the dequeue() method before returning the front element.

16. What is a queue ?

- A Queue refers to a sequential organization of data.
- It is a FIFO type data structure in which an element is always inserted at the last position and any element is always removed from the first position.

17. What is adequeue?

- A dequeue is a double-ended queue.
- The elements here can be inserted or removed from either end.

18. What is a postfix expression?

- It is an expression in which each operator follows its operands.
- Here, there is no need to group sub-expressions in parentheses or to consider operator precedence..

Most Frequently asked C Interview Questions

1. What is Storage class? Explain with example  

The storage class determines the part of memory where storage is allocated for an object (particularly variables and functions) and how long the storage allocation continues to exist. In C program, there are four storage classes: automatic, register, external and static.

1.  Auto
   • They are declared at the start of a program’s block such as in the curly braces ( { } ).  Memory is allocated automatically upon entry to a block and freed automatically upon exit from the block.
   • Automatic variables may be specified upon declaration to be of storage class auto.  However, it is not required to use the keyword auto because by default, storage class within a block is auto.
   Register
   Automatic variables are allocated in the main memory of the processor; accessing these memory location for computation will take long time.
   • when we required to optimize the execution time, move the critical variable to processor register. this can be done by using the register key word.
   • when storage class is register, compiler is instructed to allocate a register for this variable.
   • scope of the register variable is same as auto variable.
   NOTE: Allocation of register is not guaranteed always, it depends on number register available in processor and number register used for manipulation. if you define 4 variable as register storage class and and processor has only 2 register for variable allocation, then compiler will allocate 2 variable in registers and treat the remaining 2 variable as auto variable. therefore usage of register keyword should should be justified and cross checked with disassembly weather register is allocated or not.
   Extern
   • For using the external global variable from other files extern keyword is used.
   • any file can access this global variable and lifetime over entire program run.
   Static
   • static variable have lifetime over entire program run.
   • scope of this variable is limited based on the place of declaration.
   • if static variable is defined in a file and not inside any function, then scope of the variable is limited within that file.
   • if static variable is defined inside a function, then the scope of the variable is limited within that function.
   • we can use this variable any file and any function indirectly by accessing through pointer.

2. what is qualifiers?   

 

Qualifiers defines the property of the variable. Two qualifiers are const and volatile. The const type qualifier declares an object to be unmodifiable. The volatile type qualifier declares an item whose value can legitimately be changed by something beyond the control of the program in which it appears, such as a concurrently executing thread / interrupt routine.

3. What are volatile variables? Where we should use?

A volatile variable is one that can change unexpectedly. Consequently, the compiler can make no assumptions about the value of the variable. In particular, the optimizer must be careful to reload the variable every time it is used instead of holding a copy in a register. Examples of volatile variables are:

• Hardware registers in peripherals (for example, status registers)
• Non-automatic variables referenced within an interrupt service routine
• Variables shared by multiple tasks in a multi-threaded applications

4. What does the keyword const mean? What do the following declarations mean?

const int a;
int const a;
const int *a;
int * const a;
int const * a const;

The first two mean the same thing, namely a is a const (read-only) integer.

The third means a is a pointer to a const integer (that is, the integer isn’t modifiable, but the pointer is).

The fourth declares a to be a const pointer to an integer (that is, the integer pointed to by a is modifiable,but the pointer is not).

The final declaration declares a to be a const pointer to a const integer
(that is, neither the integer pointed to by a, nor the pointer itself may be modified).

5. Can a parameter be both const and volatile ? Explain.

Yes. An example is a read-only status register. It is volatile because it can change unexpectedly. It is const because the program should not attempt to modify it

6. Can a pointer be volatile ? Explain.

   Yes, although this is not very common. An example is when an interrupt service routine modifies a pointer to a buffer

7. What’s wrong with the following function?

int square(volatile int *ptr)
{
return *ptr * *ptr;

}

This one is wicked. The intent of the code is to return the square of the value pointed to by *ptr . However, since *ptr points to a volatile parameter, the compiler will generate code that looks something like this:

int square(volatile int *ptr)
{
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}

}
Because it’s possible for the value of *ptr to change unexpectedly, it is possible for a and b to be different. Consequently, this code could return a number that is not a square! The correct way to code this is:

long square(volatile int *ptr)
{
int a;
a = *ptr;
return a * a;
}

8. Data Declarations

a) int a; // An integer
b) int *a; // A pointer to an integer
c) int **a; // A pointer to a pointer to an integer
d) int a[10]; // An array of 10 integers
e) int *a[10]; // An array of 10 pointers to integers
f) int (*a)[10]; // A pointer to an array of 10 integers
g) int (*a)(int); // A pointer to a function a that takes an integer argument and
returns an integer
h) int (*a[10])(int); // An array of 10 pointers to functions that take an integer
argument and return an integer

10. What are Dangling pointers and Wild Pointers

Dangling Pointer :

Dangling pointers in computer programming are pointers that do not point to a valid object of the appropriate type. Dangling pointers arise when an object is deleted or deallocated, without modifying the value of the pointer, so that the pointer still points to the memory location of the deallocated memory.

Examples of Dangling Pointers

int main()
{
     int *p;
     p = (int *) malloc (sizeof (int));

    free(p);
    *p=10;

}

In the above piece of code we are using *p after we free the memory to it.
Such usage is called dangling pointer usage.

int main()
{
int *p = NULL;
{
int a = 10;
p = &a;
}
/*address of a is out of scope and pointer p is now called the dangling pointer, we should initialize the p to NULL before coming out or initialize the pointer to some known value before using it again*/
…
}

int* fun1()
{
int a = 10;
return(&a); /*in this line we are returning the pointer of variable ‘a’ which is out scope.*/
}

Wild Pointers:

Wild pointers are created by omitting necessary initialization prior to first use. Thus, strictly speaking, every pointer in programming languages which do not enforce initialization begins as a wild pointer. This most often occurs due to jumping over the initialization, not by omitting it. Most compilers are able to warn about this.

{

int* a;

/* a is wild pointer, it is not initialized and it may have some garbage value*/

}

correct way is

{

int* a = NULL;

}

10. When should unions be used? Why do we need them in Embedded Systems  programming?

Unions are particularly useful in Embedded programming or in situations where direct access to the hardware/memory is needed. Here is a trivial example:

typedef union
{
    struct {
        unsigned char byte1;
        unsigned char byte2;
        unsigned char byte3;
        unsigned char byte4;
    } bytes;
    unsigned int dword;
} HW_Register;
HW_Register reg;

Then you can access the reg as follows:

reg.dword = 0×12345678;
reg.bytes.byte3 = 4;

Endianism and processor architecture are of course important.

Another useful feature is the bit modifier:

typedef union
{
    struct {
        unsigned char b1:1;
        unsigned char b2:1;
        unsigned char b3:1;
        unsigned char b4:1;
        unsigned char reserved:4;
    } bits;
    unsigned char byte;
} HW_RegisterB;
HW_RegisterB reg;

With this code you can access directly a single bit in the register/memory address:

x = reg.bits.b2;

Low level system programming is a reasonable example.

unions are used to breakdown hardware registers into the component bits. So, you can access an 8-bit register into the component bits.

This structure would allow a control register to be accessed as a control_byte or via the individual bits. It would be important to ensure the bits map on to the correct register bits for a given endianness.

typedef union {
    unsigned char control_byte;
    struct {
        unsigned int nibble  : 4;
        unsigned int nmi     : 1;
        unsigned int enabled : 1;
        unsigned int fired   : 1;
        unsigned int control : 1;
    }
} ControlRegister;

11. Why is sizeof(‘a’) not 1?

Perhaps surprisingly, character constants in C are of type int, so sizeof(‘a’) is sizeof(int) (though it’s different in C++).
Result:
In Turbo C output is: 2
In Turbo C++ output is: 1

 

12. why n++ executes faster than n+1? 
The expression n++ requires a single machine instruction such as INR to carry out the increment operation whereas, n+1 requires more instructions to carry out this operation.

13. Volatile explanation revisited !

Another use for volatile is signal handlers. If you have code like this:

quit = 0;
while (!quit)
{
    /* very small loop which is completely visible to the compiler */
}

The compiler is allowed to notice the loop body does not touch the quit variable and convert the loop to a while (true) loop. Even if the quit variable is set on the signal handler for SIGINT andSIGTERM; the compiler has no way to know that.
However, if the quit variable is declared volatile, the compiler is forced to load it every time, because it can be modified elsewhere. This is exactly what you want in this situation.

14. Data Alignment & Structure Padding

Data Alignment: Data alignment means putting the data at a memory offset equal to some multiple of the word size, which increases the system’s performance due to the way the CPU handles memory
Data Structure Padding: To align the data, it may be necessary to insert some meaningless bytes between the end of the last data structure and the start of the next, which is data structure padding
Here is a structure with members of various types, totaling 8 bytes before compilation:

struct MixedData
{
    char Data1;
    short Data2;
    int Data3;
    char Data4;
};

After compilation the data structure will be supplemented with padding bytes to ensure a proper alignment for each of its members:

struct MixedData  /* After compilation in 32-bit x86 machine */
{
    char Data1; /* 1 byte */
    char Padding1[1]; /* 1 byte for the following 'short' to be aligned on a 2 byte boundary 
assuming that the address where structure begins is an even number */
    short Data2; /* 2 bytes */
    int Data3;  /* 4 bytes - largest structure member */
    char Data4; /* 1 byte */
    char Padding2[3]; /* 3 bytes to make total size of the structure 12 bytes */
};

The compiled size of the structure is now 12 bytes. It is important to note that the last member is padded with the number of bytes required so that the total size of the structure should be a multiple of the largest alignment of any structure member (alignment(int) in this case, which = 4 on linux-32bit/gcc)
In this case 3 bytes are added to the last member to pad the structure to the size of a 12 bytes (alignment(int) × 3).

struct FinalPad {
  float x;
  char n[1];
};

In this example the total size of the structure sizeof(FinalPad) = 8, not 5 (so that the size is a multiple of 4 (alignment of float)).

struct FinalPadShort {
  short s;
  char n[3];                                                                                
};

In this example the total size of the structure sizeof(FinalPadShort) = 6, not 5 (not 8 either) (so that the size is a multiple of 2 (alignment(short) = 2 on linux-32bit/gcc)).
It is possible to change the alignment of structures to reduce the memory they require (or to conform to an existing format) by reordering structure members or changing the compiler’s alignment (or “packing”) of structure members.

struct MixedData  /* after reordering */
{
    char Data1;
    char Data4;   /* reordered */
    short Data2;
    int Data3;  
};

The compiled size of the structure now matches the pre-compiled size of 8 bytes. Note that Padding1[1] has been replaced (and thus eliminated) by Data4 and Padding2[3] is no longer necessary as the structure is already aligned to the size of a long word.
The alternative method of enforcing the MixedData structure to be aligned to a one byte boundary will cause the pre-processor to discard the pre-determined alignment of the structure members and thus no padding bytes would be inserted.
While there is no standard way of defining the alignment of structure members, some compilers use #pragma directives to specify packing inside source files. Here is an example:

#pragma pack(push)  /* push current alignment to stack */
#pragma pack(1)     /* set alignment to 1 byte boundary */

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
};

#pragma pack(pop)   /* restore original alignment from stack */

This structure would have a compiled size of 6 bytes on a 32-bit system. The above directives are available in compilers from Microsoft, Borland, GNU and many others.
Another example:

struct MyPackedData
{
    char Data1;
    long Data2 __attribute__((packed));
    char Data3;
};

Embedded Systems Interview Questions

What is the need for an infinite loop in Embedded systems?

Infinite Loops are those program constructs where in there is no break statement so as to get out of the loop, it just keeps looping over the statements within the block defined.
Example:
While(Boolean True) OR for(;;);
{
//Code
}
Embedded systems need infinite loops for repeatedly processing/monitoring the state of the program. One example could be the case of a program state continuously being checked for any exceptional errors that might just occur during run time such as memory outage or divide by zero etc.,

For e.g. Customer care Telephone systems where in a pre-recorded audio file is played in case the dialer is put on hold..

Also circuits being responsible for indicating that a particular component is active/alive during its operation by means of LED's.

How does combination of functions reduce memory requirements in embedded systems?

The amount of code that has to be dealt with is reduced thus easing the overhead and redundancy is eliminated in case if there is anything common among the functions.

Memory allocation is another aspect that is optimized and it also makes sense to group a set of functions related in some way as one single unit rather than having them to be dispersed in the whole program.

In case of interactive systems display of menu list and reading in the choices of user's could be encapsulated as a single unit.

A vast majority of High Performance Embedded systems today use RISC architecture why?

According to the instruction sets used, computers are normally classified into RISC and CISC.RISC stands for 'Reduced Instruction Set Computing' .The design philosophy of RISC architecture is such that only one instruction is performed on each machine cycle thus taking very less time and speeding up when compared to their CISC counterparts.

Here the use of registers is optimised as most of the memory access operations are limited to store and load operations.

Fewer and simple addressing modes, and simple instruction formats leads to greater efficiency, optimisation of compilers, re-organisation of code for better throughput in terms of space and time complexities. All these features make it the choice of architecture in majority of the Embedded systems.

CISC again have their own advantages and they are preferred whenever the performance and compiler simplification are the issues to be taken care of.

Why do we need virtual device drivers when we have physical device drivers?

Device drivers are basically a set of modules/routines so as to handle a device for which a direct way of communication is not possible through the user's application program and these can be thought of as an interface thus keeping the system small providing for minimalistic of additions of code, if any.
Physical device drivers can’t perform all the logical operations needed in a system in cases like IPC, Signals and so on...
The main reason for having virtual device drivers is to mimic the behaviour of certain hardware devices without it actually being present and these could be attributed to the high cost of the devices or the unavailability of such devices.
These basically create an illusion for the users as if they are using the actual hardware and enable them to carryout their simulation results.
Examples could be the use of virtual drivers in case of Network simulators,also the support of virtual device drivers in case a user runs an additional OS in a virtual box kind of a software.

What is the need for DMAC in ES?

Direct memory access is mainly used to overcome the disadvantages of interrupt and progam controlled I/O.
DMA modules usually take the control over from the processor and perform the memory operations and this is mainly because to counteract the mismatch in the processing speeds of I/O units and the procesor.This is comparatively faster.
It is an important part of any embedded systems,and the reason for their use is that they can be used for bursty data transfers instead of single byte approaches.
It has to wait for the systems resources such as the system bus in case it is already in control of it.

What is Endianness of a system and how do different systems communicate with each other?

Endianness basically refers to the ordering of the bytes within words or larger bytes of data treated as a single entity.
When we consider a several bytes of data say for instance 4 bytes of data,XYZQ the lower byte if stored in a Higher address and others in successively decreasing addresses ,then it refers to the Big Endian and the vice versa of this refers to Little Endian architecture.
Intel 80x86 usually follows Little Endian and others like IBM systems follow Big Endian formats.
If the data is being transmitted care has to be taken so as to know as to which byte,whether the higher or the lower byte is being transmitted.
Hence a common format prior to communication has to be agreed upon to avoid wrong interpretation/calculations.
Usually layer modules are written so as to automate these conversion in Operating systems.

How are macros different from inline functions?

Macros are normally used whenever a set of instructions/tasks have to be repeatedly performed. They are small programs to carryout some predefined actions.
We normally use the #define directive in case we need to define the values of some constants so in case a change is needed only the value can be changed and is reflected throughout.
#define mul(a,b) (a*b)
The major disadvantage of macros is that they are not really functions and the usual error checking and stepping through of the code does not occur.
Inline functions are expanded whenever it is invoked rather than the control going to the place where the function is defined and avoids all the activities such as saving the return address when a jump is performed. Saves time in case of short codes.
inline float add(float a,float b)
{
return a+b;
}
Inline is just a request to the compiler and it is upto to the compiler whether to substitute the code at the place of invocation or perform a jump based on its performance algorithms.

What could be the reasons for a System to have gone blank and how would you Debug it?

Possible reasons could be,
- PC being overheated.
- Dust having being accumulated all around.
- CPU fans not working properly .
- Faulty power connections.
- Faulty circuit board from where the power is being drawn.
- Support Drivers not having being installed.

Debugging steps which can be taken are:

- Cleaning the system thoroughly and maintaining it in a dust-free environment.
Environment that is cool enough and facilitates for easy passage of air should be ideal enough.

- By locating the appropriate support drivers for the system in consideration and having them installed.

Explain interrupt latency and how can we decrease it?

Interrupt latency basically refers to the time span an interrupt is generated and it being serviced by an appropriate routine defined.,usually the interrupt handler.
External signals,some condition in the program or by the occurrence of some event,these could be the reasons for generation of an interrupt.
Interrupts can also be masked so as to ignore them even if an event occurs for which a routine has to be executed.
Following steps could be followed to reduce the latency
- isrs being simple and short.
- Interrupts being serviced immediately
- Avoiding those instructions that increase the latency period.
- Also by prioritizing interrupts over threads.
- Avoiding use of inappropriate APIs.

How to create a child process in linux?

Prototype of the function used to create a child process is pid_t fork(void);
Fork is the system call that is used to create a child process. It takes no arguments and returns a value of type pid_t.
If the function succeeds it returns the pid of the child process created to its parent and child receives a zero value indicating its successful creation.
On failure, a -1 will be returned in the parent's context, no child process will be created, and errno will be set
The child process normally performs all its operations in its parents context but each process independently of one another and also inherits some of the important attributes from it such as UID, current directory, root directory and so on.

Significance of watchdog timer in Embedded Systems

Watchdog timer is basically a timing device that is set for predefined time interval and some event should occur during that time interval else the device generates a time out signal.
One application where it is most widely used is when the mobile phone hangs and no activity takes place,in those cases watchdog timer performs a restart of the system and comes to the rescue of the users.
It is used to reset to the original state whenever some inappropriate events take place such as too many commands being given at the same time or other activities that result in malfunctioning of the GUI.It is usually operated by counter devices.

If you buy some RTOS, what are the features you look for in ?

-Deterministic operating system having guaranteed worst-case interrupt latency and context-switch times.
-Documentation providing for the minimum, average, and maximum number of clock cycles required by each system call
-Interrupt response times should be very minute.
-Context switch time should be very low.
-Compatibility with several plugin devices.
- Overall it should be very reliable.

Why is java mostly used in embedded systems?

Java was mainly designed and conceputalised for code that can work on different platforms without any hassles and also for being secure enough so as to not harm or corrupt other modules of code.
Features like exception handling,simple syntax and Automatic Garbage collection all work in its favour as the language for use in ES's.
Also that it is widely used in the form of Java applets makes it very popular confining it to the limits of JVM.It is Dynamic in nature.
Its use is also being exploited in enterprise systems in the form of J2EE ,J2SE
J2ME in case of mobile applications.

Differentiate between mutexes vs semaphores

-Semaphores is a synchronisation tool to overcome the critical section problem.
- A semaphore S is basically an integer variable that apart from initialisation is accesses only through atomic operations such as wait() and signal().
- Semaphore object basically acts as a counter to monitor the number of threads accessing a resource.
- Mutex is also a tool that is used to provide deadlock free mutual exclusion.It protects access to every critical data item.if the data is locked and is in use,it either waits for the thread to finish or awakened to release the lock from its inactive state.

What are the commonly found errors in Embedded Systems?

- Damage of memory devices due to transient current and static discharges.
- Malfunctioning of address lines due to a short in the circuit
- Malfunctioning of Data lines.
- Some memory locations being inaccessible in storage due to garbage or errors.
- Improper insertion of Memory devices into the memory slots
- Faulty control signals.

What is the need for having multibyte data input and output buffers in case of device ports?

It’s normally the case that some devices transfer the output either in a bursty or a sequential manner and also during input entry. If we take the example of keyboards, all the data entered is stored in a buffer and given at a time or one character at a time.
In case of networking there may be several requests to access the same resource and all these are queued in a buffer and serviced in the order they are received
Hence to avoid the input/output units from getting overloaded with requests, we use multibyte buffers.