TCS NQT IMPORTANT CODING QUESTIONS

Program 1: Anagram of the first string

Write a program to find the whether the given string is the anagram of the first
string.

Sample Input:

eat

ate

Output:

Anagram

 Case 1

Input (stdin)
eat
ate

Output (stdout)
Anagram

Case 2
Input (stdin)
program
prograd

Output (stdout)
Not anagrams

Program 2: Create and Implement a Tree structure

Write a program to create and implement a Tree structure. Use DFS to display the
elements (in-order, pre-order, post-order).

Output:

Output consists of three lines, First line prints "in-order", Second line prints"pre-
order" and third line print the output of "post-order" .

Sample Input:
5

58946

Ouptut:

45689

54869

46985

 Case 1

Input (stdin)
5
5 8 9 4 6

Output (stdout)
4 5 6 8 9
5 4 8 6 9
4 6 9 8 5

Case 2
Input (stdin)
6
6 5 4 8 3 9

Output (stdout)
3 4 5 6 8 9
6 5 4 3 8 9
3 4 5 9 8 6

Program 3: Naughty Students

You are the class leader. The teacher asked you to write down the names of students
on the board who are talking. Also, she asked to write the student's name as many
times they talk in the class(the same student shall be present on the board more
than once). Finally, the teacher decided to give imposition based on the number of
times a student's name got repeated. For example, If Suresh's name is repeated 4
times he needs to write and submit the assignment for 4 times). The list of students
is given as your input. Your output should be arranged in lexicographical order.

Input :

 First line contains an integer 'N', i.e the no. of students in the class.
 Next 'N' lines contains the names of the students.
Output:

 Each line consists of the name of student space and separated its frequency.

Constraints:

 1<=N<=1000
 string length<=100
 string consists of lowercase letters

Sample Input:

sumit

ambuj

himanshu

ambuj

ambuj

Sample Output:

ambuj 3

himanshu 1

sumit 1

 Case 1

Input (stdin)
5
sumit
ambuj
himanshu
ambuj
ambuj

Output (stdout)
ambuj 3
himanshu 1
sumit 1

 Case 2

Input (stdin)
6
raj
raj
dinesh
dinesh
tamil
tamil

Output (stdout)
dinesh 2
raj 2
tamil 2

Program 4: Sweet seventeen

Problem statement:

Given a maximum of four digit to the base 17(10 -> A, 11 -> B, 12 -> C, 16 -> G) as
input, output its decimal value.

Input - 1

1A

Expected Output

27

Input - 2

23GF

Expected Output

10980

 Case 1

Input (stdin)
1A

Output (stdout)
27

 Case 2

Input (stdin)
23GF

Output (stdout)
10980

Program 5: Word is key

One programming language has the following keywords that cannot be used as
identifiers:

break, case, continue, default, defer, else, for, func, goto, if, map, range,
return, struct, type, var

Write a program to find if the given word is a keyword or not

Example-1

Input

defer

Expected Output

defer is a keyword

Example-2

Input

While

Expected Output

while is not a keyword

 Case 1

Input (stdin)
defer

Output (stdout)
defer is a keyword

 Case 2

Input (stdin)
while

Output (stdout)
while is not a keyword

Program 6: Minting Mints

Problem statement:

It was one of the places, where people need to get their provisions only through fair
price (“ration”) shops. As the elder had domestic and official work to attend to, their
wards were asked to buy the items from these shops. Needless to say, there was a
long queue of boys and girls. To minimize the tedium of standing in the serpentine
queue, the kids were given mints. I went to the last boy in the queue and asked him
how many mints he has. He said that the number of mints he has is one less than
the sum of all the mints of kids standing before him in the queue. So I went to the
penultimate kid to know how many mints she has.

She said that if I add all the mints of kids before her and subtract one from it, the
result equals the mints she has. It seemed to be the uniform response from
everyone. So, I went to the boy in the head of queue consoling myself that he would
not give the same response as others. He said, “I have four mints”.

Given the number of first kid’s mints (n) and the length (len) of queue as input, write
a program to display the total number of mints with all the kids.

constraints:

2<n<10

1<len<20

Example-1

Input

42

Expected output:

Example-2

Input

14 4

Expected output

105

 Case 1
Input (stdin)
4 2

Output (stdout)
7

 Case 2

Input (stdin)
14 4

Output (stdout)
105

Program 7: To zero or not to zero

Problem statement:

Given a pair of positive integers m and n (m < n; 0 < m < 999; 1 < n < = 999),
write a program to smarty affix zeroes, while printing the numbers from m to n.

Example-1

Input

5 10

Expected output

05 06 07 08 09 10

Example-2

Input

9 100

Expected output

009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027
028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046
047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065
067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085
086 087 088 089 090 091 092 093 094 095 096 097 098 099 100

Example-3
Input

19

Expected output

123456789

 Case 1

Input (stdin)
1 9

Output (stdout)
1 2 3 4 5 6 7 8 9

 Case 2

Input (stdin)
3 7

Output (stdout)
3 4 5 6 7

Program 8: A Sober walk

Problem statement:

Our hoary culture had several great persons since time immemorial and king
vikramaditya’s nava ratnas (nine gems) belongs to this [Link] are named in the
following shloka:

Among these, Varahamihira was an astrologer of eminence and his book Brihat
Jataak is recokened as the ultimate authority in astrology.

He was once talking with Amarasimha,another gem among the nava ratnas and the
author of Sanskrit thesaurus, Amarakosha.

Amarasimha wanted to know the final position of a person, who starts from the origin
0 0 and travels per following scheme.

 He first turns and travels 10 units of distance

 His second turn is upward for 20 units
 Third turn is to the left for 30 units
 Fourth turn is the downward for 40 units
 Fifth turn is to the right(again) for 50 units
… And thus he travels, every time increasing the travel distance by 10 units.

constraints:

2<=n<=1000

Input-1

Expected output:

-20 20

Input -2

Expected output:

-20 -20

 Case 1

Input (stdin)
3

Output (stdout)
-20 20

 Case 2

Input (stdin)
4

Output (stdout)
-20 -20

Program 9: Oddly even

Given a maximum of 100 digit numbers as input, find the difference between the
sum of odd and even position digits.

Input 1:
4567

Expected output:

Explanation

Sum of odd position digits 4 and 6 is 10. Sum of even position digits 5 and 7 is 12.
The difference is 12-10=2.

Input #2:

9834698765123

Expected output:

Input 3:

5476

Expected output:

 Case 1

Input (stdin)
4567

Output (stdout)
2

 Case 2

Input (stdin)
9834698765123

Output (stdout)
1

Program 10: segregate all the 0’s in left side and 1’s in
right side
Write a program to segregate all the 0’s in left side and 1’s in right side in the same
array with O(n) complexity.
Sample Input:

01010

Output:

00011

 Case 1

Input (stdin)
5
0 1 0 1 0

Output (stdout)
00011

 Case 2

Input (stdin)
7
0 0 0 1 1 0 0

Output (stdout)
0000011

Program 11: Insert and delete using Singly Linked List

Write a program to create a Singly Linked List using dynamic memory allocation. If
linked list is empty, print "Linked list is empty".

Hint:

1. Insert an element at beginning of linked list.

2. Insert an element at end of linked list.

3. Traverse linked list.

4. Delete element from beginning.

5. Delete element from end.

6. Exit

Sample Input:

Enter value of element

10

Enter value of element

20

Sample Output:

10 20

10 deleted from beginning successfully.

20 deleted from end successfully.

 Case 1

Input (stdin)
1
10
2
20
3
4
5
6

Output (stdout)
Enter value of element
Enter value of element
10 20
10 deleted from beginning successfully.
20 deleted from end successfully.

 Case 2

Input (stdin)
1
10
3
6

Output (stdout)
Enter value of element
10
Program 12: Find the Nth element
Write a program to create a Singly Linked List and find the Nth element from the end
of the list.

Hint : Insertion at the beginning.

Output:

output consists of single line, print the element in the given position in a list, else
print"No node found"

Sample Input:

10 8 6 4 0

Output:

 Case 1

Input (stdin)
5
10 8 6 4 0
2

Output (stdout)
8

 Case 2

Input (stdin)
10
100 200 300 400 500 600 700 800 900 101
11

Output (stdout)
No node found

Program 13: Extract Number from the String

Bastin once had trouble finding the numbers in a string. The numbers are distributed
in a string across various test cases.
There are various numbers in each test case you need to find the number in each
test case. Each test case has various numbers in sequence. You need to find only
those numbers which do not contain 9. For eg, if the string contains "hello this is
alpha 5051 and 9475".You will extract 5051 and not 9475. You need only those
numbers which are consecutive and you need to help him find the numbers. Print the
largest number.

Note: Use long long for storing the numbers from the string.

Input:

The first line consists of T test cases and next T lines contain a string.

Output:

For each string output the number stored in that string if various numbers are there
print the largest one. If a string has no numbers print -1.

Constraints:

1<=T<=100

1<=|S|<=10000

Example:

Input:

This is alpha 5057 and 97

Output:

5057

 Case 1

Input (stdin)
1
This is alpha 5057 and 97

Output (stdout)
5057

 Case 2

Input (stdin)
1
dream job 100 and 101

Output (stdout)
101
Program 14: Largest power of prime
Given a positive integer N and a prime p, the task is to print the largest power of
prime p that divides N!. Here N! means the factorial of N = 1 x 2 x 3 . . (N-1) x N.

Note that the largest power may be 0 too.

Input:

The first line of input contains a single integer T denoting the number of test cases.
Then T test cases follow. Each test case consists of a single line containing a positive
integer N and a prime p.

Output:

Corresponding to each test case, in a new line, print the largest power of
prime p that divides N.

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 100000

2 ≤ p ≤ 5000

Example:

Input:

62 7

76 2

35

Output:

73

 Case 1

Input (stdin)
3
62 7
76 2
3 5

Output (stdout)
9
73
0
 Case 2

Input (stdin)
1
1000 100

Output (stdout)
10

Program 15: Family Game

In this lockdown a family of N members decided to play a game the rules of which
are :-

 All N members are made to sit uniformly in a circle (ie. from 1 to N in

clockwise direction).
 The game start with the person sitting at first position.
 A song is played in the background. The lyrics of the song are denoted by a
string which consists of only letters 'x' and 'y'. Assume that each lyric of the
song is a single letter.
 If the lyric 'x' occurs in the song, the member who is currently holding the
Parcel passes it on to the next member. This passing takes place in clockwise
direction.
 If the lyric 'y' occurs in the song, the member who is currently holding the
Parcel loses his/her chances of winning the game. He/she hands over the
parcel to the next member (in clockwise direction) and moves out.
 The game continues until a single member survives in the end. He/she will be
the winner of the game.
 Note that the song repeats continuously ie. while the game is going on, if at
all the song ends, the stereo system will automatically start playing the song
from the start without any delay.

You have to find out the member who wins the game.

Input : The input consists of 2 lines. The first line consists of N, the member of family
in the class. The next line consists of a string denoting the lyrics of the song the
teacher plays.

Output :

Print a single integer denoting the roll number of the student who wins the game.

Constraints :

2≤N≤100000

1≤|S|≤10000, where |S| denotes the length of the input string. It is guaranteed that
at least 1 lyric in the song will be a 'y'
Note: Copy and paste is disabled for all the questions. Try not to use other ides.

Sample input:

xyx

Output:

ExplanationStarting from 1 lyrics : 'x' therefore he passes the ballto 2nd

2nd turn lyrics : 'y' therefore 2nd member gets out of game and passes to 3rd

3rd turn lyrics : 'x' therefore 3rd passes ball to first.

4th turn lyrics : 'x' passes to 3rd

5th turn lyrics: 'y' therefore gets eliminated.

Hence person sitting at position 1 won this game.

 Case 1

Input (stdin)
3
xyx

Output (stdout)
1

 Case 2

Input (stdin)
500
xyxyyxxxxyyyyxxyyxyxyyxyxxyxxxxyxxxxyxyxyxxxyxyyyyyyyxxxxxxxyyyyyyxyxyxxxyyyyxxxxyx
yxxxxxxxxxyyyxyyxxyxxyxxyyxxyxyxyxyyxyyxxyyyxyyxyyxxxyxyxxxxxyyyyyyyyxxxyxxyxxxxyyx
xxyxxyyyxxyxyyyyxyxyxxxxxxxxyxxyxyxyxxxxyyxyyyyxxxxyyyyxxxyxxyxxyxxyyyxyyyyyxyxyyyx
xxxyxxyxxxyyyyxyyxyyxyyxyyxxxxxxxxyxyxxyxxxxxxxxyyxyyyyyxyxxxyyxxxyyyyyxyyyyyxxxxyy
xyxxyyyyyyyyyxxyyxxyyxyxxxxxyxyxyyyyxxyxxyyxyxxyxxxyxyyxyyxxyyyyyxxyxyyxxyxyyyxyxyy
xxxxyyxxxyyyyyyxyyxxyyxyyxxxxyyxyxyxyyxyyxxyyxyyyyyyxyxyxxyxyxxxyyyxxxyyxyyxyxxyyyx
xx

Output (stdout)
83

Program 16: Unique Number

Write a program to find the count of numbers which consists of unique digits.
Input:

Input consist of two Integer lower and upper value of an range

Output:

Output consists of single line, print the count of unique digits in given range. Else
Print"No Unique Number"

Sample Input:

10

15

Ouput:

 Case 1

Input (stdin)
10
15

Output (stdout)
5

 Case 2

Input (stdin)
10
20

Output (stdout)
10

Program 17: Prime Pairs

There is a range given n and m in which we have to find the count all the prime pairs
whose difference is 6. We have to find how many sets are there within a given range.

Output:

Output consists of single line, print the count prime pairs in given range. Else
print"No Prime Pairs".

constraints:

2<=n<=1000
n<=m<=2000

Sample Input:

30

Output:

Explanation:

(5, 11) (7, 13) (11, 17) (13, 19) (17, 23) (23, 29) . we have 6 prime pairs.

 Case 1

Input (stdin)
4
30

Output (stdout)
6

 ase 2

Input (stdin)
10
100

Output (stdout)
13

Program 18: Robot Move

A Robot wants to move through a cave grid of size M x N. (M- Rows N- Columns). It
starts from (0,0) and destination is (M-1,N-1). It can only move right or down.
Calculate the total number of ways robot can reach the destination.

sample Input:

55

Output:

70

 Case 1

Input (stdin)
5
5

Output (stdout)
70

 Case 2

Input (stdin)
10
10

Output (stdout)
48620

Program 19: Divide Apples

N boys are sitting in a circle. Each of them have some apples in their hand. You find
that the total number of the apples can be divided by N. So you want to divide the
apples equally among all the boys. But they are so lazy that each one of them only
wants to give one apple to one of the neighbors at one step. Calculate the minimal
number of steps to make each boy have the same number of apples.

Input

The first line of input is an integer N. 2 <= N <= 10000 The second line is N integers
indicates the number of apples of the ith boy. Each integer is positive and no more
than 10^9.

Output

A single line contains the minimal number of steps to make each boy have the same
number of apples.

Sample Input:

1397

Output:

ExplanationHere are the 8 steps starting from (1,3,9,7):

1. (2,3,9,6)
2. (3,3,9,5)
3. (3,4,8,5)
4. (3,5,7,5)
5. (3,6,6,5)
6. (3,7,5,5)
 7. (4,6,5,5)
8. (5,5,5,5)

 Case 1

Input (stdin)
4
1 3 9 7

Output (stdout)
8

 Case 2

Input (stdin)
5
3 2 5 4 6

Output (stdout)
4

Program 20: Birthday Party

Madhav went to Riya's Birthday Party. He was a geek so he had no idea regarding
which gift she'l [Link] he took an array of integers with him. The array followed a
particular order. First element of array is [Link] element of array is 6.

Other elements of the array are two less than the mean of the number preceding
and succeeding [Link] it is obvious, Riya felt that this idea was stupid and hence she
wanted to punish [Link] decided to ask Madhav the nth number of the array. If
he tells the wrong answer, she would slap [Link] Madhav to escape from this
embarrassing situation.

Input:

The input starts with T, the number of Test Cases.

Next T lines contain integer N.

Output:

For each test case, output an integer which is the Nth number of the array. As the
answer can be very large, output it modulo 109+7

Constraints:

1 ≤ T ≤ 105

1 ≤ N ≤ 1018

Sample Input:
2

Output:

15

Explanation:

First test case is trivial as a [1] = 1. In second test case, a[2]=(a[1]+a[3])/2-2.

Substituting the values of a [1] and a[2] , we get: 6=(1+a[2])/2-2. So, a[2]=8*2-
1=15

 Case 1

Input (stdin)
2
1
3

Output (stdout)
1
15
 Case 2

Input (stdin)
3
101
35
251

Output (stdout)
20301
2415
125751

Program 21: Nearest Prime

Joy is a hacker at hackerclub and he got a new problem on prime [Link]
problem states that given an integer N find the nearest prime number to [Link]
multiple answer is possible then output the smallest one of [Link] are T number
of test cases.

1<=N<10^6

1<=T<=2*10^6

INPUT:
First line of input contains an Integer T denoting the number of test cases.

Next each of the T lines contain one integer N.

OUTPUT:

Output the nearest prime number possible to N in a new line

Sample Input:

51

12

65

Output:

53

11

67

 Case 1

Input (stdin)
3
51
12
65

Output (stdout)
53
11
67

 Case 2

Input (stdin)
2
452
526

Output (stdout)
449
523
Program 22: Palindromic Array
You are given an array A of size N. Your task is to find the minimum number of
operations needed to convert the given array to 'Palindromic Array'.

Palindromic Array:

[23,15,23] is a ‘Palindromic Array’ but [2,0,1] is not.

The only allowed operation is that you can merge two adjacent elements in the array
and replace them with their sum.

Input:

The first line of input contains an integer T denoting the number of test [Link]
first line of each test case is N, where N is the size of [Link] second line of each
test case contains N space separated integers which is the input for the array.

Output:

Output the minimum number of operations required to make the given array a
palindromic array.

Constraints:

1 <= T <= 100

1 <= N <= 100

1 <= A[] <= 100

Example:

Input:

32335

5334
Output:

Explanation:

For Test Case 1: [3 2 3 3 5] after merging the 1st two elements 3 and 2, we get the
array as [5 3 3 5] which is a palindrome, hence only 1 operation is needed.

 Case 1

Input (stdin)
2
5
3 2 3 3 5
4
5 3 3 4

Output (stdout)
1
3

 Case 2

Input (stdin)
1
6
6 3 6 3 2 1

Output (stdout)
3

Program 23: Hack the money

You are a bank account [Link] you have 1 rupee in your account, and you
want exactly N rupees in your [Link] wrote two hacks, First hack can multiply
the amount of money you own by 10, while the second can multiply it by 20. These
hacks can be used any number of time . Can you achieve the desired
amount N using these hacks.

Constraints:

1<=T<=100

1<=N<=10^12

Input:
  The first line of the input contains a single integer T denoting the number of
test cases.
 The description of T test cases [Link] first and only line of each test case
contains a single integer N.

Output :

For each test case, print a single line containing the string "Yes" if you can make
exactly N rupees or "No" otherwise.

Sample Input:

10

25

200

Output:

Yes

No

Yes

No

Yes

Explanation:

In the last case hacker can get Rs. 200 by first using 10x hack and then using 20x
hack once.

1 -> 10 -> 200

 Case 1

Input (stdin)
5
1
2
10
25
200

Output (stdout)
Yes
No
Yes
No
Yes

 Case 2

Input (stdin)
3
101
52
124

Output (stdout)
No
No
No

Program 24: Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1
is included. Write a program to find Nth Ugly Number.

Input:

The first line of input contains an integer T denoting the number of test
cases. T testcases follow. For each testcase there is one line of input that contains
the number N.

Output:

Print the Nth Ugly Number.

Constraints:

1 ≤ T ≤ 104

1 ≤ N ≤ 104

Example:
Input:

10

Output:

12

 Case 1

Input (stdin)
2
10
4

Output (stdout)
12
4

 Case 2

Input (stdin)
3
520
432
125

Output (stdout)
1166400
455625
3125

Program 25: Rotate the String

Write a program to Rotate the string in the specified direction and print the output.

Input Format:

First line contains the String A.

Second line contains the number of positions you have to shift the elements in the
string.

Third line contains the direction either 'L' or 'R'.

Output Format:
Print the rotated string

Constrain:

1<=len(A)<1000

Sample Input:

faceprep

Sample Output:

eprepfac

 Case 1

Input (stdin)
faceprep
3
R

Output (stdout)
repfacep

 Case 2

Input (stdin)
faceprep
3
R

Output (stdout)
Repfacep

Program 26: Fight against Corona

Dinesh is fond of video games. Due to the pandemic, he designs a video game called
the Corona world. In this game, the player enters the game with a certain energy.
The player should defeat all the corona infected zombies to reach the next level.
When time increases the zombies will increase double the previous minute. Anyhow
the player can manage to fight against all the zombies. In this case, definitely the
player can not achieve the promotion. Hence the player gets a superpower to
destroy all the zombies in the current level when the current game time is a
palindrome. Anyhow the player can manage only if he knows the time taken to get
the superpower. Help the player by providing the minimum minutes needed to get
the superpower by which he can destroy all the zombies. You will be provided with
the starting time of the game.
Input Format:

First-line contains a string representing the starting time.

Output:

A string representing the minimum minutes needed to get the superpower.

Constraints:

Input time will be in 24 hours format

Sample Input:

05:39

Sample Output:

11

Explanation:

It takes 11 minutes for minute value to become 50, 05:50 is a palindromic time.

 Case 1
 Case 2

Input (stdin)
05:39

Output (stdout)
11

 Case 2

Input (stdin)
13:31

Output (stdout)
0

Program 27: Weighted substring

Every character has a weight. The weight of an English uppercase alphabet A-Z is
given below. A=1 B=2*A+A C=3*B+B D=4*C+C . . . Y=25*X+X Z=26*Y+Y The
weight of any string made up of these characters is the summation of weights of
each character. Given a total string weight, determine shortest string of that given
weight. If there is more than one solution, return the lexicographically smallest of
them. For example, given weight = 25, and the weights of the first few characters of
the alphabet are A=1, B=3, C=12, D=60 it is certain that no letter larger than C is
required. Some of the strings with a total weight equal to the largest are ABBBBC,
ACC, and AAAAAAABBBBBB. The shortest of these is ACC. While any permutation of
these characters will have the same weight, this is the lexicographically smallest of
them. Function Description Complete the function smallestString in the editor below.
The function must return the shortest string of the target weight. If there are
multiple answers, return the lexicographically smallest of them. smallestString has
the following parameter(s): weight: a long integer that denotes the target weight.

Input Format

Input consists of a string s.

Output Format

Output should be in the form of integer.

Constraints

1<=weight<=1016

Refer the sample output for formatting

Sample Input:

20

Sample Output:

AABBC

 Case 1

Input (stdin)
20

Output (stdout)
AABBC

Program 28: Balanced parenthesis

Write a program to check whether the given parenthesis is balanced or not.

Input Format

The input consists of the parenthesis.

Output Format

The consists of the result whether it is Balanced or Not Balanced.

Sample Input:
{()}[]

Sample Output:

Balanced

Hint: {}, [] and () are used

 Case 1
 Case 2

Input (stdin)
{()}[]

Output (stdout)
Balanced
 Case 2

Input (stdin)
{{}(})

Output (stdout)
Not Balanced

Program 29: Lowest Common Ancestor

Write a C++ program to find the common ancestor of given two numbers in a tree.
Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is
defined as the lowest node in T that has both n1 and n2 as descendants(where we
allow a node to be descendant of itself). The LCA of n1 and n2 in T is the shared
ancestor of n1 and n2 that is located farthest from the root. Computation of Lowest
common ancestor is useful, for instance, as part of a procedure for determining the
distance between pairs of node in a tree: the distance from n1 to n2 can be
computed as the distance from the root to n1, plus the distance from from the root
to n2, minus twice the distance from the root to their lowest common ancestor.

Sample Input:

-1

36

Sample Output:
6

 Case 1

Input (stdin)
5 3 7 2 4 6 8 -1
2 4

Output (stdout)
3

 Case 2

Input (stdin)
6 3 1 4 2 -1
3 6

Output (stdout)
6

Program 30: Pairwise swap elements in linked list

Given a linked list, write a program to swap elements pairwise. If the list is empty,
print "List is empty".

Input Format

The input consists of a list of integers, negative value indicates the end of the linked
list.

Output Format

The output should be numbers in the list in separate line.

Refer the sample input & output for formatting specifications.

Sample Input

10

20

20

10

-30

Sample Output
20

10

10

20

 Case 1

Input (stdin)
10
20
20
10
-30

Output (stdout)
20
10
10
20

Program 31: Permutations - All of Them

"I'm not a fan of having kids memorize formulas, and I'm even less of a fan of
pushing them to learn those formulas," says Mr. John, 7th grade Math teacher.
Maybe he has got a point. He believes in teaching the logic rather than the formula.
Anyway, we aren't here to weigh/debate about his opinions. All we gotta do is help
Mr. John and his students by writing an algorithm that can calculate & print all the
permutations of a given number in strictly sorted order. Remember, Mr. John is
gonna use your algorithm to demonstrate permutations in his next class.

Input Format

The input consists of a string

Output Format

Print all the permutations of the given string

Refer the sample output for formatting

Sample Input:

abc

Sample Output:

abc

acb
bac

bca

cab

cba

 Case 1

Input (stdin)
abc

Output (stdout)
abc
acb
bac
bca
cab
cba

Program 32: Getting Dizzy

Given an integer matrix, R x C, traverse it as shown below: 1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16

Input Format

One line containing two integers R and C representing the dimensions of the matrix
M as rows R, and columns C, respectively.

R lines, each containing C space separated number of integers which collectively

form the matrix data.

Output Format

Single line containing integers without space representing the desired traversal.

Constraints

0<R,C<500

Refer the sample output for formatting

Sample Input:

123

456

789
Sample Output:

123698745

 Case 1

Input (stdin)
3
1 2 3
4 5 6
7 8 9

Output (stdout)
1 2 3 6 9 8 7 4 5

 Case 2

Input (stdin)
10
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0

