Facebook Interview Question for Software Engineers


Country: United States




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

Not sure if I understood the first question right. But if all we want is the number of subarrays with less than K and not the actual subarrays themselves, doesn't it make sense to do one for loop to retrieve the count of elements that fit this criterion (let's call the count M) and return 2^M - 1? The -1 part is to exclude empty lists.

import math
def find_subarray_count(arr, K):
  ct = 0
  for x in arr:
    if x < K:
      ct += 1
  return int(math.pow(2, ct)-1)

- jdoesv April 19, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the solution

/**
 * 
 */
package subArrays;

import java.util.ArrayList;
import java.util.List;

/**
 * @author navdeepmahajan
 *
 */
public class SubArrays {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] input = {
				3, 5, 2, 7, 8, 9, 11, 2, 5, 8, 3
		};
		SubArrays test = new SubArrays();
		System.out.println(test.computeSubArrays(input, 9));
		System.out.println(test.computeNonOverlappingSubArrays(input, 9));
	}
	
	private List<List<Integer>> computeSubArrays(int[] input, int comparison){
		List<List<Integer>> computedLst = new ArrayList<>();
		List<Integer> subArray = new ArrayList<>();
		for (int i=0; i< input.length; i++) {
			if (input[i] < comparison) {
				subArray.add(input[i]);
			}else {
				if (!subArray.isEmpty()) {
					computedLst.add(subArray);
				}
				subArray = new ArrayList<>();
			}
		}
		if (!subArray.isEmpty()) {
			computedLst.add(subArray);
		}
		return computedLst;
	}
	
	private List<List<Integer>> computeNonOverlappingSubArrays(int[] input, int comparison){
		List<List<Integer>> computedLst = new ArrayList<>();
		List<Integer> subArray = new ArrayList<>();
		
		for (int i=0; i< input.length; i++) {
			if (input[i] < comparison) {
				if (subArray.size() ==0) {
					subArray.add(input[i]);
				}else {
					if(input[i] > subArray.get(subArray.size()-1)) {
						subArray.add(input[i]);
					}else {
						if (!subArray.isEmpty()) {
							computedLst.add(subArray);
						}
						subArray = new ArrayList<>();
						subArray.add(input[i]);
					}
				}
			}else {
				if (!subArray.isEmpty()) {
					computedLst.add(subArray);
				}
				subArray = new ArrayList<>();
			}
		}
		if (!subArray.isEmpty()) {
			computedLst.add(subArray);
		}
		return computedLst;
	}

}

- navdeep.mahajan June 02, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't understand what you did here... you first method looks like the answer of follow up question... and second method looks wrong.

- Anonymous June 13, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findSubarrays(arr, K):
    s_idx, e_idx = 0, -1
    total = 0
    while s_idx < len(arr) and e_idx < len(arr):
        if e_idx == -1 and arr[s_idx] < K:
            e_idx = s_idx + 1
        elif e_idx == -1:
            s_idx += 1
            continue
        elif arr[e_idx] < K:
            e_idx += 1
        else:
            total += (e_idx - s_idx) * (e_idx - s_idx + 1) // 2
            s_idx = e_idx + 1
            e_idx = -1
    if e_idx != -1:
        total += (e_idx - s_idx) * (e_idx - s_idx + 1) // 2
    return total

- yongzpub June 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure my understanding of the problem is correct.
int[] array = new int[] { 2, 3, 30, 45, 6, 7, 8, 3, 25, 5 };
Suppose k = 9
Then the output should be 3
Subarrays all elements less than 9 = {2,3}, {6,7,8,3}, {5}

private int SubArrayCount(int[] array, int k)
		{
			int count = 0;
			int length = array.Length;
			for (int i = 0; i < length; i++)
			{
				if (array[i] < k)
				{
					while (i < length && array[i] < k)
						i++;
					count++;
				}
			}

			return count;
		}

- p.rubanantony June 10, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I know the problem is only that you need the number of subarrays I include the subarray's elements and the array only for practice purpose but I need an explanation of the second part. If the owner of this exercise or someone that have the solution can explain me the problem(not the solution) I'll be very greatful.



using System;
using System.Collections.Generic;

// To execute C#, please define "static void Main" on a class
// named Solution.

