Snap Inc Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




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

static boolean containSum(int[] array, int n) {
		if (array == null)
			return false;
		else {
			HashSet<Integer> hs = new HashSet<>();
			int total = 0;
			
			for (int i = 0; i < array.length; i++) {
				total += array[i];
				if (total == n)
					return true;
				if (hs.contains(total - n)) {
					return true;
				} else {
					hs.add(total);
				}
			}
			return false;
		}
	}

- nelsonwcf May 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isSum(int[] input, int sum) {
        Preconditions.checkNotNull(input, "Illegal input");
        if (input.length == 1) {
            return sum == input[0];
        }

        boolean isSumExisting = false;
        int left = 0;
        int right = 1;
        int tmpSum = input[left];
        while (right < input.length && !isSumExisting) {

            if (tmpSum < sum || left == right -1) {
                tmpSum += input[right];
                right++;
            } else if (tmpSum > sum) {
                if (input[right] < 0) {
                    tmpSum += input[right];
                    right++;
                } else {
                    tmpSum -= input[left];
                    left++;
                }
            } else {
                isSumExisting = true;
            }
        }
        return isSumExisting;
    }

- Scavi May 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We assume that the empty subarray has sum 0.  We iterate through the array and keep a runningTotal.
We keep track of all previous runningTotals we have encountered in an unordered_set.  If the difference bbetween the needle and the current running total has previously been encountered we return true.  Expected running time O(n).

bool
solution(const std::vector<int>& input, int needle)
{
   
	if(0 == needle) return true;
        int RunningTotal = 0;
        std::unordered_set<int> partialSums;
        partialSums.insert(runningTotal);
        for(auto it = input.begin(); it != input.end(); ++it){
            RunningTotal += *it;
            const int complement = needle - RunningTotal;
            if(1 == partialSums.count(complement) ){
		return true;
            } else {
                partialSum.insert(RunningTotal);
            }
        }
        return false;   
}

- fred May 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution using a map to keep track the previous segments:
Runtime: O(n) and O(n) space.

bool check_sum_subarray(const std::vector<int> V, int N) {
    std::unordered_map<int, int> map_sum_to_index;
    std::vector<int> sum(V.size());

    int acc = 0;

    for (int i = 0; i < V.size(); i++) {
        acc += V[i];
        if (acc == N) return true;

        
        if (map_sum_to_index.find(acc - N) != map_sum_to_index.end()) {
            return true;
        }

        map_sum_to_index[acc] = i;
    }
    
    return false;
}

- Felipe Cerqueira May 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

+1

- sasachin04 June 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can be solved using the sliding window approach in linear time.
function(int[] ar,int k), initialize sum =0, and two variables i and j;
j is starting index of window
and i is end point of window
1-Run a loop to length of the array-
a- if sum == k , return true
b- else if (sum > k), sum = sum - ar[j], j++ // exclude the first index from window
c- else if (sum < k), sum = sum + ar[i], i++; //include the current index

At this point - i reached to end but if sum > k then Need to run one more loop to check from j to i.
2- while(j > i && sum >= i)
a- if sum ==k , return true
b- sum = sum - ar[j], j++
3- return false

Below is working code-

public static boolean isSum(int[] ar, int k) {
		int sum = 0;
		int j = 0; // window's starting point
		int i = 0; // windows end point
		while (i < ar.length) {

			if (sum == k) {
				return true;
			} else if (sum > k) {
				sum = sum - ar[j];
				j++;
			} else if(sum < k){
				
				sum = sum + ar[i];
				i++;
			}

		}
		
		while(j < i && sum >= k){
			if(sum == k){
				return true;
			} 
				sum = sum - ar[j];
				//System.out.println(sum);
				j++;
			
		}	
		return false;
	}

TIme complexity =~O(n), and constant space complexity

- azambhrgn May 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{static boolean containSum(int[] array, int n) {
if (array == null)
return false;
else {
HashSet<Integer> hs = new HashSet<>();
int total = 0;

for (int i = 0; i < array.length; i++) {
total += array[i];
if (total == n)
return true;
if (hs.contains(total - n)) {
return true;
} else {
hs.add(total);
}
}
return false;
}
}
}

- nelsao May 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{ static boolean containSum(int[] array, int n) {
if (array == null)
return false;
else {
HashSet<Integer> hs = new HashSet<>();
int total = 0;

for (int i = 0; i < array.length; i++) {
total += array[i];
if (total == n)
return true;
if (hs.contains(total - n)) {
return true;
} else {
hs.add(total);
}
}
return false;
}
}
}

- nelsao May 16, 2017 | Flag Reply


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