Snapdeal Interview Question Tech Leads
Country: India
Interview Type: In-Person
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();
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();
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
}
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
}
}
#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;
}
#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;
}
#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;
}
/* 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) )
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;
}
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)
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.
- Aayush February 18, 2017