Output (stdout)
1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7
8 9 9 9 9 9 9 9 9 8 7 6 5 4 3 2 2 2 2 2 2 2 3 4 5 6 7 8 8 8 8 8 8 7 6 5 4 3 3 3 3 3
4 5 6 7 7 7 7 6 5 4 4 4 5 6 6 5

Program 33: Redundant Braces

Given a string of balanced expression, find if it contains redundant parentheses or
not. A set of parentheses is redundant if the same sub-expression is surrounded by
unnecessary or multiple brackets. Print ‘Yes’ if redundant else ‘No’.

Input Format

The input consists of the expression.

Output Format

The output consists of the result.

Sample Input:

((a+b))

Sample Output:

Yes

 Case 1

Input (stdin)
((a+b))

Output (stdout)
Yes

 Case 2

Input (stdin)
(a+b*(c-d))

Output (stdout)
No

Program 34: Difficult Characters

Yesterday while Omar was trying to learn English, he saw that there are letters
repeated many times in words while some other letters repeated only few times or
not repeated at all!

Of course anyone can memorise the letters (repeated many times) better than the
letters repeated few times, so Omar will concatenate all the words in the context he
has, and try to know the difficulty of each letter according to the number of
repetitions of each letter.

So Omar has now the whole context and wants to arrange the letters from the most
difficult letter (repeated few times) to the less difficult letter (repeated many times).

If there are 2 letters with the same level of difficulty, the letter with higher value of
ASCII code will be more difficult.

Input Format:

Given an integer (T),1<=T<=10 (number of test cases).

For each test case:

Given a string of (lower English characters), .1<= size of string<=10 6

(each string in a new line).

Output Format:

Output the English lower case characters from the most difficult letter to the less
difficult letter. (leave a space between 2 successive letters) (Output each test case in
a separate line).

Sample Input:

oomar

Sample Output:

zyxwvutsqpnlkjihgfedcbrmao

 Case 1

Input (stdin)
1
oomar

Output (stdout)
z y x w v u t s q p n l k j i h g f e d c b r m a o
 Case 2

Input (stdin)
1
thirdworldwar

Output (stdout)
z y x v u s q p n m k j g f e c b t o l i h a w d r

Program 35: Great Forests

Imagine the field is a 2D plane. Each cell is either water 'W' or a tree 'T'.

A forest is a collection of connected trees. Two trees are

connected if they share a side i.e. if they are adjacent to each other.

Your task is, given the information about the field, print the size of the largest forest.

Size of a forest is the number of trees in it. See the sample case for clarity

INPUT:
First line contains the size of the matrix N.

The next N lines contain N characters each, either 'W' or 'T'.

OUTPUT:

Print the size of the biggest forest.

CONSTRAINTS:

1<=N<=1000

Sample Input:

TTTWW

TWWTT

TWWTT

TWTTT

WWTTT

Sample Output:

10

Explanation:

The forest on the top left has 6 trees but the forest on the bottom right is bigger with
10 trees.

 Case 1
 Case 2

Input (stdin)
5
TTTWW
TWWTT
TWWTT
TWTTT
WWTTT

Output (stdout)
10
  Case 2

Input (stdin)
6
TTTWWT
TWWTTT
TWWTTT
TWTTTW
WWTTTW
TWWTWW

Output (stdout)
14

Program 36: Longest Increasing Subsequence

Problem Description:

Given an integer array 'A', find the length of its Longest Increasing Subsequence of a
sub-array of the given integer array where the elements are sorted in a monotonic
increasing order.

You need to fill in a function that takes two inputs - integer 'n' and an integer array
containing 'n' integers and returns the length of its LIS.

Input Specification:

Input 1: integer input 'n'(1 <=input1 <= 1000)

Input2: integer array 'A' input, containing 'n' integers.

Output Specification;

Return the length of its LIS.

Example 1:

Input 1: 3

Input 2: {1, 3, 2}

Output: 2

 Case 1

Input (stdin)
3
1 3 2

Output (stdout)
2
  Case 2

Input (stdin)
9
10 22 9 33 21 50 41 60 80

Output (stdout)
6

Program 37: Odd occurring element

Given an array of integers where every element appears even number of times
except one element which appears odd number of times, write a program to find
that odd occurring element in O(log n) time.

The equal elements must appear in pairs in the array but there cannot be more than
two consecutive occurrences of an element.

For example :

232

It doesn't have equal elements appear in pairs

1122233

It contains three consecutive instances of an element.

22311

It is valid and the odd occurring element present in it is 3.

Enter only valid inputs.

Sample Input:

22311

Sample Output:
3

 Case 1

Input (stdin)
5
2 2 3 1 1

Output (stdout)
3

 Case 2

Input (stdin)
11
2 2 3 3 2 2 4 4 3 1 1

Output (stdout)
3

Program 38: Reaching the nth step of a staircase

A naughty kid is climbing a staircase of 'n' steps. He can take either 1 step or 2 steps
at a time. Write a program to find the number of distinct ways to reach the nth step.
Assume he is standing on the 0th step.

Sample Input:

Sample Output:

Constraints:

1 <= n <= 40

Examples:

Input: n = 1

Output: 1

There is only one way to climb 1 stair

Input: n = 2

Output: 2

There are two ways: (1, 1) and (2)

Input: n = 4

Output: 5

(1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)

 Case 1

Input (stdin)
5

Output (stdout)
8

Input (stdin)
39

Output (stdout)
102334155

Program 39: Perfect Sum

Given an array of integers and a sum, the task is to count all subsets of given array
with sum equal to given sum.

Input:

The first line of input contains an integer T denoting the number of test cases. Then
T test cases follow. Each test case contains an integer n denoting the size of the
array. The next line contains n space separated integers forming the array. The last
line contains the sum.

Output:

Count all the subsets of given array with sum equal to given sum.

NOTE: Since result can be very large, print the value modulo 109+7.
Constraints:

1<=T<=100

1<=n<=103

1<=a[i]<=103

1<=sum<=103

Example:

Input:

2 3 5 6 8 10

10

12345

10

Output:

Explanation:

Testcase 1: possible subsets : (2,3,5) , (2,8) and (10)

Testcase 2: possible subsets : (1,2,3,4) , (2,3,5) and (1,4,5)

 Case 1
Input (stdin)
2
6
2 3 5 6 8 10
10
5
1 2 3 4 5
10

Output (stdout)
3
3

 Case 2

Input (stdin)
1
7
56 57 8 9 6 3 4
60

Output (stdout)
2

Program 40: Say no to Handshakes!!!

Before the outbreak of corona virus to the world, a meeting happened in a room in
Wuhan. A person who attended that meeting had COVID-19 and no one in the
room knew about it! So everyone started shaking hands with everyone else in the
room as a gesture of respect and after meeting unfortunately every one got
infected! Given the fact that any two persons shake hand exactly once, Can you tell
the total count of handshakes happened in that meeting?

