Chitkara

PAPER OF 17/12/2025 - CSE 2024 - DSOOPS / CSE(AI) - DSA PCT 25J EXAM

Q1. Quality Check

The "Digital Die Factory" produces custom dice for board games. Each die face is engraved with a single number. For a new, highly-
regulated game, the customer has a strict requirement: they must know the exact count of dice with Even numbers and the count of
dice with Odd numbers being packaged in every box.

The factory's automated scanner reads the face-up numbers of a batch of dice as they are loaded into a crate. This sequence of
numbers is passed to the Quality Control (QC) software.

You are tasked with writing the core QC analysis function, void count(int a[], int T), for the factory's software. This function must
process the batch of numbers, determine the parity (even or odd) of each number, and report the two counts.

Input Format
First line contains an integer t denoting the total number of dice.
Second line contains t integers representing the face-up numbers of the dice.

Output Format
Print the count of even and odd numbers space-separated.

Sample Input
4
1 3 5 8

Sample Output
1 3

Explanation
Elements 1, and 5 are odd and 8 is even.

ANSWER:

Test case 1 :
Input:
4
1358
Output:
13

Test case 2 :
Input:
7
11 22 43 52 6 67 34
Output:
43

Test case 3 :
Input:
10
11 22 43 52 6 67 34 56 78 90
Output:
73

Test case 4 :
Input:
10
11 22 43 52 6 67 3 56 8 9
Output:
55

Test case 5 :
Input:
5
1 80 0 10 2
Output:
41

Test case 6 :
Input:
5
 4 8 10 12 6
Output:
50

Q2. The Daily Loss Counter

Sarah, the owner of "The Local Bookstore," is trying to get a quick handle on her store's financial health. She keeps a detailed record of
her Daily Net Financial Performance for the month. This performance is an integer that represents the total profit or loss for that day:

A positive number means the store made a profit.

Sarah doesn't need the total profit or loss; she simply wants to know: "On how many days did the bookstore incur a loss?"

You are tasked with writing a small analysis utility for Sarah's accounting software. You need to implement a function, int count(int
a[], int T), that processes her daily performance data and returns the specific count of loss days.

A "loss day" is defined as any day where the net performance value is strictly less than 0.

Input Format
First line contains an integer t denoting the total number of days.
Second line contains t integers representing the daily net performance figures.

Output Format
Print the total number of days that resulted in a financial loss.

Sample Input
4
1 2 3 -5

Sample Output
1

ANSWER:

Test case 1 :
Input:
4
1 2 3 -5
Output:
1

Test case 2 :
Input:
8
-1 1 -1 1 -1 1 -1 1

Output:
4

Test case 3 :
Input:
10
-11 -22 43 52 6 67 34 56 78 -90
Output:
3

Test case 4 :
Input:
10
-11 -22 -43 -52 -6 -67 -3 -56 -8 -9
Output:
10

Test case 5 :
Input:
7
1 2 3 -2 -4 -9 70
Output:
3

Test case 6 :
Input:
7
-1 -2 -3 -4 -9 -1121 0
 Output:
6

Q3. Count the total reward points Clone

Let us suppose that each of the digits from 0 to 9 are associated with the reward points, as given below:
1, 2, 3, 5, and 7 = 0 points.
0, 4, 6, and 9 = 1 points.
8 = 2 points.

Your task is that given a number, find out the total reward points that you will get from all the digits in it.

For example, the number 928 can earn you 3 reward points.

Complete the function countPoints(), which takes an integer as argument and return an integer denoting the total number of reward
points.

Your solution must be optimized otherwise you may get an error "Time Limit Exceeded".

Input Format:
First line contains the number of test cases i.e. T, and next T lines containing the number as test case each.

Output Format:
Print the number of reward points that you can earn for each given number in the new line.

Constraints:
1 ≤ num ≤ 10^9

Sample Input
2 // Test Cases
515
928

Sample Output
0
3

Explanation:
For 515, add the reward points for each digit, 5, 1 and 5. Return 0 + 0 + 0 = 0.
For 928, add the reward points for each digit, 9, 2 and 8. Return 1 + 0 + 2 = 3.

ANSWER:

Test case 1 :
Input:
2
515
928
Output:
0
3

Test case 2 :
Input:
4
630
1288
1235
12345678
Output:
2
4
0
4