class Solution
{
static void Main(string[] args)
{

int k;
int arraySize;
Console.WriteLine("Type the size of the array");
arraySize = Int32.Parse(Console.ReadLine());
int[] array = new int[arraySize];
Console.WriteLine("Type the value of K");
k = Int32.Parse(Console.ReadLine());
for(int i=0; i<arraySize; i++)
{
int j = i + 1;
Console.WriteLine("Type the position " + j + " number of the array");
array[i] = Int32.Parse(Console.ReadLine());
}

SubArrays(array, k);

}

static void SubArrays(int[] array, int k)
{
List<List<int>> subArrayList = new List<List<int>>();
List<int> subArray = new List<int>();
Console.WriteLine("The original array is: ");
for(int i=0; i<array.Length; i++)
{

Console.WriteLine(array[i]);
if(array[i] < k)
{
subArray.Add(array[i]);
}
else if(subArray.Count !=0)
{
if(subArray != null)
{
subArrayList.Add((subArray));
}
subArray = new List<int>();
}

}
if(subArray != null && subArray.Count !=0)
{
subArrayList.Add((subArray));
}

Console.WriteLine("\nThe size of sub arrays in wich all elements are less than k: " + subArrayList.Count);
Console.WriteLine("\nThe elements of the sub arrays are: ");

foreach(var subList in subArrayList)
{
foreach(var element in subList)
{
Console.Write(element);
}
Console.WriteLine();
}
}
}

Or if you have corrections with my solution, you are welcome.

Thanks.

- Anonymous June 10, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ruby solution:

def find_subs(arr, k)
  retvals = []
  arr.each do |i|
    if i <= k
      retvals = retvals + retvals.map { |j| j + [i] }
      retvals << [i]
    end
  end
  return retvals
end

def non_overlapping_pairs(arrs)
  pairs = {}
  arrs.each.each_with_index do |a,i|
    ((i+1)...arrs.length).each do |j|
      other = arrs[j]
      which = a.length > other.length
      overlapping = (which ? other : a).any? { |i| (which ? a : other).include?(i) }
      next if overlapping
      pairs[a] ||= []
      pairs[a] << other
    end
  end
  return pairs
end

a = find_subs([1,2,3,4,5], 4)
p a
p non_overlapping_pairs(a)

- vik June 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ruby solution:

def find_subs(arr, k)
  retvals = []
  arr.each do |i|
    if i <= k
      retvals = retvals + retvals.map { |j| j + [i] }
      retvals << [i]
    end
  end
  return retvals
end

def non_overlapping_pairs(arrs)
  pairs = {}
  arrs.each.each_with_index do |a,i|
    ((i+1)...arrs.length).each do |j|
      other = arrs[j]
      which = a.length > other.length
      overlapping = (which ? other : a).any? { |i| (which ? a : other).include?(i) }
      next if overlapping
      pairs[a] ||= []
      pairs[a] << other
    end
  end
  return pairs
end

a = find_subs([1,2,3,4,5], 4)
p a
p non_overlapping_pairs(a)

- vik June 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int calc(int left, int right){
		int n = right-left;
		return n*(n+1)/2;
	}
	int findSubArrays(int[] arr, int k){
		int ans=0;
		int ptr=0;
		while(ptr<arr.length){
			if(arr[ptr] < k){
				int ptrForward = ptr;
				while(arr[ptrForward] < k)
					ptrForward++;
				sum+=calc(ptr, ptrForward);
			}else{
				ptr++;
			}
		}	
	}

- nikhil19kekan June 21, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript

const subsets = function(array, k) {
  let ret = [], index = 0;
  if (array.indexOf(k) == -1) {
    return ret;
  } else {
    index = array.indexOf(k);
  }
  let newArray = array.slice(0, index);

  const permute = function(arr, index) {
    if (arr.length != 0)
      ret.push(arr);

    for (let i = index; i < newArray.length; ++i) {
      permute([...arr, array[i]], i+1);
    }
  }

  permute([], 0);
  return ret;
}

