## Snapdeal Interview Question for Tech Leads

• 0

Country: India
Interview Type: In-Person

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

Looks like it should be possible to do this in O(N) time. I just maintain a list of sums of all subarrays ending at each index.

``````def find_sums(arr):
l = len(arr);
if l == 1:
res = [{}];
res[0][arr[0]] = 1;
return res;
temp = {};
prev_res = find_sums(arr[1:]);
if arr[0] == -1:
last_res = prev_res[-1];
for key in last_res.keys():
temp[key-1] = last_res[key];
temp[-1] = 1 if -1 not in temp.keys() else (temp[-1] + 1);
elif arr[0] == 1:
last_res = prev_res[-1];
for key in last_res.keys():
temp[key+1] = last_res[key];
temp[1] = 1 if 1 not in temp.keys() else (temp[1] + 1);

prev_res.append(temp);
return prev_res;

print find_sums([-1,1,1,-1,-1,1,1,1,-1,-1,1,-1,1]);``````

Then we just take a sum of 0 indexed elements at each index.

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

``````int[] combos = new int[]{-1,1,1,-1};
int sum = 0;
int condition = 0;
int numberofCombos = 0;

//twos

for(int a = 0; a < combos.Length; a++)
{
for(int b = a+1; b < combos.Length; b++)
{

sum = combos[a] + combos[b];
if (sum == condition)
{
Console.WriteLine("This equals " + condition + ":{a:" + combos[a] + ",b:" + combos[b] + "}");
numberofCombos = numberofCombos + 1;
}
}

}

// threes

for (int a = 0; a < combos.Length; a++)
{
for (int b = a + 1; b < combos.Length; b++)
{

for (int c = b + 1; c < combos.Length; c++)
{
if (sum == condition)
{
sum = combos[a] + combos[b] + combos[c];
Console.WriteLine("This equals " + condition + ":{a:" + combos[a] + ",b:" + combos[b] + ",c:" + combos[c] + "}");
numberofCombos = numberofCombos + 1;
}
}

}

}

//four
sum = combos[0] + combos[1] + combos[2] + combos[3];
if (sum == condition)
{
Console.WriteLine("This equals " + condition + ":{a:" + combos[0] + ",b:" + combos[1] + ",c:" + combos[2] + ",c:" + combos[3] + "}");
numberofCombos = numberofCombos + 1;

}

Console.WriteLine("total combos = " + numberofCombos);

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

``````int[] combos = new int[]{-1,1,1,-1};
int sum = 0;
int condition = 0;
int numberofCombos = 0;

//twos

for(int a = 0; a < combos.Length; a++)
{
for(int b = a+1; b < combos.Length; b++)
{

sum = combos[a] + combos[b];
if (sum == condition)
{
Console.WriteLine("This equals " + condition + ":{a:" + combos[a] + ",b:" + combos[b] + "}");
numberofCombos = numberofCombos + 1;
}
}

}

// threes

for (int a = 0; a < combos.Length; a++)
{
for (int b = a + 1; b < combos.Length; b++)
{

for (int c = b + 1; c < combos.Length; c++)
{
if (sum == condition)
{
sum = combos[a] + combos[b] + combos[c];
Console.WriteLine("This equals " + condition + ":{a:" + combos[a] + ",b:" + combos[b] + ",c:" + combos[c] + "}");
numberofCombos = numberofCombos + 1;
}
}

}

}

//four
sum = combos[0] + combos[1] + combos[2] + combos[3];
if (sum == condition)
{
Console.WriteLine("This equals " + condition + ":{a:" + combos[0] + ",b:" + combos[1] + ",c:" + combos[2] + ",c:" + combos[3] + "}");
numberofCombos = numberofCombos + 1;

}

Console.WriteLine("total combos = " + numberofCombos);

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

O(N^2) solution

``````package main

import "fmt"

func CountZero(m []int, sum int) int {
res := 0
for i := 0; i < len(m)-1; i++ {
sum := 0
for j := i + 1; j < len(m); j++ {
sum += m[j]
if sum == -m[i] {
res++
}
}
}
return res
}

func main() {
fmt.Println(CountZero([]int{-1, 1, -1, 1}, 0)) // 4
fmt.Println(CountZero([]int{-1, -1, 1, 1}, 0)) // 2
fmt.Println(CountZero([]int{-1, 1}, 0))        // 1
}``````

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

O(n2) solution in Java:

``````public class CountZero {

public static int countZero(int[] a) {
int count = 0;

for (int i = 0; i < a.length; i++) {
int sum = a[i];
for (int j = i + 1; j < a.length; j++) {
sum += a[j];
if (sum == 0) {
count++;
}
}
}
return count;
}

public static void main(String[] args) {
System.out.println(countZero(new int[] { -1, 1, -1, 1 })); // 4
System.out.println(countZero(new int[] { 1, -1, -1, 1, -1, -1, 1 })); // 6
System.out.println(countZero(new int[] { 1, 1, -1, -1 })); // 2
System.out.println(countZero(new int[] { -1 })); // 0
System.out.println(countZero(new int[] {})); // 0
System.out.println(countZero(new int[] { -1, -1, -1, -1, -1, -1, -1 })); // 0
}
}``````

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