Test case 3 :
Input:
3
1000000
8888888
987654320
Output:
6
14
6

Test case 4 :
 Input:
10
23
45
5646
56531254
9064
9068
888
8488
468288
898860123
Output:
0
1
3
2
4
5
6
7
8
9

Test case 5 :
Input:
2
1
1000000000
Output:
0
9

Test case 6 :
Input:
3
873467
1987
256
Output:
4
3
1

Q4. Evaluate the postfix expression using Stack

Dr. Emily Carter, a professor of computer science, is running a challenging lab session. Her students are learning about data
structures, specifically Stacks, and how they are used to process mathematical expressions. She has given them a series of expressions
written in Reverse Polish Notation (RPN), also known as Postfix notation.

In Postfix notation, unlike standard algebra (Infix), the operator comes after the operands. For example, the standard expression 3 + 4
is written as 3 4 +. Evaluating these expressions is a classic application of a Stack.

Input Format
The first line of input contains an integer T denoting the number of test cases.
The next T line contains a postfix expression.
An expression in postfix form will consist of all digits and following five operators: +, -, *, /, ^

Output Format
Print the final output of postfix expression evaluation in new line for each test case.

Sample Input
2 // Testcases
8425+-*
546+*493/+*

Sample Output
-24
350

ANSWER:

Test case 1 :
Input:
2
8425+-*
546+*493/+*
Output:
 -24
350

Test case 2 :
Input:
1
6324+-*
Output:
-18

Test case 3 :
Input:
2
723*-4^93/+
834+-382/+*2^3+
Output:
4
52

Test case 4 :
Input:
2
7435+-*
346+*891/+*
Output:
-28
510

Test case 5 :
Input:
1
231*+9-
Output:
-4

Test case 6 :
Input:
2
62/3+
23^4+
Output:
6
12

Q5. Flip the odd elements of queue Clone

Write a function flipHalfQueue() that takes a queue of integers and reverses the order of the elements at odd-numbered positions
(positions 1, 3, 5, 7, …).

Position counting starts from 0. Elements at even positions (0, 2, 4, 6, …) must remain unchanged. Only one stack may be used as
auxiliary storage.

Example:

Original queue
Index: 0 1 2 3 4 5 6 7
Values: 5 7 6 2 9 18 11 15

Odd-indexed values:
(7, 2, 18, 15)

After reversing → (15, 18, 2, 7)

Final queue:
5 15 6 18 9 2 11 7

Input Format
Line 1: Integer n (number of elements)
Line 2: n space-separated integers (queue from front to back)

Output Format
Print the queue after reversing all values at odd positions.

Example

Input:
8
5 7 6 2 9 18 11 15
 Output:
5 15 6 18 9 2 11 7

ANSWER:

Test case 1 :
Input:
8
5 7 6 2 9 18 11 15
Output:
5 15 6 18 9 2 11 7

Test case 2 :
Input:
8
1 8 7 2 9 18 12 0
Output:
1 0 7 18 9 2 12 8

Test case 3 :
Input:
6
012345
Output:
052341

Test case 4 :
Input:
4
20 40 50 30
Output:
20 30 50 40

Test case 5 :
Input:
5
10 20 30 40 50

Output:
10 40 30 20 50

Test case 6 :
Input:
6
123456

Output:
163452

Q6. Buy the tickets at counter

You are going to a PVR to watch a movie with your friends. The ticket counter have one queue to buy tickets and they sell only 1 ticket
at a time (to avoid any brokers in between with bulk of tickets). Given your position in ticket queue and number of tickets you need
find out how much time you need to buy them all. (One transaction will be counted as 1 time unit). For example,

If ticket requirements are [1, 3, 6] and your position is 1 (means 3 tickets required), Then the queue and bought tickets will be as
below:
Time Tickets needed Tickets bought Queue front to rear
t=0 1 | 3 | 6 0 | 0 | 0 0, 1, 2
t=1 0 | 3 | 6 1 | 0 | 0 1, 2
t=2 0 | 2 | 6 1 | 1 | 0 2, 1
t=3 0 | 2 | 5 1 | 1 | 1 1, 2
t=4 0 | 1 | 5 1 | 2 | 1 2, 1
t=5 0 | 1 | 4 1 | 2 | 2 1, 2
t=6 0 | 0 | 4 1 | 3 | 2 2, 1
t=7 0 | 0 | 3 1 | 3 | 3 2
Means you have all required tickets in t=6 time units.