- Terence Ng June 30, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
			int[] inpArr = new int[9] { 20, 13, 14, 8, 21, 17, 18, 11, 5};
			int subArrCnt = 6;
			Array.Sort<int>(inpArr);
			int relPos = 6;
            for (int subArrLength = 2; subArrLength <= relPos + 1; subArrLength++)
            {
                //////////////////////////////////////////
                subArrCnt += GetSubArrCnt(0, relPos, subArrLength, inpArr);
                //////////////////////////////////////////
		    }
			Console.WriteLine("SubArrCount - {0}", subArrCnt);
			Console.ReadLine();
        }

		private static int GetSubArrCnt(int startPos, int relPos, int subArrLength, int[] inpArr)
		{
			int subArrCnt = 0;
			for (int i = 0; i < relPos - subArrLength + 1; i++)
			{
				int startPosofArr = i;
				for (int j = startPosofArr + 1; j < relPos; j++)
				{
					int k = 1;
					int[] subArr = new int[subArrLength];
					subArr[0] = inpArr[startPosofArr];
					int m = j;
					while (k < subArrLength)
					{
						subArr[k] = inpArr[m];
						k++;
						m++;
					}
					subArrCnt++;
				}
			}

			return subArrCnt;
		}

- varunpvk July 19, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In JS....

var k = 10;
var arr = [1,1,0,12,1,1,0,12,1,0,1,11,1,0,12,0,0,1,0,12,1,0,1];

let results = [];
let currentSubArray = [];
let isReset = false;
for (let index = 0; index < arr.length; ++index) {
   if (arr[index] < k) {
      currentSubArray.push(arr[index]);
      if (index === arr.length - 1) {
        isReset = true;
      }
   } else if (currentSubArray.length) {
     isReset = true;
   }

  if (isReset) {
    results.push(currentSubArray);
    currentSubArray = [];
    isReset = false;
  }
}

let usedKeys = [];
var dedupedSet = results.reduce((acc, r) => {
  const elementKey = JSON.stringify(r);
  if (!usedKeys.includes(elementKey)) {
     usedKeys.push(elementKey);
     acc.push(r);
  }
  return acc;
}, []);

console.log(results);
console.log(dedupedSet);

- Dave July 22, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def numSubarrayLessThanK(self, nums: List[int], k: int) -> int:
        ans = 0
        left  = 0
        for right in len(nums):
            if nums[right] > k:
                left = right
                continue
            ans += right - left +1

- Anonymous July 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def numSubarrayLessThanK(self, nums: List[int], k: int) -> int:
        ans = 0
        left  = 0
        for right in len(nums):
            if nums[right] > k:
                left = right
                continue
            ans += right - left +1

- Python July 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findSubArrays(numList, compareNum) {
    let resultArrays = [];
    if (!numList) {
        return result;
    }
    let subArray = [];
    for (let i=0; i< numList.length; i++) {
        if (numList[i] < compareNum) {
            subArray.push(numList[i]);
        } else {
            if (subArray.length) {
                resultArrays.push(subArray);
                subArray=[];
            }
        }
    }
    if (subArray.length) {
        resultArrays.push(subArray);
    }
    return resultArrays;
}

function findNonOverlapSubArrys(numList, compareNum) {
    let resultArrays = [];
    if (!numList) {
        return result;
    }
    let subArray = [];
    for (let i=0; i< numList.length; i++) {
        if (numList[i] < compareNum) {
            if (subArray.length && numList[i] < subArray[subArray.length - 1]) {
                resultArrays.push(subArray);
                subArray = [numList[i]];
            } else {
                subArray.push(numList[i]);
            }
        } else {
            if (subArray.length) {
                resultArrays.push(subArray);
                subArray=[];
            }
        }
    }
    if (subArray.length) {
        resultArrays.push(subArray);
    }
    return resultArrays;
}

- yolanda August 31, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Selfwork {
	public static void main(String[] args) {
		List<Integer> elements = Arrays.asList(0, 10, 4, 6, 8, 1, 9, 2, 3, 7);
		int k = 5;
		int numberOfSubArrays = find(elements, 5);
		System.out.println(numberOfSubArrays);
	}

	private static int find(List<Integer> elements, int k) {
		List<Integer> eliminatedList = elements.stream().filter(e -> e < 5).collect(Collectors.toList());
		int size = eliminatedList.size();
		return combination(size, k);
	}

	private static int combination(int set, int k) {
		if(k == 0) {
			return 0;
		}
		int upResult = 1;
		int downResult = 1;
		int tempSet = set;
		int tempK = k;
		while(tempK >= 1) {
			upResult *= tempSet--;
			downResult *= tempK--;
		}
		int result = upResult / downResult;
		return result + combination(set, --k);
	}
}

