## Microsoft Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

This is an O(n^2) solution, although it is very clumsy. Here, i have just iterated through all the elements as starting position of 1 sub-array, and traversed from the end to find the max length under the given conditions.

``````public void getMaxLength(int[] arr) {
int len = arr.length;
int maxCount = 0;
for(int i=0;i<len;i++) {
int head = i; int tail = len-1;
int max = 0; // Max value of smaller sub-array
int min = Integer.MAX_VALUE; // Min value of larger sub-array
int currentCount = 0; // Max length sub-array for elements starting at index i
int startMax = -1; // 1 = head represents larger sub-array ; 2 = tail represents larger sub-array

if(startMax == -1)
startMax = arr[head] > arr[tail] ? 1 : 0;
else {
if((startMax == 1) && ((arr[head] < arr[tail]) || (arr[head] < max) || (arr[tail] > min))) {
startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; currentCount = 0;
continue;
}
else if((startMax == 0) && ((arr[head] > arr[tail]) || (arr[head] > min) || (arr[tail] < max))) {
startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; currentCount = 0; continue;
}
}

max = (startMax == 1) ? Math.max(max, arr[tail]) : Math.max(max, arr[head]);
min = (startMax == 1) ? Math.min(min, arr[head]) : Math.min(min, arr[tail]);
maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
}

}
System.out.println("Max Length = " + maxCount);
}``````

Comment hidden because of low score. Click to expand.
0

This seems working. Riku, can you provide subjective description of the solution

Comment hidden because of low score. Click to expand.
0

It fails for the following inputs

{ 5, 50, 6, 35, 0, 1, 2, 7, 45, 4, 30, 40, 41, 60, 3 });
{ 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }

Comment hidden because of low score. Click to expand.
0

There is minor bug in the code which is causing incorrect output for the cases mentioned above. Actually you don't need to reset head to i when condition fails.

Here is c# code after fixing the bug

``````public static void getMaxLength(int[] arr) {
int len = arr.Length;
int maxCount = 0;
for(int i=0;i<len;i++) {
int head = i; int tail = len-1;
int max = 0; // Max value of smaller sub-array
int min = int.MaxValue; // Min value of larger sub-array
int currentCount = 0; // Max length sub-array for elements starting at index i
int startMax = -1; // 1 = head represents larger sub-array ; 2 = tail represents larger sub-array

if(startMax == -1)
{
startMax = arr[head] > arr[tail] ? 1 : 0;
max = (startMax == 1) ? Math.Max(max, arr[tail]) : Math.Max(max, arr[head]);
min = (startMax == 1) ? Math.Min(min, arr[head]) : Math.Min(min, arr[tail]);
tail--;
currentCount++;
maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
continue;
}
else {
if((startMax == 1) && ((arr[head] < arr[tail]) || (arr[head] < max) || (arr[tail] > min))) {
startMax = -1;
max = 0;
min = int.MaxValue;
currentCount = 0;
continue;
}
else if((startMax == 0) && ((arr[head] > arr[tail]) || (arr[head] > min) || (arr[tail] < max))) {
startMax = -1;
max = 0;
min = int.MaxValue;
currentCount = 0;
continue;
}
}

max = (startMax == 1) ? Math.Max(max, arr[tail]) : Math.Max(max, arr[head]);
min = (startMax == 1) ? Math.Min(min, arr[head]) : Math.Min(min, arr[tail]);
tail--;
currentCount++;
maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
}
}
Console.WriteLine("Max Length = " + maxCount);
}
public static void Main(string[] args)
{
getMaxLength(new int[] { 20, 5, 7, 2, 11, 55, 9, 26, 48, 22, 12 }); // Expected 4
getMaxLength(new int[] { 20, 5, 7, 2, 11, 55, 9, 26, 48, 22, 10 }); // Expeced 3
getMaxLength(new int[] { 10, 5, 100, 2, 70, 3, 60, 1, 99, 4, 66 }); // expected 1

getMaxLength(new int[] { 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }); // Expcted 4

}``````

Comment hidden because of low score. Click to expand.
0