Write the function howMuchToWait() which accepts the required tickets array and your position in the array, and return the total
time required to you for buying the tickets.

Input Format
The first line contains an integer n, the size of the array tickets.
The next n lines each contain an element tickets[i] where 0 ≤ i < n.
The next line contains an integer p denoting your position in line.

Output Format
 Print the time units required to buy tickets

Sample Input
3
1
3
6
1

Sample Output
6

ANSWER:

Test case 1 :
Input:
3
1
3
6
1
Output:
6

Test case 2 :
Input:
5
2
6
3
4
5
2
Output:
12

Test case 3 :
Input:
4
1
1
1
1
0
Output:
1

Test case 4 :
Input:
4
5
5
2
3
3
Output:
11

Test case 5 :
Input:
607
87
896
88
978
3
529
708
301
414
38
382
719
281
548
83
665
517
360
514
166
94
851
92
981
402
320
643
12
929
946
924
540
180
857
639
9
575
51
547
705
664
500
428
826
416
272
63
893
343
782
466
167
161
700
422
509
925
471
767
685
402
562
496
1
577
299
456
484
784
803
449
180
179
660
941
728
779
515
746
978
504
189
661
580
352
259
656
140
280
551
581
449
967
367
89
77
623
143
748
370
29
360
926
151
358
933
817
563
850
586
771
278
67
237
218
172
908
247
887
411
219
122
838
961
553
497
914
985
430
188
987
28
119
171
105
258
258
120
535
800
590
736
619
841
358
872
762
560
372
329
174
505
943
461
889
797
375
914
369
60
109
372
588
18
102
964
635
372
983
229
808
98
567
819
289
580
609
996
364
823
185
200
443
455
284
203
847
988
626
999
311
383
957
148
968
307
449
698
11
638
996
755
412
567
349
459
670
151
838
377
50
2
259
229
607
5
962
922
896
911
458
643
131
458
262
407
206
648
849
598
282
760
698
571
834
48
743
946
410
922
203
657
777
569
153
272
113
442
552
875
372
166
206
196
406
300
47
467
551
193
582
616
320
889
664
36
514
196
717
422
380
316
248
674
548
811
228
569
610
591
14
293
746
584
823
483
256
582
65
825
235
477
359
159
68
618
487
720
766
796
9
263
909
62
150
932
905
241
179
982
18
124
478
841
386
246
5
999
200
647
964
360
489
196
869
116
887
946
623
684
756
912
521
198
253
391
749
880
144
267
975
618
624
704
318
982
486
79
911
281
751
456
591
993
858
336
631
406
792
682
879
107
300
991
573
115
75
152
548
486
315
912
552
539
965
228
118
829
972
956
38
801
996
113
202
515
886
39
558
814
496
186
912
339
271
946
446
878
880
672
956
421
591
313
933
322
576
656
399
950
540
181
682
286
264
18
975
408
44
185
178
436
327
345
489
908
13
849
228
702
827
121
349
110
855
157
423
439
482
163
513
393
255
369
266
937
875
610
988
605
237
224
754
919
997
640
427
887
526
307
391
467
565
561
990
353
945
949
382
209
283
277
108
165
765
977
95
937
997
545
305
461
104
505
255
752
385
95
126
84
241
112
934
951
190
536
520
965
182
505
305
176
218
48
135
930
237
877
288
887
925
841
535
454
206
631
73
846
515
85
169
483
343
106
474
784
381
183
235
755
69
280
361
294
584
626
610
930
104
196
454
283
363
215
94
385
295
120
47
770
205
43
413
19
679
567
458
582
843
134
382
195
911
267
982
601
125
883
15
282
238
935
409
517
48
342
30
477
826
37
722
724
340
32
314
765
530
439
111
962
623
468
18
60
412
41
471
593
96
397
372
693
422
293
40
43
332
334
Output:
132409