Input Format:

The first line contains the number of test cases T, T lines follow.

Each line then contains an integer N, the total number of people attended that
meeting.

Output Format:

Print the number of handshakes for each test-case in a new line.

Constraints:

1 <= T <= 1000

0 < N < 106

Sample Input:

Output:

Explanation:

Case 1 : The lonely board member shakes no hands, hence 0.

Case 2 : There are 2 board members, 1 handshake takes place.

 Case 1

Input (stdin)
2
1
2

Output (stdout)
0
1

 Case 2

Input (stdin)
3
100
101
102

Output (stdout)
4950
5050
5151

Program 41: Exchange Books

For enhancing the book reading, school distributed story books to students as part of
the Children’s day celebrations. To increase the reading habit, the class teacher
decided to exchange the books every weeks so that everyone will have a different
book to read. She wants to know how many possible exchanges are possible.

If they have 4 books and students, the possible exchanges are 9. Bi is the book of i-
th student and after the exchange, he should get a different book, other than Bi.

B1 B2 B3 B4 – first state, before exchange of the books

B2 B1 B4 B3

B2 B3 B4 B1

B2 B4 B1 B3

B3 B1 B4 B2

B3 B4 B1 B2

B3 B4 B2 B1

B4 B1 B2 B3

B4 B3 B1 B2

B4 B3 B2 B1

Find the number of possible exchanges, if the books are exchanged so that every
student will receive a different book.

Constraints

1<= N <= 1000000

Input Format

Input contains one line with N, indicates the number of books and number of
students.

Output Format

Output the answer modulo 100000007.

Refer the sample output for formatting

Sample Input:

Sample Output:

9
  Case 1

Input (stdin)
4

Output (stdout)
9

 Case 2

Input (stdin)
10

Output (stdout)
1334961

Program 42: Pendulum

Bob is doing a research in Pendulum. He is just pushing the pendulum aside and the
pendulum started moving in to-and-fro motion. Bob will push the pendulum always
towards his right side to start the oscillation. Bob wanted to calculate the distance
between extreme position and the centre position of pendulum for each oscillations.
He somehow calculated all the possible distance. Since he is busy in this research he
is giving the task to his assistant who needs to arrange the values as instructed.

Since he is pushing the pendulum to his right always. He wanted to store that
distance in the right extreme of the arrangement. And the pendulum will move
towards the extreme left at that time he want that value to be stored in the left most
extreme in the arrangement. And this continues till the pendulum stops. He is also
sure that the distance reached at that oscillation will always be lesser than the
previous oscillation towards that particular [Link] a program to arrange the
distance as instructed.

Sample Input:

13254

Sample Output:

42135

Explanation:

The maximum distance in the given data is 5 hence that is placed in the right most
end
The next maximum element is 4 which is placed in the left most end.

Again the pendulum oscillates towards right to cover a distance of 3 and this
continues.

 Case 1

Input (stdin)
5
1 3 2 5 4

Output (stdout)
4 2 1 3 5

 Case 2

Input (stdin)
10
100 231 1 487 232 91 80 50 30 10

Output (stdout)
232 100 80 30 1 10 50 91 231 487

Program 43: Fake Palindrome

You are given a string A and you have to find the number of different sub-strings of
the string A which are fake palindromes.

Note:

1. Palindrome: A string is called a palindrome if you reverse the string yet the
order of letters remains the same. For example, MADAM.
2. Fake Palindrome: A string is called as a fake palindrome if any of its
permutations is a palindrome. For example, AAC is fake palindrome, but ACD
is not.
3. Sub-string: A sub-string is a contiguous sequence (non-empty) of characters
within a string.
4. Two sub-strings are considered same if their starting indices and ending
indices are equal.

Input Format:

 First line contains a string S

Output Format:

Print a single integer (number of fake palindrome sub-strings).

Constraints:

 1 <= |S| <= 2 * 105

 The string will contain only Upper case 'A' to 'Z'
Sample Input 1:

ABAB

Sample Output 1:

Explanation:

The fake palindrome for the string ABAB are A, B, A, B, ABA, BAB, ABAB.

Sample Input 2:

AAA

Sample output 2:

Explanation:

The fake palindrome for the string AAA are A, A, A, AA, AA, AAA

 Case 1
 Case 2

Input (stdin)
ABAB

Output (stdout)
7

 Case 2

Input (stdin)
AAA

Output (stdout)
6

Program 44: String Prime Sum

John and Thor wanted to test their students learning. Hence they come up with a
problem. The problem consists of a string containing an integer. You should convert
the string to its equivalent integer and then find the sum of prime number. There can
be negative number also hence you need to multiply the negative value by 11. In
case of invalid string print the output as 0.

You have been provided with a strict instruction that you should not use atoi()
function in this problem. Usage of this function will refrain you from any upcoming
scholarships.
Input Format:

String contains the integer value.

Output Format:

Should be an Integer.

Sample Input:

12

Sample output:

28

Explanation:

2+3+5+7+11 = 28

 Case 1

Input (stdin)
12

Output (stdout)
28

 Case 2

Input (stdin)
123456K

Output (stdout)
0

Program 45: Selection of Cities

James has decided to take a break from his work. He makes a plan to visit India for a
few days with his family. He knows a lot about India, and also about the various
cities he could visit. He decides to write down all the cities on a paper. Let the
number of cities be n. Now, he shows the list to his wife and asks her, the city/cities
she wants to visit. He tells her that she can select any city/cities and any number of
cities. The wife says, she needs a day to decide.

After this, James calls his son and tells him all about the trip, and the list of cities. He
gives him a task and asks him, the number of ways the city/cities can be chosen
from the list, if the total number of cities written on the list is n. The cities are
numbered from 1 to n. At least 1 city has to be selected.
He now asks your help to find the answer for the question that was asked to him.

The problem consists of a number of test cases.

INPUT:

The first line of input contains the number of test cases t.

Then t lines follow, each contains a number n, the number of cities.

OUTPUT:

Output contains t lines, each line contains the answer for that test case. As the
answer can be large, print the answer modulo 10^9+7

CONSTRAINTS:

1<=t<=100000

1<=n<=1012

SAMPLE INPUT:

Output:

Explanation:

For test case 1: The only ways to select the cities is [1], [2], [1, 2]. Therefore the
answer is 3.

For test case 2: The only way to select a city is [1] Therefore the answer is 1.
  Case 1

Input (stdin)
2
2
1

Output (stdout)
3
1

 Case 2

Input (stdin)
5
5
4
6
3
2

Output (stdout)
31
15
63
7
3