You are outputting the max length. Where are the sub-arrays?

Comment hidden because of low score. Click to expand.
0

Can you explain this solution? Its hard to get it by tracing the code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Say k = size of each sequence. Check all subsequences length k from k = 1 to n/2. Keep track of the min/max of subsequences. If subsequences are non intersecting and the max of one is smaller than a min of the other, you've found your answer. This is expected to be an O(n^3) algorithm

Comment hidden because of low score. Click to expand.
0

O(n^3) is obvious answer. I think interviewer is looking for a better solution (O(n^2) or more better), with the use of hint that all numbers in the sequence are unique

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use DP to solve this problem in O(n^2)

``````void longestSubArray(int A[], int n)
{
int *dp[2]; for (int i = 0; i < 2; ++i) dp[i] = new int[n];

int len = 0, s1 = 0, s2 = 0;

for (int i = n - 1; i >= 0; --i)
{
dp[i & 1][i] = 0; dp[i & 1][n - 1] = 1;

for (int j = n - 2; j > i; --j)
{
int tmp = (A[i] > A[j]) == (A[i + 1] > A[j + 1]) ? dp[(i + 1) & 1][j + 1] + 1 : 1;

if (tmp > j - i) tmp = j - i;

if (tmp > len)
{
len = tmp; s1 = i; s2 = j;
}

dp[i & 1][j] = tmp;
}
}

if (len == 0)
{
cout << "no answer!" << endl;
}

cout << "first subarray: "; for (int i = s1; i < s1 + len; ++i) cout << A[i] << " "; cout << endl;

cout << "second subarray: "; for (int i = s2; i < s2 + len; ++i) cout << A[i] << " "; cout << endl;
}``````

Comment hidden because of low score. Click to expand.
0

What does i& 1 return? i itself , if i is non-zero?

Comment hidden because of low score. Click to expand.
0

I honestly don't know what you're doing there. Care to elaborate?
In any case, whatever it is, it is wrong. With this input it already fails: {1,2,5,3,7,4,9,8}.

Comment hidden because of low score. Click to expand.
0

nope, for this array: [7,6,5,4,9,11,3,2,8]
it returns

``````first subarray: 4 9 11
second subarray: 3 2 8``````

which is not correct

Comment hidden because of low score. Click to expand.
0

nope, for this array: 7,6,5,4,9,11,3,2,8
it returns:
first subarray: 4 9 11
second subarray: 3 2 8
which is not correct

Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array, and divide it into two, then we get the required result right ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array, and dividing it into two, will give the required result right ?

Comment hidden because of low score. Click to expand.
0

Sorting will change the order of arrary element, and the problem will reduce to max sub arraylegnth = arraylegnth/2 which is straightforward.Better to check with interviewer before hand.

Comment hidden because of low score. Click to expand.
0

sorting will change the order of elements in array, better to check with interviewer before hand

Comment hidden because of low score. Click to expand.
0
of 0 vote

the code does not workfor the input {11,2,3,4,55,68,78,88,9}. Please check.

Expected is 4 i.e 11,2,3,4 and 55,68,78,88.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here my logic by brute force first:

1. MaxSubArrayLength = InPutArray.Length /2
2. While MaxSubarrayLength>=2
3. Create sub arrays of length MaxSubarrayLength . Incase of inputArray of length 8, we will get 2 subarrays of length 4 each. If these array comparison doesnt gives our result we decrease MaxSubArrayLength by 1 (untill we reach 2).

4. In our case array of length 8 with sub array of length 3 will give us 6 subarrays which we compare in pairs to check if we get desired result. If we get our desire result we stop.
thats max sub array length ans sub array

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's an adaptation of the LCS (longest common substring) algorithm. N^2.

``````static void FindSubarrays(int[] values, out int first, out int second, out int size)
{
var acc = new int[values.Length + 1, values.Length + 1];
size = 0;
first = -1;
second = -1;

for (int i = 0; i <= values.Length; i++)
{
for (int j = 0; j <= values.Length; j++)
{
if (i == 0 || j == 0 || values[i-1] >= values[j-1])
acc[i, j] = 0;
else
{
int maxDistance = MaxDistance(i, j);
acc[i, j] = Math.Min(acc[i - 1, j - 1] + 1, maxDistance);
if (size < acc[i, j])
{
size = acc[i, j];
first = i - size;
second = j - size;
}
}
}
}
}

