Untitled

py
 avatar
unknown
plain_text
a year ago
34 kB
3
Indexable
* virtual functions can be re-implemented in derived class, derived classes can have different implementations
* abstract function prevent instantiation of that class
1. A,B
2. A
3. B (third question is missing)
4. A
5. A


number station
import collections

ids=[1,2,3,4,5,6,7,8,9,10,11]
msg='-hello-bye-'

ct=collections.defaultdict(str)
for i,j in zip(ids,msg):        
    if j=='-' and i in ct:        
        print(ct[i])
        ct=collections.defaultdict(str)      
    elif j=='-':
        ct[i+1]=''         
    else:
        ct[i+1]=ct[i]+j

# def process_sample():
#     pass

# def on_message_complete():
#     pass



from collections import defaultdict
from heapq import heappush, heappop

class Q1:
    def __init__(self, elephants, schedule):
        # map of our elephants' names to their sizes
        self.sizeMap = {elephant: size for elephant,size in elephants}
        # elephants of mine that are present at any given time
        self.mine = set()

        # we have to ignore our elephants entering and leaving
        # because we flush them independently, this keeps track
        self.ignoreMap = defaultdict(int)
        
        # other elephants that are present (max heap by size)
        self.others = []
        # elephants that have left but are still in the heap (lazy deletion)
        self.othersLeft = defaultdict(int) 

        # schedule sorted by time of arrival/leaving
        self.schedule = []
        for event in schedule:
            name, arrival, departure = event
            self.schedule.append((name, arrival, "arrive"))
            self.schedule.append((name, departure, "depart"))
            self.ignoreMap[(self.sizeMap[name], arrival, "arrival")] += 1
            self.ignoreMap[(self.sizeMap[name], departure, "departure")] += 1


        self.schedule.sort(key = lambda t: t[1])
        # schedule index
        self.si = 0

    def elephantEntered(self, time, height):
        key = (height, time, "arrival")
        if self.ignoreMap[key] > 0:
            self.ignoreMap[key] -= 1
        else:
            heappush(self.others, -height)

    def elephantLeft(self, time, height):
        key = (height, time, "departure")
        if self.ignoreMap[key] > 0:
            self.ignoreMap[key] -= 1
        else:
            self.othersLeft[height] += 1

    def getBiggestElephants(self, time):
        # flush my set of elephants to the ones that 
        # are currently in the room based on time
        while self.si < len(self.schedule) and self.schedule[self.si][1] <= time:
            name, _, type = self.schedule[self.si]
            if type == "arrive":
                self.mine.add((name, self.sizeMap[name]))
            else:
                self.mine.remove((name, self.sizeMap[name]))
            self.si += 1

        # flush the heap of other elephants to find the 
        # one who is the tallest and still present
        while self.others:
            cur = abs(self.others[0])
            if self.othersLeft[cur] > 0:
                heappop(self.others)
                self.othersLeft[cur] -= 1
            else:
                break

        tallestRival = abs(self.others[0])
        candidates = [name for name,height in self.mine if height >= tallestRival]
        candidates.sort()
        return candidates

sol = Q1([("marry", 300), ("rob", 250)], [("marry", 10, 15), ("rob", 13, 20)])
sol.elephantEntered(8, 200)
sol.elephantEntered(10, 310)
sol.elephantEntered(10, 300)
print(sol.getBiggestElephants(11))
sol.elephantEntered(13, 250)
sol.elephantLeft(13, 310)
print(sol.getBiggestElephants(13))
sol.elephantLeft(15, 300)
print(sol.getBiggestElephants(16))
sol.elephantLeft(16, 310)
sol.elephantLeft(20, 310)


from dataclasses import dataclass
import bisect

@dataclass
class Dividend:
    amount: int
    days: int


class FuturePricingEngine:
    # def __init__(self, stock_price: int, dividends: list[Dividend]):
    def __init__(self, stock_price, dividends):
        self.stock_price = stock_price
        self.dividends = dividends

    def update_dividend(self, dividend_id, updated_dividend):
        self.dividends[dividend_id - 1] = updated_dividend

    def calculate_future_price(self, days_to_future):
        res = self.stock_price
        for dividend in self.dividends:
            if days_to_future >= dividend.days:
                res -= dividend.amount
        return res                

