Refurnish Technical Skills

Implementatio in C: Using Array #include<stdio.h> #include<stdlib.h> struct stack {     int top;     unsigned capacity;     int* array; }; struct stack* create(unsigned capacity) {     struct stack* stack = (struct stack*)malloc(sizeof(struct stack));     stack->top = -1;     stack->capacity = capacity;     stack->array = (int*)malloc(capacity * sizeof(int));     return(stack); } int isFull(struct stack* stack) {     return(stack->top == stack->capacity - 1); } int isEmpty(struct stack* stack) {     return(stack->top == -1); } void push(struct stack* stack, int data) {     if(isFull(stack))         printf("Stack overflow");     stack->array[++stack->top] = data;     printf("\nPushed data on stack : %d\n",data); } int pop(struct stack* stack) {     if(isEmpty(...

Implementation in C: #include<stdio.h> #include<stdlib.h> struct node { int data; struct node* next; }; void push(struct node** ref, int newData) {     struct node* newNode = (struct node*)malloc(sizeof(struct node));     newNode->data = newData;     newNode->next = (*ref);     (*ref) = newNode; } int identical(struct node* a,struct node* b) {     while(1)     {     if(a == NULL && b == NULL)         return 1;     if(a == NULL && b != NULL)         return 0;     if(a != NULL && b == NULL)         return 0;     if(a->data != b->data)         return 0;     a = a->next;     b = b->next;     } } int main() {     struct node* a = NULL;     struct node* b = NULL;     p...

Implementation in C: #include<stdio.h> #include<stdlib.h> struct node { int data; struct node* next; }; void push(struct node** ref, int newData) {     struct node* newNode = (struct node*)malloc(sizeof(struct node));     newNode->data = newData;     newNode->next = (*ref);     (*ref) = newNode; } void print(struct node* n) {     struct node* temp = n;     if(temp == NULL)     {     printf("Empty LinkedList");     }     while(temp!=NULL)     {     printf(" %d",temp->data);     temp=temp->next;     } } void alternateDelete(struct node* head) {     struct node* prev= head;     struct node* node=head->next ;     if(head == NULL)         return;     while(prev != NULL && node != NULL)     {     prev->...

Implementation in C: #include<stdio.h> #include<stdlib.h> struct node { int data; struct node* next; }; void push(struct node** ref, int newData) {     struct node* newNode = (struct node*)malloc(sizeof(struct node));     newNode->data = newData;     newNode->next = (*ref);     (*ref) = newNode; } void print(struct node* n) {     struct node* temp = n;     if(temp == NULL)     {     printf("Empty LinkedList");     }     while(temp!=NULL)     {     printf(" %d",temp->data);     temp=temp->next;     } } void relocate(struct node** head) {     struct node* current= *head;     struct node* temp= NULL;     if(*head == NULL || (*head)->next == NULL)         return;     while(current->next != NULL)     {     tem...

Implementation in C: #include<stdio.h> #include<stdlib.h> struct node { int data; struct node* next; }; void push(struct node** ref, int newData) {     struct node* newNode = (struct node*)malloc(sizeof(struct node));     newNode->data = newData;     newNode->next = (*ref);     (*ref) = newNode; } void print(struct node* n) {     struct node* temp = n;     if(temp == NULL)     {     printf("Empty LinkedList");     }     while(temp!=NULL)     {     printf(" %d",temp->data);     temp=temp->next;     } } void pairswap(struct node* head) {     struct node* current = head;     while(current!=NULL && current->next != NULL)     {     swap(&current->data,&current->next->data);     current = current->next->next; ...

void removeDuplicates(struct node* head) {     struct node* current = head;     struct node* next;     if(current == NULL)         return;     while(current->next!= NULL)     {         if(current->data == current->next->data)         {         next=current->next->next;         free(current->next);         current->next=next;         }         else         {         current = current->next;         }     } }   Time Complexity:  O(n)

void printReverse(struct node* head) { if(head == NULL) return; else printReverse(head->list); printf("%d",head->data); } Time Complexity:  O(n)

Logic: 1) Find the total number of elements in both the LL. 2) Find the difference between number of elements of the two linked list. 3) Move the pointer of that LL which contains more number of elements by the difference. 4) Then move the pointers of both the list and check if nodes present in first LL is same as the node present in second LL. Time Complexity:  O(m+n) if first LL contains m elements and second LL contains n elements. Space Complexity:  O(1)

