What Did He Code?

Problem - Given two sorted linked lists, merge them so that the resulting linked list is also sorted. Approach - Create a linked list with NULL value, Maintain a head and tail pointer to traverse the linked lists. Choose head of the merged linked list by comparing the first nodes of both the linked lists, the one with lowest value gets inside the merged linked list. Move pointer one step forward and repeat. Code-  typedef  node *  temp ; node *  merge_sorted ( temp head1 ,  temp head2 ) {    if ( head1 == NULL )    {      return  head2 ;    }    else   if ( head2 == NULL )    {      return  head1 ;    }      temp mergedhead =  NULL ;   //merged head     if ( head1->data <= head2->data )    {     mergedhead = head1 ;     head1 =...

Problem - You are given an array from 1 to n, such that all numbers are present except 'x'.  Find 'x' Approach - We know that the sum of all numbers from 1 to n is n(n+1)/2, If we know this value, then we can easily delete the sum of all the elements except x to find x. Code - #include< bits/stdc++.h > using   namespace  std ; int  main () {    int  n ;  cin >> n ;    int  sum_of_n  =   ( n *( n + 1 ))/ 2 ;    int  arr [ n ];    int  sum_of_arr ;    for ( int  i = 0 ; i < n ; i ++)    {     cin >> arr [ i ];     sum_of_arr += arr [ i ];    }    int  x =  sum_of_arr  -  sum_of_n ;   cout << x ;    return   0 ; }

Finding subarrays can become a cumbersome task to handle if we don't know the right approach for it. In this particular question we will be using a new method.  Pair is used to combine together two values which may be different in type. Pair provides a way to store two heterogeneous objects as a single unit. Such as vector<first attribute, second attribute>. To access these attributes we use keywords 'first' and 'second' Approach - Input values and find total sum of all terms Create a loop and calculate average term by term, use logic ->  sum= first element this_average=sum/elements in the sum SZ= Elements left in array= size-elements in sum other_average=(total-sum)/SZ Use if loop to find whether this_average is bigger than other_average or not. If true, input the (i+1)th and (j+1)th element in the pair, Increment counter by 1 Sort the pair and output it. Code- #include< bits/stdc++.h > using namespace std ; int main () {       ...

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(right subtree) The balance factor of any node of an AVL tree is in the integer range [-1,+1]. If after any modification in the tree, the balance factor becomes less than −1 or greater than +1, the subtree rooted at this node is unbalanced, and a rotation is needed. Code -  int height(node* root) {     if(root)             return root->ht;     else         return -1; } void rotateright(node* &root) {     node* temp= root->left;     root->left= root->left->right;     temp->right=ro...

Question - A binary tree is a tree which is characterized by one of the following properties: It can be empty (null). It contains a root node only. It contains a root node with a left subtree, a right subtree, or both. These subtrees are also binary trees. In-order traversal is performed as Traverse the left subtree. Visit root. Traverse the right subtree. For this in-order traversal, start from the left child of the root node and keep exploring the left subtree until you reach a leaf. When you reach a leaf, back up to its parent, check for a right child and visit it if there is one. If there is not a child, you've explored its left and right subtrees fully. If there is a right child, traverse its left subtree then its right in the same manner. Keep doing this until you have traversed the entire tree. You will only store the values of a node as you visit when one of the following is true: it is the first node visited, the first time visited it is a leaf, should only be visited once...

There's one thing i realized over the course of these months, given time and practice, you can become good at the things you thought you were not capable or smart enough to crack.  I had flagged this question because i wasn't sure of how to code it and 3 days later i started with this question, all along playing with ideas and somehow, all the test cases passed. Remember kids, If you don't get it in first try, try again, if you fail...give some time and come back to it after some time.  Question- Given a square grid of characters in the range ascii[a-z], rearrange elements of each row alphabetically, ascending. Determine if the columns are also in ascending alphabetical order, top to bottom. Return  YES  if they are or  NO  if they are not. Approach- Sort the elements in the array Create a bool function to check if element in column 1 is lesser than or greater than element in column 2 Implement the bool function over the array Return YES or NO accordingly...

Sometimes it's better to stop and first formulate a way to solve a problem before jumping right into it. Why? Well because it gives you more time to better understand a problem and secondly, in some cases even a simpler way to solve a problem.  Remember kids! When solving algorithms, Math is your friend! I realized that a little late into this question and when i did, it was just a 5 min snippet. Question-  Approach - It's quite simple and straight forward.  Instead of dividing array into two halves, getting their sums, checking whether the sums are equal and trying to find out if an element which causes sum to be unequal exist or not, here's a better approach. array - [5,6,8,11] , here we have 5+6=11 in LHS and 11 in RHS with 8 being an extra element. Imagine LHS and RHS as same, ex - x+y+x= sum. i.e 2x= sum-y. Here we just need to check if this equality holds, if it does we print YES and add value to x, else we print NO Code- 

Sometimes the easiest of the questions can become cumbersome and actually put our knowledge to the test. The following question had me writing code for 30 minutes, only to be rejected by the compiler telling me that I was missing something! Question-  Approach -  Make a new array with last element = 0   Input all values of Bigger array Delete similar values found in Smaller array Print all the values which are higher than 0 Now what took me so long? I made nested for loops to check every value of A if it lies in B, if it doesn't, I would append this value to an empty array, sort it and print it. But when i did that, It gave me repeating values and the output was in the form of m+n where m and n are sizes of the array respectively. Hence, I had to do some brainstorming and research which led me to a realization that i can simply add all elements of bigger array brr[m] in a new array C, then delete the same values from C taking elements of arr[n] into consideration!...

Here we have another Hackerrank question on String manipulation, this one involving the classic Palindrome index.  Question-  Approach - Pretty simple, we just need to check values one by one, iterating a loop from index 0 being compared to index n, where n is the last value in the index, narrowing it down to inner values one by one. The point where the elements do not stay equal is the point where element needs to be removed in order to make the string into a palindrome  The steps are -  initialise i = 0; j= string.length()-1 //last value in the string Run a loop from i to middle of the string, i increments while j decrements, bringing us a section to focus on within the string Run an if condition which checks whether character at i is equal to j or not If it is not equal, we check if the element after character at i is equal to j or not If yes, we check whether the element before j is equal to character at i and character after i is subsequently equal to element at...

Hello There! Been a long time since i posted anything here, Oh no no, I didn't forget i had a blog, Just got really busy preparing for my Semester end exams and now i am free! So today we have a question with us from Hackerrank based on String Manipulations. Question-   Approach- First we define all the conditions which will result into a failed attempt to solve the conditions mentioned, by creating a function called - Bool alternate which gives us False conditions if 2 characters chosen are equal, do not belong in the original string or size constraints are not met. Next, in the main function,  Input string s Run a loop for char a, iterating over alphabets a-z Run a nested loop for char b, iterating over alphabets b-z for every iteration, if char a is equal to char b, we move ahead  we check whether char a or b exists in the string s, if they do, we input the value in a mew string t In the end we run alternate function to check false conditions  After running t...

 Union( List1, List2) --> Create an empty Hash Table, Traverse both lists one by one, for each element visited, look for the element in the hash table, if not present --> add it, if present --> ignore it.  Intersection( List1 , List 2 ) --> Create empty Hash Table, Traverse list 1, Initialize Result List as NULL, insert elements of List 1 in hash table, Traverse List2 and look for the element in the hash table, if present, Insert it into the Result List, else ignore it.  Code--> #include<bits/stdc++.h> using namespace std; struct Node{     int data;     struct Node* next; }; //utility function to insert node  void push(struct Node* head, int new_data) {     struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));     new_node->data= new_data;     new_node->next= head;     head= new_node; } //function to store elements of both lists void store(struct Node* head1, struct No...

 Given an array of N elements, where each element is at most k away from its target position, devise and algorithm to sort in O(n logk) time Method - We can either use insertion sort code-->  void insertionsort(int arr[], int size) {          int i, key, j;            for(int i=1; i<size; i++)            {   key=arr[i];               j=i-1;               while(j>=0 && arr[j] > key)               {         arr[i+1]=arr[i];                           j-=1;                   }                    arr[j+1]=key;      ...

 Question- write an efficient program to print k largest elements in an array. Elements in array can be in any order.  Method- Sort array in descending order, print first k elements  code- #include<bits/stdc++.h> using namespace std; void kelements(int arr[], int n, int k) {     sort( arr, arr + n, greater<int>());     for(int i = 0 ; i < k ; i ++)     {               cout<<arr[i]<<" ";     }

Problem You are conducting a contest at your college. This contest consists of two problems and  participants. You know the problem that a candidate will solve during the contest. You provide a balloon to a participant after he or she solves a problem. There are only green and purple-colored balloons available in a market. Each problem must have a balloon associated with it as a prize for solving that specific problem. You can distribute balloons to each participant by performing the following operation: Use green-colored balloons for the first problem and purple-colored balloons for the second problem Use purple-colored balloons for the first problem and green-colored balloons for the second problem You are given the cost of each balloon and problems that each participant solve. Your task is to print the minimum price that you have to pay while purchasing balloons. Approach -  First we input all the values and then iterate loops to find if jth element of array [i][j] is 1 or ...

Problem You are given two arrays a1,a2,…,an and b1,b2,…,bn. In each step, you can set ai=ai−bi if ai≥bi. Determine the minimum number of steps that are required to make all a's equal. Input format First line: n  Second line: a1,a2,…,an Third line: b1,b2,…,bn Output format Print the minimum number of steps that are required to make all a's equal. If it is not possible, then print -1. Constraints 1≤n, ai, bi≤5000 Sample input 2 5 6 4 3 Sample output -1 Approach -> We need to make sure that all the elements of the array A are equal, we will set the first value of the array A[] as minimum and iterate a loop to find the min value in the array, Once found we will iterate another loop to check array values higher than min value and perform a[i]-b[i] operation until they are equal to min. A step variable will be created to increment after every operation. CODE-> #include < stdio.h > int main (){ int n , i , a [ 5000 ], b [ 5000 ], min = a [ 0 ], steps = 0 , f = 0 ; scanf...

There is a circle, you are given 2 values-> The amount of petrol in every petrol pump Distance of petrol pump to the next petrol pump Calculate the first point from where a truck will be able to complete the circle(truck stops at each pump and has infinite capacity). Assume for 1ltr petrol, the truck can go 1 unit of distance. Example- there are 4 petrol pumps with amount of petrol and distance to next petrol pump in pairs as {4,3},{6,5},{7,3},{4,5}. The first point from where the truck can make a circular tour is 2nd petrol pump.  Output should be "start=1" (index of 2nd petrol pump) An easy solution is to consider ever petrol pump and check whether it can create a circular tour, we use queue to store the values. We first will enqueue first petrol pump to the queue, we keep enqueuing petrol pumps until petrol amount becomes negative, then we dequeue petrol pumps until queue becomes empty. Code--> class petrolpump{     public:     int petrol;    ...

This is the opposite of inserting a Stack using 2 queues. Here we are going to implement a Queue using Stacks. The main thing to remember here is that A queue has operations on both ends - Front and rear, and follow FIFO structure.  Queue can be implemented using 2 stacks, Either we can make changes in the enqueue function or in the dequeue function, for this particular problem we are going to make changes to the Enqueue function so that-> while stack1 is not empty, push everything from stack1 to stack2 push x to stack1  push everything back to stack1 time complexity will be O(n) for dequeue() -> if stack1 is not empty, pop item from stack1 and return it  time complexity for dequeue is O(1)    Code--> class queue{     stack<int> s1, s2;          void enqueue(int x)     {          while(!s1.empty())               s2.push(s1.top());  ...

Here comes the fun part or i should say the extensive part. We can learn one data structure and then mess with it to create other data structures, here we are going to see how to implement a Stack using a singly linked list.  For this we must keep in mind that a stack follows Last in First out structure (LIFO), Now we are ready to tackle this problem with certain Stack operations like Push, pop, peek-to give top element and display in mind. Code--> Class Node{     int data;     Node* link; }; Node* top; //function to add element  void push(int data) {          Node* temp= new Node(data);          if(!temp)          {                    cout<<"Overflow";                    exit(1);          }          temp->link=top...