Sollicitatievraag

Sollicitatiegesprek voor de functie Software Developer

-Amsterdam

Booking.com

Given the following list of objects {user, loginTime, logoutTime}. What is the maximum number of concurrent users logged in at the same time? Input: [ {user: A, login: 1, logout: 3}, {user: B, login: 3, logout: 4}, {user: C, login: 1, logout: 2}, {user: D, login: 123123123, logout: 987987987}, {user: E, login: 1, logout: 3} ] Output: 3

Antwoord

Antwoorden op sollicitatievragen

6 antwoorden

1

#include #include #include using namespace std; struct entry { char c; int login; int logout; bool operator entries; entry A('A', 1, 3); entries.insert(A); entry B('B', 3, 4); entries.insert(B); entry C('C', 1, 2); entries.insert(C); entry D('D', 123, 987); entries.insert(D); entry E('E', 1, 3); entries.insert(E); priority_queue logouts; int res = 0; for(auto it = entries.begin(); it != entries.end(); ++it) { if (!logouts.size() || it->login logout); if (res login >= -logouts.top()) { logouts.pop(); } logouts.push(-it->logout); if (res < logouts.size()) res = logouts.size(); } } cout << res << endl; return 0; }

C++ answer op

2

The code below is in javascript, but didn't test it. I believe it's complexity is O(n * log n) because of the sort, but there might be a better solution. let logins = []; let logouts = []; let max = 0; let current = 0; let j = 0, k = 0; for(let i=0; i

Anoniem op

1

Complexity is O(n*logn + 2n) . You can reduce it to O(nlogn +n ) by implemeting own quicksort during assigment. Overall its O(nlogn) time complexity logs = [(1,3), (3,4), (1,2), (111111,555555),(1,3)] sorted_logs = [] for elm in logs: sorted_logs.append((elm[0], 1)) sorted_logs.append((elm[1], -1)) sorted_logs.sort(key=lambda x: x[0]) ans = tmp = 0 for elm in sorted_logs: tmp += elm[1] if tmp > ans: ans = tmp print(ans)

Rashid op

0

My solution Ruby: arr.group_by { |k| k[:login] }.map{|k,v| [k, v.size]}.to_h.values.max

zazaoui op

0

import java.util.LinkedList; import java.util.Queue; public class MaximumNumberOfConcurrentUsers { public static void main(String[] args) { int[][] users = {{1,3}, {3,4}, {1,2}, {111111,555555},{1,3}}; quickSort(users, 0, users.length-1); int maxUsers = Integer.MIN_VALUE; Queue usersStack = new LinkedList(); usersStack.add(users[0]); while (!usersStack.isEmpty()) { for(int i=1;i usersStack.peek()[1]) { maxUsers = Math.max(maxUsers, usersStack.size()); usersStack.poll(); } usersStack.add(users[i]); } maxUsers= Math.max(maxUsers, usersStack.size()); break; } System.out.println(maxUsers); } static void quickSort(int [][]users, int start, int end) { if(!(end>start)) return; int pIndex = partitionArr(users, start, end); quickSort(users, start, pIndex-1); quickSort(users, pIndex+1, end); } static int partitionArr(int [][]users, int start, int end) { int pivot = users[end][0]; int pLogout=users[end][1]; int partition= start; for(int i=start; i

Mahmoud op

1

The problem is categorized as a finding the maximum overlap algorithm. I solved it with a for loop in a for loop, by comparing every object with each other and calculating the maximum numbers of intersections. The ideal solution would be to sort the login times in an array, and the logout times in a separate array, and merge them while increasing (when you take from login array) or decreasing (when you take from logout array) a variable and calculating its max.

Anoniem op

Voeg antwoorden of opmerkingen toe

Meld u aan of registreer u om hier een opmerking over te maken.