Data Structures FAQ

FREQUENTLY ASKED QUESTIONS

• ·         Write your own C program to implement the atoi() function
• ·         Implement the memmove() function. What is the difference between the memmove()                                                                                and memcpy() function?
• ·         Write C code to implement the strstr() (search for a substring) function.
• ·         Write your own printf() function in C
• ·         Implement the strcpy() function.
• ·         Implement the strcmp(str1, str2) function.
• ·         Implement the substr() function in C.
• ·         Write your own copy() function
• ·         Write C programs to implement the toupper() and the isupper() functions
• ·         Write a C program to implement your own strdup() function.
• ·         Write a C program to implement the strlen() function
• ·         Write your own strcat() function
• ·         Write a C program to swap two variables without using a temporary variable
• ·         What is the 8 queens problem? Write a C program to solve it.
• ·         Write a C program to print a square matrix helically.
• ·         Write a C program to reverse a string
• ·         Write a C program to reverse the words in a sentence in place.
• ·         Write a C program generate permutations.
• ·         Write a C program for calculating the factorial of a number
• ·         Write a C program to calculate pow(x,n)?
• ·         Write a C program which does wildcard pattern matching algorithm
• ·         How do you calculate the maximum subarray of a list of numbers?
• ·         How to generate fibonacci numbers? How to find out if a given number is a                                                                                        fibonacci number or not? Write C programs to do both.
• ·         Solve the Rat In A Maze problem using backtracking.
• ·         What Little-Endian and Big-Endian? How can I determine whether a machine's                                                                                   byte order is big-endian or little endian? How can we convert from one to another?
• ·         Write C code to solve the Tower of Hanoi problem.
• ·         Write C code to return a string from a function
• ·         Write a C program which produces its own source code as its output
• ·         Write a C progam to convert from decimal to any base (binary, hex, oct etc...)
• ·         Write C code to check if an integer is a power of 2 or not in a single line?
• ·         Write a C program to find the GCD of two numbers.
• ·         Finding a duplicated integer problem
• ·         Write code to remove duplicates in a sorted array.
• ·         Find the maximum of three integers using the ternary operator.
• ·         How do you initialize a pointer inside a function?
• ·         Write C code to dynamically allocate one, two and three dimensional arrays (using malloc())
• ·         How would you find the size of structure without using sizeof()?
• ·         Write a C program to multiply two matrices.
• ·         Write a C program to check for palindromes.
• ·         Write a C program to convert a decimal number into a binary number.
• ·         Write C code to implement the Binary Search algorithm.
• ·         Wite code to evaluate a polynomial.
• ·         Write code to add two polynomials
• ·         Write a program to add two long positive numbers (each represented by linked lists).
• ·         How do you compare floating point numbers?
• ·         What's a good way to implement complex numbers in C?
• ·         How can I display a percentage-done indication on the screen?
• ·         Write a program to check if a given year is a leap year or not?
• ·         Is there something we can do in C but not in C++?
• ·         How to swap the two nibbles in a byte ?
• ·         How to scan a string till we hit a new line using scanf()?
• ·         Write pseudocode to compare versions (like 115.10.1 vs 115.11.5).
• ·         How do you get the line numbers in C?
• ·         How to fast multiply a number by 7?
• ·         Write a simple piece of code to split a string at equal intervals
• ·         Is there a way to multiply matrices in lesser than o(n^3) time complexity?
• ·         How do you find out if a machine is 32 bit or 64 bit?
• ·         Write a program to have the output go two places at once (to the screen and to a file also)
• ·         Write code to round numbers
• ·         How can we sum the digits of a given number in single statement?
• ·         Given two strings A and B, how would you find out if the characters in B were a subset                                                                        of the characters in A?
• ·         Write a program to merge two arrays in sorted order, so that if an integer is in both the                                                                    arrays, it gets added into the final array only once. *
• ·         Write a program to check if the stack grows up or down
• ·         How to add two numbers without using the plus operator?
• ·         How to generate prime numbers? How to generate the next prime after a given prime?
• ·         Write a program to print numbers from 1 to 100 without using loops!
• ·         Write your own trim() or squeeze() function to remove the spaces from a string.
• ·         Write your own random number generator function in C.*
• ·         Write your own sqrt() function in C

Data Structures Part 6

Can you construct a tree using postorder and preorder traversal? 

          

No Consider 2 trees below Tree1 a b Tree 2 a b preorder = ab postorder = ba Preorder and postorder do not uniquely define a binary tree. Nor do preorder and level order (same example). Given an expression tree, evaluate the expression and obtain a paranthesized form  of the expression.  The code below prints the paranthesized form of a tree. infix_exp(p) { if(p) { printf("("); infix_exp(p->left); printf(p->data); infix_exp(p->right); printf(")"); } } What is a threaded binary tree?   Since traversing the three is the most frequent operation, a method  must be devised to improve the speed. This is where Threaded tree comes into picture. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. An extra field called the rthread is used.  If rthread is equal to 1, then it means that the right link of  the node points to the inorder success. If its equal to 0, then the right link represents an link connecting the right subtree. struct node { int value; struct node *left; struct node *right; int rthread; } Function to find the inorder successor mynode *inorder_successor(mynode *x) { mynode *temp; temp = x->right; if(x->rthread==1)return(temp); while(temp->left!=NULL)temp = temp->left; return(temp); } Function to traverse the threaded tree in inorder void inorder(mynode *head) { mynode *temp; if(head->left==head) { printf("\nTree is empty!\n"); return; } temp = head; for(;;) { temp = inorder_successor(temp); if(temp==head)return; printf("%d ", temp->value); } } Inserting toward the left of a node in a threaded binary tree. void insert(int item, mynode *x) { mynode *temp; temp = getnode(); temp->value = item; x->left = temp; temp->left=NULL; temp->right=x; temp->rthread=1; } Function to insert towards the right of a node in a  threaded binary tree. void insert_right(int item, mynode *x) { mynode *temp, r; temp=getnode(); temp->info=item; r=x->right; x->right=temp; x->rthread=0; temp->left=NULL; temp->right=r; temp->rthread=1; } Function to find the inorder predecessor (for a left threaded binary three) mynode *inorder_predecessor(mynode *x) { mynode *temp; temp = x->left; if(x->lthread==1)return(temp); while(temp->right!=NULL) temp=temp->right; return(temp); }

