Question

Atlassian | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-21

Answer 1

A beautiful subarray is defined as an array of length having a specific number of odd elements. Given an array of integers and a number of odd elements that constitutes beauty, create as many distinct beautiful subarrays as possible. Distinct means the arrys dont share identical starting and ending indices, though they may share one of the two.
For example, given the array [1,2,3,4,5] and a beautiful number 2, the following beautiful subarrays can be formed.
[1,2,3]
[1,2,3,4]
[2,3,4,5]
[3,4,5]
output: 4

 

More Example
[2,5,4,9] , 2

 

subarrays
[5,4,9]
[2,5,4,9]
output:2

Answer 2

C++ solution. Brute force (O(n^2)) and Sliding Window Implementation (O(n))

 

#include<vector>
#include<iostream>

using namespace std;

int findSubarray(vector<int> nums, int n){
	int count = 0;

	for (int i = 0; i<nums.size(); i++){
		int odd = 0;
		for (int j = i; j<nums.size(); j++){
			if (nums[j] % 2 != 0)
				odd++;
			if (odd > n){
				break;
			}
			if (nums[i] != nums[j] && odd == n){
				cout << nums[i] << "  " << nums[j] << endl;
				count++;
			}

		}
	}
	return count;

}

int findSubarraySlidingWindow(vector<int> nums, int n){
	int windowStart = 0, odd = 0;
	int count = 0;

	for (int windowEnd = 0; windowEnd < nums.size(); windowEnd++){
		if (nums[windowEnd] % 2 != 0){
			odd++;
		}
		if (odd == n && nums[windowStart] != nums[windowEnd]){
			cout << nums[windowStart] << " " << nums[windowEnd] << endl;
			count++;
		}
		while(odd > n){
			// shrink the window
			if(nums[windowStart++] % 2 != 0){
				odd--;
			} 
			if (odd == n && nums[windowStart] != nums[windowEnd]){
				cout << nums[windowStart] << " " << nums[windowEnd] << endl;
				count++;
			}
		}
	}

	int windowEnd = nums.size() -1;
	// There could be more even numbers at front so we could still shrink it even though we are at the end of the array. 
	while(odd >= n){
		// shrink the window
		if(nums[windowStart++] % 2 != 0){
			odd--;
		} 
		if (odd == n && nums[windowStart] != nums[windowEnd]){
			cout << nums[windowStart] << " " << nums[windowEnd] << endl;
			count++;
		}
	}

	return count;
}



int main(void){	
	int ewa = findSubarray({2,5,4,9}, 2);
	cout << "result " << ewa << endl;
	cout << "find subarray sliding window" << endl;
	int result = findSubarraySlidingWindow({2,5,4,9}, 2);
	cout << "result " << result << endl;
	return 0;
}