1) Given a sorted integer array, A and an integer input, M, find two values in A whose sum is equal to M. If there are no such numbers, your program should state, “No such numbers”. Your program must run in O (N) and utilize a space of O (1).
Examples:
#1:
Input Array, A: 2 6
10 15 100
M: 110
The numbers are 10 100
#2:
Input Array, A: 2 6
10 15 100
M: 173
No such numbers
2) An integer array, A of size N takes positive
input values. Write a program which separates even and odd numbers in A such
that all even numbers come first, followed by all the odd numbers. Your program
must run in O (N) and utilize a space of O (1).
Example:
Input size of the array:
5
Input Array:
1
10 24 45
78
Output:
78 10 24
45 1
3)
Your program will take positive, unsorted input values into
an integer array, A. You must write a program that computes if the
values in A are in consecutive or
non-consecutive order. Your program should run in O (n) and utilize a memory of
O (n).
Examples:
#1:
Array, A: 56, 61, 57, 60, 59, 58
The values in A are in consecutive order.
#2:
Array, A: 56, 61, 57, 60, 56, 58
The
values in A are not in consecutive
order.
#3:
Array, A: 56, 64, 57, 60, 56, 58
The
values in A are not in consecutive
order.
4)
Your program will take input values for two, sorted integer arrays
(of size, M and N) and merge the values into a third integer array (of size = M
+ N) such that the values in the third array are also sorted. Your program must run in O (M +
N) and utilize a space of O (1).
Example:
Array 1: 10 34 56 89
112 150 167 200
Array 2: 2 5 12 154
880 900
Merged
Array: 2 5 10 12 34 56 89 112 150 154 200 880 900
5)
Given a
sorted array of integers, A that contains both positive and negative integers,
find two values in the array such that their sum is closest to zero. Your
program must run in O (N) and utilize a space of O (1).
Examples:
#1:
Input array: -45
-30 -20 5
15
Output: -20 and 15
#2:
Input array: -7 1 2 17 19
Output: 1 and 2
6) Your program will take integer
input values into an integer array and print those values in the array that are
greater than all the values to its right side. The
rightmost element of the array will always be printed. Your program must run in
O (N) and utilize a space of O (1).
Examples:
#1:
Input Array, A: 6, 8, 4, 3, 5, 1
Output: 1 5 8
#2:
Input Array, A: 1, 2,3,4,5
Output: 5
7)
A peak value in an array is a value that is greater than or equal
to its neighbors (values to the left and right).
The
following rules apply for the first and last values in the array:
· If the
first value in the array is >= second value in the array, it is a peak
value.
· If the
last value in the array is > = second to last value in the array, it is a
peak value.
Examples:
1) 1 2 6 5 3
7: Peak values are 6 are 7
2) 1 2 3 4 5
6: Peak value is 6
3) 2 2 2 2 2
2: Peak value is 2
4) 6 5 4 3 2
1: Peak value is 6
Write a program
that finds a peak value in an input array of integers. If there is more than
one peak value, your program should print any one of them. Your program
must run in O (log n) and utilize a memory of O (1).
8)
Your program will take integer values into an array, A and find the two numbers in A with the maximum difference such that
the larger number appears after the smaller number. Your program should
run in O (n) and utilize a memory of O (1).
Examples:
#1:
Input:
Array, A: 2, 3, 10, 6, 4, 8, 1
Output:
2 and 10
#2:
Input:
Array, A: 7, 9, 5, 6, 3, 2
Output:
7 and 9
#3:
Input:
Array, A: 7, 9, 5, 6, 13, 2
Output:
5 and 13
9)
An element in integer array (of size n) is called
a majority element if it appears more than n/2 times. Write a program
that takes an integer array as the input and returns the majority element. If
no such element exists in the array, the program should state, “No majority
element in the input array”. Your program must run in O (N) and utilize a space
of O (1).
Examples:
#1:
Array, A: 2, 4, 2, 5, 2, 3, 4, 2, 2
Majority value = 2
#2:
Array, A: 2, 4, 12, 5, 2, 3, 4, 2, 2
No majority value in A