Facebook Interview Question Software Engineers
Country: United States
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
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;
}
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.
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)
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)
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;
}
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;
}
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);
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;
}
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);
}
}
/*
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;
}
# 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))
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
Here's the solution
- navdeep.mahajan June 02, 2020/** * */ 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; } }