yura.gunko
BAN USERint findFirstUniqueIndex(const std::string &str)
{
std::unordered_map<char, int> hmap;
const int size = str.size();
for (int i = 0; i < size; ++i) // O(n)
{
if (hmap.find(str.at(i)) == hmap.end()){ // avg O(1) lookup
hmap[str.at(i)] = 1;
}
else{
hmap[str.at(i)]++;
}
}
for (int i = 0; i < size; ++i){ // O(n)
if (hmap[str.at(i)] == 1){
return i;
}
}
return -1;
}
TEST(String, FindFirstUnique_probe_a)
{
{
std::string str("abcdeadcb");
EXPECT_EQ(findFirstUniqueIndex<void>(str), 4);
}
{
std::string str("abcdabcd");
EXPECT_EQ(findFirstUniqueIndex<void>(str), -1);
}
}
Just try to solver this tasks by memory :)
#pragma once
#include <map>
#include <vector>
#include <utility>
#include <limits>
namespace junk
{
namespace vacation_selector
{
class VacationSelector
{
public:
VacationSelector(const std::vector<std::pair<char, int>> &vacations)
: m_idx(0)
, m_size(0)
, m_value(INT_MAX){
process(vacations);
}
void process(const std::vector<std::pair<char, int>> &vacations)
{
// to identify unique set
std::map<char, int> flags;
for (const auto &v : vacations){
flags[v.first] = 0;
}
// use slow & fast runner
size_t slow = 0;
size_t fast = 0;
const size_t v_size = vacations.size();
do
{
bool is_full_set = true;
for (const auto &f : flags) {
if (f.second == 0){
is_full_set = false;
break;
}
}
if (is_full_set)
{
int curr = 0;
for (const auto &f : flags) {
curr += f.second;
}
if (m_value > curr)
{
m_idx = slow;
m_size = fast - slow;
m_value = curr;
}
flags[vacations[slow].first] -= vacations[slow].second;
slow++;
}
else
{
if (fast >= vacations.size()) {
return; // skip no full sets left
}
flags[vacations[fast].first] += vacations[fast].second;
fast++;
}
} while (true);
}
int min_idx() const { return m_idx; }
int size() const { return m_size; }
int value() const { return m_value; }
private:
int m_idx;
int m_size;
int m_value;
};
}
}
TEST(Array, MinCompleteSetInArray_VacationSelector_probe_a)
{
{
VacationSelector vacation(
{ {'A', 1}, {'A', 1 }, {'B', 2}, {'B', 2}, {'C', 4} }
);
EXPECT_EQ(vacation.min_idx(), 1);
EXPECT_EQ(vacation.value(), 9);
EXPECT_EQ(vacation.size(), 4);
}
{
VacationSelector vacation(
{ { 'A', 3 },{ 'A', 2 },{ 'A', 1 },{ 'A', 2 },{ 'A', 4 } }
);
EXPECT_EQ(vacation.min_idx(), 2);
EXPECT_EQ(vacation.value(), 1);
EXPECT_EQ(vacation.size(), 1);
}
{
VacationSelector vacation(
{ { 'A', 3 },{ 'B', 2 },{ 'C', 5 },{ 'A', 1 },{ 'B', 1 },{ 'B', 2 },{ 'C', 1 } }
);
EXPECT_EQ(vacation.min_idx(), 3);
EXPECT_EQ(vacation.value(), 5);
EXPECT_EQ(vacation.size(), 4);
}
}
#pragma once
#include <map>
#include <stdlib.h>
#include <stack>
#include <string>
namespace junk
{
namespace str_equation_analise
{
class Equation
{
typedef std::map<std::string, float> TMapTerm;
enum class eq_sign {
sign_plus = 0,
sign_minus,
};
struct eq_term
{
eq_sign sign;
std::string p;
float m;
eq_term() { clear(); }
void clear() {
sign = eq_sign::sign_plus;
m = 1.f;
p = "";
}
};
public:
Equation(char *str)
{
if (!str){
throw std::invalid_argument("invalid_argument");
}
analise_eq(str, str + strlen(str), 1);
}
std::string get_eq_by(std::string &&key)
{
std::string out;
TMapTerm::iterator iter_find = m_terms.find(key);
if (iter_find != m_terms.end())
{
float div = iter_find->second;
if (div != 0)
{
out += key + '=';
bool first = true;
for (TMapTerm::iterator iter = m_terms.begin(); iter != m_terms.end(); ++iter) {
if (iter->first != key)
{
float digit = (float)((-1.f * iter->second) / div);
if (!first && digit > 0) {
out += '+';
}
std::string str_d = std::to_string(digit);
str_d.erase(str_d.find_last_not_of('0') + 1, std::string::npos);
out += str_d + iter->first;
first = false;
}
}
}
}
return out;
}
private:
void analise_eq(char *start, char *last, int sign)
{
char *iter = start;
eq_term term; // current eq term
while (iter != last)
{
if (*iter == '(')
{
std::stack<char> p_stack;
p_stack.push(*start);
char *iter_brace = iter + 1;
while (iter_brace)
{
if (*iter_brace == '(') {
p_stack.push(*iter);
}
else if (*iter_brace == ')') {
p_stack.pop();
}
if (p_stack.empty()) {
break;
}
iter_brace++;
}
if (!iter_brace) {
throw std::invalid_argument("invalid format");
}
analise_eq(iter + 1, iter_brace, sign * (term.sign == eq_sign::sign_plus ? 1 : -1));
iter = iter_brace + 1;
continue;
}
else if (*iter == '=') {
analise_eq(iter + 1, last, -1);
return;
}
char *end;
process_term(iter, last, term, &end);
iter = end;
// term complete
if (is_sign(*iter) || iter == last)
{
add_term(term, sign);
term.clear();
}
}
}
void process_term(char *begin, char *last, eq_term &term, char **end)
{
if (is_sign(*begin)) {
term.sign = (*begin == '+') ? eq_sign::sign_plus : eq_sign::sign_minus;
*end = begin + 1;
}
else if (!is_digit(*begin)) //
{
char *iter = begin + 1;
while (iter != last)
{
if (is_digit(*iter) || is_sign(*iter) || *iter == ')') {
break;
}
++iter;
}
term.p.assign(begin, iter - begin);
*end = iter;
}
else // digit
{
term.m = strtof(begin, end);
}
}
protected:
void add_term(const eq_term &term, int sign)
{
float val = term.m * ((term.sign == eq_sign::sign_minus ? -1 : 1)) * sign;
if (m_terms.find(term.p) == m_terms.end()){
m_terms[term.p] = val;
}
else {
m_terms[term.p] += val;
}
}
static bool is_digit(const char chr) { return chr >= '0' && chr - '0' <= 9; }
static bool is_sign(const char chr) { return chr == '+' || chr == '-'; }
public:
TMapTerm m_terms;
};
}
}
TEST(Array, StrEquationAnalise)
{
{
char *str_eq = "3y-4x+(3-(2x-3y))=10y";
Equation eq(str_eq);
std::string eqs = eq.get_eq_by({ 'y' });
EXPECT_EQ(eqs, std::string("y=0.75-1.5x"));
}
{
char *str_eq = "3y-4x-(3-(2x-3y))=10y";
Equation eq(str_eq);
std::string eqs = eq.get_eq_by({ 'y' });
EXPECT_EQ(eqs, std::string("y=-0.3-0.2x"));
}
{
char *str_eq = "(x+x)-(2y-(10x-7y))=15y";
Equation eq(str_eq);
std::string eqs = eq.get_eq_by({ 'y' });
EXPECT_EQ(eqs, std::string("y=0.5x"));
}
}
/*
arrayA = [12, 24, 8, 32]
arrayB = [13, 25, 32, 11]
Push each number into sorted list sequence and mark element
by mask which array it belongs to.
(A, B, both or 0. 0 means element yet used).
For instance:
elements: 32 -> 25 -> 24 -> 13 -> 12 -> 11 -> 8
mask: ab b a b a b a
shuffling goes from left to right.
* if element belongs to B array we can do nothing but connect
most right A element and remove corresponding masks. e.g.(32 - 8)
* if element belongs to A array we take closest right B element e.g.(32 - 25) end mark element as used.
* move to next unused element.
linear time if using double linked list but O(n) aux space.
*/
const int MASK_A = 1;
const int MASK_B = 2;
struct Node
{
Node(int v, unsigned int m)
: value(v)
, mask(m)
, next(nullptr) {}
int value;
unsigned int mask; // array's mask or both. 0- means item not used
Node *next;
};
class List
{
public:
List()
: m_head(nullptr) {}
~List() { clear(); }
void insert_value(int value, unsigned int mask)
{
if (!m_head) {
insert_after(nullptr, value, mask);
}
else
{
Node *iter = m_head;
Node *p = nullptr;
while (iter)
{
if (value > iter->value) {
break;
}
else if (value == iter->value)
{
iter->mask |= mask;
return;
}
p = iter;
iter = iter->next;
}
insert_after(p, value, mask);
}
}
void insert_after(Node *after, int value, unsigned int mask)
{
if (!m_head) {
m_head = new Node(value, mask);
}
else
{
if (!after)
{
Node *new_node = new Node(value, mask);
new_node->next = m_head;
m_head = new_node;
return;
}
Node *iter = m_head;
while (iter)
{
if (iter == after)
{
Node *new_node = new Node(value, mask);
new_node->next = iter->next;
iter->next = new_node;
break;
}
iter = iter->next;
}
}
}
void shuffle(std::vector<int> &outA, std::vector<int> &outB)
{
Node *iter = m_head;
while (iter)
{
if (iter->mask & MASK_B) // B-array
{
outB.push_back(iter->value);
// find most right A object
Node *i = iter->next;
Node *r = nullptr;
while (i)
{
if (i->mask & 1) { // object belongs to A-array
r = i;
}
i = i->next;
}
assert(r);
outA.push_back(r->value);
// clear masks
iter->mask &= ~MASK_B;
r->mask &= ~MASK_A;
}
if (iter->mask & MASK_A) // A-array
{
outA.push_back(iter->value);
// find closest right B-object
Node *i = iter->next;
while (i)
{
if (i->mask & MASK_B) {
break;
}
}
assert(i);
outB.push_back(i->value);
iter->mask &= ~MASK_A;
i->mask &= ~MASK_B;
}
iter = iter->next;
}
}
void clear()
{
Node *iter = m_head;
while (iter)
{
Node *next = iter->next;
delete iter;
iter = next;
}
}
protected:
Node *m_head;
};
TEST(Lists, Build_ArrayA_over_ArrayB)
{
List list;
const int SIZE = 4;
int arrayA[] = { 12, 24, 8, 32 };
int arrayB[] = { 13, 25, 32, 11 };
for (int i = 0; i < SIZE; ++i){
list.insert_value(arrayA[i], MASK_A);
}
for (int i = 0; i < SIZE; ++i) {
list.insert_value(arrayB[i], MASK_B);
}
std::vector<int> A, B;
list.shuffle(A, B);
EXPECT_TRUE(A.size() == SIZE && B.size() == SIZE);
int countA = 0;
int countB = 0;
for (int i = 0; i < SIZE; ++i)
{
if (A[i] == B[i]) {
continue;
}
if (A[i] > B[i]){
countA++;
}
else{
countB++;
}
}
EXPECT_TRUE(countA > countB);
}
Possible solution is to use binary min heap to distribute all tasks payload.
First we create min heap with N nodes (workers)
Sort task array to distribute tasks evenly from most expensive to lowers
increase key of most low task. O(1) for localize min and O(log(n)) to increase
get max node in heap O(n)
class HeapMin
{
public:
HeapMin()
: m_heap(nullptr)
, m_last(-1)
, m_size(0)
{ m_size = reallocate();}
~HeapMin() { delete m_heap;}
void insert(int value)
{
if (m_last == m_size - 1){
m_size = reallocate();
}
m_heap[++m_last] = value;
insert_impl(m_last);
}
void increase_min(int val)
{
if (!m_heap){
return;
}
m_heap[0] += val;
min_heapify(0, m_last + 1);
}
int min()
{
int min = INT_MIN;
if (m_heap && m_last >= 0) {
min = m_heap[0];
}
return min;
}
int max()
{
int max = INT_MIN;
if (m_heap && m_last >= 0)
{
max = m_heap[0];
for (int i = 1; i < m_last + 1; ++i) {
if (m_heap[i] > max) {
max = m_heap[i];
}
}
}
return max;
}
static int LEFT(int i) { return 2 * i + 1; }
static int RIGHT(int i) { return 2 * i + 2; }
static int PARENT(int i) { return (i - 1) / 2; }
protected:
void min_heapify(int i, int len)
{
int lowest = i;
int lhs = LEFT(i);
if (lhs < len && m_heap[lhs] < m_heap[i]){
lowest = lhs;
}
int rhs = RIGHT(i);
if (rhs < len && m_heap[rhs] < m_heap[lowest]) {
lowest = lhs;
}
if (i != lowest)
{
std::swap(m_heap[i], m_heap[lowest]);
min_heapify(lowest, len);
}
}
void insert_impl(int i)
{
if (i == 0){
return;
}
int parent = PARENT(i);
if (m_heap[parent] > m_heap[i])
{
std::swap(m_heap[parent], m_heap[i]);
insert_impl(parent);
}
}
int reallocate()
{
int size = m_size;
if (!m_heap)
{
size = m_size == 0 ? 127 : m_size;
m_heap = new int [size];
}
else
{
size = size * 2 + 1;
int *new_alloc = new int[size];
memcpy(static_cast<void*>(new_alloc), static_cast<void*>(m_heap), sizeof(m_heap) * sizeof(int));
delete m_heap;
m_heap = new_alloc;
}
return size;
}
private:
int *m_heap;
int m_size;
int m_last;
};
TEST(Heap, MinHeap_calc_task_max_min)
{
int tasks[] = { 2, 2, 3, 7, 1 };
HeapMin heap;
heap.insert(0); // add worker 1
heap.insert(0); // add worker 2
const int SIZE = sizeof(tasks) / sizeof(int);
std::sort(tasks, tasks + SIZE);
for (int i = SIZE - 1; i >= 0; --i) {
heap.increase_min(tasks[i]);
}
EXPECT_EQ(heap.min(), 7);
EXPECT_EQ(heap.max(), 8);
}
return 0 without unlock call?
- yura.gunko March 05, 2017find new list's end (k -1) and rearrange elements to list's head
template<typename T>
struct Node
{
T value;
Node *next;
Node(const T &val)
: value(val)
, next(nullptr)
{}
};
template<typename T>
class List
{
public:
List()
: m_head(nullptr)
, m_len(0)
{}
~List()
{
Node<T> *iter = m_head;
while (iter)
{
Node<T> *next = iter->next;
delete iter;
iter = next;
}
}
void Insert(const T value)
{
if (!m_head)
{
m_head = new Node<T>(value);
m_len++;
}
else
{
Node<T> *iter = m_head->next;
Node<T> *prev = m_head;
while (iter)
{
prev = iter;
iter = iter->next;
}
prev->next = new Node<T>(value);
m_len++;
}
}
void RotateOn(size_t k)
{
size_t mod_k = k % m_len;
if (m_head && mod_k > 0)
{
// localize new end of a list
Node<T> *iter_kth = m_head;
for (size_t i = 0; i < mod_k - 1; i++){
iter_kth = iter_kth->next;
}
// get current end-node
Node<T> *iter = iter_kth->next;
Node<T> *end = iter_kth;
while (iter)
{
end = iter;
iter = iter->next;
}
// rearrange list nodes
Node<T> *new_head = iter_kth->next;
iter_kth->next = nullptr;
end->next = m_head;
m_head = new_head;
}
}
private:
Node<T> *m_head;
size_t m_len;
};
One possible solution of this chart problem is to use map with a key of band name and
max-heap for records. Localize of max rate song in max-heap is O(1).
Increase song's rate may cause rearrange max-heap calling max_heapify
template<typename T>
class heap
{
heap(const heap&) = delete;
heap& operator=(const heap&) = delete;
public:
heap()
: m_heap(nullptr)
, m_size(0)
, m_last(-1)
{
m_size = reallocate();
}
~heap()
{
delete []m_heap;
}
size_t PARENT(size_t i) const { return i / 2; }
size_t LEFT(size_t i) const { return i * 2 + 1; }
size_t RIGHT(size_t i) const { return i * 2 + 2; }
void insert(const T&value)
{
if (m_last == m_size - 1) {
m_size = reallocate();
}
m_last++;
m_heap[m_last] = value;
insertImpl(m_last);
}
void build_max_heap()
{
const size_t actual_size = m_last + 1;
for (int i = actual_size / 2; i >= 0; i--) {
max_heapify(i, actual_size);
}
}
void max_heapify(size_t index, size_t len)
{
T &curr = m_heap[index];
size_t l = LEFT(index);
size_t r = RIGHT(index);
size_t largest = index;
if ((l < len) && curr < m_heap[l]){
largest = l;
}
if (r < len && m_heap[largest] < m_heap[r]) {
largest = r;
}
if (largest != index)
{
std::swap(curr, m_heap[largest]);
max_heapify(largest, len);
}
}
size_t size() const { return m_size; }
size_t last() const { return m_last; }
T* data() const { return m_heap; }
protected:
private:
int reallocate()
{
int size = m_size;
if (!m_heap)
{
size = (m_size == 0) ? 128 : m_size;
m_heap = new T[size];
}
else
{
const size_t new_size = m_size * 2;
T *new_heap = new T[new_size];
memcpy(static_cast<void*>(new_heap), static_cast<void*>(m_heap), m_size * sizeof(T));
delete[] m_heap;
m_heap = new_heap;
size = new_size;
}
return size;
}
void insertImpl(size_t index)
{
while (index)
{
size_t parent = PARENT(index);
if (m_heap[parent] < m_heap[index])
{
std::swap(m_heap[parent], m_heap[index]);
}
index = parent;
}
}
private:
T *m_heap;
size_t m_size;
int m_last;
};
class Chart
{
public:
struct Record
{
std::string name;
size_t rate;
Record()
: name()
, rate(0) {}
Record(const std::string &_name)
: name(_name)
, rate(1){}
void incRate() { rate++; }
bool operator < (const Record &other)
{
return rate < other.rate;
}
};
using TChart = std::map<std::string, heap<Record>*>;
Chart()
{}
~Chart()
{
for each (auto &item in m_chart){
delete item.second;
}
}
void PlaySong(const std::string &author, const std::string &name)
{
TChart::const_iterator iter_find = m_chart.find(author);
if (iter_find == m_chart.end()) {
m_chart.insert(std::make_pair(author, new heap<Record>()));
}
bool bFind = false;
Record *pdata = m_chart[author]->data();
int len = m_chart[author]->last();
for (int i = 0; i <= len; i++)
{
if (pdata[i].name == name)
{
pdata[i].incRate();
m_chart[author]->build_max_heap();
bFind = true;
break;
}
}
if (!bFind) {
m_chart[author]->insert(Record(name));
}
}
std::string TopSong(const std::string &author)
{
std::string out;
TChart::const_iterator iter_find = m_chart.find(author);
if (iter_find != m_chart.end())
{
if (m_chart[author]->last() >= 0)
{
out = m_chart[author]->data()[0].name;
}
}
return out;
}
protected:
private:
TChart m_chart;
};
//--------------------------------
TEST(HeapChart, Chart)
{
Chart chart;
chart.PlaySong("Lady Gaga", "La-la-la");
chart.PlaySong("Lady Gaga", "Pokerface");
chart.PlaySong("Lady Gaga", "Pokerface");
chart.PlaySong("Sting", "Desert rose");
EXPECT_EQ(chart.TopSong("Lady Gaga"), std::string("Pokerface"));
}
- yura.gunko May 24, 2017