## Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

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

``````/**
* This method divides the array into halves and calls recursively
* for the count. countZeros will count the zeros that go
* across left and right
*/
private static int getConsecutiveZeroCount(int [] inputArray,int lo,int hi) {
int mid = lo + (hi-lo)/2;
if (hi <= lo) return 0;
int count = getConsecutiveZeroCount(inputArray, lo, mid);
count +=getConsecutiveZeroCount(inputArray, mid+1, hi);
return count+countZeros(inputArray,lo,hi,mid);
}
/**
* This method will count any zeros between left and right array
* @return
*/
private static int countZeros(int [] inputArray,int lo, int hi,int mid) {
if(inputArray[mid+1] == 0 && inputArray[mid] == 0) return 1;
return 0;
}
public static void  main(String[] args) {
int [] inputArray = new int[]{3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
System.out.println(getConsecutiveZeroCount(inputArray, 0, inputArray.length-1));
}``````

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

Not sure why a divide and conquer approach would be requested- the problem can be solved easily enough in a linear fashion with O(n) complexity and O(1) memory:

``````public static int countConsecutive0s(int[] arr){
int counter = 0;
for(int i = 1; i < arr.length; i++){
if(arr[i-1] == 0 && arr[i] == 0){
counter++;
}
}
return counter;
}``````

However, if you had to do a divide and conquer approach specifically like if you were doing some GPU work, then you could do it like the following (pseudo coded up from the perspective of each core)

linearly count consecutive 0s in assigned section
if(not the first section in the array)
if(section starts with 0 and previous section ends with 0){
}
}
save the counts to a working buffer
use logarithmic compression to sum all the counts from the different cores

Runtime complexity will by O(n / c + c log c) where c is the number of cores and memory is O(c)

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

Above code is generic so you can make to check only fir zeros

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

You just need to use a binary search over the array looking for zeros. Whenever it finds one, just check whether the element to the right is also a zero.

Note however that you do not gain anything by using divide and conquer in this problem. It may incur additional cost even, since the DaC paradigm brings in more space complexity due to the call stack.

An implementation in C:

``````int count(const int *V, int s, int e, int n)
{
if (e < s) return 0;

int counter = 0;
int mid_idx = (s+e)/2;

if (V[mid_idx] == 0) {
if (mid_idx < n && V[mid_idx+1] == 0) {
++counter;
}
}

return counter + count(V, s, mid_idx-1, n) +
count(V, mid_idx+1, e, n);
}

int main(int argc, char *argv[])
{
int V[] = {3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
int n = sizeof(V)/sizeof(int);

printf("%d\n", count(V, 0, n-1, n-1));
return 0;
}``````

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

Is it given that array is sorted? you can do binary search in sorted array only

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

Why can't we forward and backward linear search simultaneously. When we the center break the loop.

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

Following code could be used.. though I have not checked but in the similar lines we can use it...

int duplicateCounter = 0 ;

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

if (a[i] == a[i+1]
duplicateCounter ++ ;

if (a[arr.lenght - i] == a[arr.lenght - (i+1)]
duplicateCounter ++ ;

}

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

``````#include <iostream>
#include <cstdio>

using namespace std;

int across(int arr[], int mid, int l, int h) {
int count = 0;
if (arr[mid] == 0) {
if (mid - 1 >= l && arr[mid - 1] == 0) {
count++;
}
if (mid + 1 <= h && arr[mid + 1] == 0) {
count++;
}
}
return count;
}

int countConsec(int arr[], int l, int h) {
if (l > h) {
return 0;
}
int mid = (l + h) / 2;
int count;
int a = countConsec(arr, l, mid - 1);
int b = countConsec(arr, mid + 1, h);
int c = across(arr, mid, l, h);
count = a + b + c;
return count;
}

int main() {
int arr[] = {3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
cout << countConsec(arr, 0, 12) << endl;
return 0;
}``````

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

Python 3

``````def consecutive_zeros(lst):
pairs = 0
for i, y in enumerate(lst):
try:
if y == 0:
if lst[i + 1] == 0:
pairs += 1
except IndexError:
pass
return pairs

print(consecutive_zeros([3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2]))  # 3``````

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.