1.
String_Game
Like Every year, again this year a coding challenge was conducted by the geek's man group.
Based on these challenges, geeks mean group offers scholarships, goodies, prize money, and
other stuff to students who participated in the contest. This year, Alex a nd his friend Bob
participated in the contest. Alex solved all the questions while Bob didn't as he spent so much
time on one question in which he was having a binary string SS of even length NN and twisted
the little by adding that string only contains N/2N/2 zero and N/2N/2 ones. To make the question
more complex it's added that he can reverse any substring of SS in one operation. So he has
to find the minimum number of operations to make the string SS alternating. So he wants your
help in figuring out the solution as he feels dishonored if he takes help from Alex. Note: A
substring of a string is a contiguous subsequence of that string SS and its alternating if
Si≠Si+1Si≠Si+1 for all ii.
Input Format
The first contains an integer TT where TT denotes the number of test cases. The first line of
each test case contains a single integer NN where NN denotes the length of the string SS. The
second line of each test case contains binary string SS of length NN and has exactly N/2N/2
zeroes and N/2N/2 ones.
Output Format
Print the minimum operations required to make string SS alternating.
Time Limit
1 second
Constraints
1≤T≤5∗1041≤T≤5∗104 2≤N≤1052≤N≤105 Note: It's guaranteed that the total sum of NN over
test cases doesn't exceed 105105.
Example
Sample Input
3 4 0110 8 11101000 4 1001
Sample Output
121
Sample Test case Explanation
In the second test case, we can make it in two operations. 1.1. 11101000 −>−> 10101100. 2.2.
10101100 −>−> 10101010.
2.Zip Linked List
You are given the head of the Singly linked list of arbitrary length KK. Your task is to zip the
linked list in-place (i.e., doesn't create a brand new linked list) and return it's head.
A linked list is zipped if it's nodes are in the following order, whe re KK is the length of the linked
list:
• 1st node -> Kth node -> 2nd node -> (k-1)th node -> 3rd node -> (k-2)th node -> ....
Note - You can assume that the input linked list will always have atleast one node, in other
words, the head will never be NULL.
Input Format
The first line of input contains a single integer TT - denoting the number of test cases. Each
test case follows:
• The first line of each test case contains a single integer KK, denoting the size of the
linked list
• The second line contains KK space-separated integers - denoting the elements of the
list.
Output Format
The output contains TT lines, each line containing the modified list. Note - You only need to
implement zipLinkedList(), and return the head of the linked list.
Constraints
1≤T≤1001≤T≤100 1≤K≤100001≤K≤10000
Time Limit
1 second
Example
Sample Input
271263456278
Sample Output
162564378
3.Clever Friend
Aman and Raman are friends as well as neighbors. They used to share everything, play
together, and like to spend most of the time together. Raman being clever also sometimes take
advantage of Aman like give him the homework to complete by making excuses an d his projects
are also made by Aman. As exams are going on and both of them are preparing for exams then
suddenly Aman realizes that his science book is missing so he asked Raman to give him the
book for few hours but being clever Raman puts condition and provided him with the array AA
with NN integers and twisted the little by adding that he has to find the count of the cool
subarrays i.e.the subarray which has the sum of all elements in it a perfect square and told
Aman to solve this first if he needs th e book. So tomorrow they are having the exam, so Aman
wants your help in solving it so that he can get the book and can prepare for his exam.
Input Format
The first line of the input contains an integer NN where NN denotes the length of the array. The
second line conatins NN space integers A1,A2,A3,....ANA1,A2,A3,....AN.
Output Format
Print the count of the subarray for which the sum of the elements is a perfect square.
Time Limit
1 second
Constraints
1≤T≤5∗1031≤T≤5∗103 2≤Ai≤1062≤Ai≤106
Example
Sample Input
41432
Sample Output
Sample Test case Explanation
The given array is : 11 44 33 22
let us list the sum of all possible subarrays: [1,1]=1[1,1]=1 [1,2]=1+4=5[1,2]=1+4=5
[1,3]=1+4+2=7[1,3]=1+4+2=7 [1,4]=1+4+2+3=10[1,4]=1+4+2+3=10 [2,2]=4[2,2]=4
[2,3]=4+2=6[2,3]=4+2=6 [2,4]=4+2+3=9[2,4]=4+2+3=9 [3,3]=2[3,3]=2 [3,4]=2+3=5[3,4]=2+3=5
[4,4]=3[4,4]=3
[1,4,9]=3
4.Add One to the Number
You are given a linked list representing a number such that each individual node acts as a digit
of the number. The list HEADHEAD-> 11-> 22-> 33 -> NULLNULL corresponds to the number
123. Your task is to add 1 to this number.
Input Format
The first line contains an integer TT, number of test cases. Then follows TT test cases. Each
test case consists of two lines. The first line contains an integer NN representing length of the
linked list The second line contains NN space separated integers representing nodes of a linked
list.
Output Format
The output contains TT lines, each line containing the modified number as a linked list. Note -
You only need to implement addOneToList() function, and return the head of the linked list.
Example
Sample Input
2312349999
Sample Output
1241000 0
4.h
There are N employees sitting in consecutive cubicles, we have to send a few of them
onsite, but each time we send one employee onsite, his cubicle becomes empty. Now,
the other employees from both sides of that empty cubicle stop working until they are
given a gift. The gifts are given on both sides of the empty cubicle until we reach the end
or found another cubicle.
Input Format:
• Number of cubicles
• Index numbers of people to be sent
Output Format:
Minimum number of gifts needed
2) Glowing Bulbs problem
3) Gold mine problem
You also need to be thorough with the following data structures related problems.
Find the Minimum and Maximum values of given expression with + and
*
Program to find the minimum and maximum values of given expression is discussed here.
Given an algebraic expression with + and *, find the minimum and maximum values.
For example,
Sample Input:
1+2*3+4*5
Sample Output:
27
105
Explanation:
1 + (2 * 3) + (4 * 5) = 27 (Minimum)
(1 + 2) * (3 + 4) * 5 = 105 (Maximum)
• Implement Depth First Search (DFS)
• Implement Breadth First Search (BFS)
• Number of Islands
• Subset sum problem
• Rat in a maze problem
• Treasure and cities problem
• 0-1 Knapsack problem
• Sudoku problem
• Minimum and maximum values of a given expression
• Minimum sum partition problem
• Number of ways to reach the nth stair