static int MaxDistance(int i, int j)
{
int first = Math.Min(i, j);
int distance = Math.Abs(i - j);
return Math.Min(first, distance);
}``````

The question also says that all numbers are unique. That may be a key for a simpler solution, which I do not see yet.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Below code is perfect. we must reset the head to i but at the same time we need to take care of the tail. a few manipulations to the code written by Riku will give us the result. Anyways credit goes to riku.

public class ss {
public static void getMaxLength(int[] arr) { int leng = arr.length;
int maxCount = 0;
for(int i=0;i<leng;i++) {
int len=arr.length;
int head = i; int tail = len-1;
int max = 0; // Max value of smaller sub-array
int min = Integer.MAX_VALUE; // Min value of larger sub-array
int currentCount = 0; // Max length sub-array for elements starting at index i
int startMax = -1; // 1 = head represents larger sub-array ; 2 = tail represents larger sub-array

if(startMax == -1)
startMax = arr[head] > arr[tail] ? 1 : 0;
else {
if((startMax == 1) && ((arr[head] < arr[tail]) || (arr[head] < max) || (arr[tail] > min))) {
startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; len--;tail=len;
currentCount = 0;
continue;
}
else if((startMax == 0) && ((arr[head] > arr[tail]) || (arr[head] > min) || (arr[tail] < max))) {
startMax = -1; max = 0; min = Integer.MAX_VALUE; head = i; len--;tail=len;
currentCount = 0; continue;
}
}

max = (startMax == 1) ? Math.max(max, arr[tail]) : Math.max(max, arr[head]);
min = (startMax == 1) ? Math.min(min, arr[head]) : Math.min(min, arr[tail]);

maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
}

}
System.out.println("Max Length = " + maxCount);
}

