Snap Inc Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
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;
}
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;
}
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;
}
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
{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;
}
}
}
{ 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