Program 46: Help your roommate

After performing a lot of experiments at the SEGP and EEDC Lab, you need a break.
You see your roommate stuck at a math problem. He asks for your help and says he
will give you party at the NC if you solve this problem for him.

The problem is:

Initially you are given the number 0. After each day the number doubles itself. At
any day, you can add the number 1 any number of times during the day.

You are given a number N and you need to tell the minimum number of times you
have to add 1 to get N at any point of time.

Input Format:

The first line contains a single integer T denoting the number of test cases.

Next T lines contain the integer N.

Output Format:

For every test case print the required output.

Constraints:

1≤T≤100

1 ≤N ≤109

Sample Input:

Output:

Explanation:

For 8, you need to add 1 only once at the starting. It will double to 2, then to 4, then
to 8.

For 5, you need to add 1 at the beginning, it will double to 2, then to 4, then you will
have to add 1 again to make it 5. So, answer is 2.

 Case 1
Input (stdin)
4
4
8
7
5

Output (stdout)
1
1
3
2
 Case 2

Input (stdin)
2
9
10

Output (stdout)
2
2

Program 47: Longest Palindromic Sub sequence

Problem Description:

Given a string x (1<= len(x)<=1000), find the length of its longest palindromic
subsequence.

The string contains only lowercase letters.

Write a program that takes in input as String x and returns the length of the longest
palindromic subsequence of x.

Input Specification:

input1: string input

Output Specification:

Return the length of the longest palindromic subsequence.

Example1:

input1: ababa

Output: 5

Explanation:

Length of Longest palindromic sequence is 5 that is “ababa”.

 Case 1
Input (stdin)
ababa

Output (stdout)
5

 Case 2

Input (stdin)
Drivingracecar

Output (stdout)
7

Program 48: Perfect Sum

Given an array of integers and a sum, the task is to count all subsets of given array
with sum equal to given sum.

Input:

The first line of input contains an integer T denoting the number of test cases. Then
T test cases follow. Each test case contains an integer n denoting the size of the
array. The next line contains n space separated integers forming the array. The last
line contains the sum.

Output:

Count all the subsets of given array with sum equal to given sum.

NOTE: Since result can be very large, print the value modulo 109+7.

Constraints:

1<=T<=100

1<=n<=103

1<=a[i]<=103

1<=sum<=103

Example:

Input:
2

2 3 5 6 8 10

10

12345

10

Output:

Explanation:

Testcase 1: possible subsets : (2,3,5) , (2,8) and (10)

Testcase 2: possible subsets : (1,2,3,4) , (2,3,5) and (1,4,5)

 Case 1
 Case 2

Input (stdin)
2
6
2 3 5 6 8 10
10
5
1 2 3 4 5
10

Output (stdout)
3
3

 Case 2

Input (stdin)
1
7
56 57 8 9 6 3 4
60

Output (stdout)
2

Program 49: Grab some sweets

You are going to a sweet shop to have sweets as you are low on energy. The sweets
are selling out. There is only a kilogram of N types of sweets remaining, each having
a specific cost and energy. You have a total of C amount of money with you. Your
task is to calculate the maximum total energy that you can gain by purchasing the
sweets optimally and savoring them. In particular, note that you can buy only a
portion weighing K of the provided sweet less than or equal to kilogram that contains
a provided energy parameter e. Eating this sweet can increase your total energy by
e x k. The maximum total energy can be denoted as a fraction x/y in lowest terms,
that is, GCD (x,y) =1. Print the answer as (x*(y-1))%109+7.

Input Format

The first line contains an integer N denoting the number of elements in costs.

Each line i of N subsequent lines (where 0<=i<N) contains n integer describing

costs[i].

Each line i of N subsequent lines (where 0<=i<N) contains n integer describing

energies[i].

The next line contains an integer C denoting the available money.

Output Format

Output will be in the form of energy.

Constraints

1<=N<105

1<costs[i]<=109

1<=energies[i]<=109

1<=C<=109

Refer the sample output for formatting

Sample Input:

3
1

Sample Output:

17

Explanation:

N=3. Costs= [5,3,1]. Energies= [7,8,9]. Available money = C = 4. We can eat last
two sweets fully (1kg each) to gain 17 energy.

 Case 1

Input (stdin)
3
5
3
1
7
8
9
4

Output (stdout)
17

Program 50: Bitonic Generator Sort

Given an array of N distinct numbers, the task is to sort all even-placed numbers in
increasing and odd-placed numbers in decreasing order. The modified array should
contain, all sorted even-placed numbers followed by reverse sorted odd-placed
numbers.

Note: The first element is considered as even because of its index 0.

Format:

Input:

The first line of input contains an integer T denoting the number of test cases.
Then T test cases follow. Each test case contains an integer N denoting the size of
the array. The next line contains N space-separated integers forming the array.
Output:

Print the modified array which contains all sorted even placed numbers followed by
reverse sorted odd placed numbers.

Constraints:

1 <= T <= 10^5

1 <= n <= 10^5

1 <= a[i] <= 10^5

Example:

Input:

01234567

3 1 2 4 5 9 13 14 12

Output:

02467531

2 3 5 12 13 14 9 4 1

 Case 1

Input (stdin)
2
8
0 1 2 3 4 5 6 7
9
3 1 2 4 5 9 13 14 12

Output (stdout)
0 2 4 6 7 5 3 1
2 3 5 12 13 14 9 4 1

 Case 2

Input (stdin)
4
8
421 152 141 175 263 340 215 147
6
52 47 852 41 21 58
5
789 456 123 258 147
2
524 963

Output (stdout)
141 215 263 421 340 175 152 147
21 52 852 58 47 41
123 147 789 456 258
524 963

Program 51: Rat Maze With Multiple Jumps

A Maze is given as N*N binary matrix of blocks where source block is the upper left
most block i.e., maze[0][0] and destination block is lower rightmost block
i.e., maze[N-1][N-1]. A rat starts from source and has to reach the destination. The
rat can move in only two directions: first forward if possible or down. If multiple
solutions exist, the shortest earliest hop will be accepted. For the same hop distance
at any point, forward will be preferred over downward.

In the maze matrix, 0 means the block is the dead end and non-zero number means
the block can be used in the path from source to destination. The non-zero value of
mat[i][j] indicates number of maximum jumps rat can make from cell mat[i][j].

In this variation, Rat is allowed to jump multiple steps at a time instead of 1.

Input:

The first line of input contains an integer T denoting the number of test cases. For
each test case, the first line contains an integer n denoting the size of the square
matrix followed by N*N space-separated values of the matrix m where 0's represents
blocked paths and any number represents valid paths.

Output:

For each test case, the output is a matrix containing 1 for the path taken and 0 for
not chosen path. If no path exists print -1.