Test case 6 :
Input:
489
827
137
53
505
283
937
336
341
421
251
847
91
157
696
599
48
993
272
391
609
483
647
130
159
405
72
412
155
604
805
320
979
477
180
152
418
723
450
596
764
310
468
768
174
796
177
939
354
35
945
890
992
428
480
521
422
330
851
489
809
136
209
314
233
262
442
3
984
477
411
932
307
653
520
850
407
429
472
995
132
763
445
477
509
279
128
523
190
284
536
751
332
687
908
776
424
581
844
158
724
577
459
56
835
979
535
924
189
545
55
551
736
545
892
544
624
996
768
385
847
69
609
981
165
496
126
835
592
859
704
57
173
543
522
617
805
383
281
671
712
399
693
528
661
318
501
963
951
892
662
372
89
588
773
436
498
786
15
473
522
614
608
276
610
287
160
5
504
785
863
105
552
871
850
492
971
616
275
559
779
157
780
386
508
737
540
874
533
135
256
108
324
23
978
919
717
746
926
318
531
208
175
763
189
529
70
781
322
464
683
2
901
705
513
21
65
740
438
209
261
182
280
651
152
343
168
875
733
758
786
491
352
479
147
510
871
93
321
850
698
999
6
294
51
126
269
252
854
845
731
239
409
496
310
78
269
357
33
111
746
653
726
164
390
867
153
72
807
731
275
203
300
116
141
681
855
582
104
783
181
244
243
78
563
515
516
821
27
184
61
474
149
918
176
337
478
781
947
483
923
539
661
904
382
751
902
125
984
696
66
902
869
234
622
981
707
664
721
416
818
674
700
702
236
457
146
98
478
686
616
38
261
942
877
377
82
296
611
313
406
212
620
393
125
941
653
972
287
792
133
71
506
995
878
482
105
446
19
991
95
260
360
289
844
178
661
78
126
591
491
189
553
538
508
208
551
263
486
67
632
433
489
578
347
97
588
942
50
381
435
425
970
625
547
180
600
169
460
264
452
716
838
513
409
754
28
732
531
207
51
26
727
325
475
90
565
29
796
267
137
574
850
174
405
964
618
544
25
130
570
21
739
527
388
206
86
349
386
179
735
21
507
441
330
827
269
917
697
415
640
695
645
690
457
48
642
869
555
211
919
533
999
951
555
985
581
522
921
945
120
79
916
961
222
553
35
691
77
741
726
760
535
884
262
959
 22
349
944
708
44
Output:
229702

Q7. Reverse Alternate K nodes of Linked List Clone

Given the head of a singly linked list and an integer K, reverse every alternate K nodes of the list in-place.

Complete the function revAltKNodes() which takes the head node of a linked list & an integer K as parameters and return the head of
modified list after reversing all alternative K nodes of the list.

Input Format
First line contains an integer T, the number of test cases.
For each test case:
First line: an integer N, the number of nodes in the linked list.
Second line: N space-separated integers, the values of the nodes.
Third line: an integer K.

Output Format
For each test case, print the node values of the modified linked list in a single line, separated by spaces.

Sample Input
2 // Test Cases
6 // no. of nodes (TC 1)
1 2 3 4 5 6 // node's data (TC 1)
2 // K (TC 1)
8
1 2 3 4 5 6 7 8
3


Sample Output
2 1 3 4 6 5
3 2 1 4 5 6 8 7

Explanation:
Test Case 1:
K = 2
Reverse first 2 nodes →2 1
Skip next 2 nodes → 3 4
Reverse next 2 nodes →6 5
Result → 2 1 3 4 6 5

Test Case 2:
K = 3
Reverse first 3 nodes →3 2 1
Skip next 3 nodes → 4 5 6
Reverse next 2 nodes →8 7
Result → 3 2 1 4 5 6 8 7

ANSWER:

Test case 1 :
Input:
2
6
123456
2
8
12345678
3
Output:
213465
32145687

Test case 2 :
Input:
1
2
12
3
Output:
21

Test case 3 :
Input:
2
8
12345678
1
8
12345678
3
Output:
12345678
32145687

Test case 4 :
Input:
3
10
1 2 3 4 5 6 7 8 9 10
2
0
2
1
2
2
Output:
2 1 3 4 6 5 7 8 10 9

