Problem #1:
The input to
your program will be as below:
·
An integer
array, A whose values are already sorted in ascending order.
·
An integer
input, M.
Your program
has to insert M into the array (A) at the appropriate spot so that the
resulting array is also sorted in ascending order. Your program has to run in O (N) and utilize a space of O (1). Refer
to the program output and ensure that you have handled all the test cases.
In the examples below:
·
The length of A = 7.
·
Six input integer values are inserted into A
from Cell#0 through Cell#5. Cell#6 is left empty (a [6] = 0) to handle the
insertion of M.
Program Output:
Test#1 (M is less than some values and
greater than other values in A):
Initial
Array, A: 1 5 10 20
30 42 0
Input value
to insert, M: 12
The updated
array, A: 1 5 10
12 20 30
42
Test#2 (M is less than all values in A):
Initial
Array, A: 1 5
10 20 30
42 0
Input value
to insert, M: -10
The updated
array, A: -10
1 5 10
20 30 42
Test#3 (M is greater than all values in
A):
Initial
Array, A: 1 5
10 20 30
42
Input value
to insert, M: 100
The updated
array, A: 1 5 10
20 30 42
100
Test#4 (M is a duplicate of an existing
value in A):
Initial
Array, A: 1 5
10 20 30
42 0
Input value
to insert, M: 30
The updated
array, A: 1 5
10 20 30
30 42
Problem #2:
Write a program to play the game
of Mastermind:
In the game of Mastermind, the
computer selects a three-digit number in which all three digits are distinct.
The task of the human player is to keep making guesses until he or she guesses
all three digits in the proper order. Each time the human makes a guess, the
computer tells the human the following:
a) How many
hits the player had, where one hit means getting one correct digit in its
correct position.
b) How many
matches the player had, where one match means getting one correct digit in the
wrong position.
Example:
(Let’s say the computer generated 476)
Guess number
569
0 hits 1 matches
Guess number
123
0 hits 0 matches
Guess number
674
1 hits 2
matches
Guess number
746
1 hits 2
matches
Guess number
476
3 hits 0 matches
The Guess is accurate! GAME OVER!
Problem #3:
Your program will take input
values into an integer array, A and compute the total number
of strictly increasing sub-arrays of size more than 1. A strictly increasing
sub-array of A is a sub-array whose values are in increasing order.
Example:
Array, A: 10 20 30 25 40 60
Strictly increasing sub-arrays of
size > 1:
10 20 30
10 20
20 30
25 40 60
25 40
40 60
Total = 6
For your program, you don’t have
to print all the strictly increasing sub-arrays. Your output would simply be
the total number of strictly increasing sub-arrays of size > 1. Your program
should have a running time of O (n)and utilize a space of O (1).
Problem #4:
A balance point in an integer
array is the value in the array (let’s say, X) for which the following property
holds true:
· Sum of
values at cells less than the cell# of X (left-sum) = Sum of values at cells
greater than the cell# of X (right-sum).
Since there are no cells to the
left of the first cell, the left-sum of the first cell is 0. Hence, the first
value in the array is called the balance point if its right-sum is equal to 0.
Similarly, as there are no cells to the right of the last cell, its right-sum is
0. Therefore, the last value in the array is called the balance point if its
left-sum is equal to 0.
Write a program to find the
balance point of an input integer array. Your program must find only
one balance point in the array. If a balance point was not found in
the input array, your program should print, “No balance point in the input
array”.
Your program must run in O (n)
and utilize a memory of O (1).
Examples:
a) -7, 1, 5,
2, -4, 3, 0 : Balance Point is 2 ( -7 + 1 + 5 = -4 + 3
+ 0 = -1)
b) 1, 2, 9,
4, -1 : Balance Point is 9 (1 + 2 = 4 + (-1) = 3)
c) 6, 1, 2,
-3 : Balance Point is 6 (1 + 2 + (-3)
= 0)
d) 4 ,1, -5 , -4 : Balance Point is -4 ( 4 + 1 + (-5) = 0)
e) 1, 2, 3,
4, 5, 6 : No balance points in the input array