Logic: 1) If LL is empty, then insert the node as head and return it. 2) If value of node to be inserted in LL is less than the value of the head node, then insert the node at start and make it head. 3) Otherwise, traverse through the list and find the appropriate place for the node and check if the value of node to be inserted is less than the value of next node, then insert the node before the next node. Implementation in C: #include<stdio.h> #include<stdlib.h> struct node {     int data;     struct node* next; }; struct node* newNode(int newData) {     struct node* newNode = (struct node*)malloc(sizeof(struct node));     newNode->data=newData;     newNode->next=NULL;     return newNode; } void print(struct node* n) {     while(n!=NULL)     {         printf("%d    ",n->data);         n=n->next;   ...

Method 1: Traverse linked list using two pointers. Move first pointer by one and second pointer by two, when second pointer reaches to the end of the list, then first pointer will reach to the middle of the list. Implementation in C: #include<stdio.h> #include<stdlib.h> struct node {     int data;     struct node* next; }; int main() {     struct node* head = NULL;     push(&head,1);     push(&head,2);     push(&head,3);     push(&head,4);     push(&head,5);     push(&head,6);     push(&head,7);     printMiddle(head);     return 0; } void push(struct node** ref, int newData) {     struct node* newNode = (struct node*)malloc(sizeof(struct node));     newNode->data = newData;     newNode->next = (*ref);     (*ref) = newNode; } void printMiddle(struct node...

From beginning of the list: #include<stdio.h> #include<stdlib.h> struct node {     int data;     struct node* next; }; int main() {     struct node* head = NULL;     push(&head,8);     push(&head,7);     push(&head,3);     push(&head,4);     push(&head,1);     printf("LinkedList:\n");     print(head);     int value = GetNth(head,0);     printf("\nValue of Nth node is: %d",value);     return 0; } void push(struct node** ref, int newData) {     struct node* newNode = (struct node*)malloc(sizeof(struct node));     newNode->data = newData;     newNode->next = (*ref);     (*ref) = newNode; } int GetNth(struct node* head, int index) {     struct node* current = head;     int count =0;     while(current != NULL)    ...

#include<stdio.h> #include<stdlib.h> struct node {     int data;     struct node *next; }; int main() {     struct node *head = NULL;     push(&head,7);     push(&head,8);     push(&head,4);     push(&head,3);     printf("\n Linked List is:\n");     print(head);     delete(&head,8);     printf("\n LinkedList after Deletion of 8: \n");     print(head);     return 0; } void push(struct node** ref, int newData) {     struct node *newNode = (struct node*)malloc(sizeof(struct node));     newNode->data = newData;     newNode->next = (*ref);     (*ref) = newNode; } void delete(struct node** headref,int key) {     struct node* temp = *headref;struct node* prev;     if(temp != NULL && temp->data == key)     {   ...

#include<stdio.h> #include<stdlib.h> struct node { int data ; struct node * next ; }; int main () { struct node * head = NULL ; append ( & head , 8 ); append ( & head , 7 ); push ( & head , 3 ); push ( & head , 4 ); append ( & head , 5 ); insertAfter ( head -> next -> next , 1 ); printf ( "Linked List is: \n " ); print ( head ); return 0 ; } void push ( struct node ** ref , int newData ) { struct node * newNode = ( struct node * ) malloc ( sizeof ( struct node )); newNode -> data = newData ; newNode -> next = ( * ref ); ( * ref ) = newNode ; } void insertAfter ( struct node * prev , int newData ) { if ( prev == NULL ) { printf ( "the given previous node can't be null" ); return 0 ; } struct node * newNode = ( struct node * ) malloc ( sizeof ( struct node )); ...

#include<stdio.h> #include<stdlib.h> struct node {  int data;  struct node *next; }; int main() {  struct node *head = NULL;  struct node *second = NULL;  struct node *third = NULL;  head = (struct node*)malloc(sizeof(struct node));  second = (struct node*)malloc(sizeof(struct node));  third = (struct node*)malloc(sizeof(struct node));  head->data = 1;  head->next = second;  second -> data = 2;  second -> next = third;  third -> data =3;  third -> next = NULL;  print(head);  return 0; } void print(struct node *n) {  while(n!= NULL)  {  printf("%d",n->data);  n = n ->next;  } }

We can take string as input with the help of gets() function but this function suffers with the problem of buffer overflow as it does not care about the maximum limit of array of characters (do not perform aray bound testing) and it takes input as long as it sees a newline character. Apart from it, fgets reads string input till the maximum limit of array is reached.