Test case 5 :
Input:
1
500
225 247 986 800 830 872 25 940 700 5 464 195 535 772 680 457 703 117 613 860 36 809 136 111 591 2 901 449 417 543 567 603 616 17
76 878 598 474 149 580 174 939 325 439 551 668 911 126 825 227 902 649 338 388 266 330 658 513 512 902 523 666 213 357 734 590
458 742 68 991 376 71 969 632 296 673 496 678 754 662 754 269 880 753 442 130 912 471 30 573 240 445 335 282 624 221 578 429 73
39 343 86 795 488 122 22 648 786 506 317 782 127 508 959 437 514 26 850 398 64 815 161 230 658 529 464 418 165 375 509 6 453 523
235 238 19 272 634 842 590 194 332 810 779 468 793 279 574 47 22 135 932 684 185 217 813 333 461 449 844 96 82 422 865 110 399
628 128 634 624 560 545 529 590 103 749 516 764 631 113 276 640 969 830 452 334 379 668 40 342 556 209 722 318 392 208 875 787
839 151 642 292 138 415 192 897 166 235 629 24 523 193 300 806 468 681 29 466 456 122 793 582 66 952 982 49 351 113 718 438 235
820 208 172 438 798 622 537 674 618 791 54 802 751 107 827 871 334 790 131 182 363 445 833 308 650 305 689 676 96 473 446 902 196
311 260 629 771 635 270 731 288 819 342 875 970 750 286 530 164 784 370 393 50 916 414 107 516 267 545 134 759 51 908 388 153 951
257 741 236 115 454 957 201 489 807 458 612 633 187 512 247 959 597 599 680 409 996 498 87 853 63 648 582 641 677 395 26 230 59
15 84 404 691 511 956 942 895 100 748 349 447 627 558 345 480 169 747 477 952 920 126 524 886 122 149 339 645 661 852 472 584 629
430 987 786 803 787 593 750 278 600 352 122 908 948 509 62 281 675 84 859 299 772 144 446 17 315 933 446 335 835 945 98 897 981
473 793 373 128 735 940 946 92 782 307 447 477 270 269 120 24 627 550 736 887 860 101 875 932 689 1000 35 447 179 725 907 33 107
159 933 93 214 182 254 170 775 603 473 729 914 199 453 957 552 667 863 302 985 748 674 603 1000 356 421 594 194 223 785 122 844
639 274 357 841 711 58 51 674 342 975 28 170 950 341 815 811 216 699 939 589 24 82 769 362 459 670 604 972 806 330 996 983 686
921 497 171 439 100 603
33
Output:
616 603 567 543 417 449 901 2 591 111 136 809 36 860 613 117 703 457 680 772 535 195 464 5 700 940 25 872 830 800 986 247 225 17
76 878 598 474 149 580 174 939 325 439 551 668 911 126 825 227 902 649 338 388 266 330 658 513 512 902 523 666 213 357 734 590 73
429 578 221 624 282 335 445 240 573 30 471 912 130 442 753 880 269 754 662 754 678 496 673 296 632 969 71 376 991 68 742 458 39
343 86 795 488 122 22 648 786 506 317 782 127 508 959 437 514 26 850 398 64 815 161 230 658 529 464 418 165 375 509 6 453 110 865
422 82 96 844 449 461 333 813 217 185 684 932 135 22 47 574 279 793 468 779 810 332 194 590 842 634 272 19 238 235 523 399 628
128 634 624 560 545 529 590 103 749 516 764 631 113 276 640 969 830 452 334 379 668 40 342 556 209 722 318 392 208 875 787 235
438 718 113 351 49 982 952 66 582 793 122 456 466 29 681 468 806 300 193 523 24 629 235 166 897 192 415 138 292 642 151 839 820
208 172 438 798 622 537 674 618 791 54 802 751 107 827 871 334 790 131 182 363 445 833 308 650 305 689 676 96 473 446 902 196 951
153 388 908 51 759 134 545 267 516 107 414 916 50 393 370 784 164 530 286 750 970 875 342 819 288 731 270 635 771 629 260 311 257
741 236 115 454 957 201 489 807 458 612 633 187 512 247 959 597 599 680 409 996 498 87 853 63 648 582 641 677 395 26 230 59 629
584 472 852 661 645 339 149 122 886 524 126 920 952 477 747 169 480 345 558 627 447 349 748 100 895 942 956 511 691 404 84 15 430
987 786 803 787 593 750 278 600 352 122 908 948 509 62 281 675 84 859 299 772 144 446 17 315 933 446 335 835 945 98 897 981 107
33 907 725 179 447 35 1000 689 932 875 101 860 887 736 550 627 24 120 269 270 477 447 307 782 92 946 940 735 128 373 793 473 159
933 93 214 182 254 170 775 603 473 729 914 199 453 957 552 667 863 302 985 748 674 603 1000 356 421 594 194 223 785 122 844 639
921 686 983 996 330 806 972 604 670 459 362 769 82 24 589 939 699 216 811 815 341 950 170 28 975 342 674 51 58 711 841 357 274
497 171 439 100 603

