PraTrick
BAN USER 1of 1 vote
AnswersGiven arrays for N (>= 2) users, each representing the IDs of hotels visited, find the common IDs of the hotels visited amongst the users.
 PraTrick in India
Input:
userA = { 2, 3, 1 }
userB = { 2, 5, 3 }
userC = { 7, 3, 1 }
Output:
{3}
Assumptions:
Arrays are unsorted.
Cases:
1) Each array consists of distinct hotel IDs
2) Each array may contain duplicate hotel IDs Report Duplicate  Flag  PURGE
Booking.com Software Engineer / Developer  1of 1 vote
AnswersProblem statement
 PraTrick in India
Given a set of hotels and its guests reviews, sort the hotels based on a list of words specified by a user. The criteria to sort the hotels should be how many times the words specified by the user is mentioned in the hotel reviews.
Input
The first line contains a spaceseparated set of words which we want to find mentions in the hotel reviews.
The second line contains one integer M, which is the number of reviews.
This is followed by M+M lines, which alternates an hotel ID and a review belonging to that hotel.
Output
A list of hotel IDs sorted, in descending order, by how many mentions they have of the words specified in the input. If the count is same, sort according to the hotel IDs. Report Duplicate  Flag  PURGE
Booking.com Software Engineer / Developer
/**
* [1,3],[2,6],[8,12],[10,18] => [1,6],[8,18]
* Definition for an interval.
**/
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
bool compare(Interval a, Interval b) {
return a.start < b.start;
}
vector<Interval> merge(vector<Interval> &A) {
vector<Interval> result;
vector<Interval>::iterator it;
sort(A.begin(), A.end(), compare);
if (A.empty()) {
return result;
}
else {
result.push_back(*A.begin());
for (it = (A.begin() + 1); it != A.end(); ++it) {
if ((*it).start > result.back().end)
result.push_back(*it);
else
result.back().end = max(result.back().end, (*it).end);
}
}
}

PraTrick
July 24, 2017 We can use Binary Search (Divide & Conquer) for the solution:
#include <bits/stdc++.h>
using namespace std;
bool is_possible(int A[], int size, int B, int curr_min) {
int students = 1, sum = 0;
for (int i = 0; i < size; i++) {
if (A[i] > curr_min)
return false;
if (sum + A[i] > curr_min) {
students++;
sum = A[i];
if (students > B)
return false;
}
else
sum = sum + A[i];
}
return true;
}
int toffees(int A[], int size, int B) {
long long sum = 0;
if(size < B)
return 1;
for(int i = 0; i < size; i++)
sum = sum + A[i];
long long start = 0, mid = 0, end = sum;
int result = INT_MAX;
while(start <= end) {
mid = (start + end) / 2;
if (is_possible(A, size, B, mid)) {
result = min(result, (int)mid);
end = mid  1;
}
else
start = mid + 1;
}
return result;
}
int main() {
int A[] = {12, 34, 67, 90};
int size = sizeof(A) / sizeof(A[0]);
cout << toffees(A, size, 2);
return 0;
}

PraTrick
July 18, 2017 #include <iostream>
#include <string.h>
using namespace std;
int count = 0;
int cache[10];
bool canPass(int arr[], int n, int pos, int v) {
count++;
if (pos >= n)
return true;
if ((v <= 0)  arr[pos] == 0)
return false;
if (cache[v] != 1)
return cache[pos];
return cache[v] = canPass(arr, n, (pos + v), v)  canPass(arr, n, (pos + (v  1)), (v  1)) 
canPass(arr, n, (pos + (v + 1)), (v + 1));
}
int main() {
int pass[] = {1,1,0,1,0,1,1,1,0,1};
int N = sizeof(pass) / sizeof(pass[0]);
memset(cache, 1, sizeof(cache));
cout << canPass(pass, (N  1), 0, 1);
cout << endl << count;
return 0;
}

PraTrick
July 08, 2017 Just exploring the idea...
1) Overlapping Intervals: Use Segment Tree or Interval Tree. Tree has to be developed using minimum interval time. It can also detect collisions.
2) NonOverlapping Intervals: Use a BST with start time of the meeting as the key (end time can is kept as a value). To detect collisions, for an input start time, check if the end time of the floor(start time) node is less than the input start time, and check if the start time of the ceil(start time) node is greater than the input end time.
Open Chat in New Window
@Sameer Oak The solution given by @Makarand is correct. He's building a min heap using the first (k + 1) elements. For the following input, the solution will give the correct output.
 PraTrick March 23, 20192 1 4 3
k = 1