Data Structures Part 5

How do you convert a tree into an array? 

          

The conversion is based on these rules If i > 1, i/2 is the parent If 2*i > n, then there is no left child, else 2*i is the left child. If (2*i + 1) > n, then there is no right child, else (2*i + 1) is the  right child. Converting a tree to an array is very easy Suppose we have a tree like this A B C D E F G The array representation would be a[1] a[2] a[3] a[4] a[5] a[6] a[7] A B C D E F G That is, for every node at position i in the array, its left child  will be stored at position (2*i) and right child at (2*i + 1). The root starts at position 1. A full N-ary tree has M non-leaf nodes, how many leaf nodes does it have?  Use Geometric progression. M + (N ^ (n-1)) = (1 - (N ^ n)) / (1 - N) Here (N ^ (n-1)) is the number of leaf-nodes. Solving for this leads to the answer Leaf nodes = M * (N - 1) + 1 Suppose you have a 3-ary tree A B C D E F G H I J K L M So, here M=4 and N=3. So using the formula above, Leaf nodes = M * (N - 1) + 1 = 4 * (3 - 1) + 1 = 9

Data Structures Part 4

Given only a pointer to a node to be deleted in a singly linked list, how do you delete it? 

          

#include #include struct linkedList{ int element; struct linkedList* next; }; typedef struct linkedList* List; void deleteNode(List Node) { List tmp; if(Node){ // If current node is not NULL tmp = List->next; // take backup of next Node Node->element = Node->next->element; // replace current node element  with next Node element Node->next = Node->next->next; // change next pointer to next to  next free(tmp); // free the next Node which was taken backup } return; } How do you reverse a linked list without using any C pointers?  One way is to reverse the data in the nodes without changing the pointers  themselves.One can also create a new linked list which is the reverse of  the original linked list. A simple C program can do that for you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but you are not changing them when reversing the linked list). How can I search for data in a linked list?  The only way to search a linked list is with a linear search, because the only way a linked list?s members can be accessed is sequentially.  Sometimes it is quicker to take the data from a linked list and store  it in a different data structure so that searches can be more efficient.

How would you find out if one of the pointers in a linked list is corrupted or not? 

          

This is a really good interview question. The reason is that linked lists are used in a wide variety of scenarios and being able to detect and correct pointer corruptions might be a very valuable tool. For example, data blocks associated with files in a file system are usually stored as linked lists. Each data block points to the next data block. A single corrupt pointer can cause the entire file to be lost! Discover and fix bugs when they corrupt the linked list and not when  effect becomes visible in some other part of the program.  Perform frequent consistency checks (to see if the linked list is indeed holding the data that you inserted into it). It is good programming practice to set the pointer value to NULL immediately after freeing the memory pointed at by the pointer. This will help in  debugging,because it will tell you that the object was freed somewherebeforehand.  Keep track of how many objects are pointing to a object using  reference counts if required.  Use a good debugger to see how the datastructures are getting corrupted and trace down the problem. Debuggers like ddd on linux and memory profilers like Purify,Electric fence are good starting points. These tools should help you track down heap corruption issues easily. Avoid global variables when traversing and manipulating linked lists. Imagine what would happen if a function which is only supposed to traverse a linked list using a global head pointer accidently sets the head pointer to  NULL! Its a good idea to check the addNode() and the deleteNode() routines and  test them for all types of scenarios. This should include tests for  inserting/deleting nodes at the front/middle/end of the linked list, working with an empty linked list, run out of memory when using malloc() when allocating memory for new nodes, writing through NULL pointers, writing more data into the node fields then   they can hold (resulting in corrupting the (adjacent) "prev" and "next" pointer fields), make sure bug fixes and enhancements to the linked list code are reviewed and well tested (a lot of bugs come from quick and dirty bug fixing), log and handle all possible errors , add multiple levels of logging so that you can dig through the logs. The list is endless...  Each node can have an extra field associated with it. This field indicates  the number of nodes after this node in the linked list. This extra field needs to be kept up-to-date when we inserte or delete nodes in the linked list  (It might become slightly complicated when insertion or deletion happens not  at end, but anywhere in the linked list).Then, if for any node, p->field > 0 and p->next == NULL, it surely points to a pointer corruption. You could also keep the count of the total number of nodes in a linked list and use it to check if the list is indeed having those many nodes or not. The problem in detecting such pointer corruptions in C is that its only the  programmer who knows that the pointer is corrupted. The program has no way of knowing that something is wrong. so the best way to fix errors is check Ur logic and test your code to the max possible event. If you detect a cycle in the link list, it's definitely bad.  If it's a doubly linked list you can verify, pNode->Next->Prev== pNode. I have a hunch that interviewers who ask this question are probably hinting at  something called Smart Pointers in C++. Smart pointers are particularly useful in the face of exceptions as they ensure proper destruction of dynamically allocated objects.They can also be used to keep track of dynamically allocated  objects shared by multiple owners. This topic is out of scope here, but you can find lots of material on the Internet for Smart Pointers.