Flipkart Interview Question
SDE-2sCountry: India
Interview Type: In-Person
public class MaxCars {
static int[] startArr = { 1, 2, 3, 5 };
static int[] endArr = { 3, 3, 4, 6 };
//static int[] cars = { 2, 3, 6, 2 };
static int[] cars = { 2, 3, 4, 2 };
public static void main(String[] ar) {
System.out.println("Max Cars : " + getMaxCars(startArr.length));
}
private static int getMaxCars(int n) {
int max = cars[0];
int currentCount = max;
int i = 1, j = 0;
while (i < n && j < n) {
if (startArr[i] < endArr[j]) {
currentCount = currentCount + cars[i];
i++;
if (currentCount > max) {
max = currentCount;
}
} else {
currentCount = currentCount - cars[j];
j++;
}
}
return max;
}
}
public class MaxCars {
static int[] startArr = { 1, 2, 3, 5 };
static int[] endArr = { 3, 3, 4, 6 };
//static int[] cars = { 2, 3, 6, 2 };
static int[] cars = { 2, 3, 4, 2 };
public static void main(String[] ar) {
System.out.println("Max Cars : " + getMaxCars(startArr.length));
}
private static int getMaxCars(int n) {
int max = cars[0];
int currentCount = max;
int i = 1, j = 0;
while (i < n && j < n) {
if (startArr[i] < endArr[j]) {
currentCount = currentCount + cars[i];
i++;
if (currentCount > max) {
max = currentCount;
}
} else {
currentCount = currentCount - cars[j];
j++;
}
}
return max;
}
}
It can be solved like Kadane Algo
int mincars(int *startarr, int *endarr, int *ncarsarr, int nintervals) {
int totalcars = 0;
int dayhrs[24] = {0};
for (int i=0;i<nintervals, i++){
int start=startarr[i];
int end = endarr[i];
int ncars = ncarsarr[i];
for (int j=start;j<end;j++){
dayhrs[j]+=ncars;
if (dayhrs[j]>totalcars ) //at this hr carexceeds total need more
totalcars = dayhrs[j];
}
}
return totalcars;
}
//Car delivery
//Strategy:
//1. Prepare two lists of orders. One sorted by start time and
// another sorted by end time
//2. Iterate two list simultaneously
//3. If we encounter smaller start time, we increment # of cars
//4. If we encounter smaller end time, we decrement # of cars
//5. Take care of junctions where start and end time matches
//6. Keep track of maximum # of cars encountered so far
// Input:
//1 3 2
//2 3 3
//3 4 4
//5 6 2
//0 0 0-> exit
// Time complexity = time to sort the list [2*nlog(n)] + main computation loop (n) = O(nlogn)
// Space complexity = O(n)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct Order_t {
Order_t(int s, int e, int n):start(s),end(e),nCars(n){}
int start;
int end;
int nCars; // # of cars
};
typedef struct Order_t Order;
bool Comp1(Order a, Order b){
return a.start < b.start;
}
bool Comp2(Order a, Order b){
return a.end < b.end;
}
int main(){
freopen("input.txt", "r", stdin);
vector<Order> l1,l2;
while(true){
int start,end,n;
scanf("%d", &start);
scanf("%d", &end);
scanf("%d", &n);
if(start == 0) break;
l1.push_back(Order(start,end,n));
l2.push_back(Order(start,end,n));
}
sort(l1.begin(), l1.end(), Comp1); // sort by start time
sort(l2.begin(), l2.end(), Comp2); // sort by end time
int max_cars=0,n_cars=0;
for(int i=0,j=0; i<l1.size() && j<l2.size(); ){
if(l1[i].start < l2[j].end) {
n_cars += l1[i].nCars; // Increase number of cars
i++;
} else if (l1[i].start > l2[j].end) {
n_cars -= l2[j].nCars; // Decrease number of cars
j++;
} else { // l1[i].start == l2[j].end
int time = l1[i].start;
n_cars += l1[i].nCars;
n_cars -= l2[j].nCars;
i++;
j++;
if((i<l1.size() && l1[i].start == time) ||
(j <l2.size() && l2[j].end == time)) continue;
// We want to continue before adjusting max_cars
// since we want to consider all start and end points
// at a particular time
}
if(max_cars < n_cars) max_cars = n_cars; // Compute max cars
}
if(max_cars < n_cars) max_cars = n_cars; // re-compute max_cars if we missed last iteration
// of the above loop
cout << "Result: " << max_cars << endl;
return 0;
}
//Car delivery
//Strategy:
//1. Prepare two lists of orders. One sorted by start time and
// another sorted by end time
//2. Iterate two list simultaneously
//3. If we encounter smaller start time, we increment # of cars
//4. If we encounter smaller end time, we decrement # of cars
//5. Take care of junctions where start and end time matches
//6. Keep track of maximum # of cars encountered so far
// Input:
//1 3 2
//2 3 3
//3 4 4
//5 6 2
//0 0 0-> exit
// Time complexity = time to sort the list [2*nlog(n)] + main computation loop (n) = O(nlogn)
// Space complexity = O(n)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct Order_t {
Order_t(int s, int e, int n):start(s),end(e),nCars(n){}
int start;
int end;
int nCars; // # of cars
};
typedef struct Order_t Order;
bool Comp1(Order a, Order b){
return a.start < b.start;
}
bool Comp2(Order a, Order b){
return a.end < b.end;
}
int main(){
freopen("input.txt", "r", stdin);
vector<Order> l1,l2;
while(true){
int start,end,n;
scanf("%d", &start);
scanf("%d", &end);
scanf("%d", &n);
if(start == 0) break;
l1.push_back(Order(start,end,n));
l2.push_back(Order(start,end,n));
}
sort(l1.begin(), l1.end(), Comp1); // sort by start time
sort(l2.begin(), l2.end(), Comp2); // sort by end time
int max_cars=0,n_cars=0;
for(int i=0,j=0; i<l1.size() && j<l2.size(); ){
if(l1[i].start < l2[j].end) {
n_cars += l1[i].nCars; // Increase number of cars
i++;
} else if (l1[i].start > l2[j].end) {
n_cars -= l2[j].nCars; // Decrease number of cars
j++;
} else { // l1[i].start == l2[j].end
int time = l1[i].start;
n_cars += l1[i].nCars;
n_cars -= l2[j].nCars;
i++;
j++;
if((i<l1.size() && l1[i].start == time) ||
(j <l2.size() && l2[j].end == time)) continue;
// We want to continue before adjusting max_cars
// since we want to consider all start and end points
// at a particular time
}
if(max_cars < n_cars) max_cars = n_cars; // Compute max cars
}
if(max_cars < n_cars) max_cars = n_cars; // re-compute max_cars if we missed last iteration
// of the above loop
cout << "Result: " << max_cars << endl;
return 0;
}
// Another version
// Lease cars
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct TIME_t {
TIME_t(int hh, int mm, int c):h(hh), m(mm), cars(c){}
int h;
int m;
int cars; // +ve => cars used; -ve => cars given back
};
typedef struct TIME_t TIME;
bool operator<(const TIME& t1, const TIME& t2){
if(t1.h != t2.h) return t1.h < t2.h;
return t1.m < t2.m;
}
bool operator==(const TIME& t1, const TIME& t2){
if(t1.h != t2.h) return false;
if(t1.m != t2.m) return false;
return true;
}
int main() {
freopen("LeaseCarsInput.txt", "r", stdin);
vector<TIME> times;
int startH, endH, cars;
while(scanf("%d", &startH), startH != -1){
scanf("%d", &endH);
scanf("%d", &cars);
if(endH<startH){
cout << "Wrong Input";
return 0;
}
times.push_back(TIME(startH,0,cars));
times.push_back(TIME(endH,0,-cars));
}
if(!times.size()) return 0;
std::sort(times.begin(), times.end());
int totalCars=0;
int availableCars=0;
for(int i=0; i<times.size();){
int carsNeededNow = times[i].cars;
i++;
while(i<times.size() && times[i]==times[i-1]){
carsNeededNow += times[i].cars;
i++;
}
if(carsNeededNow <= availableCars){
availableCars -= carsNeededNow;
} else {
totalCars += carsNeededNow - availableCars;
}
}
cout << "Total Cars: " << totalCars << endl;
return 0;
}
// Test case
//Format: start_time end_time cars
// -1 => exit
1 3 2
2 3 3
3 4 4
5 6 2
-1
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<pair<int,int>>v;
for(int i=0;i<n;i++)
cin>>v[i].first>>v[i].second;
vector<int> cars(n);
for(int i=0;i<n;i++)
cin>>cars[i];
unordered_map<int,int> mp;
for(int i=0;i<n;i++)
{
mp[x.first]+=cars[i];
mp[x.second]-=cars[i];
}
int tot=0;
int maxi=0;
for(auto x:mp)
{
tot+=x.second;
maxi=max(maxi,tot);
}
cout<<maxi<<endl;
}
- AlgarveBeachBum January 14, 2016