It is not possible to directly check equality of two structures but can compare two structures by element by element basis. Reason:   There is not a good way for a compiler to implement structure comparison (i.e. to support the  ==  operator for structures) which is consistent with C's low-level flavor. A simple byte-by-byte comparison could founder on random bits present in unused ``holes'' in the structure (such padding is used to keep the alignment of later fields correct . A field-by-field comparison might require unacceptable amounts of repetitive code for large structures. Any compiler-generated comparison could not be expected to compare pointer fields appropriately in all cases: for example, it's often appropriate to compare  char *  fields with  strcmp  rather than  ==.   Struct Hack:  This technique is mainly used to create variable length array as a member in structure. We generally keep that element as last element of...

Implementation in C: #include<stdio.h> #include<string.h> #include<stdlib.h> int isRotation(char *s1, char *s2) { int len = strlen(s1); if(len == strlen(s2) && len >0) { char *temp; void *ptr; temp = (char*)malloc(sizeof(char)*(len*2 +1)); temp[0] = '\0'; strcat(temp,s1); strcat(temp,s1); ptr = strstr(temp, s2); free(temp); if(ptr!= NULL) return 1; else return 0; } return 0; } void main() { char *s1 = "waterbottle"; char *s2 = "erbottlewat"; if( isRotation(s1, s2)) { printf("Yes, s2 is the rotation of s1."); } else { printf("No, s2 is not the rotation of s1."); } } Time Complexity:  Complexity of this function depends on the implementation of strstr function.

In Object Oriented Programming, a virtual function or method is a function whose behavior can be overridden within an inheriting class by a function with the same signature. This concept is important part of polymorphism. Virtual function allows a program to call methods that don't necessarily even exist at the moment code is compiled. In C++, virtual methods are declared by prepending the function with the virtual keyword in the base class. This modifier is inherited by all implementations of that method in derived classes, meaning that they can continue to over-ride each other and be late-bound. For example, a base class  Animal  could have a virtual function  eat . Subclass  Fish  would implement  eat() differently than subclass  Wolf , but one can invoke  eat()  on any class instance referred to as Animal, and get the  eat()  behavior of the specific subclass. A  pure virtual function  or  pure virtual method ...

In C (and C++) a macro is a preprocessor directive. This means that before your program starts compiling it will go through and process all your macros. Macros are useful because They can make your program easier to read They can improve efficiency (as they can be calculated at compile time) They can shorten long or complicated expressions that are used a lot.  Disadvantages: Expand the size of your executable Can flood your name space if not careful. For example, if you have too many preprocessor macros you can accidentally use their names in your code, which can be very confusing to debug. The compilation and execution process of C can be divided in to multiple steps: Preprocessing - Using a Preprocessor program to convert C source code in expanded source code. "#includes" and "#defines" statements will be processed and replaced actually source codes in this step. Compilation - Using a Compiler program to convert C expanded source to assembly ...

There are many factors that decide the size of an object of a class in C++. These factors are: Size of all non-static data members Order of data members Byte alignment or byte padding Size of its immediate base class The existence of virtual function(s) (Dynamic polymorphism using virtual functions). Compiler being used Mode of inheritance (virtual inheritance)

Algo1:  Take every node address of original LinkedList and add to visited LinkedList if it is not exist.              else print loop is found. Time Complexity: O(n^2) Space Complexity: O(n) Algorithm 2: 1. Modify every node of the LL by inserting an extra field which is initially set to 0. 2. Visit every node of LL and verify     flag is 0 or not          if 0 , then make 1          else print loop exist Time Complexity: O(n) Space Complexity: O(n) Algorithm 3: 1. Take 2-pointer p and q where p=q=list 2. Increase p by 1 and increase q by 2 3. if(p==q), then print loop found    else goto step 2 Time Complexity: O(n) Space Complexity: O(1) Implementation in C:

Implementation in C: #include<stdio.h> #include<stdlib.h> void main() {   int **array,nrows,ncols,i,j;   printf("\n Enter number of rols and columns for matrix:\n");   scanf("%d%d", &nrows, &ncols);   array =malloc(nrows*sizeof(int*));   for(i=0;i<nrows;i++)     {         array[i] = malloc(ncols*sizeof(int*));     }   printf("\n Enter Matrix data: \n");   for(i=0; i<nrows; i++)    {        for(j=0; j<ncols; j++)        {            scanf("%d", &array[i][j]);        }        printf("\n");    }   if(array == NULL)   {     printf("Out of memory");     exit(0);   }   printf("\n Print Matrix data: \n");   for( i=0; i<nrows; i++)   {      for(j=0; j<ncols; ...

