Description
Task A
Given an empty stack and some operations (push and pop) on the stack, print the popped
element for each pop operation. When applying pop operation on an empty stack, output
‘false’ and then terminate the program. The number of operations is at most 1000. The
elements of the stack are integers. All inputs in the test case are valid. (You don’t need to
consider the case when format of input is wrong.)
You should implement a stack by yourself without using built-in classes.
Input:
The input contains multiple lines, where each line contains one operation.
Output:
Print the results, seperated by spaces. Having a trailing space at the end of the line or not
does not matter.
Examples:
1. Input:
push 1
push 2
pop
push 9
pop
Output:
2 9
2. Input:
push 3
push 12
pop
pop
pop
push 4
pop
Output:
12 3 false
3
Task B
Rearrange a singly linked list in such a way that all odd nodes together followed by the
even nodes. Note that here we are talking about the node number and not the value in the
nodes. Your program should run in O(1) space complexity and O(n) time complexity. The
first node is considered odd, the second node even and so on. 1 ≤ n ≤ 1000.
Note: You must refer to the folder ‘sketch for B’: do not change the code in main.cpp and
ListNode.h, and you are only allowed to edit 1234554321-B.cpp. You just need to submit
1234554321-B.cpp at the end. (Use your own university number.)
Input:
The input contains two lines.
The first line contains an integer n – length of the list.
The second line contains n distinct integers, standing for the list.
Output:
Print the required list, containing n integers. Having a trailing space at the end of the line
or not does not matter.
Examples:
1. Input:
6
1 5 3 7 8 11
Output:
1 3 8 5 7 11
2. Input:
7
2 1 3 5 6 4 7
Output:
2 3 6 7 1 5 4
4
Task C
Given a parentheses string s, compute the score of the string based on the following rule:
• If s is not balanced, the score is 0.
• () has score 1.
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.
A balanced string satisfies the following requirements:
• The number of ‘(’ equals the number of ‘)’ in the string.
• Counting from the first position to any position in the string, the number of ‘(’ is
greater than or equal to the number of ‘)’ in the string. (For example, ‘)(’ is not
balanced.)
The length of s is at most 30.
Input:
The input is a parentheses string s.
Output:
Print the score of s.
Examples:
1. Input:
(())
Output:
2
2. Input:
(()(()))
Output:
6
3. Input:
((()())
Output:
0
5
Task D
Given n strings, output the number of distinct strings. The sum of length of strings is at
most 106
.
Input:
The input contains two lines:
The first line is an integer n, which is the number of strings in the second line.
The second line are n strings.
Output.
Output an integer – the number of distinct strings.
Examples.
1. Input:
3
abc abcc abd
Output:
3
2. Input:
7
aaa bbb abc bjyx wegdbs szdszd aaa
Output:
6
3. Input:
5
abc lgieong lgieong kkkk lgieong
Output:
3
6