Test case 6 :
Input:
1
500
250 442 775 156 687 115 216 41 30 988 777 953 129 91 537 655 763 190 108 626 944 490 987 327 425 698 387 706 692 823 773 54 185
926 83 230 917 381 732 744 44 19 573 320 172 462 951 872 209 218 749 217 172 477 859 852 698 464 374 354 814 857 713 932 165 269
431 883 402 38 725 768 248 743 662 64 275 483 192 632 653 270 758 272 480 720 213 247 50 138 262 411 654 460 929 197 35 427 225
692 587 16 499 708 726 131 746 629 109 477 299 327 994 792 732 735 911 223 780 23 92 297 442 291 731 687 829 687 753 718 973 930
78 152 363 495 225 386 310 326 791 467 342 492 965 692 749 109 504 78 646 407 885 642 937 721 75 96 317 208 748 664 364 172 923
250 302 659 899 522 364 848 897 832 755 255 876 598 839 110 977 369 156 672 468 117 348 358 673 138 429 646 331 641 783 620 556
479 92 267 282 679 288 700 355 901 82 465 974 746 214 466 761 657 237 833 128 241 907 596 151 738 309 663 538 943 946 88 309 518
48 639 484 457 637 769 880 182 117 484 456 792 144 824 287 523 650 1 296 464 828 149 419 107 689 946 8 192 36 517 380 3 419 10 224
844 451 150 773 59 794 673 465 838 313 734 565 839 369 589 74 358 947 251 344 97 875 123 95 257 938 212 559 758 655 676 171 637
761 766 133 419 361 937 952 214 176 837 83 520 747 215 234 621 597 920 377 512 520 389 956 797 349 44 650 853 303 759 578 473 293
686 941 235 477 180 416 292 600 526 574 141 415 765 854 680 361 550 667 125 182 804 850 807 531 457 159 772 724 704 776 604 479
 523 824 557 574 633 690 554 373 748 762 164 404 651 925 892 477 787 58 435 46 344 99 194 751 760 521 450 695 641 698 434 72 627
57 109 449 72 99 595 20 154 841 407 438 771 968 918 113 599 519 452 522 356 675 794 54 926 450 24 2 373 124 149 444 301 249 980
316 67 705 959 764 153 495 445 405 651 406 889 41 213 457 717 294 62 121 711 355 390 595 795 981 649 577 362 527 173 779 748 830
827 763 364 349 661 549 899 971 287 459 985 276 331 879 830 98 788 185 414 582 54 988 885 868 379 267 240 241 84 354 500 226 994
761 942 530 746
25
Output:
425 327 987 490 944 626 108 190 763 655 537 91 129 953 777 988 30 41 216 115 687 156 775 442 250 698 387 706 692 823 773 54 185
926 83 230 917 381 732 744 44 19 573 320 172 462 951 872 209 218 662 743 248 768 725 38 402 883 431 269 165 932 713 857 814 354
374 464 698 852 859 477 172 217 749 64 275 483 192 632 653 270 758 272 480 720 213 247 50 138 262 411 654 460 929 197 35 427 225
692 731 291 442 297 92 23 780 223 911 735 732 792 994 327 299 477 109 629 746 131 726 708 499 16 587 687 829 687 753 718 973 930
78 152 363 495 225 386 310 326 791 467 342 492 965 692 749 109 504 78 755 832 897 848 364 522 899 659 302 250 923 172 364 664 748
208 317 96 75 721 937 642 885 407 646 255 876 598 839 110 977 369 156 672 468 117 348 358 673 138 429 646 331 641 783 620 556 479
92 267 538 663 309 738 151 596 907 241 128 833 237 657 761 466 214 746 974 465 82 901 355 700 288 679 282 943 946 88 309 518 48
639 484 457 637 769 880 182 117 484 456 792 144 824 287 523 650 1 296 464 313 838 465 673 794 59 773 150 451 844 224 10 419 3 380
517 36 192 8 946 689 107 419 149 828 734 565 839 369 589 74 358 947 251 344 97 875 123 95 257 938 212 559 758 655 676 171 637 761
766 650 44 349 797 956 389 520 512 377 920 597 621 234 215 747 520 83 837 176 214 952 937 361 419 133 853 303 759 578 473 293 686
941 235 477 180 416 292 600 526 574 141 415 765 854 680 361 550 667 125 404 164 762 748 373 554 690 633 574 557 824 523 479 604
776 704 724 772 159 457 531 807 850 804 182 651 925 892 477 787 58 435 46 344 99 194 751 760 521 450 695 641 698 434 72 627 57
109 449 72 124 373 2 24 450 926 54 794 675 356 522 452 519 599 113 918 968 771 438 407 841 154 20 595 99 149 444 301 249 980 316
67 705 959 764 153 495 445 405 651 406 889 41 213 457 717 294 62 121 711 276 985 459 287 971 899 549 661 349 364 763 827 830 748
779 173 527 362 577 649 981 795 595 390 355 331 879 830 98 788 185 414 582 54 988 885 868 379 267 240 241 84 354 500 226 994 761
942 530 746

