## Uber Interview Question for SDE-2s

Country: United States
Interview Type: Phone Interview

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

solution of approach 2; but still don't know how to do the improvement that i mentioned;

``````static int subArrays(int arr[], int k) {

int count = 0;
Set<Integer> set = new HashSet<>();

//Count single length
for (int i = 0; i < arr.length; i++) {
count += set.contains(arr[i]) ? 0 : 1;
}

int s = 0;
int oddCount = 0;

int i = 0;
for (; i < arr.length; i++) {

if (arr[i] % 2 != 0)
oddCount++;

//count length > 1
if (i - s > 0 && oddCount == k) {
count++;
}

//Slide the window
if (oddCount > k) {

while (oddCount > k && s < i) {

if (arr[s] % 2 != 0)
oddCount--;
s++;

if (i - s > 0 && oddCount == k) {
count++;
break;

}

}
}
}
i--;

//if left over array has more then 2 element, count them too
while (i - s + 1 >= 2) {
s++;
if (i - s + 1 >= 2)
count++;

}

return count;
}``````

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

Create a prefix array where the ith element of that array will denote the number of odd elements encountered up till ith index .
Then for every index i suppose the value of the pref[i]=p then use binary search to find the first occurence of a value greater than or equal to p-k . Suppose that index is j . Then j-i+1 is added to the answer .
Complexity O(Nlog2(N)).

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

I think u missed the last part of question or I may not understood ur solution, pls elobrate

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

If we ignore the second condition that no two sub-arrays can be duplicate, below is the solution

``````public class KOddArrays{

static int result=0;

public static void findKAtmostOddSubArrays(int[] arr, int k , int i, int odds){
if(i>arr.length-1){
return;
}else{

if(odds>0 && odds<=k){
result++;
}

int newOdds = odds;
if(arr[i]%2 !=0){
newOdds++;
}

//use current element
findKAtmostOddSubArrays(arr,k,i+1,newOdds);
//dont use current element
findKAtmostOddSubArrays(arr,k,i+1,odds);
}
}

public static void main(String[] args){
int[] arr = {3, 2, 3, 4};
int k=1;

findKAtmostOddSubArrays(arr,k,0,0);
System.out.println(result);
}
}``````

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

Isn't this solution n^3 in the worst case?

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

Isn't this solution n^3? (It can be made n^2 using sliding window approach)

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.