if __name__ == "__main__":
    engine = FuturePricingEngine(1000, [Dividend(100, 10), Dividend(50,100)])
    print(engine.calculate_future_price(15))
    engine.update_dividend(2, Dividend(40,20))
    print(engine.calculate_future_price(15))
    print(engine.calculate_future_price(25))


# from heapq import heappop, heappush
from collections import deque
class LogServer:
    def __init__(self, m):
      self.m = m
      self.logs = deque() # [timestamp, log_id]

    def recordLog(self, logId, timestamp):
      if len(self.logs) and timestamp <= self.logs[-1][0]:
        return
      self.logs.append((timestamp, logId))
      while self.logs[0][0] <= self.logs[-1][0] - 3600:
        self.logs.popleft()


    def getLogs(self):
      # comma separated latest m log id past hour
      recent_logs = []
      cnt = self.m
      while cnt > 0:
        recent_logs.append(str(self.logs[-cnt][1]))
        cnt -= 1
      return ",".join(recent_logs)

    def getLogCount(self):
      return len(self.logs)


if __name__ == "__main__":
  server = LogServer(2)
  server.recordLog(1, 0)
  server.recordLog(7, 600)
  server.recordLog(3, 1200)
  server.recordLog(5, 1800)
  print(server.getLogs())
  print(server.getLogCount())
  server.recordLog(2, 2400)
  print(server.getLogs())
  print(server.getLogCount())

//
// Author --> https://leetcode.com/meta_fever/
//

class Solution
{
public:
    unordered_map<char, unordered_map<char, char>> adjList;
    char source, destination;
    long long maxWeight;

    vector<char> resPathNodes;

    enum ValidationErrors
    {
        E_OK = 0,
        E1 = 1, // Malformed input
        E2 = 2, // Logical input error
        E3 = 3  // No route found
    };
    ValidationErrors err = E_OK;

    string getErrorMessage(ValidationErrors err)
    {
        switch (err)
        {
        case E1: return "E1"; break;
        case E2: return "E2"; break;
        case E3: return "E3"; break;
        default: return "E_OK";
        }
    }

    bool isValidNode(char c)
    {
        return (c >= 'A' && c <= 'Z');
    }

    // E1 - Syntax Error                      - DONE  (ToDo: Weight limit check)
    // E2 - Duplicate Definitions             - DONE
    //    - Target node definitions not found - DONE
    //    - Disconnected Graphs               - DONE
    //    - Multiple Routes                   -       (ToDo)
    // E3 - No Route Found                    - DONE

    void findSingleShortestPath(string& allPairs, string& targetPair)
    {
        //cout << allPairs << endl;
        //cout << targetPair << endl;

        // Step-1: Parse input to create adjacency list
        parseInput(allPairs, targetPair);
        if (err != E_OK)
        {
            cout << getErrorMessage(err);
            return;
        }

        // Step-2: Find shortest paths from source to all nodes, for a weighted undirected graph - Dijkstra's algorithm
        findShortestPathsUtil();
        if (err != E_OK)
        {
            cout << getErrorMessage(err);
            return;
        }

        // Step-3: Print the path
        string resPath;
        for (char node : resPathNodes)
        {
            if (!resPath.empty())
                resPath += "->";
            resPath += node;
        }
        cout << resPath;
    }

    void findShortestPathsUtil()
    {
        unordered_map<char, unsigned int> distance; // <node, shortest_distance>
        unordered_map<char, char> parent; // <node, parent>
        unordered_set<char> visited;

        for (auto const& [k, v] : adjList)
            distance[k] = UINT_MAX;
        distance[source] = 0;

        parent[source] = source;

        // <weight, node>
        set<pair<int, char>> s; // to simiulate min heap
        s.insert({ 0, source });
        while (!s.empty())
        {
            auto x = *(s.begin());
            s.erase(x);
            visited.insert(x.second);
            for (auto it : adjList[x.second]) // iterate through neighbors of this node
            {
                if (visited.count(it.first) == 0 &&
                    distance[it.first] > distance[x.second] + it.second)
                {
                    s.erase({distance[it.first], it.first});
                    distance[it.first] = distance[x.second] + it.second;
                    parent[it.first] = x.second;
                    s.insert({ distance[it.first], it.first });
                }
            }
        }

        if (visited.size() < adjList.size()) // if there are disconnected nodes, we can't reach them.
            err = E2;
        if (distance[destination] > maxWeight)
            err = E3;

        copyNodesToResult(parent, destination);
    }

