SDE - 1

1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N after the Nth node 
2) Now copy the arbitrary link in this fashion 


original->next->arbitrary = original->arbitrary->next; /*TRAVERSE 
TWO NODES*/
This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary. 
3) Now restore the original and copy linked lists in this fashion in a single loop. 


original->next = original->next->next;
copy->next = copy->next->next;
4) Make sure that last element of original->next is NULL.

The idea to solve the problem is to use BFS. To find the shortest path through BFS, start from the start word and push it in a queue. And once the target is found for the first time, then return that level of BFS traversal. In each step of BFS one can get all the words that can be formed using that many steps. So whenever the target word is found for the first time that will be the length of the shortest chain of words.

Start from the given start word.
Push the word in the queue
Run a loop until the queue is empty
Traverse all words that adjacent (differ by one character) to it and push the word in a queue (for BFS)
Keep doing so until we find the target word or we have traversed all words.

We can solve this problem by computing modulo of array numbers with K. if sum of two numbers is divisible by K, then if one of them gives remainder i, other will give remainder (K – i). First we store frequencies of numbers giving specific remainder in a frequency array of size K. Then we loop for all remainders i and include max(f[i], f[K – i]). Why? a subset with no pair sum divisible by K must include either elements with remainder f[i] or with remainder f[K – i]. Since we want to maximize the size of subset, we pick maximum of two sizes.
In below code array numbers with remainder 0 and remainder K/2 are handled separately. If we include more than 2 numbers with remainder 0 then their sum will be divisible by K, so we have taken at max 1 number in our consideration, same is the case with array numbers giving remainder K/2.

The idea is to use Binary Search. We fix a value for the number of pages as mid of current minimum and maximum. We initialize minimum and maximum as 0 and sum-of-all-pages respectively. If a current mid can be a solution, then we search on the lower half, else we search in higher half.
Now the question arises, how to check if a mid value is feasible or not? Basically, we need to check if we can assign pages to all students in a way that the maximum number doesn’t exceed current value. To do this, we sequentially assign pages to every student while the current number of assigned pages doesn’t exceed the value. In this process, if the number of students becomes more than m, then the solution is not feasible. Else feasible.
Below is an implementation of above idea.

The simplest approach to solve the above problem is to iterate up to N and keep excluding all numbers less than N containing the digit 9. Finally, print the Nth natural number obtained.

Follow below steps below to solve the problems : 

Initialize one variable count = 0
and use for loop and pass the element of loop to isDigitNine(i) function to check whether that number contains 9 or not and increment that if not present 
And once count hit N assign the last i to to count and break the loop.
Return answer as count

We generate n! possible job assignments and for each such assignment, we compute its total cost and return the less expensive assignment. Since the solution is a permutation of the n jobs, its complexity is O(n!).

The idea is to use a dynamic programming paradigm, and see who wins the game. ‘X’ start’s the game and has 3 options, to choose ‘A’ or ‘B’ or 1 coin. Similarly, ‘Y’ makes a move and so on. The player who is not able to move further loses the coin game. We solve in a bottom-up manner from 0 to 'NO_OF_COINS' coins and calculate our ans.

Let’s say if we have some i coins, and Player ‘X’ is playing the game, ‘X’ will always try to reach a point from where ‘Y’ cannot win. So, we are checking all three options, we can reach a point from where the other player cannot win we return true otherwise we return false.



The algorithm is as follows :

Declare a boolean array ‘DP’, where DP[i] stores the player starting with ‘i’ coins wins the game or not, if the player starting with ‘i’ coins wins it stores true, otherwise false.
Set, DP[0] to false.
Set, DP[1] to true.
Iterate from ‘i’ = 2 to ‘N’,
Set, DP[i] to ans to true if DP[i - 1] is false.
If ‘i’ >= ‘A’, set DP[i] to true if DP[i - A] is false.
If ‘i’ >= ‘B’, set DP[i] to true if DP[i - B] is false.
Return, DP[N].