Q8. Move the Smallest and largest to head and tail of list Clone

Given a pointer to the head node of a linked list, find the smallest and largest of this list. Now move the smallest node to the front and
move the largest node to the end of the list.

Input Format:
First line contains one integer denoting the number of test cases.
For each test case, first line contains the total number of nodes in list i.e. N and next N lines contains the elements of nodes.
The function shiftSmallLarge() takes the head node of a linked list as a parameter and returns the head pointer after doing both shifts

Note: Do not read any input from stdin/console. Each test case calls the shiftSmallLarge method individually and passes it the head of
a list.

Output Format:
Print the integer data for each element of the linked list separated by space.

Sample Input
1
7
12
8
6
20
1
50
16

Sample Output
1 12 8 6 20 16 50

ANSWER:

Test case 1 :
Input:
1
7
12
8
6
20
1
50
16
Output:
1 12 8 6 20 16 50

Test case 2 :
Input:
5
7
12
8
6
20
1
 50
16
0
1
2
2
1
50
2
50
1
Output:
1 12 8 6 20 16 50

2
1 50
1 50

Test case 3 :
Input:
2
6
2
4
6
8
10
12
6
6
4
2
12
10
8
Output:
2 4 6 8 10 12
2 6 4 10 8 12

Test case 4 :
Input:
1
8
13
3
4
5
8
14
6
9
Output:
3 13 4 5 8 6 9 14

Test case 5 :
Input:
1
7
40
5
22
90
13
2
77
Output:
2 40 5 22 13 77 90

Test case 6 :
Input:
1
5
3
7
5
6
1
Output:
13567

Q9. Split the Circular Linked List in two parts Clone

Now, given a pointer to the head node of a circular linked list with even number of nodes, cut it from middle and return the two lists
as two separate circular linked lists.

Complete the function listCut() which takes the head node of a circular linked list, so you need to cut the list in two parts and return
the pointer to second half of list. The first part will remain in the pointer head.

Input Format:
First line will contain an integer denoting number of test cases.
Each test case will have 2 lines, In first line total number of nodes is written and in 2nd line the node values are given.

Output Format:
Print the nodes of two circular lists separated by space on two lines.

Sample Input
1
4
1 2 3 4

Sample Output
1 2
3 4

ANSWER:

Test case 1 :
Input:
1
4
1234
Output:
12
34

Test case 2 :
Input:
2
8
12121212
4
1111
Output:
1212
1212
11
11

Test case 3 :
Input:
2
6
123456
4
3456
Output:
123
456
34
56

Test case 4 :
Input:
3
4
4321
0
6
654321
Output:
43
21

654
321

Test case 5 :
Input:
1
10
6 7 8 9 10 11 12 13 14 15
Output:
6 7 8 9 10
11 12 13 14 15

Test case 6 :
Input:
2
2
44
6
133133
Output:
4
4
133
133