CareerCup

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;
	}

}

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

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

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)

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++;
			}
		}	
	}

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;
}