Data Structures Assignment # 1
Deadline : To be decided
1
Problem # 1
Given a string of a, b, c, find the number of substrings with equal number of a, b and c. If the
input string is : ”abacbcba”, the output will be 3 (”acb”, ”cba”, ”acbcba”)
1.1
Input Specification
Integer N followed by N input strings, each on a separate line.
1.2
Output Specification
For each string output the number of substrings with equal a, b and c.
1.3
Sample Input
2
abacbcba
abab
1.4
Sample Output
3
0
2
Problem # 2
Given an array of integers and an integer k, find the kth smallest element in the array. (You can
assume that k will be smaller than the size of the array)
Constraint : Your solution should be more efficient than any of the sorting algorithms.
2.1
Input Specification
Integer N followed by N test cases. Each test case will be of three lines, first line will be an integer
NA (size of the array), next line will contain the array in space separated format and third line will
be the value of k.
2.2
Output Specification
Print the kth smallest elemnt in the array.
1
2.3
Sample Input
2
4
21 1 2 78
2
1
1
1
2.4
Sample Output
2
1
3
Problem # 3
You are given prices of stock of a particular company in an array A, such that A[i] is the value of
stock on ith day. You have to buy and sell the stock in such a way that you maximize the profit.
3.1
Input Specification
Integer N followed by N test cases. Each test case will be of two lines, first line will be an integer
NA (size of the array) , next line will contain the array in space separated format.
3.2
Output Specification
For each test case, Print the mazimum profit that can be obtained.
3.3
Sample Input
3
2
10 5
6
4 2 1 10 5 8
3
2 20 10
3.4
Sample Output
0
9
18