Problem:  You have N computers and [Ca, Cb] means a is connected to b and this connectivity is symmetric and transitive. Write a program which checks that all computers are interconnected and talk to each other. Solution:  BFS. Since graph is connected, there will be path from every node to another.  Algorithm: BFS(V)      VISITED(V) =1;      Add(V,Q);      while(Q is not empty)                x= Delete(Q);                for all W adjacent x                      if(W is not visited)                             Visited(W) = 1;                             Add(W,Q); Implementation in C:  BFS Time complexity:  O(V + (V...

Algorithm: 1. Check if both trees are empty , return 1 2. If both trees are not empty:  a) Compare data of root node  b) Check left subtree recursively and compare  c) Check right subtree recursively and compare  d) If all above conditions return true, then return 1. 3. If any one of the tree is empty, return 0. Implementation in C: #include<stdio.h> #include<stdlib.h> struct node {  int data;  struct node *left;  struct node *right; }; struct node *newnode(int data) {  struct node *node = (struct node*) malloc(sizeof(struct node));  node->data = data;  node->left = NULL;  node->right = NULL;  return(node); } int identical(struct node *a, struct node *b)  {   if(a == NULL && b == NULL)    return 1;   else   {    if( a!= NULL && b!= NULL)    {      return ( a->data == b->data &...

Case 1: When range of elements is given Take an array count depending on the range of elements and initialize every element as zero. Traverse the entire unsorted / sorted array, keep track of count of all elements if you find any element whose count is not zero, then print that element as repeating element. Implementation in C: #include<stdio.h> #include<stdlib.h> void repeat(int*, int); int main()  {   int arr[] = {4, 5, 6, 5, 3, 1};   int arr_size = sizeof(arr) / sizeof(arr[0]) ;   repeat(arr, arr_size);   return 0;  } void repeat(int arr[], int size)  {   int *count = (int*) calloc(sizeof(int), (size-2) );   int i, flag =0;   for(i=0;i<size;i++)   {     if (count[arr[i]] == 0)       count[arr[i]] = 1;    else       flag = 1;   }  if(flag == 0)   printf("\nAll unique elements are present in array");  else   ...

There are many different ways to find the 2's complement of the binary number. One of the way is start from LSB and till the '1' comes for the first time copy the bits as it is till the first 1 place and then flip rest of the bits. Implementation in C: #include<stdio.h> #include<string.h> void complement(char*); int main() { char a[] = "1010100"; complement(a); return 0; } void complement(char *a) { int l = strlen(a)-1; while (a[l] == '0') { l--; } l--; while (l>=0) { if(a[l] == '0') a[l] = '1'; else a[l] = '0'; l--; } printf("2's Complement of binary number: %s",a); } Algorithm to find 2's Complement (Outplace)

Given a program: int i; int main() { int j; int *k = (int *) malloc (sizeof(int)); ... } Where are each of these variables stored? Solution: (int *) malloc (sizeof(int)) --- this will allocate memory in heap of size int. int *k --- this will allocate memory in call stack and point to memory present in the heap

Stack is the best data structure to check balance of parentheses in Expression. Last opened , first closed Last closed, first opened 1. Scan from left to right. 2. If opening bracket, then add it to stack 3. If closing bracket, then remove last opening symbol from stack. 4. At end, stack should be empty. In whole process, bracket is added or removed from same end of the list, so stack can be used here. Implementation in C: #include<stdio.h> #include<stdlib.h> #define bool int struct node  {   char data;   struct node *next;  }; void push(struct node**,int); int pop(struct node**); bool isMatching(char character1, char character2) {  if(character1 == '(' && character2 == ')')   return 1;  else if(character1 == '{' && character2 == '}')   return 1;  else if(character1 == '[' && character2 == ']')   return 1;  else   return 0; } /*Return 1 if expression has ...

Algorithm: 1. Initialize both first and second smallest as INT_MAX. 2. Traverse elements of array i. If the element of array is smaller than first , then update second with first and first with that element. ii. If the element of array is smaller than second , then update second with that element and check if that element of array is not equal to first element. Implementation in C: #include<stdio.h> #include<limits.h> void printsmall(int,int); int main() { int arr[]={19,18,17,38,12,15,9,6,4}; printsmall(arr,9); return 0; } void printsmall(int arr[], int n) {   int i,first,second;   first=second=INT_MAX;   for(i=0;i<n;i++)     {     if(arr[i]<first)     {     second=first;     first=arr[i];     }     else if(arr[i]<second && arr[i]!=first)     {     second=arr[i];     }     }  if(second==INT_MAX) ...