- esoner.sezgin September 13, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given an integer array and an integer K, find the number of sub arrays in which all elements are less than K.
Assume continous numbers.

Example:
k = 5
{1, 5, 2 , 3, 1, 1, 2, 6, 0, 4}
*/

typedef unsigned int uint32_t;

uint32_t find_sub_num (uint32_t array[], uint32_t k, size_t len)
{
uint32_t result = 0;
uint32_t counter = 0, i;

if (array == NULL) {
return 0;
}


if (len == 1) {
if (array[0] < k) {
return 1;
} else {
return 0;
}
}

for (i = 0; i < len; i++) {
if (array[i] + result < k) {
counter ++;
result += array[i];

} else if (array[i] < k) {
counter ++;
result = array[i];
} else {
result = 0;
}
printf("result %d counter %d array[%d] %d \n", result, counter, i, array[i]);

}

return counter;

}

int main (void)
{
uint32_t array[] = {1, 5, 2, 3, 1, 1, 2, 6,0,4};

printf("%d\n", find_sub_num(array, 5, sizeof(array)/sizeof(array[0])));
return 0;
}

- Mohamed October 21, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Given an integer array and an integer K, find the number of sub array in
# which all elements are less than K.
#
# Follow up -
# Given an integer array and an integer K, find the number of non
# overlapping unordered pairs of sub array in which all elements are less
# than K.

from itertools import combinations

K = 10
a = [1, 2, 3, 11, 4, 5, 12, 13, 7]


def get_sub_array_sizes(a: [int], k: int):
    sub_size = 0
    for v in a:
        if v < k:
            sub_size += 1
        else:
            if sub_size > 0:
                yield sub_size
            sub_size = 0

    if sub_size > 0:
        yield sub_size


# Count the number of max size sub array with all elements less than K
# For the example above, sub array are: [1,2,3], [4, 5], [7].  num = 3
def num_sub_arrays(a: [int], k: int) -> int:
    return sum(1 for i in get_sub_array_sizes(a, k))


# number of non overlapping interval pairs in a range(n)
# e.g. range(1,3) can produce the following pairs:
# [[1,(2,3)], [1, 2], [1,3], [(1,2), 3], [2,3]
# for the total of 5 pairs
def num_range_interval_pairs(n: int) -> int:
    return sum((i + 1) * (n - i - 1) * (n - i) / 2 for i in range(n))


# Number of non overlapping subarray pairs size > 0 with all elements < K
def num_outer_sub_array_pairs(a: [int], k: int) -> int:
    return sum(a * (a+1)/2 * b * (b+1)/2
               for a, b in combinations(get_sub_array_sizes(a, k), 2))


def num_inner_sub_array_pairs(a: [int], k: int) -> int:
    return sum(num_range_interval_pairs(a) for a in get_sub_array_sizes(a, k))


def num_sub_array_pairs(a: [int], k: int) -> int:
    return num_inner_sub_array_pairs(a, k) + num_outer_sub_array_pairs(a, k)


print(num_sub_arrays(a, K))
print(num_sub_array_pairs(a, K))

- Vassili Gorshkov April 10, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int count_subarrays(int l) {
return (l * (l - 1)) / 2 + l;
}

int count_subarrays_less_than_k(std::vector<int> a, int k) {
int count = 0;
int start = 0;
for (int i = 0; i <= a.size(); ++i) {
if (i == a.size() || a[i] >= k) {
int l = i - start;
count += count_subarrays(l);
start = i + 1;
}
}
return count;
}


int count_non_overlapping_subarrays(int l) {
int count = 0;
for (int i = 1; i < l; ++i) {
count += count_subarrays(i) * (l - i);
}
return count;
}