    void copyNodesToResult(unordered_map<char, char>& parent, char node)
    {
        if (parent.count(node) == 0)
        {
            // Could not find parent
            err = E3;
            return;
        }

        if (node == source)
        {
            resPathNodes.push_back(node);
            return;
        }
        copyNodesToResult(parent, parent[node]);
        resPathNodes.push_back(node);
    }

    void parseInput(string& allPairs, string& targetPair)
    {
        int M = allPairs.size();
        int N = targetPair.size();

        if (M == 0 || N == 0 ||
            allPairs[0] == ' ' || allPairs[M -1] == ' ' ||      // no leading/trailing spaces allowed
            targetPair[0] == ' ' || targetPair[N-1] == ' ')   // no leading/trailing spaces allowed
        {
            err =  E1;
            return;
        }

        bool duplicateEdgesFound = false; // We cannot immediately throw E2, 
                                          // because we may find a E1 later. So hold your horses until everything is parsed.

        // 1) Parse all pairs
        int i = 0;
        while (i < M)
        {
            // Get next edge data; Format: (A,B,<number>)
            char s, d;
            long int w = 0;
            if (i + 6 < M
                && allPairs[i] == '['
                && isValidNode(allPairs[i + 1])
                && allPairs[i + 2] == ','
                && isValidNode(allPairs[i + 3])
                && allPairs[i + 4] == ','
                && isdigit(allPairs[i + 5]))
            {
                s = allPairs[i + 1];
                d = allPairs[i + 3];

                if ((adjList.count(s) > 0 && adjList[s].count(d) > 0) ||
                    (adjList.count(d) > 0 && adjList[d].count(s) > 0))
                    duplicateEdgesFound = true;

                i = i + 5; // now we are at first index of weight
                string num;
                while (i < M && isdigit(allPairs[i]))  // ToDo: Add a check to limit the number to max of unsigned int.
                    num += allPairs[i++];
                
                if ((i < M - 1 && allPairs[i] == ']' && allPairs[i + 1] == ' ') || // Not the last edge-pair
                    (i == M - 1 && allPairs[i] == ']'))                            // The last edge pair
                {
                    w = stol(num);
                    adjList[s][d] = w;
                    adjList[d][s] = w;
                    i = i + 2; // go to next edge pair
                }
                else
                {
                    err = E1;
                    return;
                }
            }
            else
            {
                err = E1;
                return;
            }
        }

        // Parse Target Pair; Format:  A->D,<number>
        i = 0;
        if (i + 5 < N
            && isValidNode(targetPair[i])
            && targetPair[i + 1] == '-'
            && targetPair[i + 2] == '>'
            && isValidNode(targetPair[i + 3])
            && targetPair[i + 4] == ','
            && isdigit(targetPair[i + 5]))
        {
            source = targetPair[i];
            destination = targetPair[i + 3];
            i = i + 5; // now we are at first index of weight
            string num;
            while (i < N && isdigit(targetPair[i]))  // ToDo: Add a check to limit the number to max of unsigned int.
                num += targetPair[i++];

            if (i == N)
            {
                maxWeight = stol(num);
            }
            else
            {
                err = E1;
                return;
            }
        }
        else
        {
            err = E1;
            return;
        }

        if (adjList.count(source) == 0 || adjList.count(destination) == 0 || duplicateEdgesFound)
            err = E2;
    }
};

int main()
{
    Solution s;
    string allPairs, targetPair;
    try
    {        
        //getline(cin, allPairs);
        //getline(cin, targetPair);
        
        allPairs = "[A,B,3] [A,C,7] [C,D,2] [B,C,5]";          // A->C->D
        //allPairs = "[A,B,5] [A,C,2] [B,C,4] [B,D,6] [C,B,7]";  // E2
        //allPairs = "[A,B,3] [B,C,5] [C,D,2]";                     // A->B->C->D
        targetPair = "A->D,10";
        
        s.findSingleShortestPath(allPairs, targetPair);
    }
    catch (exception)
    {
        cout << s.getErrorMessage(Solution::E1);
    }
    
    system("pause");
}