Storage class determines the amount of memory allocated for the variable and how long the storage allocation continues to exist. It also determines the part of program over which that variable is visible. Four storage classes in C: 1. Auto 2. Register 3. External 4. Static Auto Storage Class: It is default storage class in C. These variables are declared inside the function in which they are to be used. They are created at the time of function call and destroyed automatically when we exit from the function. If automatic variables are not initialized, they will contain garbage value. Extern Storage Class:  These variables are declared outside the function. Generally, known as Global Variables and default value is zero. Extern declaration does not allocate storage space for variables. If any variable is declared as extern, then compiler checks for that variable initialization in the program. If that variable is not initialized, then compiler will show an error. Any ext...

Stack overflow generally occurs when computer program tries to use more memory space than call stack has available. The call stack is consists of limited amount of address space, often determined at the start of the program. The size of call stack depends on many factors like architecture of the machine on which program runs, programming language, and amount of memory available in the system. When a program tries to use more memory than that is available to call stack i.e. out of call stack bounds, then the stack is said to overflow. Whenever stack overflow occurs due to excessive demand of memory, then program (sometimes the whole computer) may crash. Reasons for Stack Overflow: 1. This error can be caused by certain types of malware. It can be minimized by reviewing the latest updated OS and avoiding websites and embedded email links. 2. Most common cause is excessively deep or infinite recursion. Lets understand it with the below code snippet of Infinite recursion in C: int ...

Data structures can be used to implement cache:- 1. A Queue which is implemented using doubly Linked List. 2. A Hash table For more info, refer to below link: Implementation in C

Both type of data structure are used to store linear data of similar types. Though, both have some positive and negative sides. Advantages of linked list over array: 1. Dynamic Size                          As the size of array is fixed, we need to know the upper limit of number of elements in advance. But in practical use, number of elements are less than the upper limit so there is wastage of allocated memory. 2. Ease of Insertion / Deletion                                          In case of array it is difficult to insert or delete any element in middle of the array as for both insertion and deletion in array, we have to shift other elements to the right or left in the array Advantages of Array over Linked List: 1. Random access is allowed in array but random access is not allowed in Linked List. We hav...

Problem:  Another term for the same problem is Jelly Beans Problem. Mostly asked in Interview as Puzzle. Suppose you have three jars. One jar contains Apple, another jar contains Orange and third jar contains mixture of both the fruits. You have to fix the labels of jars by picking up as many fruits as you want from each jar. What is the minimum number of fruits that you have to pick and from which jars to correctly label them ? Solution:  As all jars are labeled incorrectly. So, if you pick one fruit from jar label Apple+Oranges, then whatever fruit comes be it Apple or Orange, then label that jar with the name of that fruit. Lets say orange come out of it, then label jar with Orange which was initially labelled as Apple+Orange. Now, jar labeled with Orange can be jar of either apples or mixture of fruits and jar labeled with Apple can be jar of either apples or mixture of fruits but jar labeled with Apple can't be labeled with Apple so it has to be jar of Apple+Orange. ...

Gap Buffer is one of the data structure that is used in the implementation of popular text editor "Notepad++". It is one of the frequently used data structure for text editors. Gap Buffer is a dynamic array that allows insertion and deletion efficiently. Mostly changes took place in editors at the place where cursor is pointing at that time. Data is divided into two strings usually considering point at which cursor is located and one side of the gap is stored in one buffer and other side of the gap is stored in other buffer and as the cursor is moved so follows the text. There is another data structure Rope  which is binary tree having leaf nodes as small strings. In this, weight of the string i.e. length of the string is also stored. Each node has weight equal to the length of the string plus sum of all the weights of its left subtree.  Thus a node with two children divides the whole string into two parts: the left subtree stores the first part of the string. The righ...

One and only difference between an array and a pointer pointing to the beginning of the array is that the compiler keeps some extra information for the arrays, to keep track of their storage information. Lets understand it more with the example by using the sizeof operator :  If we get the size of both an array and a pointer using the sizeof  operator, sizeof(ptr) will give us how much space does the pointer itself occupies (4 in case of int) while sizeof array will give us, the amount of space occupied by the whole array (if array contains 10 elements of int data-type (2 bytes) , then this operator will give 20). In general, *(array+n) is equivalent to array[n].

Limitation of Void Pointers: 1. They can't be dereferenced.     Reason:  Each variable type takes different amount of memory. So, in order to read the actual value stored there, the compiler has to know how many consecutive memory locations to read in order to get the full value. Dereferencing a pointer means getting the value that is stored in the memory location pointed by the pointer. The operator * is used to do this, and is called the dereferencing operator. 2. We can't perform arithmetic operations on them.   Reason:  The compiler cannot know how many bytes ahead the next variable is located. Void pointers are mainly used to keep addresses that we have to convert later on to a specific pointer type, before using them.