Categories
Top C & Data Structure Interview Questions and Answers
The C programming language and Data Structures are among the frequently tested skills in most IT professions by major organizations. This C and Data Structures Interview Questions blog includes the top interview questions on C and Data Structures asked during interviews. So, ensure that you take a quick look at these C and Data Structures interview questions below before you go for any IT-related job interview:
1. What are different techniques for making hash function?
Techniques for making hash function.
Truncation Method This is the simplest method for computing address from a key.In this method we take only a part of the key as address.
Midsquare Method In this method the key is squared and some digits from the middle of this square are taken as address.
Folding Method In this technique, the key is divided into different part where the length of each part is same as that of the required address, except possibly the last part.
Division Method (Modulo-Division) In Modulo-Division method the key is divided by the table size and the remainder is taken as the address of the hash table.
Let the table size is n then
Truncation Method This is the simplest method for computing address from a key.In this method we take only a part of the key as address.
Midsquare Method In this method the key is squared and some digits from the middle of this square are taken as address.
Folding Method In this technique, the key is divided into different part where the length of each part is same as that of the required address, except possibly the last part.
Division Method (Modulo-Division) In Modulo-Division method the key is divided by the table size and the remainder is taken as the address of the hash table.
Let the table size is n then
H (k) =k mod n
2. What is the use of volatile keyword?
The modifier ‘volatile’ tells the compiler that a variable’s value may be changed in ways not explicitly specified by the program. For example, a global variable’s address may be passed to the operating system’s clock routine and used to hold the system time.
In this situation, the contents of the variable are altered without any explicit assignment statements in the program.
This is important because most C compilers automatically optimize certain expressions by assuming that a variable’s content is unchanging if it does not occur on the left side of an assignment statement. Thus, it may not be reexamined each time it is referenced. Also, some compilers change the order of evaluation of an expression during the compilation process. The volatile modifier prevents these changes.
In this situation, the contents of the variable are altered without any explicit assignment statements in the program.
This is important because most C compilers automatically optimize certain expressions by assuming that a variable’s content is unchanging if it does not occur on the left side of an assignment statement. Thus, it may not be reexamined each time it is referenced. Also, some compilers change the order of evaluation of an expression during the compilation process. The volatile modifier prevents these changes.
3. What are the issues that hamper the efficiency in sorting a file?
1) Length of time required by the programmer in coding a particular sorting program.
2) Length of time required by the programmer in coding a particular sorting program.
3) Length of time required by the programmer in coding a particular sorting program.
2) Length of time required by the programmer in coding a particular sorting program.
3) Length of time required by the programmer in coding a particular sorting program.
4. What are differences between sizeof operator and strlen function?
sizeof is keyword of C that can find size of a String constant including null character, but strlen is function which has been defined string.h and can find number of characters in a string excluding null character.
5. What is an lvalue?
An lvalue is an expression to which a value can be assigned. The lvalue expression is located on the left side of an assignment statement whereas an rvalue is located on the right side of an assignment statement.
6. When does the compiler not implicitly generate the address of the first element of an array?
The compiler does not implicitly generate the address of the first element of an array whenever an array name appears:
1) as an operand of the sizeof operator
2) as an operand of & operator
3) as a string literal initialize for a character array
1) as an operand of the sizeof operator
2) as an operand of & operator
3) as a string literal initialize for a character array
7. Is using exit() the same as using return?
No, the exit() function is used to exit your program and return() controls the operating system.
The return statement is used to return from a function and return control to the calling function. If you make a return from the main() function, you are essentially returning control(operating system) to the calling function. In this case, the return statement and exit() function are similar.
8. What is an lvalue?
An lvalue is an expression to which a value can be assigned. The lvalue expression is located on the left side of an assignment statement whereas an rvalue is located on the right side of an assignment statement.
Each assignment statement must have an lvalue and an rvalue. The lvalue expression must refer a storable variable in memory. It cannot be a constant.
Each assignment statement must have an lvalue and an rvalue. The lvalue expression must refer a storable variable in memory. It cannot be a constant.
9. What is the difference between goto, longjmp() and setjmp()?
1) A goto statement implements a local jump of program execution whereas the longjmp() and setjmp() functions implement a nonlocal or far jump of the program execution.
2) Generally, a jump in any execution should be avoided because it is not considered good programming practice to use such statements as goto and longjmp in your program.
3) A goto statement simply bypasses code in your program and jumps to a predefined position. To use the goto statement, you give it a labeled position to jump to. This predefined position must be within the same function. You cannot implement goto between functions.
However, when your program calls setjmp(), the current state of your program is saved in a structure of type jmp_buf. Later, your program can call the longjmp() function to restore the program’s state as it was when you called setjmp().Unlike the goto statement, the longjmp() and setjmp() functions do not need to be implemented in the same function.
There is a major drawback of using these functions: your program, when restored to its previously saved state, it will lose its references to any dynamically allocated memory between the longjmp() and the setjmp(). This means you will waste memory for every malloc() or calloc() you have implemented between your longjmp() and setjmp(), and your program will be inefficient. It is highly recommended that you avoid using functions such as longjmp() and setjmp() because they, like the goto statement, are quite often an indication of poor programming practice.
2) Generally, a jump in any execution should be avoided because it is not considered good programming practice to use such statements as goto and longjmp in your program.
3) A goto statement simply bypasses code in your program and jumps to a predefined position. To use the goto statement, you give it a labeled position to jump to. This predefined position must be within the same function. You cannot implement goto between functions.
However, when your program calls setjmp(), the current state of your program is saved in a structure of type jmp_buf. Later, your program can call the longjmp() function to restore the program’s state as it was when you called setjmp().Unlike the goto statement, the longjmp() and setjmp() functions do not need to be implemented in the same function.
There is a major drawback of using these functions: your program, when restored to its previously saved state, it will lose its references to any dynamically allocated memory between the longjmp() and the setjmp(). This means you will waste memory for every malloc() or calloc() you have implemented between your longjmp() and setjmp(), and your program will be inefficient. It is highly recommended that you avoid using functions such as longjmp() and setjmp() because they, like the goto statement, are quite often an indication of poor programming practice.
10. What do you understand by splay tree?
Splay tree is a self-balancing Binary Search Tree (BST). The main idea of splay tree is to bring the recently accessed item to root of the tree. This makes the recently searched item to be accessible in O (1) time if accessed again. The idea is to use locality of reference (In a typical application: 80% of the access are to 20% of the items).
Imagine a situation, where we have millions or billions of keys and only few of them are accessed frequently, which is very likely in many practical applications.
All splay tree operations run in O(log n) time on average, where n is the number of entries in the tree. Any single operation can take Theta(n) time in the worst case.
Imagine a situation, where we have millions or billions of keys and only few of them are accessed frequently, which is very likely in many practical applications.
All splay tree operations run in O(log n) time on average, where n is the number of entries in the tree. Any single operation can take Theta(n) time in the worst case.
11. What is Treap?
Treap is a Balanced Binary Search Tree, but not guaranteed to have height as O(Log n). The idea is to use Randomization and Binary Heap property to maintain balance with high probability. The expected time complexity of search, insert and delete is O(Log n).
1) Key follows standard BST ordering (left is smaller and right is greater)
2) Priority Randomly assigned value that follows Max-Heap property.
1) Key follows standard BST ordering (left is smaller and right is greater)
2) Priority Randomly assigned value that follows Max-Heap property.
12. How to implement LRU caching scheme? What data structures should be used?
We are given total possible page numbers that can be referred. We are also given cache (or memory) size (Number of page frames that cache can hold at a time). The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache.
A Queue: which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).
A Hash: with page number as key and address of the corresponding queue node as value. When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue. If the required page is not in the memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of queue, and add the new node to the front of queue.
A Queue: which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).
A Hash: with page number as key and address of the corresponding queue node as value. When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue. If the required page is not in the memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of queue, and add the new node to the front of queue.
13. Suppose, there are two linked lists: L1 and L2 (of same lengths) that intersect at a particular node N1, which is a common endpoint to all other nodes. What are the possibilities to find N1?
Linear solution is possible. Have two pointers say P1 pointing to the first node of L1 and P2 to that of L2. Traverse through both the lists. If P1 reaches L1’s last node, point it to the first node of L2 and continue traversing.
Do the same thing for P2 when it reaches L2’s last node. (By doing this, we are balancing the difference in the length between the linked lists. The shorter one will get over soon and by redirecting to longer list’s head, it will traverse the extra nodes also). Finally, they will meet at the Intersection node.
Do the same thing for P2 when it reaches L2’s last node. (By doing this, we are balancing the difference in the length between the linked lists. The shorter one will get over soon and by redirecting to longer list’s head, it will traverse the extra nodes also). Finally, they will meet at the Intersection node.
14. Given two keys K1 & K2, write an algorithm to print all the elements between them with K1<=K2 in a BST.
1) Linear solution is possible without using any extra space.
2) Perform an inorder traversal.
3) Once you find K1, print it and continue traversal now.
4) Once you find K1, print it and continue traversal now.
2) Perform an inorder traversal.
3) Once you find K1, print it and continue traversal now.
4) Once you find K1, print it and continue traversal now.
15. How many stacks are required to implement a Queue.
Two stacks are required to implement a Queue.
1) For Enqueue: Take two stacks S1 and S2 and perform push on S1.
2) For Dequeue: If S2 is empty, pop all the elements from S1 and push it to S2. The last element you popped from S1 is an element to be dequeued. If S2 is not empty, then pop the top element in it.
1) For Enqueue: Take two stacks S1 and S2 and perform push on S1.
2) For Dequeue: If S2 is empty, pop all the elements from S1 and push it to S2. The last element you popped from S1 is an element to be dequeued. If S2 is not empty, then pop the top element in it.
16. What is XOR linked list?
XOR linked list is a Memory Efficient Doubly Linked List. An ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory efficient version of Doubly Linked List can be created using only one space for address field with every node. This memory efficient Doubly Linked List is called XOR Linked List or Memory Efficient as the list uses bitwise XOR operation to save space for one address.
In the XOR linked list, instead of storing actual memory addresses, each node stores the XOR of addresses of previous and next nodes.
Let us call the address variable in XOR representation npx (XOR of next and previous)
In the XOR linked list, instead of storing actual memory addresses, each node stores the XOR of addresses of previous and next nodes.
Let us call the address variable in XOR representation npx (XOR of next and previous)
