Shopify Interview Question
Country: Canada
/*
It can be done, in multiple linear traversals.
[1] Traverse to find out the min and max of the session ranges.
[2] Create a list of session count per time point, and keep on increasing
[3] Last traversal, find out the range which has max count.
We do not know (a,b) means both inclusive, or first inclusive 2nd exclusive.
It is assumed that (a,b) means user was live from a to b, that is, both inclusive
That does not match the sample output, obviously
*/
def get_max_session( session_list ){
seed = { 'm' : num('inf'), 'M' : num('-inf') }
range = fold( session_list , seed ) as {
$.p.m = ( $.p.m > $.o[0] ) ? $.o[0] : $.p.m
$.p.M = ( $.p.m < $.o[1] ) ? $.o[1] : $.p.M
$.p // return
}
// now create a list, counters:
counters = list( [range.m : range.M + 1] ) as { 0 } // done
// next, increment counters...
for ( session : session_list ){
for ( offset : [ session[0] : session[1] + 1] ){
counters[ range.m - offset ] += 1 // incrementing sessions
}
}
// now, find out the range where max count exists
max_range = { 's' : range.m , 'e' : range.m , 'c' : counters[0] }
cur_range = { 's' : range.m , 'e' : range.m , 'c' : counters[0] }
for ( i : [ 0 : size(counters) ] ){
if ( cur_range.c != counters[i] ){
cur_range = { 's' : i + range.m , 'e' : i + range.m , 'c' : counters[i] }
if ( cur_range.c > max_range.c ){
// update max
max_range = { 's' : cur_range.s, 'e' : cur_range.e, 'c' : cur_range.c }
}
} else {
cur_range.e = i + range.m
}
}
// print max
println( max_range )
}
session_list = [ [2,5], [3,6], [8,10],[10,12], [9,20] ]
get_max_session( session_list )
result:
{s=13, c=3, e=13}
def has_overlap(A_start, A_end,sessions):
for B_sess in sessions:
B_start, B_end =B_sess[0],B_sess[1]
latest_start = max(A_start, B_start)
earliest_end = min(A_end, B_end)
if latest_start <= earliest_end:
print(A_start,A_end,B_start,B_end)
return True
else: return False
session_list = [ [2,5], [3,6], [8,10],[9,10],[10,12], [9,20] ]
count=0
for i ,sess in enumerate(session_list):
if has_overlap(sess[0],sess[1],session_list[i+1:]):
count+=1
print(count)
def has_overlap(A_start, A_end,i,sessions,memo):
count=0
for j,B_sess in enumerate(sessions):
key=str(i)+":"+str(j)
key_r=str(j)+":"+str(i)
if key in memo or key_r in memo:
continue
if i!=j:
B_start, B_end =B_sess[0],B_sess[1]
latest_start = max(A_start, B_start)
earliest_end = min(A_end, B_end)
if latest_start < earliest_end:
print(A_start,A_end,B_start,B_end)
memo[key]=1
count+=1
return count,memo
def get_max_session(session_list):
max_count=0
memo={}
for i ,sess in enumerate(session_list):
c,memo=has_overlap(sess[0],sess[1],i,session_list,memo)
max_count+=c
return max_count
# session_list = [ [2,5], [3,6], [8,10],[10,12],[9,20] ]
session_list = [ [2,5], [3,6], [8,10],[9,12],[12,20] ]
print(get_max_session(session_list))
import numpy as np
def maxSessionCount(k:np.array):
maxSession=0
for j in range(0,len(k)):
a= k[j,0]<=k[:,1]
b= k[j,0]>=k[:,0]
idx=np.where(a & b)
maxSession=max(len(idx[0]),maxSession)
print (j,np.where(a & b), len (idx[0]),k[idx[0],])
print(maxSession)
k=np.array([(2,5),(3,6),(8,10),(10,12),(9,20)])
k2=np.array([(2,5),(3,6),(8,10),(9,12),(12,20)])
#no sorting necessary
maxSessionCount(k) # outputs 3
maxSessionCount(k2) # outputs 2
import nump as np
def maxSessionCount(k:np.array):
maxSession=0
for j in range(0,len(k)):
a= k[j,0]<=k[:,1]
b= k[j,0]>=k[:,0]
idx=np.where(a & b)
maxSession=max(len(idx[0]),maxSession)
print (j,np.where(a & b), len (idx[0]),k[idx[0],])
print(maxSession)
k=np.array([(2,5),(3,6),(8,10),(10,12),(9,20)])
k2=np.array([(2,5),(3,6),(8,10),(9,12),(12,20)])
maxSessionCount(k)
maxSessionCount(k2)
Here is even simpler solution but I wonder if numpy library is acceptable in programming interviews, as it avoids the need of looping.
k2=np.array([(2,5),(3,6),(8,10),(9,12),(12,20)])
condA=k2[:,0]<=k2[:,1,None] # pairwise comparison of start time with all end times
condB=k2[:,0]>=k2[:,0,None] # same as above but start time vs start times
finalCond=condA & condB
print(finalCond[0,])
max([ len(np.where(finalCond[j,])[0]) for j in range(0,len(k)) ] )
// const appointments = [
// [2,5],
// [3,6],
// [8,10],
// [10,12],
// [9,20]
// ];
const appointments = [
[2,5],
[3,6],
[8,10],
[9,12],
[12,20]
];
let timeTable = new Map();
for( let [start,end] of appointments){
while(start <= end ){
// console.log(start,1);
timeTable.set(start, (timeTable.get(start) || 0) + 1);
start++;
}
}
console.log(Array.from(timeTable.values()).sort((a,b)=>b-a)[0]);
// const appointments = [
// [2,5],
// [3,6],
// [8,10],
// [10,12],
// [9,20]
// ];
const appointments = [
[2,5],
[3,6],
[8,10],
[9,12],
[12,20]
];
let timeTable = new Map();
for( let [start,end] of appointments){
while(start <= end ){
// console.log(start,1);
timeTable.set(start, (timeTable.get(start) || 0) + 1);
start++;
}
}
console.log(Array.from(timeTable.values()).sort((a,b)=>b-a)[0]);
/*
Algo:
1. Sort with start time of the sessions .
2. Then merge all overlapped/concurrent sessions, count it and update max count,
4. return max_count .
*/
public static int findConcurrentSessions( int [][] sessions)
{
Arrays.sort(sessions,(a,b)->a[0]-b[0]);
List<int[]> out = new ArrayList<>();
int [] curr = sessions[0];
out.add(curr);
int max =0; //maximum number of concurrent sessions
int count =1 ;
for( int i= 1 ; i < sessions.length ; i++)
{
int [] next = sessions[i];
if( next[0] < curr[1]) //next start before end of curr, overlapped/concurrent,so merge .
{
//merge these two session and increment count ,
curr[1] = Math.max(curr[1],next[1]);
count++;
}else
{
max = Math.max(max,count);
count=1;
curr = next;
out.add(next);
}
}
max = Math.max(max,count); // after last session - update max .
return max;
}
public static void main(String[] args) {
int [][] input1 = { {2,5}, {3,6},{8,10},{10,12},{9,20}};
int [][] input2 = { {2,5}, {3,6},{8,10},{9,12},{12,20}};
System.out.println(Arrays.deepToString(input1));
int result = findConcurrentSessions(input1);
System.out.println(" concurrent sessions = " + result);
}
- LANorth July 06, 2019