public static void main(String[] args) {
getMaxLength(new int[] {6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }); // Expected 4

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the max sub array is doable in O(n)
now just iterate left side and right side find the max sub array of both and compare find the cross over point. Check the cross over point and see which of the 2 (before cross over and after) yeilds the greater values sum

Comment hidden because of low score. Click to expand.
0
of 0 vote

Below Solution having - O(n^4) complexity
-------------------------------------------------------------------------------------------------

``````void printMaxContiguousSubArrays(int[] arr) {

// max sequence will be equal to the size of the input array/2
int maxSeq = arr.length / 2;
int k = maxSeq;

// k>1 because we do not want to have sublists of array size 1 as output
while (k > 1) {
// divide into subarrays of size k
List<List<Integer>> subArrays = divideIntoSubArrays(arr, k);

// compare contents of sublists to find the legitimate combination
for (int i = 0; i < subArrays.size(); i++) {
List<Integer> tempSubList1 = subArrays.get(i);
// System.out.println(subList);
for (int j = i + 1; j < subArrays.size(); j++) {
List<Integer> tempSubList2 = subArrays.get(j);

// sort the sublists to compare. sorted sublists will be stored in temp sublists
List<Integer> tempSubListSorted1 = sort(tempSubList1);
List<Integer> tempSubListSorted2 = sort(tempSubList2);

if ((tempSubListSorted1.get(0) > tempSubListSorted2.get(0) && tempSubListSorted1.get(0) > tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(tempSubListSorted2.size() - 1))
|| (tempSubListSorted1.get(0) < tempSubListSorted2.get(0) && tempSubListSorted1.get(0) < tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(tempSubListSorted2.size() - 1))) {
System.out.println("Maximum contiguous sequence sub arrays are: " + tempSubList1 + " and " + tempSubList2);
return;
}
}
}
k--;
}

System.out.println("No contiguous subarrays found meeting the required conditions");
}

// method to sort the input list of integers
List<Integer> sort(List<Integer> lst) {
List<Integer> tempLst = new ArrayList<Integer>();

for (Integer i : lst) {
}

Collections.sort(tempLst);
return tempLst;
}

// divide the array into contiguous blocks arrays of size k
List<List<Integer>> divideIntoSubArrays(int[] arr, int k) {

List<List<Integer>> subArrays = new ArrayList<List<Integer>>();

List<Integer> subList = null;

int j = 0;
for (int l = 0; l < arr.length; l++) {
int i = l;
while (i < arr.length) {
if (j == k)
j = 0;

if (j == 0) {
subList = new ArrayList<Integer>();
}
j++;
i++;
}
}

return subArrays;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Below Solution having - O(n^4) complexity
-------------------------------------------------------------------------------------------------

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PrintContiguousSubArrays {
public static void main(String[] args) {
int[] arr = { 6, 5, 4, 1, 3, 7 };
printMaxContiguousSubArrays(arr);
}

static void printMaxContiguousSubArrays(int[] arr) {

// max sequence will be equal to the size of the input array/2
int maxSeq = arr.length / 2;
int k = maxSeq;

// k>1 because we do not want to have sublists of array size 1 as output
while (k > 1) {
// divide into subarrays of size k
List<List<Integer>> subArrays = divideIntoSubArrays(arr, k);

// compare contents of sublists to find the legitimate combination
for (int i = 0; i < subArrays.size(); i++) {
List<Integer> tempSubList1 = subArrays.get(i);
// System.out.println(subList);
for (int j = i + 1; j < subArrays.size(); j++) {
List<Integer> tempSubList2 = subArrays.get(j);

// sort the sublists to compare. sorted sublists will be stored in temp sublists
List<Integer> tempSubListSorted1 = sort(tempSubList1);
List<Integer> tempSubListSorted2 = sort(tempSubList2);

if ((tempSubListSorted1.get(0) > tempSubListSorted2.get(0) && tempSubListSorted1.get(0) > tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) > tempSubListSorted2.get(tempSubListSorted2.size() - 1))
|| (tempSubListSorted1.get(0) < tempSubListSorted2.get(0) && tempSubListSorted1.get(0) < tempSubListSorted2.get(tempSubListSorted2.size() - 1)
&& tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(0) && tempSubListSorted1.get(tempSubListSorted1.size() - 1) < tempSubListSorted2.get(tempSubListSorted2.size() - 1))) {
System.out.println("Maximum contiguous sequence sub arrays are: " + tempSubList1 + " and " + tempSubList2);
return;
}
}
}
k--;
}

System.out.println("No contiguous subarrays found meeting the required conditions");
}

static List<Integer> sort(List<Integer> lst) {
List<Integer> tempLst = new ArrayList<Integer>();

for (Integer i : lst) {
}

Collections.sort(tempLst);
return tempLst;
}

// divide the array into contiguous blocks arrays of size k
static private List<List<Integer>> divideIntoSubArrays(int[] arr, int k) {

List<List<Integer>> subArrays = new ArrayList<List<Integer>>();

List<Integer> subList = null;

int j = 0;
for (int l = 0; l < arr.length; l++) {
int i = l;
while (i < arr.length) {
if (j == k)
j = 0;

if (j == 0) {
subList = new ArrayList<Integer>();
}
j++;
i++;
}
}

return subArrays;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the techinque, took some time to figure it out,
We need some space to figure out this problem, the space required for this problem is n*n, because there will be n*n many intervals, we need this space to save the min/max of an internal and help in figure out the min and max of its near by intervals in o(1) time.
Here is the algorithm

``````n <- size of the array A
define M(n,n) as two value matrix storing both min and max, where M(i,j) repersents min and max between the array i and j, This will a symmetric matrix(M(i,j) = M(j,i)
set M(i,j) = (min = infinity, max = -infinity)
For k = 2 to n/2 // as one size sub is always a solution for this problem
for j = 1 to n-2k  // assuming array from A[1 to n]
if M(j,j+k) is not defined, define it
for i = j+k+1 to n-k
if M(i,i+k) is not defined, define it
if M(j,j+k) and M(i,i+k) satisfy the condition,
save k and indexes to return the answer at the end, we will overwrite the old values of k is higher
end
end
end``````

``````Condition_check((Min1,Max1),(Min2,Max2))
if Max1 < Min2 or Min1 > Max2 then return true else return false``````

Here is how we define the vales of M

``````Set_MValues(A,M,i,j)
If Defined(M(i,j-1)
Then Min(M(i,j) = Min(A[j], Min(M(i,j-1)) and Max(M(i,j) = Max(A[j], Max(M(i,j-1))
If Defined(M(i-1,j)
Then Min(M(i,j) = Min(A[i], Min(M(i-1,j)) and Max(M(i,j) = Max(A[i], Max(M(i-1,j))
else figure out min and max between A(i...j].``````

Complexity
Time : O(n*n*n)
Space : O(n*n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedList;
import java.util.Queue;

public class maxLenSubArrays {

public static void main(String[] args){
int[] nums = { 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4};
int n = nums.length;
int[][] mins = buildMins(nums);
int[][] maxs = buildMaxs(nums);
System.out.print("(");
for(int i: first) System.out.print(i + " ");
System.out.print(") - (");
for(int i: second) System.out.print(i + " ");
System.out.println(")");
}
}

public static int[][] buildMins(int[] nums){
int n = nums.length;
int size = n;
int[][] mins = new int[n][n];

while(size > 0){
minQueue minQ = new minQueue(size);
for(int i = 0; i < n; i++ ){
if(i >= size -1) mins[i- size + 1][i] = minQ.getMin();
}
size--;
}

return mins;
}

public static int[][] buildMaxs(int[] nums){
int n = nums.length;
int size = n;
int[][] maxs = new int[n][n];

while(size > 1){
maxQueue maxQ = new maxQueue(size);
for(int i = 0; i < n; i++ ){
if(i >= size - 1) maxs[i-size + 1][i] = maxQ.getMax();
}
size--;
}

return maxs;
}

int n = nums.length;
int size = n / 2;
int twosize = size * 2;
boolean found = false;
//complexity = size * i / size * i / size, hence n^2
while(size > 1 && !found){
for(int i = 0; i < n - twosize + 1; i++){
int firstmin = mins[i][i+size-1];
int firstmax = maxs[i][i+size-1];
for(int j = i + size; j < n - size + 1; j++){
int secondmin = mins[j][j+size-1];
int secondmax = mins[j][j+size-1];
if(firstmax < secondmin || firstmin > secondmax) {
found = true;
}
}
}
size--;
}
return output;
}

private static LinkedList[] buildArr(int[] nums, int i, int j, int size){
for(int k = i; k < i + size ; k++) first.add(nums[k]);
res[0] = first;
for(int k = j; k < j + size ; k++) second.add(nums[k]);
res[1] = second;
return res;
}

static class maxQueue{
int size = 0;
public maxQueue(int size){
this.size = size;
}

if(mainq.size() == size) remove();
while(!maxq.isEmpty() && maxq.get(maxq.size() - 1) < val) maxq.remove(maxq.size() - 1);
}

public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!maxq.isEmpty() && maxq.get(0) == val) maxq.remove(0);
mainq.remove();
}

public int getMax(){
if(maxq.isEmpty()) return Integer.MIN_VALUE;
return maxq.get(0);
}

public int size(){
return mainq.size();
}

}

static class minQueue{
int size = 0;
public minQueue(int size){
this.size = size;
}

if(mainq.size() == size) remove();
while(!minq.isEmpty() && minq.get(minq.size() - 1) > val) minq.remove(minq.size() - 1);
}

public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!minq.isEmpty() && minq.get(0) == val) minq.remove(0);
mainq.remove();
}

public int getMin(){
if(minq.isEmpty()) return Integer.MIN_VALUE;
return minq.get(0);
}

public int size(){
return mainq.size();
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedList;
import java.util.Queue;

public class maxLenSubArrays {

public static void main(String[] args){
int[] nums = { 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4};
int n = nums.length;
int[][] mins = buildMins(nums);
int[][] maxs = buildMaxs(nums);
System.out.print("(");
for(int i: first) System.out.print(i + " ");
System.out.print(") - (");
for(int i: second) System.out.print(i + " ");
System.out.println(")");
}
}

public static int[][] buildMins(int[] nums){
int n = nums.length;
int size = n;
int[][] mins = new int[n][n];

while(size > 0){
minQueue minQ = new minQueue(size);
for(int i = 0; i < n; i++ ){
if(i >= size -1) mins[i- size + 1][i] = minQ.getMin();
}
size--;
}

return mins;
}

public static int[][] buildMaxs(int[] nums){
int n = nums.length;
int size = n;
int[][] maxs = new int[n][n];

while(size > 1){
maxQueue maxQ = new maxQueue(size);
for(int i = 0; i < n; i++ ){
if(i >= size - 1) maxs[i-size + 1][i] = maxQ.getMax();
}
size--;
}

return maxs;
}

int n = nums.length;
int size = n / 2;
int twosize = size * 2;
boolean found = false;
//complexity = size * i / size * i / size, hence n^2
while(size > 1 && !found){
for(int i = 0; i < n - twosize + 1; i++){
int firstmin = mins[i][i+size-1];
int firstmax = maxs[i][i+size-1];
for(int j = i + size; j < n - size + 1; j++){
int secondmin = mins[j][j+size-1];
int secondmax = mins[j][j+size-1];
if(firstmax < secondmin || firstmin > secondmax) {
found = true;
}
}
}
size--;
}
return output;
}

private static LinkedList[] buildArr(int[] nums, int i, int j, int size){
for(int k = i; k < i + size ; k++) first.add(nums[k]);
res[0] = first;
for(int k = j; k < j + size ; k++) second.add(nums[k]);
res[1] = second;
return res;
}

static class maxQueue{
int size = 0;
public maxQueue(int size){
this.size = size;
}

if(mainq.size() == size) remove();
while(!maxq.isEmpty() && maxq.get(maxq.size() - 1) < val) maxq.remove(maxq.size() - 1);
}

public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!maxq.isEmpty() && maxq.get(0) == val) maxq.remove(0);
mainq.remove();
}

public int getMax(){
if(maxq.isEmpty()) return Integer.MIN_VALUE;
return maxq.get(0);
}

public int size(){
return mainq.size();
}

}

static class minQueue{
int size = 0;
public minQueue(int size){
this.size = size;
}

if(mainq.size() == size) remove();
while(!minq.isEmpty() && minq.get(minq.size() - 1) > val) minq.remove(minq.size() - 1);
}

public void remove(){
if(mainq.isEmpty()) return;
int val = mainq.peek();
if(!minq.isEmpty() && minq.get(0) == val) minq.remove(0);
mainq.remove();
}

public int getMin(){
if(minq.isEmpty()) return Integer.MIN_VALUE;
return minq.get(0);
}

public int size(){
return mainq.size();
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

time: O(N^2 * log(N)), space O(N)
for each possible length L of a continuous sub-array, find all possible N-L+1 sub-arrays, and calculate the min/max of values in each sub-array. This can be done in N.

Now the question is checking if there exists two non-overlapped intervals: This can be done in n*log(n) after sorting the intervals by their min values.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think we are going to have an O(n^4) algorithm.
First how many sub arrays could there be in a range of n numbers
It is not counted as a group if there is only 1 element in it.
For 2 elements you get n-1 groups
For 3 you get n-2
And so on
(n-1)+(n-2)+(n-3)…..(1)
(n^2 + n)/2 – n
(n^2 –n)/2
Now lets say we have numbers from 1 to k inclusive
For a given set i to j (where i is at least one smaller then j ) inclusive we can match with any set before or after it
We won’t count the sets before it so we don’t double count
It boggles the mind but it looks pretty O(n^4) to me.
I don’t recall how to compute the series.
But the code will look like 4 nested loops I think hopefully not 6

Comment hidden because of low score. Click to expand.
0

none of the above code is correct....

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.