def maxSubstringPartition(s, k):
    n = len(s)
    if k == 1:
        return n
        
    # pal[i][j] = true if s[i:j+1] is palindrome, 
    # nonexistent in the dictionary otherwise
    pal = [{} for _ in range(n)]
    
    for i in range(n):
        for si, sj in ((i, i), (i, i+1)):
            good = True
            while good and si >= 0 and sj < n:
                good &= s[si] == s[sj]
                pal[si][sj] = good
                si -= 1
                sj += 1
    dp = [0]
    for j in range(1, n + 1):
        # dp[j] = max number of divisions for s[:j]
        # where every division is size >= k.
        # we only count divisions that are "valid"
        this = dp[-1]
        for i in range(j - k + 1):
            if pal[i].get(j - 1, False):
                print(i, j - 1, dp[i])
                this = max(this, dp[i] + 1)
        dp.append(this)
    
    return dp[-1]

https://leetcode.com/discuss/interview-question/2768659/Optiver-OA-Q1
https://leetcode.com/discuss/interview-question/357982/Optiver-or-OA-or-Summer-SWE-Intern-2020
https://leetcode.com/discuss/interview-question/588375/Optiver-Amsterdam-or-OA-or-Graduate-Software-Engineer
https://leetcode.com/discuss/interview-question/1768013/Optiver-or-Online-Assessment-or-Traveling-the-Graphs
https://leetcode.com/discuss/interview-question/2730450/Optiver-Online-Assessment-2022
https://leetcode.com/discuss/interview-question/2523121/Optiver-new-grad-online-assesment
https://leetcode.com/discuss/interview-question/1953262/Optiver-OA-Travelling-the-Graphs
https://leetcode.com/discuss/interview-question/2768667/Optiver-OA-Q2
https://leetcode.com/discuss/interview-question/2007154/optiver-new-grad







// Given two dates calculate how many days are in between
// string valid binary search tree of errors hashmap
class Solution {
private:
    int countNodes(vector<int>& l, vector<int>& r, int root) {
        if (root == -1) return 0;
        return countNodes(l, r, l[root]) + countNodes(l, r, r[root]) + 1;
    }
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> indegree(n, 0);
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1 && indegree[leftChild[i]]++ == 1) return false; // indegree exceeds 1
            if (rightChild[i] != -1 && indegree[rightChild[i]]++ == 1) return false; 
        }
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                if (root == -1) {
                    root = i;
                } else {
                    return false;
                }
            }
        }
        if (root == -1) return false;
        return countNodes(leftChild, rightChild, root) == n;
    }
};

using namespace std;
    struct Node {
        char data;
        Node *parent;
        Node *left;
        Node *right;
        Node() : data('a'), parent(nullptr), left(nullptr), right(nullptr){}
    };