#include <bits/stdc++.h>

using namespace std;

/// Expected Time O(n)
int solve(){

/// read the lenght of array
int n;
scanf("%d",&n);

vector<int> elements(n);
for(int i = 0; i < n; ++i){
scanf("%d",&elements[i]);
}

unordered_map<int,int> frecuency; /// a hash table default c++11 , expected time 0(1)
for(int i = 0; i < n; ++i){
if(i > 0){
elements[i] += elements[i-1];
}
frecuency[elements[i]]++; /// update the frecuency
}

int goal = 0;
int ways = 0;
for(int i = 0; i < n; ++i){
ways += frecuency[goal];
goal = elements[i];
frecuency[elements[i]]--;
}
return ways;
}

int main(){

//give a array of just -1 or 1 , how many subarray there are , so that the sum = 0 ?
freopen("in.c","r",stdin);

cout << solve() << endl;

return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

/// Expected Time O(n)
int solve(){

/// read the lenght of array
int n;
scanf("%d",&n);

vector<int> elements(n);
for(int i = 0; i < n; ++i){
scanf("%d",&elements[i]);
}

unordered_map<int,int> frecuency; /// a hash table default c++11 , expected time 0(1)
for(int i = 0; i < n; ++i){
if(i > 0){
elements[i] += elements[i-1];
}
frecuency[elements[i]]++; /// update the frecuency
}

int goal = 0;
int ways = 0;
for(int i = 0; i < n; ++i){
ways += frecuency[goal];
goal = elements[i];
frecuency[elements[i]]--;
}
return ways;
}

int main(){

//give a array of just -1 or 1 , how many subarray there are , so that the sum = 0 ?
freopen("in.c","r",stdin);

cout << solve() << endl;

return 0;
}

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

``````#include <bits/stdc++.h>

using namespace std;

/// Expected Time O(n)
int solve(){

/// read the lenght of array
int n;
scanf("%d",&n);

vector<int> elements(n);
for(int i = 0; i < n; ++i){
scanf("%d",&elements[i]);
}

unordered_map<int,int> frecuency; /// a hash table default c++11 , expected time 0(1)
for(int i = 0; i < n; ++i){
if(i > 0){
elements[i] += elements[i-1];
}
frecuency[elements[i]]++; /// update the frecuency
}

int goal = 0;
int ways = 0;
for(int i = 0; i < n; ++i){
ways += frecuency[goal];
goal = elements[i];
frecuency[elements[i]]--;
}
return ways;
}

int main(){

//give a array of just -1 or 1 , how many subarray there are , so that the sum = 0 ?
freopen("in.c","r",stdin);

cout << solve() << endl;

return 0;
}``````

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

``````/* shows how declarative paradigm is powerful */
def count_zero_sum_sub_arrays( arr ){
len = size(arr)
// generate sum from combinations of [0,1,2,...len-1] taking 2 at a time
sum ( comb( [0:len] , 2 ) ) ->{
// when the sum is 0 add 1, else 0
( 0 == sum( [\$.0:\$.1+1] ) -> { arr[\$.o] } ) ? 1 : 0
}
}
arr = [-1,1,-1,1]
println( count_zero_sum_sub_arrays(arr) )``````

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

We can solve this in linear time by traversing through the array and keeping the current sum of all the values. When we encounter a sum that we have already found previously that means that there is a subarray with sum 0.

For example, for input: [-1, 1, -1, 1]
As we traverse and keep the sum we get the following values:
0, -1, 0, -1, 0

three zeros indicate there are three subarrays that sum to zero. Two -1s indicate there is one subarray that sums to zero.

Java implementation:

``````public int countSubArraysSumZero(int[] nums) {
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
count.put(0, 1);

int sum = 0, res = 0;
for(int i : nums) {
sum += i;
if(count.containsKey(sum)) {
res += count.get(sum);
count.put(sum, count.get(sum)+1);
}else{
count.put(sum, 1);
}
}

return res;
}``````

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

``````def count_zero(a):
n = len(a)
d = {}
temp_sum = 0

for i in xrange(n):
temp_sum = temp_sum + a[i]
if temp_sum in d:
d[temp_sum] = d[temp_sum] + 1
else:
d[temp_sum] = 1

count = 0
for i in d:
count = count + (d[i]*(d[i]-1))/2

if 0 in d:
count = count + d[0]
return count

a = map(int, raw_input().strip().split(' '))
print count_zero(a)``````

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.