int count_non_overlapping_subarrays_less_than_k(std::vector<int> a, int k) {
std::vector<int> counts;
int count = 0;
int start = 0;
for (int i = 0; i <= a.size(); ++i) {
if (i == a.size() || a[i] >= k) {
int l = i - start;
if (l > 0) {
counts.push_back(count_subarrays(l));
count += count_non_overlapping_subarrays(l);
}
start = i + 1;
}
}
for (int i = 0; i < counts.size(); ++i) {
for (int j = i + 1; j < counts.size(); ++j) {
count += counts[i] * counts[j];
}
}
return count;
}



std::cout << count_subarrays_less_than_k({ 1, 6, 12, 13, 4, 2, 5, 13, 2 }, 7) << std::endl;
std::cout << count_non_overlapping_subarrays_less_than_k({ 1, 6, 12, 13, 4, 2, 5, 13, 2 }, 7) << std::endl;

10
33

- Omri.Bashari May 04, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findNumberofSubArray(int[] input, int k) {
        int arrayCount = 0;
        int prev = k+1;
        for (int i=0; i<input.length; i++) {
            if ( prev < k && input[i] <k) {

            } else if(prev < k && input[i] >= k) {
                arrayCount++;
            } else if(prev > k && input[i] > k) {

            } else if(prev > k && input[i] < k) {

            }
            prev = input[i];
        }
        if (input[input.length - 1]<k) {
            arrayCount++;
        }
        return arrayCount;
    }

- Anonymous May 27, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question doesn't make sense at all. It will make sense if the SUM of all elements of subarray is less than K.

- Probably the description miss some information June 15, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question as it is here does not make any sense. But it will make sense if it says: that the SUM of all elements of sub array is less than K.

- AICre8r June 15, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{import java.util.Arrays;

public class NumbersOfSubArrayLessThanK {


public static int countSubArray(int []array, int k) {
// Base case1
if (array == null || array.length < 1) {
return 0;
}
// Sorting array
Arrays.sort(array);

// Again base case check because we have sorted array
if (k < array[0]) {
return 0;
}
// we do not need to check whole array because array is sorted just find subarray where you have to find all less than k combination
int j = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] < k) {
j = j + 1;
}
}
int totalcount = j;
int l =0;

int cumm = 0;
int processing = 0;
while (processing < j) {
cumm = cumm + array[l];
if (cumm < k) {
for (int i = l + 1; i < j; i++) {
int tmp = cumm + array[i];
if (tmp >= k) {
break;
}
totalcount = totalcount + 1;
}
}
l = l + 1;
if (l == j) {
processing = processing + 1;
l = processing;
cumm = 0;
}
}
return totalcount;
}

public static void main(String[] args) {
long result = countSubArray(new int [] {12, 11, 20}, 10);
// [1], [2], [3], [1, 2, 3], [1, 2], [1, 3], [2, 3] {1, 2, 3}, 10
System.out.println(result);
}

}
}}

- shalnatwal89 June 16, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

K = 10
A = [1, 2, 3, 11, 4, 5, 12, 13, 7,9]
def get_sub_arrays2(A,k):
result=[]
temp=[]
i=0
while i< len(A):
print(A[i])
if A[i]<k:
temp.append(A[i])
else:
if len(temp) >0:
result.append(temp)
print(temp)
temp=[]
i+=1


if (len(temp) >0):
result.append(temp)
return result

print(get_sub_arrays2(A,K))

- Hermasoft September 06, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def findNonOverlappingSubarrayPairs(arr, K):
    s_idx, e_idx = 0, -1
    total = 0
    blocks = []
    def calculator(s_idx, e_idx):
        t = 0
        t += e_idx - s_idx - 1        
        comb = (e_idx - s_idx) * (e_idx - s_idx + 1) // 2
        for p in blocks:
            t += comb * p
        blocks.append(comb)
        return t
    while s_idx < len(arr) and e_idx < len(arr):
        if e_idx == -1 and arr[s_idx] < K:
            e_idx = s_idx + 1
        elif e_idx == -1:
            s_idx += 1
            continue
        elif arr[e_idx] < K:
            e_idx += 1
        else:
            total += calculator(s_idx, e_idx)
            s_idx = e_idx + 1
            e_idx = -1
    if e_idx != -1:
        total += calculator(s_idx, e_idx)    
    return total

- yongzpub June 08, 2020 | 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