// Create an adjacency map, where we map each node to a list of nodes it has an edge to.
// a. If any of them have more than two children, stop building and return E1.
// If any of the nodes have two edges to the same node, return E2.
// Pick an arbitrary node to be the root. Do a simple DFS from this node to check if a cycle is present, if so, return E3.
// In your DFS, if you only visited a subset of the nodes, there must be two roots. Return E4.
//     (A,B) (B,D) (D,E) (A,C) (C,F) (E,G)
// Sample Output #02
// (A(B(D(E(G))))(C(F)))
void treeErrors(std::string pairs) {
  // Invalid input format, dups and more than two children as we build the tree.
  const std::string nodes = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  std::vector<std::string> input = split(pairs, " ");
  std::set<std::string> dup;
  char indegree[26] = {0};
  std::unordered_map<char, std::vector<char>> tree;
  bool duplicate = false, more_than_two_children = false;
  for (const std::string& i : input) {
    if (i.length() != 5 || i[0] != '(' || i[4] != ')' || i[2] != ',' ||
        nodes.find(i[1]) == std::string::npos || nodes.find(i[3]) == std::string::npos) {
      std::cout << "E1\n";
      return;
    }
    if (!dup.insert(i).second) duplicate = true;

    char parent = i[1], child = i[3];
    std::vector<char>& children = tree[parent];
    children.push_back(child);
    if (children.size() > 2) more_than_two_children = true;
    indegree[child - 'A']++;
  }
  if (duplicate) {
    std::cout << "E2\n";
    return;
  }
  if (more_than_two_children) {
    std::cout << "E3\n";
    return;
  }

  // Traverse the tree and check for multiple nodes and cycles.
  int visited = 0;
  std::queue<char> q;
  for (int i = 0; i < 26; i++) {
    if (indegree[i] == 0 && tree.count(i)) q.push(i);
  }

  if (q.size() > 1) {
    std::cout << "E4\n";
    return;
  }
  if (q.size() == 0) {
    std::cout << "E5\n";
    return;
  }
  while (!q.empty()) {
    for (int i = 0; i < q.size(); i++) {
      char node = q.front();
      std::vector<char>& children = tree[node];
      for (char c : children) {
        indegree[c - 'A']--;
        if (indegree[c - 'A'] == 0) {
          q.push(c);
          visited++;
        }
      }
    }
    q.pop();
  }
  // input contains all nodes except root. Same with visited, if no cycles.
  if (visited < input.size()) std::cout << "E5\n";
  return;
}

// Sample Input #02
// (A,B) (A,C) (B,D) (D,C)
// Sample Output #02
// E3
    public void treeErrors(String pairs) {
        
        // Invalid input format, dups and more than two children as we build the tree.
        String nodes = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        String[] input = pairs.split(" ", -1);
        Set<String> dup = new HashSet<>();
        char[] indegree = new char[26];
        Map<Character, List<Character>> tree = new HashMap<>();
        boolean duplicate = false, more_than_two_children = false;
        for (String i : input) {
            if (i.length() != 5 || i.charAt(0) != '(' || i.charAt(4) != ')' || 
                i.charAt(2) != ',' || nodes.indexOf(3) == -1 || nodes.indexOf(5) == -1) {
                System.out.println("E1");
                return;
            }
            if (!dup.add(i)) duplicate = true;
            
            char parent = i.charAt(1), child = i.charAt(3);
            List<Character> children = tree.getOrDefault(parent, new ArrayList<>());
            children.add(child);
            if (children.size() > 2) more_than_two_children = true;
            tree.put(parent, children);
            indegree[child - 'A']++;
        }
        if (duplicate) {
            System.out.println("E2");
            return;
        }
        if (more_than_two_children) {
            System.out.println("E3");
            return;
        }
        
        // Traverse the tree and check for multiple nodes and cycles.
        int visited = 0;
        Queue<Character> q = new LinkedList<>();
        for (int i = 0; i < 26; i++)
            if (indegree[i] == 0 && tree.containsKey((char)i))
                q.offer((char)i);
        
        if (q.size() > 1) {
            System.out.println("E4");
            return;
        }
        if (q.size() == 0) {
            System.out.println("E5");
            return;
        }
        while (!q.isEmpty()) {
            for (int i = 0; i < q.size(); i++) {
                char node = q.poll();
                List<Character> children = tree.get(node);
                for (char c : children) {
                    indegree[c - 'A']--;
                    if (indegree[c - 'A'] == 0) {
                        q.offer(c);
                        visited++;
                    }
                }
            }
        }
        // input contains all nodes except root. Same with visited, if no cycles.
        if (visited < input.length) System.out.println("E5");
        return;
    }
