Join Us
Loading Similar Posts
Entering edit mode
Avg CTC: 16 to 20lpa
Job Roles: Software Engineering, Java Developer, Full Stack Developer
Job Locations: Hyderbad, Bengaluru
Job Link: Software Engineering Roles
Question 1
Multiply the Subarray Sums
Problem Statement
Implement the following function:
int ProductOfSums(int arr[], int n);
The function accepts a positive integer array 'arr' of length 'n' as its argument. The array can be divided into two parts, where first part of array (starting from 0 up to i) is in ascending order and second part of it (starting from i up to n-1) is in descending order. Implement the function to find the sum of first part (ascending order) and sum of second part (descending order). Return the product of sum of first and second part.
Assumption: All elements in array are unique.
Note:
• Return -1, if n < 3 or array is null (or None in case of python).
• Computed value lies within integer range.
Example:
Input:
arr: 3 8 14 12 10 7 4
Output:
1175
Explanation:
Sum:
• Sum of first part (ascending order) = 3 + 8 + 14 = 25.
• Sum of second part (descending order) = 14 + 12 + 10 + 7 ÷ 4 = 47.
Product of sums = 25 * 47 = 1175. Thus, output is 1175.
The custom input format for the above case:
7
3 8 14 12 10 7 4
(The first line represents the size of the array 'n' and the second line represents the elements of the array 'arr')
Sample input
arr: 5 6 7 8 4 3
Sample Output
390
The custom input format for the above case:
6
5 6 7 8 4 3
of the array 'arp')
(The first line represents the size of the array 'n' and the second line represents the elements of the array ‘arr’)
Click here to Practice
Submit Problem to OJ
Question 2
Size of Smallest Possible Array
Implement the following function:
int MinSizeArray (int* arr, int n, int k);
The function accepts a positive integer array 'arr' consisting of 'n' elements and a positive integer 'k' as its argument.
Remove the elements of array according to following rules:
•Exactly three elements are removed in one turn.
•The removed three elements must be adjacent in array, i.e., arr[i], arr[j+1], arr[j+2]. And the second element must be k greater than the first element and the third element must be k greater than the second element, i.e., arr[j+1] - arr[i] = k and arr[j+2] - arr[j+1] = k.
Implement the function to remove the elements from array until no further triplets can be removed and return the size of the smallest possible such array.
Note : Return -1 if 'arr' is empty.
Example:
Input:
k: 2
arr: 2 4 6 8 10 12 8 10 6 8
Output:
1
Explanation:
One way of removing elements from array is:
•Elements {8, 10, 12} at positions {3, 4, 5} respectively are removed to get an array {2, 4, 6, 8, 10, 6, 8}.
•Then, elements {6, 8, 10} at positions {2, 3, 4} respectively are removed to get an array {2, 4, 6, 8}.
•Then, elements {2, 4, 6} at positions {0, 1, 2} respectively are removed to get an array {8}.
Size of final array is 1. Thus, output is 1.
The custom input format for the above case:
2
10
2 4 6 8 10 12 8 10 6 8
(The first line represents 'k', the second line represents 'n', the third line represents the elements of the array 'arr')
Sample input
k: 1
arr: 12 13 14 15 16 19
Sample Output
3
Click here to Practice
Submit Problem to OJ
Entering edit mode
Question 2: Size of smallest possible array
Overview
- Given an array of numbers and a constant k, minimize the size of the array with the given rules for removing elements.
Approach
- For every element
arr[i]there are two possibilities.
1) Either the element is not removed.
2) Or the element is removed (if it follows rules of removal). When an element is removed, there are again two possibilities.
a) It may be removed directly, i.e., initial `arr[i+1] is arr[i]+k` and `arr[i+2]` is `arr[i] + 2*k`.
b) There exist `x` and `y` such that `arr[x] – arr[i] = k, arr[y] – arr[x] = k`, and subarrays `arr[i+1…x-1]` & `arr[x+1…y-1]` can be completely removed.
// Returns size of minimum possible size of `arr[low..high]` after removing elements according to given rules
`findMinSize(arr[], low, high, k)`
1) If `high-low+1 < 3`, return `high-low+1` // If there are less than 3 elements in `arr[low..high]`
2) `result = 1 + findMinSize(arr, low+1, high)` // Consider the case when `arr[low]` is not considered as part of any triplet to be removed. Initialize the result using this case
3)
For all i from low+1 to high // Case when arr[low] is part of some triplet and removed. Try all possible triplets that have `arr[low]`
For all j from i+1 to high
Update result if all of the following conditions are met
a) arr[i] - arr[low] = k
b) arr[j] - arr[i] = k
c) findMinSize(arr, low+1, i-1, k) returns 0
d) findMinSize(arr, i+1, j-1, k) also returns 0
e) The result calculated for this triplet (low, i, j) is smaller than the existing result.
4) Return result
Complexity
Time Complexity: O(N^2), N is the size of the array.
Entering edit mode
Overview
- You have been given an array which first monotonically increases till a peak point and then monotonically decreases.
- We have the multiply the sums from left to the peak point and right to the peak point.
Approach
- The above can be easily done using prefix/suffix sums.
- First , find the peak point in the given array. ( Simple linear search )
- Lets say idx = index of peak point.
- Run a loop from (0 -> idx) and do sum_left += array[i]
- Run a loop from (idx-> n-1) and do sum_right += array[i]
- Return (sum_left *sum_right)
Complexity
- O(N) time contributed by linear search and traversing the array during summation.
- O(1) space complexity.
Code
The time complexity of the proposed solution is O (N4 )
as Time complexity = no. of states * work done per state
i.e N^2 * N^2