Flipkart Interview Question
SDE-2sCountry: India
Interview Type: Phone Interview
#include <bits/stdc++.h>
#define M 25
using namespace std;
int tree[4*M+1][2];
int timein[25];
int timeout[25];
struct node
{
int login,logout;
};
void build(int node ,int start,int end)
{
if(start==end)
{
tree[node][0] += timein[start];
tree[node][1] += timeout[start];
}
else{
int mid = (start+end)/2;
build(2*node,start,mid);
build(2*node+1,mid+1,end);
tree[node][0] = tree[2*node][0]+tree[2*node+1][0];
tree[node][1] = tree[2*node][1]+tree[2*node+1][1];
}
}
struct node *query(int node,int start,int end,int l,int r)
{
struct node *p1,*p2,*ans;
ans = (struct node *)malloc(sizeof(struct node));
if(r<start || end<l || start>end)
{
ans->login = 0;
ans->logout = 0;
return ans;
}
if(l<=start && end<=r)
{
ans->login = tree[node][0];
ans->logout = tree[node][1];
return ans;
}
int mid = (start+end)/2;
p1 = query(node*2, start, mid, l, r);
p2 = query(node*2+1, mid + 1, end, l, r);
ans->login = p1->login + p2->login;
ans->logout = p1->logout + p2->logout;
return ans;
}
int main()
{
int i,n,login,logout;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&login,&logout);
timein[login]++;
timeout[logout]++;
}
build(1,0,24);
int q;
struct node *ans;
scanf("%d",&q);
while(q--){
int l,r;
scanf("%d%d",&l,&r);
ans = query(1,0,24,l,r);
printf("Total No. of Users LoggedIn=>%d & Loggedout=>%d in b/w [%d,%d]\n",ans->login,ans->logout,l,r);
}
return 0;
}
I would use a red-black tree the key being the login time, then write an additional function rangeQuery which collects the users. Red black tree because it is balanced and therefore faster. In the rangeQuery function we keep adding till we hit the upper bound, but we have to traverse a part of the left tree as well if the root is greater than the lower bound.
- JimmyMVP February 27, 2016