Constraints:

1 <= T <= 50

2 <= n <= 10

0 <= m[i][j] <= 5

Example:

Input

2100

3001

0101

0001

2100

2001

0101

0001

Output:

1000

1001

0001

0001

-1

Explanation:

Testcase 1: Rat started with m[0][0] and can jump up to 2 steps right/down. First
check m[0][1] as it is 1, next check m[0][2], this won't lead to the solution. Then
check m[1][0], as this is 3(non-zero), so we can make 3 jumps to reach m[1][3].
From m[1][3] we can move downwards taking 1 jump each time to reach destination
at m[3][3].

Testcase 2: As no path exists, so -1.

 Case 1
 Case 2
Input (stdin)
2
4
2 1 0 0
3 0 0 1
0 1 0 1
0 0 0 1
4
2 1 0 0
2 0 0 1
0 1 0 1
0 0 0 1

Output (stdout)
1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1
-1

 Case 2

Input (stdin)
1
4
2 1 0 0
3 0 0 1
0 1 0 1
3 0 0 1

Output (stdout)
1 0 0 0
1 0 0 0
0 0 0 0
1 0 0 1

Program 52: Binary Search Tree - Diameter

Write a program to find the diameter of a binary search tree.

Sample Input:

-1
Sample Output:

Diameter of the given binary tree is 4

 Case 1

Input (stdin)
1
2
3
4
5
-1

Output (stdout)
Diameter of the given binary tree is 4

 Case 2

Input (stdin)
1
2
3
-1

Output (stdout)
Diameter of the given binary tree is 3

Program 53: Distinct Years

The United Nations Organization released an official document regarding the most
important events from the beginning of time (date: 00-00-0000) with a brief
description of the events. The date of all the events is mentioned in the ‘DD-MM-
YYYY’ format. Find the total number of distinct years referenced in the document.

Input Format

Given input is in the form of string containing the content of the document.

Output Format

Return the total number of distinct years referenced in the document.

Refer the sample output for formatting

Sample Input:

UN was established on 24-10-1945. India got freedom on 15-08-1947.

Sample Output:

2
Explanation:

2 distinct years, 1945 and 1947 have been referenced.

 Case 1

Input (stdin)
UN was established on 24-10-1945. India got freedom on 15-08-1947.

Output (stdout)
2

Input (stdin)
The company was founded on 2-04-2017 and By this year 2-04-2020 it would be 2
years. I have Joined the company on 07-05-2017.

Output (stdout)
2

Program 54: Weighted substring

Every character has a weight. The weight of an English uppercase alphabet A-Z is
given below. A=1 B=2*A+A C=3*B+B D=4*C+C . . . Y=25*X+X Z=26*Y+Y The
weight of any string made up of these characters is the summation of weights of
each character. Given a total string weight, determine shortest string of that given
weight. If there is more than one solution, return the lexicographically smallest of
them. For example, given weight = 25, and the weights of the first few characters of
the alphabet are A=1, B=3, C=12, D=60 it is certain that no letter larger than C is
required. Some of the strings with a total weight equal to the largest are ABBBBC,
ACC, and AAAAAAABBBBBB. The shortest of these is ACC. While any permutation of
these characters will have the same weight, this is the lexicographically smallest of
them. Function Description Complete the function smallestString in the editor below.
The function must return the shortest string of the target weight. If there are
multiple answers, return the lexicographically smallest of them. smallestString has
the following parameter(s): weight: a long integer that denotes the target weight.

Input Format

Input consists of a string s.

Output Format

Output should be in the form of integer.

Constraints

1<=weight<=1016

Refer the sample output for formatting

Sample Input:

20

Sample Output:

AABBC

 Case 1

Input (stdin)
20

Output (stdout)
AABBC

Program 55: Maximum profit obtained by buying and

selling stocks
You have been given stock prices for next N days. Find out the maximum profit that
can be obtained by buying and selling the stocks. Conditions: Stock must be sold any
day after the buying date You can buy and sell multiple times, but cannot hold more
than 1 stock at a time. You can only perform a single transaction on a day i.e., can
only either buy or sell on a single day. For example: Share price in thousands 5 1 4 6
7 8 4 3 7 9 Max benefit:

1. Buy share on day 2 at the cost of 1

2. Sell share on day 6 when the price rises to 8

3. Buy a share again on day 8 at the cost of 3

4. Sell share on day 10 when the price rises to 9 Total: (8-1)+(9-3)=13

Input Format

First line consists of integer n.

Second line consists of an array elements of given size n.

Output Format

Output should consists of Integer

Refer the sample output for formatting

Sample Input:

10

5146784379

Sample Output:
13

 Case 1

Input (stdin)
10
5 1 4 6 7 8 4 3 7 9

Output (stdout)
13

Program 56: Append without duplicates

John assigned a roll number to each student in ascending order. Every time he
assigns a number to a student he wants to check whether the number is already
assigned to any other student to avoid the duplicates in the roll number. Add the
number to the list only if the number is not present already. Implement this concept
using a Linked List. If the list is empty, print "List is empty".

Input Format

The input consists of a list of integers, negative value indicates the end of the linked
list.

Output Format

The output should be numbers in the list in separate line.

Refer the sample input & output for formatting specifications.

Sample Input

11

22

33

22

33

44

-77

Sample Output

11
22

33

44

 Case 1
 Case 2

Input (stdin)
11
22
33
22
33
44
-77

Output (stdout)
11
22
33
44

 Case 2

Input (stdin)
-5

Output (stdout)
List is empty

Program 57: Reverse a Linked List Recursively

Given a linked list of N nodes. The task is to reverse this list.

Input:

The first line of input contains the number of test cases T. For each test case, the
first line contains the length of the linked list and the next line contains the elements
of the linked list.

Output:

For each test case, print the reversed linked list in a new line.

User Task:
The task is to complete the function reverseList() with head reference as the only
argument and should return a new head after reversing the list.

Expected Time Complexity: O(N).

Expected Auxiliary Space: O(1).

Constraints:

1 <= T <= 100 //denotes number of cases

1 <= N <= 104

Example:

Input:

123456

2 7 8 9 10

Output:

654321

10 9 8 7 2

Explanation:

Testcase 1: After reversing the list, elements are 6->5->4->3->2->1.

Testcase 2: After reversing the list, elements are 10->9->8->7->2.

 Case 1

Input (stdin)
2
6
1 2 3 4 5 6
5
2 7 8 9 10

Output (stdout)
6 5 4 3 2 1
10 9 8 7 2

 Case 2

Input (stdin)
3
3
1 12 3
4
17 18 19 10
6
25 45 23 60 40 55

Output (stdout)
3 12 1
10 19 18 17
55 40 60 23 45 25