Untitled
py
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