int main() {
    unordered_map<char, char> paired;
    string x;
    vector< string> v;
    
    getline(cin, x);
    string space = " ";
    //add a space to end of x;
    x.append(space);
    for (size_t i = 0; i < x.length(); i+=6){
        if (x[i] != '(' || !isupper(x[i+1]) || x[i+2] != ',' || !isupper(x[i+3]) || x[i+4] != ')' || !isspace(x[i+5])){
            cout << "E1";
            return 0;
        }
        //before pushback check for duplicate;
        if (!v.empty()){
            if (find(v.begin(), v.end(), x.substr(i,5)) != v.end() || v.back() == x.substr(i,5) ){
                cout << "E2";
                return 0;
             }
            }   
        v.push_back(x.substr(i,5));
    }
    //all good data
    
    node* root = new Node;
    for (size_t j = 0; j < v.size(); j++){
        char parent = v[j][1];
        char child = v[j][3];
        
        Node* node1 = new Node;

        node1->data = parent;
        Node* node2= new Node;
        node2->data = child;
        if (node1->left == nullptr){
            node1->left = node2;
            node2->parent = node1;
        }
        else if (node1->right == nullptr){
            node1->right = node2;
            node2->parent = node1;
        }
        else {
            cout << "E3";
            return 0;
        }
   
    }
    return 0;
}
// number stations
ids=[1,2,3,4,5,6,7,8,9,10,11]
msg='-hello-bye-'

ct=collections.defaultdict(str)
for i,j in zip(ids,msg):        
    if j=='-' and i in ct:        
        print(ct[i])
        ct=collections.defaultdict(str)      
    elif j=='-':
        ct[i+1]=''         
    else:
        ct[i+1]=ct[i]+j

// future pricing with linked list
// DaysInMonth(month, year) numOfDays()
class Solution {
public:
    bool leapyear(int y) {
        if (y % 400 == 0) return true;
        if (y % 100 == 0) return false;
        if (y % 4 == 0) return true;
        return false;
    }
    int days_in_month(int m, int y) {
        if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) return 31;
        if (m == 2) return leapyear(y) ? 29 : 28;
        return 30;
    }
    int days(string s) {
        int Y = stoi(s.substr(0, 4));
        int M = stoi(s.substr(5, 2));
        int D = stoi(s.substr(8, 2));
        int date = 0;
        for (int y = 1971; y < Y; y++) {
            date += leapyear(y) ? 366 : 365;
        }
        for (int m = 1; m < M; m++) {
            date += days_in_month(m, Y);
        }
        return date + D;
    }
    int daysBetweenDates(string date1, string date2) {
        return abs(days(date1) - days(date2));
    }
};

// smallest string expression of tree
// gas station distance, prices lowest price, gas tank 50 cost[n-1, n] = p[n-1] * d[n-1] or inf, cost[n-2, n] = min(cost[n-2, n], cost[n-2, n-1] + cost[n-1][n])

// Elephant exhibition
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

class Q1 {
public:
  Q1(vector<pair<string, int>> elephants, vector<tuple<string, int, string>> schedule) {
    // map of our elephants' names to their sizes
    sizeMap = unordered_map<string, int>();
    for (auto &elephant : elephants) {
      sizeMap[elephant.first] = elephant.second;
    }

    // elephants of mine that are present at any given time
    mine = set<pair<string, int>>();

    // we have to ignore our elephants entering and leaving
    // because we flush them independently, this keeps track
    ignoreMap = unordered_map<tuple<int, int, string>, int>();

    // other elephants that are present (max heap by size)
    others = priority_queue<int, vector<int>, greater<int>>();
    // elephants that have left but are still in the heap (lazy deletion)
    othersLeft = unordered_map<int, int>();

    // schedule sorted by time of arrival/leaving
    schedule.sort(
        [](const tuple<string, int, string> &a, const tuple<string, int, string> &b) {
          return get(a) < get(b);
        });
    si = 0;
  }

  void elephantEntered(int time, int height) {
    tuple<int, int, string> key = make_tuple(height, time, "arrival");
    if (ignoreMap[key] > 0) {
      ignoreMap[key]--;
    } else {
      heappush(others, -height);
    }
  }

  void elephantLeft(int time, int height) {
    tuple<int, int, string> key = make_tuple(height, time, "departure");
    if (ignoreMap[key] > 0) {
      ignoreMap[key]--;
    } else {
      othersLeft[height]++;
    }
  }

