## Snapdeal Interview Question for Tech Leads

• 0
of 0 votes

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);
Console.ReadLine();

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);
Console.ReadLine();

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);

/// read the elements
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);

/// read the elements
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);

/// read the elements
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)

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More