Facebook Interview Question
SDE1sCountry: United States
'''
window:
* queue of intervals
* running count of strictly increasing subarrays
* running count of strictly decreasing subarrays
* keep track of flat subarrays too
@ every window step, we output num_incr_subarrs - num_decr_subarrs
Time complexity: O(n)
Space complexity: O(k)
'''
from collections import deque # Pythonic queue
class Interval(object):
def __init__(self, slope, x, y):
self.slope = slope
self.q = deque()
self.q.append(x)
self.q.append(y)
class Window(object):
def __init__(self):
self.queue = deque()
self.num_incr_subarrs = 0
self.num_decr_subarrs = 0
self.start_new_interval_flag = True
def insert(self, num1, num2):
# Strictly Increasing
if num1 < num2:
if (self.start_new_interval_flag
or len(self.queue) == 0
or not self.queue[-1].slope > 0):
self.queue.append(Interval(1, num1, num2))
else:
self.queue[-1].q.append(num2)
self.num_incr_subarrs += len(self.queue[-1].q) - 1
self.start_new_interval_flag = False
# Strictly Decreasing
elif num1 > num2:
if (self.start_new_interval_flag
or len(self.queue) == 0
or not self.queue[-1].slope < 0):
self.queue.append(Interval(-1, num1, num2))
else:
self.queue[-1].q.append(num2)
self.num_decr_subarrs += len(self.queue[-1].q) - 1
self.start_new_interval_flag = False
# Flat
else:
self.queue.append(Interval(0, num1, num2))
self.start_new_interval_flag = True
def cut_left(self):
if len(self.queue) == 0:
return
interval = self.queue[0]
if interval.slope > 0:
self.num_incr_subarrs -= len(interval.q) - 1
elif interval.slope < 0:
self.num_decr_subarrs -= len(interval.q) - 1
if len(interval.q) == 2:
self.queue.popleft()
else:
interval.q.popleft()
def solution(nums, k):
n = len(nums)
assert k > 1
assert n >= k
output = []
# Populate initial window
window = Window()
for i in range(k - 1):
window.insert(nums[i], nums[i + 1])
output.append(window.num_incr_subarrs - window.num_decr_subarrs)
for i in range(k - 1, n - 1):
window.cut_left()
window.insert(nums[i], nums[i + 1])
output.append(window.num_incr_subarrs - window.num_decr_subarrs)
return output
nums = [188930, 194123, 201345, 154243, 154243]
k = 3
attempt = solution(nums, k)
print(attempt)
assert attempt[0] == 3
assert attempt[1] == 0
assert attempt[2] == -1
Python solution :
nums = [188930, 194123, 201345, 154243, 154243]
k = 3
for i in range(len(nums)-k+1):
i_ln,d_ln,i_cnt,d_cnt = 1,1,0,0
s = nums[i:k+i]
#Increasing order
for j in range(len(s)-1):
if s[j] < s[j+1]:
i_ln += 1
else:
i_cnt += int(((i_ln-1)*i_ln)/2)
i_ln = 1
if i_ln > 1:
i_cnt += ((i_ln-1)*i_ln)/2
#Decreasing order
for j in range(len(s)-1):
if s[j] > s[j+1]:
d_ln += 1
else:
d_cnt += int(((d_ln-1)*d_ln)/2)
d_ln = 1
if d_ln > 1:
d_cnt += ((d_ln-1)*d_ln)/2
print(int(i_cnt),int(d_cnt),int(i_cnt-d_cnt))
O(n) soln. -
public static void main(String[] args){
int[] arr = {188930, 194123, 201345, 154243, 154243};
int k = 3;
diff(arr, k);
}
//188930, 194123, 201345, 154243, 154243
public static void diff(int[] arr, int k){
int n = arr.length;
int[] dpi = new int[n];
int[] dpd = new int[n];
int increase = 0;
int decrease = 0;
for(int i = 1; i < n; i++){
if(arr[i] > arr[i-1]){
int t = increase+1;
increase += t;
dpi[i] = increase;
if(k >= 2)
dpd[i] = dpd[k-2];
else
dpd[i] = 0;
decrease = dpd[i];
}else if(arr[i] < arr[i-1]){
int t = decrease+1;
decrease += t;
dpd[i] = decrease;
if(k >= 2)
dpi[i] = dpi[k-2];
else
dpi[i] = 0;
increase = dpi[i];
}
}
for(int i = k-1; i < n; i++){
int incr = dpi[i];
int decr = dpd[i];
if(i-k >= 0){
incr -= dpi[i-k];
decr -= dpd[i-k];
}
System.out.print((incr-decr) + " ");
}
}
from operator import gt, lt
def cnt_seq(seq, fun):
# fun - any operator to compare two numbers
tot = 0
cur_len = 1
for i in range(len(seq)-1):
if fun(seq[i+1], seq[i]):
tot += cur_len
cur_len += 1
else:
cur_len = 1
return tot
seq = [1, 2, 3, 1, 2]
n_inc = cnt_seq(seq, gt) # num on increasing subseqs [1, 2], [2, 3], [1, 2], [1, 2, 3]
n_dec = cnt_seq(seq, lt) # num of decreasing subseqs [3, 1]
print(n_inc, n_dec)
O(n * k) time and O(n) space. Space can be improved to O(k) by using a linked list instead of inc and dec arrays.
- Alex November 03, 2017