vzyarko
BAN USER/*
* Assuming that a breakfast MUST consists of three items
* which makes Bread-Butter, Bread-Butter, Bread-Butter a valid breakfast = 3A
* let A = Bread-Butter, B = Pizza, C = Burger
* having enough days all reachable combinations (permutations) would be:
*
* AAA, BBB, CCC, perm (A, B,C), arrange: A in [BB], A in [CC], B in [AA], B in [CC], C in [AA], C in [BB]
* 1 + 1 + 1 + 3! + 3 + 3 + 3 + 3 + 3 + 3 = 27
*
* if letting ABB == BAB == BBA then total = 15
*
*/
template <class T>
static std::ostream& operator << (std::ostream& stream, const std::pair<T, T>& pt){
return stream << "(" << pt.first << ", " << pt.second << ")";
}
template <class T>
class Square
{
public:
// costruct by a diagonal A-C; A, B, C, D clokwise
Square(const std::pair<T, T>& a, const std::pair<T, T>& c):
ptA(a),
ptB((a.first + a.second + c.first - c.second) / 2, (a.second + c.first + c.second - a.first) / 2),
ptC(c),
ptD((a.first - a.second + c.first + c.second) / 2, (a.first + a.second - c.first + c.second) / 2)
{}
const std::pair<T, T> ptA, ptB, ptC, ptD;
void print() const{
std::cout << "square: " << ptA << "," << ptB << "," << ptC << "," << ptD << "\n";
}
};
template <class T>
static void findSquaerInVector(const std::vector<std::pair<T, T> >& vec)
{
auto pair_hash = [](const pair<T, T>& p) {
return hash<decltype(p.first)>()(p.first) * 9315 + hash<decltype(p.second)>()(p.second);
};
std::unordered_set <std::pair<T, T>, decltype(pair_hash) > ptHash (10, pair_hash);
for (const auto& pt : vec){
ptHash.insert(pt);
}
for (int i = 0; i < vec.size(); ++i)
{
for (int j = i + 1; j < vec.size(); ++j)
{
Square<T> sq(vec[i], vec[j]);
// check for corresponding diagonal
if (ptHash.find(sq.ptB) != ptHash.end()
&& ptHash.find(sq.ptD) != ptHash.end())
{
sq.print();
return;
}
}
}
}
public class LazyBartender {
static private final java.util.HashMap<String, DrinkCustomerBase> drinksCustomerBase =new java.util.HashMap<>();
static private final Customer customers[] = {
new Customer("C1", new String[] { "n3", "n7", "n5", "n2", "n9" }),
new Customer("C2", new String[] { "n5" }),
new Customer("C3", new String[] { "n2", "n3" }),
new Customer("C4", new String[] { "n4" }),
new Customer("C5", new String[] { "n3", "n4", "n5", "n7" }) };
/*
* Helper class Customer
*/
public static class Customer {
public final String name;
public final java.util.HashSet<String> drinks = new java.util.HashSet<String>();
Customer(String name, String[] drinks) {
this.name = name;
this.drinks.addAll(java.util.Arrays.asList(drinks) );
for (String d:drinks) {
DrinkCustomerBase dc = drinksCustomerBase.get(d);
if (dc == null){
dc = new DrinkCustomerBase(d);
drinksCustomerBase.put(d, dc);
}
dc.customers.add(this);
}
}
boolean hasDrink(String d) {
return drinks.contains(d);
}
}
/*
* Helper class DrinkCustomerBase: drink to customers relation
*/
public static class DrinkCustomerBase implements Comparable<DrinkCustomerBase> {
public final String drink;
public final java.util.HashSet<Customer> customers;
public DrinkCustomerBase(String drink) {
this.drink = drink;
this.customers = new java.util.HashSet<Customer> ();
}
// compare by customer base, greater base first
@Override
public int compareTo(DrinkCustomerBase dc) {
return dc.customers.size() - this.customers.size();
}
}
/*
* Brute-force combination n Choose k, k: 1..n, n: total number of unique drinks
*/
static boolean checkCustomers(String drinks[]) {
java.util.HashSet<Customer> customersSet = new java.util.HashSet<Customer>();
for (Customer c: customers) {
for (String d:drinks){
if (c.hasDrink(d)){
customersSet.add(c);
if (customersSet.size() == customers.length)
return true;
}
}
}
return false;
}
/*
* n choose k
*/
static boolean drinksFound = false;
static <T> void combinations(T arr[], T data[], int start, int end, int index, int r) {
if (index == r) {
if (!drinksFound && checkCustomers ((String[])data) ){
System.out.println(java.util.Arrays.asList(data));
drinksFound = true;
}
return;
}
for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
data[index] = arr[i];
combinations(arr, data, i + 1, end, index + 1, r);
}
}
/*
* BF. find first smallest set
*/
static void findDrinksBf () {
String[] uniquedrinks = drinksCustomerBase.keySet().toArray(new String[0]);
/*
* check combinations n:i
*/
for (int i = 1; i <= uniquedrinks.length; ++i){
String data[]=new String[i];
combinations(uniquedrinks, data, 0, uniquedrinks.length -1, 0, i);
if (drinksFound)
break;
}
}
/*
* Find good enough for the lazy
*/
static void findGoodDrinkSet() {
java.util.LinkedList<DrinkCustomerBase> drinkList = new java.util.LinkedList<>(drinksCustomerBase.values());
drinkList.sort(null); // sort using DrinkCustomerBase.compareTo
java.util.HashSet<Customer> customerBase = new java.util.HashSet<>();
java.util.HashSet<String> drinks = new java.util.HashSet<>();
for (DrinkCustomerBase dc : drinkList) {
for (Customer c : dc.customers) {
if (!customerBase.contains(c)) {
drinks.add(dc.drink);
customerBase.add(c);
}
}
}
System.out.println(drinks.toString());
}
public static void main(String[] arg) {
findGoodDrinkSet();
findDrinksBf();
}
}
DFS
public boolean findBranch(Node node, int sum) {
if (node.left == null && node.right == null){ // leaf
return node.data == sum;
}
return (node.left != null && findBranch(node.left, sum - node.data)) ||
(node.right != null && findBranch(node.right, sum - node.data));
}
public static void maxPeople() {
int A[] = { 1, 4 };
int B[] = { 3, 5 };
int C[] = { 2, 7 };
int D[] = { 5, 10 };
int Room[][] = { A, B, C, D };
int firstH =0, lastH = 0;
for (int Hrs[] : Room) {
System.out.printf("[%d - %d)\n", Hrs[0], Hrs[1]);
firstH = Math.min(firstH, Hrs[0]);
lastH = Math.max(lastH, Hrs[1]);
}
int nPeople = 0;
for (int i = firstH; i < lastH; ++i) {
int np = 0;
for (int Hrs[] : Room) {
if ( Hrs[0] <= i && Hrs[1] > i)
np++;
}
nPeople = Math.max(nPeople, np);
}
System.out.printf("max People: %d\n", nPeople);
}
public class BinTreeDistance {
private static class Node {
private int data;
Node left = null;
Node right = null;
public static class DataCount {
public int cnt = 0;
}
public Node (int level, DataCount dataCnt) {
if (level != 0) {
this.left = new Node(level - 1, dataCnt);
this.data = ++dataCnt.cnt;
this.right = new Node(level - 1, dataCnt);
}
else
this.data = ++dataCnt.cnt;
}
}
private Node tree = new Node(5, new Node.DataCount());
private int nodeDistance(Node root, int data) {
int x = -1;
if (root == null) {
return -1;
}
if (root.data == data || (x = nodeDistance(root.left, data)) > -1 || (x = nodeDistance(root.right, data)) > -1) {
return x + 1;
}
return -1;
}
private Node nodeLca(Node root, int left, int right) {
if (root == null) {
return null;
}
if (root.data == left || root.data == right)
return root;
Node lNode = nodeLca(root.left, left, right);
Node rNode = nodeLca(root.right, left, right);
if (lNode != null && rNode != null)
return root;
if (lNode != null)
return lNode;
if (rNode != null)
return rNode;
return null;
}
private int bstNodeDistance(Node root, int data) {
int x = -1;
if (root == null) {
return -1;
}
if (root.data == data)
return x +1;
if (root.data > data && (x = bstNodeDistance(root.left, data)) > -1){
return x + 1;
}
if (root.data < data && (x = bstNodeDistance(root.right, data)) > -1) {
return x + 1;
}
return -1;
}
private Node bstNodeLca(Node root, int left, int right) {
if (root == null) {
return null;
}
if (root.data > left && root.data > right)
return bstNodeLca(root.left, left, right);
if (root.data < left && root.data < right)
return bstNodeLca(root.right, left, right);
return root;
}
public static void main(String[] args) {
BinTreeDistance btd = new BinTreeDistance();
//btd.tree.printTree();
Node nLca = btd.bstNodeLca(btd.tree, 4, 45);
int ld = btd.bstNodeDistance(nLca, 4);
int rd = btd.bstNodeDistance(nLca, 45);
System.out.println();
System.out.println(ld + rd );
nLca = btd.nodeLca(btd.tree, 4, 45);
ld = btd.nodeDistance(nLca, 4);
rd = btd.nodeDistance(nLca, 45);
System.out.println(ld + rd );
}
}
#include <unordered_map>
#include <deque>
#include <thread>
#include <chrono>
struct Message
{
uint64_t timestamp;
int user_id, container_id, item_id;
bool success;
};
typedef std::shared_ptr<Message> MessagePtr;
typedef std::deque< MessagePtr > MessageQue_t;
typedef std::unordered_map<int, MessagePtr> UserHash_t;
typedef std::unordered_map<int, MessagePtr>::iterator UserHashIter_t;
MessageQue_t MessageQue;
uint64_t milliseconds_now();
void too_fast(MessagePtr oldMsg, MessagePtr newMsg) {}
/*
* Scan queue, assuming that messages are appended externally
*/
void FindShortIntervals()
{
using namespace std::chrono_literals;
while (true)
{
UserHash_t userMessages;
uint64_t ts = milliseconds_now() - 1000;
// scan queueu tail backwards
for (MessageQue_t::reverse_iterator iter(MessageQue.rbegin()); iter != MessageQue.rend(); ++iter)
{
// scan for messages added during last second only,
// considering prev messages already reported
if ((*iter)->timestamp < ts)
break;
UserHashIter_t userIt = userMessages.find((*iter)->user_id);
if (userIt == userMessages.end())
{ // new user
userMessages.insert(UserHash_t::value_type((*iter)->user_id, *iter) );
}
else
{
if (userIt->second->timestamp > (*iter)->timestamp - 1000)
{
too_fast(userIt->second, *iter);
userIt->second = *iter;
}
}
}
// sleep for next loop
std::this_thread::sleep_for(1000ms);
}
}
Since the tree B is exact copy of A the traversals A is repeatable in B. Thus a simple counter (node enumerator) will do the path. no need for string.
struct TreeNode {
std::vector<TreeNode> adjacentNodes;
};
struct TestNodeBase {
TestNodeBase(TreeNode* n, int p) : node(n), path(p) {}
TreeNode* node;
int path;
};
struct TestNode: TestNodeBase {
TestNode(TreeNode* n) : TestNodeBase(n, 1) {}
bool test(TreeNode* testNode) {
if (testNode == node)
return true;
path++;
return false;
}
};
struct TestPath : TestNodeBase {
TestPath(int p) : TestNodeBase(nullptr, p) {}
bool test(TreeNode* testNode) {
if (--path) {
return false;
}
node = testNode;
return true;
}
};
template <class T>
bool findPath(TreeNode& tree, T& test) {
if (test.test(&tree))
return true;
std::deque<TreeNode*> walkQue;
walkQue.push_back(&tree);
while (!walkQue.empty()) {
TreeNode* node = walkQue.front();
walkQue.pop_front();
for (int i = 0; i < node->adjacentNodes.size(); ++i) {
if (test.test( &(node->adjacentNodes[i]) )) {
return true;
}
walkQue.push_back(&(node->adjacentNodes[i]));
}
}
return false;
}
void createTree(TreeNode& root, int depth);
void FindNode() {
TreeNode root;
createTree(root, 5);
TreeNode& tn = root.adjacentNodes[1].adjacentNodes[2].adjacentNodes[0];
TestNode testn(&tn);
if (findPath(root, testn)) {
TestPath tp(testn.path);
if (findPath(root, tp)) {
TreeNode* pathN = tp.node;
std::cout << "found\n";
}
}
}
It's not clear if it's any two consecutive numbers or just any two random numbers.
in first case it's O(n) complexity - just a single scan.
in second brute force is C(n, 2) ~ n^2 but if we sort the string we just try last and last-1 elements.
P.S do not need the sort, just one scan for greatest and second greatest elements
std::vector<int> v;
std::mutex vecMtx;
float avg = 0;
const int nRequests = 100;
const int nThreads = 6;
// simulate GET, radom thread sleep
void HttpGet(const std::string& uri, int delay)
{
std::this_thread::sleep_for(std::chrono::milliseconds(delay));
std::lock_guard<std::mutex> lock(vecMtx);
v.push_back(delay);
avg += delay;
}
void worker(int iter)
{
std::random_device rd; //Will be used to obtain a seed for the random number engine
std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> dis(1, nRequests);
while (iter > 0)
{
iter--;
HttpGet("wiki", dis(gen));
}
}
void calcStats()
{
std::vector <std::thread> threads;
auto start = std::chrono::high_resolution_clock::now();
int work = nRequests;
int workChunk = work / nThreads;
while (work > 0)
{
if (workChunk > work)
workChunk = work;
threads.push_back(std::thread(worker, workChunk));
work -= workChunk;
}
for (size_t i = 0, j = threads.size(); i < j; ++ i)
{
threads[i].join();
}
auto end = std::chrono::high_resolution_clock::now();
avg /= nRequests;
std::vector<int> vr(v);
std::sort(vr.begin(), vr.end());
std::cout << "10th pr = " << vr[9] << "\n";
std::cout << "50th pr = " << vr[49] << "\n";
std::cout << "90th pr = " << vr[89] << "\n";
std::cout << "99th pr = " << vr[98] << "\n";
std::cout << "mean = " << avg << "\n";
float div = 0;
for (int i : v)
{
div += ((avg - i) * (avg - i));
}
std::cout << "std div = " << sqrt(div/nRequests) << "\n";
std::chrono::duration<double, std::milli> elapsed = end - start;
std::cout << "worked: " << elapsed.count() << " ms\n";
}
- vzyarko August 18, 2017