Alex
BAN USER#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Connection {
public:
Connection(int from, int to)
{
from_ = from;
to_ = to;
}
int from_, to_;
};
string Topology(vector<Connection> const &a)
{
unordered_map<int, int> nodes;
for (auto c : a) {
if (++nodes[c.from_] > 2 ||
++nodes[c.to_] > 2)
{
return "star";
}
}
if (a.size() == nodes.size() - 1) {
return "bus";
}
if (a.size() == nodes.size()) {
return "ring";
}
return "something else";
}
int main()
{
cout << Topology({Connection(1, 2), Connection(2, 3)}) << "\n";
cout << Topology({Connection(1, 2), Connection(2, 3), Connection(3, 1)}) << "\n";
cout << Topology({Connection(2, 1), Connection(3, 1), Connection(4, 1), Connection(5, 1)}) << "\n";
return 0;
}
To make it efficient, we can maintain Interval Search Tree.
For purposes of an interview, we can keep a list of sorted, not overlapping intervals. For each interval coming from the stream, we calculate how much of new coverage the interval brings, and then, we apply the new coverage to the existing intervals.
This can be improved by applying a binary search for finding overlapping intervals, and/or skip list/linked list for keeping the running list of intervals short.
#include <iostream>
#include <vector>
using namespace std;
class Interval {
public:
Interval(int start, int end)
{
start_ = start;
end_ = end;
}
int start_, end_;
};
int NewCoverage(vector<Interval> &a, Interval const &in)
{
int new_coverage = 0;
int i = 0;
for (; i < a.size() && a[i].start_ < in.end_; ++i) {
if (in.start_ < a[i].start_ &&
in.end_ > a[i].start_)
{
int delta = (i > 0 && a[i - 1].end_ > in.start_)
? a[i].start_ - a[i - 1].end_
: a[i].start_ - in.start_;
new_coverage += delta;
a[i].start_ -= delta;
}
if (in.end_ > a[i].end_ &&
in.start_ < a[i].end_)
{
int delta = (i + 1 < a.size() && a[i + 1].start_ < in.end_)
? a[i + 1].start_ - a[i].end_
: in.end_ - a[i].end_;
new_coverage += delta;
a[i].end_ += delta;
}
}
if (new_coverage == 0) {
new_coverage = in.end_ - in.start_;
a.insert(a.begin() + i, in);
}
return new_coverage;
}
int main(int argvc, char const **argv)
{
vector<Interval> stream({Interval(1, 2), Interval(4, 6), Interval(5, 7), Interval(3, 5), Interval(9, 11)});
vector<Interval> a;
int covered = 0;
for (auto in : stream) {
covered += NewCoverage(a, in);
cout << covered << ": ";
for (auto el : a) {
cout << el.start_ << "-" << el.end_ << ", ";
}
cout << "\n";
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int Find(vector<int> const &a, int v, int l, int r)
{
if (l < 0 ||
r < 0 ||
l >= a.size() ||
r >= a.size() ||
l > r)
{
return -1;
}
int m = (l + r) / 2;
if (a[m] == v) {
return m;
}
if (a[m] < a[l]) {
if (a[m] < v &&
a[r] >= v)
{
return Find(a, v, m + 1, r);
} else {
return Find(a, v, l, m - 1);
}
} else if (a[m] > a[l]) {
if (a[m] > v &&
a[l] <= v)
{
return Find(a, v, l, m - 1);
} else {
return Find(a, v, m + 1, r);
}
} else {
int idx = Find(a, v, l, m - 1);
if (idx == -1) {
idx = Find(a, v, m + 1, r);
}
return idx;
}
}
int main(int argvc, char const **argv)
{
vector<int> a = {4, 5, 6, 1, 2, 3};
cout << Find(a, 5, 0, a.size() - 1) << "\n";
return 0;
}
#include <vector>
#include <stack>
using namespace std;
class Node {
public:
Node()
{
pos_opening_ = pos_closing_ = -1;
}
int pos_opening_, pos_closing_;
vector<Node *> children_;
};
Node *Parse(string const &s)
{
stack<Node *> st;
st.push(new Node);
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '[') {
Node *n = new Node;
n->pos_opening_ = i;
st.top()->children_.push_back(n);
st.push(n);
} else if (s[i] == ']') {
st.top()->pos_closing_ = i;
st.pop();
}
}
return st.top();
}
void Print(Node const *n) {
cout << "[" << n->pos_opening_ << ", " << n->pos_closing_ << ", ";
if (!n->children_.empty()) {
for (int i = 0; i < n->children_.size(); ++i) {
if (i != 0) {
cout << ", ";
}
Print(n->children_[i]);
}
cout << "]";
} else {
cout << "null]";
}
}
int main(int argvc, char const **argv)
{
Node *root = Parse("[[]][]");
Print(root);
cout << "\n";
return 0;
}
If we are allowed to precompute, for each word of the dictionary we can find all possible subsequences and add them to a map subsequence => indexes of words having the subsequence. The query would extract subsequence out of the pattern, find all words having the subsequence, and check each such word agains the pattern.
If we don't allow to precompute, we can just iterate through the dictionary and check against the pattern (the code below).
Worst case O(n^2 * m^2) time and O(n * m) space.
bool Match(string const &s, string const &p, unordered_map<uint64_t, bool> &memo, int s_start = 0, int p_start = 0)
{
if (s_start < 0 ||
s_start > s.size() ||
p_start < 0 ||
p_start > p.size() ||
(s_start == s.size() ^ p_start == p.size()))
{
return false;
}
if (s_start == s.size() &&
p_start == p.size())
{
return true;
}
uint64_t memo_key = ((uint64_t)s_start << 32) | p_start;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
int k = s_start;
for (int i = p_start; i < p.size(); ++i) {
if (p[i] == '*') {
for (int j = k; j <= s.size(); ++j) {
if (Match(s, p, memo, j, i + 1)) {
memo[memo_key] = true;
return memo[memo_key];
}
}
memo[memo_key] = false;
return memo[memo_key];
} else {
if (k >= s.size() ||
(s[k] != p[i] && p[i] != '.'))
{
memo[memo_key] = false;
return memo[memo_key];
}
}
++k;
}
memo[memo_key] = (k == s.size());
return memo[memo_key];
}
Not sure why "abc.pqr.google.com" and "pqr.abc.google.com" are not valid as URLs.
As far as I understand, in the first part we are looking for the number of times a particular suffix is present in the list of strings. For this, a trie should work (the code below).
And in the second part, it looks like we should find how many times an arbitrary string appears as a substring int the list of strings. Like we can query 'qr.goog'. In this case, for each input string, we can find all of the substrings it can have, and add all of those substrings into hash table: substring => count.
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
Node() {
count_ = 0;
}
~Node()
{
for (auto child : children_) {
delete child.second;
}
}
Node *Add(char c)
{
Node *n = Get(c);
if (!n) {
children_[c] = n = new Node();
}
++n->count_;
return n;
}
Node *Get(char c) const
{
auto it = children_.find(c);
return (it != children_.end()) ? it->second : NULL;
}
int count_;
private:
unordered_map<char, Node *> children_;
};
class Trie {
public:
void Add(string const &s)
{
Node *n = &root_;
for (int i = s.size() - 1; i >= 0; --i) {
n = n->Add(s[i]);
}
}
int GetCount(string const &s) const
{
Node const *n = &root_;
for (int i = s.size() - 1; i >= 0; --i) {
n = n->Get(s[i]);
if (!n) {
return 0;
}
}
return n->count_;
}
private:
Node root_;
};
int main(int argvc, char const **argv)
{
Trie trie;
trie.Add("abc.pqr.google.com");
trie.Add("pqr.google.com");
trie.Add("pqr.google.net");
trie.Add("yahoo.com");
trie.Add("abc.yahoo.com");
cout << trie.GetCount("google.com") << "\n";
cout << trie.GetCount(".com") << "\n";
cout << trie.GetCount("pqr.google.com") << "\n";
return 0;
}
Using integer division. 2597419 valid subsets found.
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
using namespace std;
void GetSubsets(int max, int size, unordered_set<int> &subset, vector<unordered_set<int>> &subsets, int n = 1)
{
if (n < 0 ||
n > max + 1 ||
size <= 0 ||
subset.size() > size)
{
return;
}
if (subset.size() == size) {
subsets.push_back(subset);
return;
}
GetSubsets(max, size, subset, subsets, n + 1);
subset.insert(n);
GetSubsets(max, size, subset, subsets, n + 1);
subset.erase(n);
}
bool EquationIsTrue(unordered_set<int> &a, int val, vector<string> &equation, bool first_operand = true, int val_so_far = 0)
{
if (a.empty()) {
return val_so_far == val;
}
std::vector<int> keys(a.begin(), a.end());
for (int n : keys) {
a.erase(n);
if (first_operand) {
equation.push_back(to_string(n));
if (EquationIsTrue(a, val, equation, false, n)) {
return true;
}
equation.pop_back();
} else {
equation.push_back('+' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far + n)) {
return true;
}
equation.pop_back();
equation.push_back('-' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far - n)) {
return true;
}
equation.pop_back();
equation.push_back('*' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far * n)) {
return true;
}
equation.pop_back();
equation.push_back('/' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far / n)) {
return true;
}
equation.pop_back();
}
a.insert(n);
}
return false;
}
int main(int argvc, char const **argv)
{
unordered_set<int> subset;
vector<unordered_set<int>> subsets;
GetSubsets(52, 5, subset, subsets);
reverse(subsets.begin(), subsets.end());
vector<string> equation;
int val = 42;
for (auto s : subsets) {
equation.clear();
if (EquationIsTrue(s, val, equation)) {
for (int i = 0; i < equation.size(); ++i) {
cout << '(';
}
for (auto s : equation) {
cout << s << ')';
}
cout << "=" << val << "\n";
}
}
return 0;
}
ChrisK's solution, improved regarding space. O(m * n * k) time, O(m * n) space.
int Count(int m, int n, int16_t start_r, int16_t start_c, int k) {
int dp[m][n][2];
memset(dp, 0, sizeof(dp));
dp[start_r][start_c][0] = 1;
int current = 1;
int prev = 0;
for (int step = 1; step <= k; ++step) {
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
dp[r][c][current] = 0;
if (r - 1 >= 0) {
dp[r][c][current] += dp[r - 1][c][prev];
}
if (r + 1 < m) {
dp[r][c][current] += dp[r + 1][c][prev];
}
if (c - 1 >= 0) {
dp[r][c][current] += dp[r][c - 1][prev];
}
if (c + 1 < n) {
dp[r][c][current] += dp[r][c + 1][prev];
}
}
}
swap(prev, current);
}
return dp[0][0][prev];
}
O(m * n * k) time and space.
int Count(int m, int n, int16_t r, int16_t c, int k, unordered_map<uint64_t, int> &memo)
{
if (k < 0 ||
r < 0 ||
c < 0 ||
r >= m ||
c >= n)
{
return 0;
}
if (k == 0 &&
r == 0 &&
c == 0)
{
return 1;
}
uint64_t memo_key = ((uint64_t)r << 48) | ((uint64_t)c << 32) | k;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
memo[memo_key] = Count(m, n, r - 1, c, k - 1, memo) +
Count(m, n, r + 1, c, k - 1, memo) +
Count(m, n, r, c - 1, k - 1, memo) +
Count(m, n, r, c + 1, k - 1, memo);
return memo[memo_key];
}
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;
class Room;
class Door {
public:
Door(Room *to_room, int lock)
{
to_room_ = to_room;
lock_ = lock;
}
Room *to_room_;
int lock_;
};
class Room {
public:
Room(bool treasure, int key)
{
treasure_ = treasure;
key_ = treasure ? 0 : key;
}
~Room()
{
for (auto door : doors_) {
delete door;
}
}
void AddDoor(Room *to_room, int lock)
{
bool found = false;
for (auto door : doors_) {
if (door->to_room_ == to_room) {
found = true;
break;
}
}
if (!found &&
to_room != this)
{
doors_.push_back(new Door(to_room, lock));
to_room->AddDoor(this, lock);
}
}
vector<Door *> doors_;
bool treasure_;
int key_;
};
bool TreasureReachable(Room const *start_room)
{
unordered_map<int, Room const *> lock_rooms;
unordered_set<int> keys;
unordered_set<Room const *> seen;
stack<Room const *> st;
st.push(start_room);
while (!st.empty()) {
Room const *room = st.top();
st.pop();
if (room->treasure_) {
return true;
}
if (seen.find(room) == seen.end()) {
seen.insert(room);
if (room->key_) {
keys.insert(room->key_);
if (lock_rooms[room->key_]) {
seen.erase(lock_rooms[room->key_]);
st.push(lock_rooms[room->key_]);
lock_rooms.erase(room->key_);
}
}
for (auto door : room->doors_) {
if (door->lock_) {
if (keys.find(door->lock_) != keys.end()) {
keys.erase(door->lock_);
} else {
lock_rooms[door->lock_] = room;
continue;
}
}
st.push(door->to_room_);
}
}
}
return false;
}
int main() {
/*
|----------|--------|
| r1 | r2 |
| treasure | key 1 |
| | |
|----------|--------|
| | |
| r3 | r4 |
| | key 2 |
|----------|--------|
*/
Room r1(true, 0);
Room r2(false, 1);
Room r3(false, 0);
Room r4(false, 2);
r3.AddDoor(&r1, 1);
r3.AddDoor(&r4, 0);
r4.AddDoor(&r2, 2);
cout << TreasureReachable(&r1) << "\n";
cout << TreasureReachable(&r2) << "\n";
cout << TreasureReachable(&r3) << "\n";
cout << TreasureReachable(&r4) << "\n";
return 0;
}
In case the input includes number of distinct vowels:
uint64_t Count(int16_t n, int16_t k, int vowels_count, unordered_map<uint64_t, uint64_t> &memo, int prev_vowel = -1) {
if (k < 0 ||
n < 0)
{
return 0;
}
if (k == 0 &&
n == 0)
{
return 1;
}
uint64_t memo_key = ((uint64_t)n << 48) | ((uint64_t)k << 32) | prev_vowel;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
uint64_t count = Count(n - 1, k, vowels_count, memo, -1);
for (int vowel = 0; vowel < vowels_count; ++vowel) {
count += Count(n - 1, prev_vowel == vowel ? k - 1 : k, vowels_count, memo, vowel);
}
memo[memo_key] = count;
return memo[memo_key];
}
Count(..., true) is the branch when we use a vowel.
Count(..., false) is the branch when we don't use a vowel.
In the first case, depending on if the previous was a vowel, we decrement k or we don't.
I refactored it into this (though, functionally it's the same thing):
uint64_t count =
Count(n - 1, prev_is_vowel ? k - 1 : k, memo, true) +
Count(n - 1, k, memo, false);
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
class Node {
public:
Node()
{
left_ = right_ = NULL;
}
Node *left_, *right_;
};
bool AddToChildren(Node *n, Node *parent, unordered_set<Node *> &children)
{
if (n) {
if (n == parent ||
children.find(n) != children.end())
{
return false;
}
children.insert(n);
}
return true;
}
bool IsValidTree(vector<Node *> const &nodes)
{
unordered_set<Node *> children;
for (Node *n : nodes) {
if (n) {
if (!AddToChildren(n->left_, n, children) ||
!AddToChildren(n->right_, n, children))
{
return false;
}
}
}
if (children.size() != nodes.size() - 1) {
return false;
}
for (Node *n : nodes) {
children.erase(n);
}
return children.empty();
}
int main() {
/*
(1)
/ \
(2) (3)
/ \
(4) (5)
*/
Node n1, n2, n3, n4, n5;
n1.left_ = &n2;
n1.right_ = &n3;
n2.left_ = &n4;
n2.right_ = &n5;
cout << IsValidTree({&n1, &n2, &n3, &n4, &n5}) << "\n";
return 0;
}
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};
int Height(Node *n, int &max_distance)
{
int height = 0;
if (n) {
int l = Height(n->left_, max_distance);
int r = Height(n->right_, max_distance);
height = 1 + max(l, r);
max_distance = max(max_distance, 1 + l + r);
}
return height;
}
int main()
{
/*
(1)
/
(2)
/ \
(3) (4)
/ /
(6) (7)
/ \
(5) (8)
*/
Node n1(1);
Node n2(2);
Node n3(3);
Node n4(4);
Node n5(5);
Node n6(6);
Node n7(7);
Node n8(8);
n1.left_ = &n2;
n2.left_ = &n3;
n2.right_ = &n4;
n3.left_ = &n6;
n4.left_ = &n7;
n7.left_ = &n5;
n7.right_ = &n8;
int max_distance = 0;
Height(&n1, max_distance);
cout << max_distance << "\n";
return 0;
}
We can find the index in the array, where positive numbers start, and expand from the index to periphery.
vector<uint64_t> Square(vector<int32_t> const &a)
{
vector<uint64_t> out;
size_t i = 0;
while (i < a.size() &&
a[i] < 0)
{
++i;
}
size_t j = (i <= a.size()) ? i - 1 : a.size() - 1;
while (i < a.size() ||
j < a.size())
{
if (i >= a.size() ||
(j < a.size() && a[i] > - a[j]))
{
out.push_back((int64_t)a[j] * a[j]);
--j;
} else {
out.push_back((int64_t)a[i] * a[i]);
++i;
}
}
return out;
}
int Count(vector<int> const &a, unordered_map<uint64_t, int> &memo, int sum = 0, int idx = 0)
{
if (idx < 0 ||
idx >= a.size())
{
return 0;
}
uint64_t memo_key = ((uint64_t)sum << 32) | idx;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
int count = sum + a[idx] == 0 ? 1 : 0;
count += Count(a, memo, sum + a[idx], idx + 1);
count += Count(a, memo, sum, idx + 1);
memo[memo_key] = count;
return memo[memo_key];
}
My idea is first to remove all paired brackets. After that, we get something like ")))((". Then, to count how many stars and how many closing brackets are there to the left of each closing bracket. And the same logic backward pass for opening brackets.
bool Valid(string s)
{
stack<int> st;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
st.push(i);
} else if (s[i] == ')') {
if (!st.empty()) {
s[i] = ' ';
s[st.top()] = ' ';
st.pop();
}
}
}
int stars = 0;
int closings = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '*') {
++stars;
} else if (s[i] == ')') {
++closings;
}
if (closings > stars) {
return false;
}
}
stars = 0;
int openings = 0;
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] == '*') {
++stars;
} else if (s[i] == '(') {
++openings;
}
if (openings > stars) {
return false;
}
}
return true;
}
vector<int> AnagramIndexes(string const &s, string const &small_s)
{
vector<int> out;
if (!small_s.empty() &&
small_s.size() <= s.size())
{
vector<int> char_counts;
char_counts.resize(256, 0);
for (char c : small_s) {
++char_counts[c];
}
int diffs_count = small_s.size();
for (int i = 0; i < s.size(); ++i) {
--char_counts[s[i]];
diffs_count += char_counts[s[i]] < 0 ? 1 : -1;
if (i >= small_s.size()) {
++char_counts[s[i - small_s.size()]];
diffs_count += char_counts[s[i - small_s.size()]] > 0 ? 1 : -1;
}
if (diffs_count == 0) {
out.push_back(i - small_s.size() + 1);
}
}
}
return out;
}
vector<pair<int, int>> Intersection(vector<pair<int, int>> const &a, vector<pair<int, int>> const &b)
{
vector<pair<int, int>> out;
int i = 0;
int j = 0;
while (i < a.size() &&
j < b.size())
{
int s1 = a[i].first;
int e1 = a[i].second;
int s2 = b[j].first;
int e2 = b[j].second;
if (s1 >= s2 &&
s1 < e2)
{
out.push_back(pair<int, int>(s1, min(e1, e2)));
} else if (s2 >= s1 &&
s2 < e1)
{
out.push_back(pair<int, int>(s2, min(e1, e2)));
}
if (e1 < e2) {
++i;
} else {
++j;
}
}
return out;
}
bool ContainsAnagram(string const s, string const small_s)
{
if (!small_s.empty() &&
small_s.size() <= s.size())
{
vector<int> char_counts;
char_counts.resize(256, 0);
int diffs_count = small_s.size();
for (char c : small_s) {
++char_counts[c];
}
for (int i = 0; i < s.size(); ++i) {
if (char_counts[s[i]] > 0) {
--char_counts[s[i]];
--diffs_count;
} else {
--char_counts[s[i]];
++diffs_count;
}
if (i >= small_s.size()) {
char c = s[i - small_s.size()];
if (char_counts[c] < 0) {
++char_counts[c];
--diffs_count;
} else {
++char_counts[c];
++diffs_count;
}
}
if (diffs_count == 0) {
return true;
}
}
}
return false;
}
@PenChief. Thank you! I just didn't understand the task :) Updated solution:
void FindTriplet(vector<int> &array)
{
sort(array.begin(), array.end());
unordered_map<int, int> counts;
for (int n : array) {
++counts[n];
}
for (int i = 0; i < array.size(); ++i) {
int c = array[i];
int half = c >> 1;
for (int j = i - 1; j >= 0 && array[j] <= half; --j) {
int a = array[j];
int b = c - a;
if (counts[b] >= (a == half) ? 2 : 1) {
cout << a << " + " << b << " = " << c << "\n";
return;
}
}
}
}
O(N) time, O(N) space.
bool TripletExists(vector<int> const &array, int a, int b, int c)
{
unordered_map<int, int> seen;
int needed_ab_count = (a == b) ? 2 : 1;
int needed_c_count = 1;
if (a == b && b == c) {
needed_ab_count = needed_c_count = 3;
}
for (int n : array) {
++seen[n];
if (n == a ||
n == b)
{
if (seen[c - n] >= needed_ab_count &&
seen[c] >= needed_c_count)
{
return true;
}
}
if (n == c) {
if (seen[a] >= needed_ab_count &&
seen[b] >= needed_ab_count)
{
return true;
}
}
}
return false;
}
Since it's not a regular binary tree, but a binary search tree, and taking in account that parent 1 and 2 are not ancestors (meaning that the parents are located in two different subtrees), having 2 parents breaks the property of a binary search tree. So, we can just check if the child's value satisfies the property or not.
In the code below, I assume that in the BST, left child's value must be less, and the right child's value must be greater or equal to the value of the parent.
#include <iostream>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};
void FixBst(Node *n, int upper = numeric_limits<int>::max(), int lower = numeric_limits<int>::min(), Node *parent = NULL)
{
if (n) {
if (parent) {
if (n->val_ < lower ||
n->val_ >= upper)
{
cout << parent->val_ << "->" << n->val_ << "\n";
if (parent->left_ == n) {
parent->left_ = NULL;
} else {
parent->right_ = NULL;
}
}
}
FixBst(n->left_, min(upper, n->val_), lower, n);
FixBst(n->right_, upper, max(lower, n->val_), n);
}
}
int main()
{
/*
(7)
/ \
(5) (9)
\ /
(6)
*/
Node n1(7), n2(5), n3(9), n4(6);
n1.left_ = &n2;
n1.right_ = &n3;
n2.right_ = &n4;
n3.left_ = &n4;
FixBst(&n1);
return 0;
}
ChrisK's algorithm with improved readability (in my opinion):
bool ContainsAnagram(string const s, string const sub_s)
{
if (!sub_s.empty() &&
sub_s.size() <= s.size())
{
vector<int> char_counts;
char_counts.resize(256, 0);
int diffs_count = 0;
for (char c : sub_s) {
++char_counts[c];
++diffs_count;
}
for (int i = 0; i < s.size(); ++i) {
if (char_counts[s[i]] > 0) {
--char_counts[s[i]];
diffs_count--;
} else {
--char_counts[s[i]];
diffs_count++;
}
if (i >= sub_s.size()) {
if (char_counts[s[i - sub_s.size()]] < 0) {
++char_counts[s[i - sub_s.size()]];
diffs_count--;
} else {
++char_counts[s[i - sub_s.size()]];
diffs_count++;
}
}
if (diffs_count == 0) {
return true;
}
}
}
return false;
}
@PenChief. Cool! The solution looks like ChrisK's algorithm applied to my code structure :)
Though, only half of ChrisK's algorithm is applied. There should also be a pieces of code for cases when we add a char from the long string, and this char makes the difference count greater. A test case that will work wrong with your solution: "ab", "acb".
@ChrisK. That's correct. It's definitely not Rabin-Karp algorithm, it's something similar, in sense that it's using a hash and a sliding window.
Regarding time complexity, we are both right, because the complexity is really O(n*f), but since f is a constant, it's actually O(n).
@ lkjhgfdsa. You are welcome. To decide if any anagram of string sub_s is present in string s, we create a hash of sub_s, and then, we compare the hash with the hash of the sliding window (of size sub_s.size()) in string s. If the hashes are equal, then we've found a window in s which has the same characters (and the same amount of those characters) as in sub_s. The hash is basically an array, containing character counts (frequencies).
- Alex September 30, 2017We can solve this by something similar to Rabin-Karp algorithm. Since size of the alphabet is constant, worst case time complexity is O(N), where N is total number of characters in the input strings.
#include <vector>
#include <iostream>
#include <string>
using namespace std;
class Hash {
public:
Hash()
{
char_counts_.resize(256, 0);
}
void AddChar(char c)
{
++char_counts_[c];
}
void RemoveChar(char c)
{
--char_counts_[c];
}
bool operator==(Hash const &other)
{
for (int i = 0; i < char_counts_.size(); ++i) {
if (other.char_counts_[i] != char_counts_[i]) {
return false;
}
}
return true;
}
private:
vector<int> char_counts_;
};
bool ContainsAnagram(string const s, string const sub_s)
{
if (!sub_s.empty() &&
sub_s.size() <= s.size())
{
Hash sub_s_hash;
for (char c : sub_s) {
sub_s_hash.AddChar(c);
}
Hash s_window_hash;
for (int i = 0; i < s.size(); ++i) {
s_window_hash.AddChar(s[i]);
if (i >= sub_s.size()) {
s_window_hash.RemoveChar(s[i - sub_s.size()]);
}
if (s_window_hash == sub_s_hash) {
return true;
}
}
}
return false;
}
int AnagramCasesCount(vector<string> const &strings)
{
int count = 0;
for (int i = 0; i + 1 < strings.size(); ++i) {
if (ContainsAnagram(strings[i + 1], strings[i])) {
++count;
}
}
return count;
}
int main()
{
cout << AnagramCasesCount({"ab", "ab", "abc", "bca"}) << "\n";
cout << AnagramCasesCount({"ab","aqb"}) << "\n";
}
#include <vector>
#include <unordered_set>
#include <queue>
#include <iostream>
using namespace std;
class Iterator {
public:
Iterator(vector<vector<int>> const *a)
{
a_ = a;
idxes_.resize(a_->size(), 0);
for (int i = 0; i < a_->size(); ++i) {
Enqueue(i);
}
val_ = 0;
done_ = false;
GetNext();
}
int Value() const
{
return val_;
}
int operator++()
{
GetNext();
return val_;
}
bool Done() const
{
return done_;
}
private:
class PQElement {
public:
PQElement(int val, int idx)
{
val_ = val;
idx_ = idx;
}
bool operator>(PQElement const &other) const
{
return val_ > other.val_;
}
int val_, idx_;
};
void GetNext()
{
if (pq_.empty()) {
done_ = true;
return;
}
PQElement el = pq_.top();
pq_.pop();
pq_vals_.erase(el.val_);
val_ = el.val_;
while (idxes_[el.idx_] < (*a_)[el.idx_].size()) {
if (Enqueue(el.idx_)) {
break;
}
}
}
bool Enqueue(int i)
{
bool enqueued = false;
if (idxes_[i] < (*a_)[i].size()) {
if (pq_vals_.find((*a_)[i][idxes_[i]]) == pq_vals_.end()) {
pq_.push(PQElement((*a_)[i][idxes_[i]], i));
pq_vals_.insert((*a_)[i][idxes_[i]]);
enqueued = true;
}
idxes_[i]++;
}
return enqueued;
}
vector<vector<int>> const *a_;
vector<int> idxes_;
priority_queue<PQElement, vector<PQElement>, greater<PQElement>> pq_;
unordered_set<int> pq_vals_;
int val_;
bool done_;
};
int main()
{
vector<vector<int>> a = {
{1,2,3,4,7,9},
{3,5,6,8,10}
};
for (Iterator it = Iterator(&a); !it.Done(); ++it) {
cout << it.Value() << ",";
}
cout << "\n";
return 0;
}
@ChrisK. That's correct. It's worse than O(N * S). My mistake is that I counted the recursion tree nodes (there are really N * S nodes), but didn't take in account that each node doesn't do a constant time calculations. Each node iterates over multiple subsets.
- Alex September 29, 2017@ChrisK. Thank you for the tests! :)
I think time complexity of my approach is O(N * S), because the memo key is constructed as a pair of idx and sum. So, the max number of memo entries is N * S. If a memo entry already exists, the recursion doesn't go deeper.
Just for my sanity purpose, I wrote a random test (generating random vectors and sum) to compare my algorithm with brute force. No diffs found.
We can extract the text by traversing leaves from left to right (similar to inorder traversal).
This can be improved by extracting text piece by piece, and comparing the growing text strings. As soon as we find a mismatch we stop. The code below implements the idea.
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
class Node {
public:
Node(string const &tag, string const &text)
{
if (!tag.empty()) {
is_text_ = false;
tag_ = tag;
} else {
is_text_ = true;
text_ = text;
}
}
void AddChild(Node *n)
{
if (n) {
children_.push_back(n);
}
}
string tag_, text_;
bool is_text_;
vector<Node const *> children_;
};
class TextExtractor {
public:
TextExtractor(Node const *n)
{
st_.push(n);
}
string NextText()
{
while (!st_.empty()) {
Node const *n = st_.top();
st_.pop();
if (n) {
if (n->is_text_) {
return n->text_;
} else {
for (int i = n->children_.size() - 1; i >= 0; --i) {
st_.push(n->children_[i]);
}
}
}
}
return "";
}
bool Done() const
{
return st_.empty();
}
private:
stack<Node const *> st_;
};
bool SameText(Node const *n1, Node const *n2)
{
TextExtractor e1(n1), e2(n2);
string s1, s2;
while (!e1.Done() ||
!e2.Done())
{
if (!e1.Done() &&
(s1.size() < s2.size() || e2.Done()))
{
s1 += e1.NextText();
}
if (!e2.Done() &&
(s2.size() <= s1.size() || e1.Done()))
{
s2 += e2.NextText();
}
for (int i = 0; i < s1.size() && i < s2.size(); ++i) {
if (s1[i] != s2[i]) {
return false;
}
}
if (s1.size() < s2.size()) {
s2 = s2.substr(s1.size());
s1.clear();
} else {
s1 = s1.substr(s2.size());
s2.clear();
}
}
return s1 == s2;
}
int main()
{
//<html><p>hello</p></html>
Node n1("html", "");
Node n2("p", "");
Node n3("", "hello");
n1.AddChild(&n2);
n2.AddChild(&n3);
//<html><p><b>h</b>ello</p></html>
Node n10("html", "");
Node n11("p", "");
Node n12("b", "");
Node n13("", "h");
Node n14("", "ello");
n10.AddChild(&n11);
n11.AddChild(&n12);
n11.AddChild(&n14);
n12.AddChild(&n13);
cout << SameText(&n1, &n10) << "\n";
return 0;
}
@NoOne. That's correct. If we'd like to solve this by generating all subsets and checking if each subset has the needed sum, it's easy to do by using a bit set. But it's a brute force, and time complexity is O(N * 2 ^ N). A top down solution (not necessary recursive) with memoization, has time complexity O(N * S), where S is the needed sum, if we treat S as not a constant. If we have a limit for S, then, time is only O(N), which is a big difference with O(N * 2 ^ N).
- Alex September 28, 2017#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<vector<int>> SumSets(vector<int> const &a, int sum,
unordered_map<uint64_t, vector<vector<int>>> &memo, int idx = 0)
{
vector<vector<int>> sets;
if (sum == 0) {
sets.push_back(vector<int>());
return sets;
}
if (sum < 0 ||
idx >= a.size())
{
return sets;
}
uint64_t memo_key = ((uint64_t)idx << 32) | sum;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
vector<vector<int>> subsets = SumSets(a, sum - a[idx], memo, idx + 1);
for (auto const & subset : subsets) {
vector<int> set{a[idx]};
set.insert(set.end(), subset.begin(), subset.end());
sets.push_back(set);
}
subsets = SumSets(a, sum, memo, idx + 1);
sets.insert(sets.end(), subsets.begin(), subsets.end());
memo[memo_key] = sets;
return memo[memo_key];
}
int main()
{
vector<int> a = {1, 3, 4, 5, 6, 15};
unordered_map<uint64_t, vector<vector<int>>> memo;
vector<vector<int>> sets = SumSets(a, 15, memo);
for (auto const &set : sets) {
for (int n : set) {
cout << n << ", ";
}
cout << "\n";
}
return 0;
}
RepSWE
RepHire high professional child development center in Charlotte. Pal-A-Roo’s Child Development Center is a family-owned child care facility offering ...
Rep
RepIf you want to attract someone then astrologer kumar can help you. Astrologer kumar is specialized in offering kamdev vashikaran ...
- Alex November 02, 2017