  vector<string> getBiggestElephants(int time) {
    // flush my set of elephants to the ones that 
    // are currently in the room based on time
    while (si < schedule.size() && get(schedule[si]) <= time) {
      string name = get(schedule[si]);
      int size = sizeMap[name];
      if (get(schedule[si]) == "arrive") {
        mine.insert(make_pair(name, size));
      } else {
        mine.erase(make_pair(name, size));
      }
      si++;
    }

    // flush the heap of other elephants to find the 
    // one who is the tallest and still present
    while (others.size()) {
      int cur = -others.top();
      if (othersLeft[cur] > 0) {
        heappop(others);
        othersLeft[cur]--;
      } else {
        break;
      }
    }

    int tallestRival = -others.top();
    vector<string> candidates;
    for (auto &mineElephant : mine) {
      if (mineElephant.second >= tallestRival) {
        candidates.push_back(mineElephant.first);
      }
    }
    sort(candidates.begin(), candidates.end());
    return candidates;
  }

private:
  unordered_map<string, int> sizeMap;
  set<pair<string, int>> mine;
  unordered_map<tuple<int, int, string>, int> ignoreMap;
  priority_queue<int, vector<int>, greater<int>> others;
  unordered_map<int, int> othersLeft;
  int si;
};
bool search2D(char *grid, int row, int col,
               string word, int R, int C)
{
    // If first character of word doesn't
    // match with given starting point in grid.
    if (*(grid+row*C+col) != word[0])
        return false;
 
    int len = word.length();
 
    // Search word in all 8 directions
    // starting from (row, col)
    for (int dir = 0; dir < 8; dir++) {
        // Initialize starting point
        // for current direction
        int k, rd = row + x[dir], cd = col + y[dir];
 
        // First character is already checked,
        // match remaining characters
        for (k = 1; k < len; k++) {
            // If out of bound break
            if (rd >= R || rd < 0 || cd >= C || cd < 0)
                break;
 
            // If not matched,  break
            if (*(grid+rd*C+cd) != word[k])
                break;
 
            // Moving in particular direction
            rd += x[dir], cd += y[dir];
        }
 
        // If all character matched, then value of k must
        // be equal to length of word
        if (k == len)
            return true;
    }
    return false;
}
 
// Searches given word in a given
// matrix in all 8 directions
void patternSearch(char *grid, string word,
                  int R, int C)
{
    // Consider every point as starting
    // point and search given word
    for (int row = 0; row < R; row++)
        for (int col = 0; col < C; col++)
            if (search2D(grid, row, col, word, R, C))
                cout << "pattern found at "
                     << row << ", "
                     << col << endl;
}








class BIT { // One-based indexing
    vector<int> bit;
public:
    BIT(int size=0) {
        bit.assign(size + 1, 0);
    }
    int getSum(int idx) { // Get sum in range [1..idx]
        int sum = 0;
        for (; idx > 0; idx -= idx & (-idx))
            sum += bit[idx];
        return sum;
    }
    void addValue(int idx, int val) {
        for (; idx < bit.size(); idx += idx & (-idx))
            bit[idx] += val;
    }
};
class NumArray {
    BIT bit;
    vector<int> nums;
public:
    NumArray(vector<int>& nums) {
        this->bit = BIT(nums.size());
        this->nums = nums;
        for (int i = 0; i < nums.size(); ++i)
            bit.addValue(i+1, nums[i]);
    }
    void update(int index, int val) {
        int diff = val - nums[index]; // get diff amount of `val` compared to current value
        bit.addValue(index + 1, diff); // add this `diff` amount at index `index+1` of BIT, plus 1 because in BIT it's 1-based indexing
        nums[index] = val; // update latest value of `nums[index]`
    }
    int sumRange(int left, int right) {
        return bit.getSum(right+1) - bit.getSum(left);
    }
};


from dataclasses import dataclass, replace
from collections import defaultdict
@dataclass
class TruckPosition:
  x: float
  y: float

@dataclass
class TruckPositionDelta:
  truck_id: int
  delta_x: float
  delta_y: float

class Subscriber:
  def __init__(self, server):
    self.server = server
    self.subscribers = defaultdict(list) # client id: [truck_id]
    self.updates = defaultdict(list) # truck id: [truckpositiondelta]

  def process_update(self, update):
    curr_x = self.server.current_pos[update.truck_id].x
    curr_y = self.server.current_pos[update.truck_id].y
    curr_x += update.delta_x
    curr_y += update.delta_y
    self.server.add_position(update.truck_id, TruckPosition(curr_x, curr_y))
    for i in self.subscribers[update.truck_id]:
      self.updates[i].append(update)

  def subscribe_to_truck(self, truck_id, client_id):
    self.subscribers[truck_id].append(client_id)
    return self.server.subscribe_to_truck(truck_id)

  def get_updates(self, client_id):
    v = list(self.updates[client_id])
    self.updates[client_id].clear()
    return v
    
