pavelp
BAN USERI had that question on FB interview. I had two alternative ideas on how to do it, and I did it using regular substring matching. The other idea was about splitting regex and matching nodes separately is below.
#include <assert.h>
#include <regex> // for testing
#include <string>
using std::vector;
using std::string;
struct rx_node
{
int count_min, count_max;
char c;
};
typedef vector<rx_node> regex_t;
static bool match(const regex_t& rx, int i, const string &s, int pos);
static bool match_next(const regex_t& rx, int i, const string &s, int pos)
{
i++;
pos++;
if (i < rx.size())
return match(rx, i, s, pos);
else
return pos == s.size();
}
static bool match(const regex_t& rx, int i, const string &s, int pos)
{
const rx_node &r = rx[i];
if (r.count_min==0 && match_next(rx, i, s, pos-1))
return true;
int pos_max = r.count_max==-1 ? s.size() : pos+r.count_max;
if (pos_max>s.size())
pos_max = s.size();
for (int count=1; pos<s.size(); ++pos, ++count)
{
if (r.c!='.' && s[pos]!=r.c)
return false;
if (count>=r.count_min && match_next(rx, i, s, pos))
return true;
}
return false;
}
void regex_compile(const string &rx, regex_t &r)
{
for (int i=0; i<rx.size(); ++i)
{
rx_node n = {1, 1, rx[i]};
if (i<rx.size()-1)
{
if (rx[i+1]=='*')
{
n.count_min = 0;
n.count_max = -1;
i++;
}
else if (rx[i+1]=='?')
{
n.count_min = 0;
n.count_max = 1;
i++;
}
}
r.push_back(n);
}
}
bool regex_match(const string &str, const string& rx)
{
regex_t r;
regex_compile(rx, r);
bool match = match_next(r, -1, str, -1);
assert(std::regex_match(str, std::regex(rx)) == match);
return match;
}
#include <list>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
struct employee
{
string name;
int value;
vector<employee> children;
void add_child(employee &child)
{
children.push_back(child);
}
employee(string name_, int value_) : name(name_), value(value_) {}
employee() {}
};
struct get_guests_res
{
get_guests_res() : calculated_value_0(0), calculated_value_1(0) {}
int calculated_value_0;
list<employee*> guests_0;
int calculated_value_1; // best calculated value for subordinates
list<employee*> guests_1; // subordinate guests
};
get_guests_res get_guests_(employee *node)
{
get_guests_res ret;
if (!node)
return ret;
for (unsigned i = 0; i < node->children.size(); ++i)
{
get_guests_res r = get_guests_(&node->children[i]);
if (r.calculated_value_0)
{
ret.guests_1.splice(ret.guests_1.end(), r.guests_0);
ret.calculated_value_1 += r.calculated_value_0;
ret.guests_0.splice(ret.guests_0.end(), r.guests_1);
ret.calculated_value_0 += r.calculated_value_1;
}
else
{
list<employee*> guests_1 = r.guests_1;
ret.guests_1.splice(ret.guests_1.end(), r.guests_1);
ret.calculated_value_1 += r.calculated_value_1;
ret.guests_0.splice(ret.guests_0.end(), guests_1);
ret.calculated_value_0 += r.calculated_value_1;
}
}
if (node->value > 0 && ret.calculated_value_0 + node->value > ret.calculated_value_1)
{
ret.guests_0.push_back(node);
ret.calculated_value_0 += node->value;
}
else
{
ret.calculated_value_0 = 0; // parent one level up will skip two levels
}
return ret;
}
list<employee*> get_guests(employee &node)
{
get_guests_res r = get_guests_(&node);
return r.calculated_value_0 > 0 ? r.guests_0 : r.guests_1;
}
void main()
{
// init test data with values from cspat.googlecode.com/svn/trunk/Course/505%20Algorithm/HW/hw3/hwk-3-solution-archer.pdf
// President
employee top("BigShot", 5);
// Vice Presidents
top.add_child(employee("VP-1", 3));
top.add_child(employee("VP-2", 12));
top.add_child(employee("VP-3", 20));
// Middle Management
top.children[0].add_child(employee("MM-1", 6));
top.children[0].add_child(employee("MM-2", 3));
top.children[1].add_child(employee("MM-3", 7));
top.children[1].add_child(employee("MM-4", 9));
top.children[1].add_child(employee("MM-5", 8));
top.children[1].add_child(employee("MM-6", 11));
top.children[2].add_child(employee("MM-7", 4));
// Peons
top.children[0].children[1].add_child(employee("GTC-1", 28));
top.children[1].children[2].add_child(employee("Peon-1", 1));
top.children[1].children[2].add_child(employee("PG-1", 45));
list<employee*> invited = get_guests(top);
for (auto it = invited.begin(); it != invited.end(); ++it)
{
cout << (*it)->name << " is invited" << endl;
}
}
#include <algorithm>
int sorted_to_unique_std(int *data, int sz)
{
return std::unique(data, data+sz) - data - 1;
}
//same algorithm implemented manually
int sorted_to_unique(int *data, int sz)
{
if (!data || sz < 1)
return -1;
int x = data[0], offset, pos;
for (offset = 1; offset<sz && data[offset]>x; ++offset)
x = data[offset];
offset++;
for (pos = offset - 1; offset < sz; ++offset)
{
if (x != data[offset])
{
x = data[offset];
data[pos++] = x;
}
}
return pos - 1;
}
void main()
{
int data[] = {3, 3, 4, 5, 5, 6, 7, 7, 7};
int ret = sorted_to_unique_std(data, 9);
assert(ret == sorted_to_unique(data, 9));
printf("ret: %d [", ret);
for (int i=0; i<=ret; ++i)
printf("%d ", data[i]);
printf("]\n");
}
#include <limits>
struct bt_node
{
int value;
bt_node *left, *right;
};
static bool check_bst_left(bt_node *bt, int parent_value, int lbound, int rbound);
static bool check_bst_right(bt_node *bt, int parent_value, int lbound, int rbound);
bool check_bst(bt_node *bt, bt_node *parent)
{
return check_bst_left(bt->left, bt->value, std::numeric_limits<int>::min(), bt->value)
&& check_bst_right(bt->right, bt->value, bt->value, std::numeric_limits<int>::max());
}
static bool check_bst_left(bt_node *bt, int parent_value, int lbound, int rbound)
{
if (!bt)
return true;
return bt->value >= lbound && bt->value <= parent_value
&& check_bst_left(bt->left, bt->value, lbound, bt->value)
&& check_bst_right(bt->right, bt->value, bt->value, rbound);
}
static bool check_bst_right(bt_node *bt, int parent_value, int lbound, int rbound)
{
if (!bt)
return true;
return bt->value >= parent_value && bt->value <= rbound
&& check_bst_left(bt->left, bt->value, lbound, bt->value)
&& check_bst_right(bt->right, bt->value, bt->value, rbound);
}
// Something.h
#include <mutex>
class Something
{
public:
static Something *singleton()
{
if (!val)
std::call_once(val_flag, singleton_once);
return val;
}
private:
Something();
static Something *val;
static std::once_flag val_flag;
static void singleton_once()
{
static Something ret;
val = &ret;
}
};
//Something.cpp
Something *Something::val = NULL;
std::once_flag Something::val_flag;
Also, to add up, according to C++11 static declarations are thread safe, no need for call_once there... and call_once is C++11 feature :)
- pavelp May 03, 2016c++ solution of get_all_possible_paths function
#include <iostream>
#include <string>
#include <list>
// use '-', '\', and '|' chars to indicate direction.
std::list<std::string> get_all_possible_paths(const int *data, int W, int H);
using namespace std;
void get_all_possible_paths_aux(const int *data, int W, int H, list<string> &ret, int x, int y, char *path)
{
if (y > 0 && data[y*W+x-W])
path[-1] = '|', get_all_possible_paths_aux(data, W, H, ret, x, y-1, path-1);
if (y > 0 && x > 0 && data[y*W+x-W-1])
path[-1] = '\\', get_all_possible_paths_aux(data, W, H, ret, x-1, y-1, path-1);
if (x > 0 && data[y*W+x-1])
path[-1] = '-', get_all_possible_paths_aux(data, W, H, ret, x-1, y, path-1);
if (x==y && x==0)
ret.push_back(path);
}
list<string> get_all_possible_paths(const int *data, int W, int H)
{
int max_path_len = W+H-2;
char *tmp = new char[max_path_len+1];
char *path = tmp+max_path_len;
*path = '\0';
list<string> ret;
get_all_possible_paths_aux(data, W, H, ret, W-1, H-1, path);
delete[] tmp;
return ret;
}
void main()
{
int m0[] = {1,1,1, 1,1,1, 1,1,1};
int m1[] = {1,1,1, 0,0,1, 0,0,1};
list<string> p0 = get_all_possible_paths(m0, 3, 3);
list<string> p1 = get_all_possible_paths(m1, 3, 3);
cout << "available paths: " << p0.size() << endl;
for (auto it=p0.begin(); it!=p0.end(); ++it)
cout << "\t" << *it << "\n";
cout << "\navailable paths: " << p1.size() << endl;
for (auto it=p1.begin(); it!=p1.end(); ++it)
cout << "\t" << *it << "\n";
}
binary search from top-left to bottom-right to find 1, it will be located at X, where 0<=X<N. At this point you have X+X zeros, plus you need to recursively check right-top and top-bottom sections from X for extra zeros using similar technique. For right-top do binary search along top row to find 1, it will be located at Y, where X<=Y<N. So far with log n you will know how many 1s there in the right-top section: X*(N-Y). Then, recursively check rectangle bounded by X,0 and Y,X where left-bottom and right-top corners have zeros. Not sure though if the extra recursion increases log n complexity though.
- pavelp June 28, 2016