class Server:
  def __init__(self):
    self.registered_trucks = set()
    self.current_pos = {}
    
  def subscribe_to_truck(self, truck_id):
    self.registered_trucks.add(truck_id)
    # return replace(self.current_pos[truck_id])
    if truck_id not in self.current_pos:
      self.current_pos[truck_id] = TruckPosition(0,0)
    return self.current_pos[truck_id]

  def add_position(self, truck_id, pos):
    self.current_pos[truck_id] = pos

if __name__=="__main__":
  num_trucks = 1
  server = Server()
  server.add_position(0, TruckPosition(2, 3))
  subscriber = Subscriber(server)
  subscriber.process_update(TruckPositionDelta(0, 1.5, 2.5))
  print(subscriber.subscribe_to_truck(0,0))
  subscriber.process_update(TruckPositionDelta(0, 1, 2))
  subscriber.process_update(TruckPositionDelta(0, -0.5, -0.5))
  print(subscriber.subscribe_to_truck(0,1))
  print(subscriber.get_updates(0))
  subscriber.process_update(TruckPositionDelta(0, 1, 1))
  print(subscriber.get_updates(1))


from collections import defaultdict
from heapq import heappush, heappop
class Trade:
  def __init__(self, trade_id, order_price, volume):
    self.trade_id = trade_id
    self.order_price = order_price
    self.volume = volume

class PnLCalculator:
  def __init__(self):
    self.prices = defaultdict()
    self.buys = defaultdict(list)
    self.sells = defaultdict(list)

  def process_trade(self, trade_id, instrument_id, buy_sell, order_price, volume):
    # trade has happened
    if buy_sell == "buy":
      self.buys[instrument_id].append(Trade(trade_id, order_price, volume))
    elif buy_sell == "sell":
      self.sells[instrument_id].append(Trade(trade_id, order_price, volume))

  def process_price_update(self, instrument_id, price):
    # true value of an instrument is updated
    self.prices[instrument_id] = price

  def output_worst_trade(self, instrument_id):
    # trade id of the worst trade for an instrument
    min_pnl = [float('inf'), -1]
    for trade in self.buys[instrument_id]:
      pnl = (self.prices[instrument_id] - trade.order_price) 
      if pnl < min_pnl[0]:
        min_pnl[0] = pnl
        min_pnl[1] = trade.trade_id
    for trade in self.sells[instrument_id]:
      pnl = ( trade.order_price - self.prices[instrument_id]) 
      if pnl < min_pnl[0]:
        min_pnl[0] = pnl
        min_pnl[1] = trade.trade_id
    if min_pnl[0] >= 0:
      print("NO BAD TRADES")
    else:
      print(min_pnl[1])


if __name__ == "__main__":
  pnl_calculator = PnLCalculator()
  pnl_calculator.process_price_update("meta", 80)
  pnl_calculator.process_price_update("appl", 120)
  pnl_calculator.process_trade(100, "appl", "sell", 90, 2)
  pnl_calculator.process_trade(10, "meta", "buy", 100, 4)
  pnl_calculator.output_worst_trade("meta") # 10
  pnl_calculator.output_worst_trade("appl") # 100

  pnl_calculator.process_price_update("goog", 100)
  pnl_calculator.process_trade(1, "goog", "buy", 100, 10)
  pnl_calculator.output_worst_trade("goog") # nbt
  pnl_calculator.process_trade(2, "goog", "sell", 102, 5)
  pnl_calculator.process_trade(3, "goog", "sell", 103, 5)
  pnl_calculator.process_price_update("goog", 98)
  pnl_calculator.output_worst_trade("goog") # 1
  pnl_calculator.process_trade(4, "goog", "buy", 101, 10)
  pnl_calculator.process_trade(5, "goog", "buy", 100, 10)
  pnl_calculator.output_worst_trade("goog") # 4