zprogd
BAN USERSend me email: zprogd@gmail.com
Several terabytes fits in nowadays HDD not in the RAM. We should split our database into few files: index files and data file. Typically index file of database is presented as B-tree for decreasing disk read/write operations. Search time is Log b (N), where b - number of child of one node in B-tree.
- zprogd February 19, 2015We can push firsts tuples immediately to result array and for seconds tuples use min_heap. For each step compare current value with top of min_heap.
1. Split tuple3 into two tuple2: 'first' and 'second'
2. While top of min_heap less than 'first' tuple2, push the top to result array.
3. Push the 'first' tuple to result array.
4. Push 'second' tuple2 to min_hep
5. Repeat it for each tuple3
But I don't use here "id". Why interviewer give that field? Probably there is any reason.
vector<tuple2> split(const vector<tuple3>& arr) {
priority_queue<tuple2, vector<tuple2>, comp_fn> min_heap;
vector<tuple2> result;
result.reserve(2 * arr.size())
for (const tuple3& it : arr) {
tuple2 tuple(it.id, it.val1);
while (!min_heap.empty() && min_heap.top().val < tuple.val) {
result.push_back(min_heap.top());
min_heap.pop();
}
rs.push_back(tuple);
min_heap.push(tuple2(it.id, it.val2));
}
while (!min_heap.empty() ) {
rs.push_back(min_heap.top());
min_heap.pop();
}
return rs;
}
void Insert(Node*& head, Node* new_node) {
if (!head) {
head = new_node->next = new_node;
return;
}
for (Node* it = head; true; it = it->next) {
if ((new_node->val >= it->val && new_node->val <= it->next->val) ||
it->next == head) {
new_node->next = it->next;
it->next = new_node;
if (new_node->val < head->val)
head = new_node;
return;
}
}
}
O(n) solution
int min_len(const vector<int>& v, int sum) {
int curr_sum = 0;
int len = INT_MAX;
for (int i = 0, back = 0; i < v.size(); i++) {
curr_sum += v[i];
while (curr_sum > sum) {
if (len > i - back + 1)
len = i - back + 1;
curr_sum -= v[back];
back++;
}
}
return len;
}
O(n) solution. Note iterators 'beg' and 'end' only one time run from 0 to size();
For every step 'beg' we move 'end' farther while max-min <= K in range [beg, end]
List 'min_track' keeps numbers in ascending order, list 'max_track' keeps numbers in descending order,
For array 3 5 7 6 3:
for 'beg'=0 and 'end'=2:
min_track: 3 5 7, max_track: 7
for 'beg'=2 and 'end'=5
min_track: 3, max_track: 7 6 3
struct Item{
int value;
int index;
};
void PrintSlices(const vector<int>& v, int k) {
list<Item> min_track;
list<Item> max_track;
int end = 0;
for (int beg = 0; beg < v.size(); beg++) {
while (end < v.size()) {
while (!max_track.empty() && max_track.back().value <= v[end])
max_track.pop_back();
max_track.push_back(Item{v[end], end});
while (!min_track.empty() && min_track.back().value >= v[end])
min_track.pop_back();
min_track.push_back(Item{v[end], end});
if (max_track.front().value - min_track.front().value > k)
break;
end++;
}
for (int i = beg; i < end; i++)
printf("(%d, %d) ", beg, i);
if (!min_track.empty() && min_track.front().index == beg)
min_track.pop_front();
if (!max_track.empty() && max_track.front().index == beg)
max_track.pop_front();
}
}
void trim_spaces(char* str) {
int new_pos = 0, space_counter = 0;
for (int pos = 0; str[pos]; pos++) {
if (str[pos] != ' ' || (new_pos > 0 && str[new_pos-1] != ' '))
str[new_pos++] = str[pos];
else
space_counter ++;
}
while (space_counter--)
str[new_pos++] = ' ';
}
Million integer numbers that is not a big deal. It is only 4Mb memory.
Sort it in memory nLogn and just print all triplets before sum reaches d with no overhead at all.
void print_all_triplets(int arr[], int len, int d) {
sort(arr, len);
for (int a = 0; a < len && arr[a] < d ; a++) {
for (int b = a+1; b < len && arr[a]+arr[b] < d; b++) {
for (c = b+1; c < len && arr[a]+arr[b]+arr[c] <= d; c++) {
printf("%d, %d, %d\n", arr[a], arr[b], arr[c]);
}
}
}
}
struct Bundle{
int SrNo;
int price;
vector<string> items;
};
vector<Bundle> bundles;
// Auxiliary table maps name to indexes of bundels:
// Burger | 1,4,5
// French_Frice | 2,4
// Coldrink | 3, 4, 5
map<string, vector<int>> item_name_to_bundle_indexes;
int GetBundles(const set<string>& items_to_buy,
vector<int>& best_bundles) {
if (items_to_buy.empty())
return 0;
int best_price = INT_MAX;
string item_name = *items_to_buy.begin();
for (int bundle_index : item_name_to_bundle_indexes[item_name]) {
auto items_to_buy_copy = items_to_buy;
for (string item : bundles[bundle_index].items) {
items_to_buy_copy.erase(item);
}
vector<int> curr_best_bundles;
int price = bundles[bundle_index].price +
GetBundles(items_to_buy_copy, curr_best_bundles);
if (price < best_price) {
curr_best_bundles.push_back(bundle_index);
best_bundles = curr_best_bundles;
best_price = price;
}
}
return best_price;
}
bool CanCross(vector<bool>& field, int index, int velocity,
vector<vector<bool>>& cache) {
if (index >= field.size())
return true;
if (!field[index] || velosity <= 0 || cache[index][velocity])
return false;
cache[index][velocity] = true;
return CanCross(field, index+velocity, velocity) ||
CanCross(field, index+velocity+1, velocity+1) ||
CanCross(field, index+velocity-1, velocity-1);
}
void PrintRational(int num, int denum) {
std::string str = std::to_string(num / denum) + ".";
std::unordered_map<int, int> hash;
int repeat_index = 0;
while (true) {
num = (num % denum) * 10;
auto repeat = hash.find(num);
if (repeat != hash.end()) {
repeat_index = repeat->second;
break;
}
hash[num] = str.size();
str += std::to_string(num / denum);
}
std::cout << str.substr(0, repeat_index)
<< "(" << str.substr(repeat_index) <<")"
<< std::endl;
}
DFS works well here.
void BuildAllProjects() {
for (Project p : projects) {
BuildProjectRec(p);
}
}
void BuildProjectRec(Project project) {
if (project.status == PROCESSED)
return;
if (project.status == IN_PROGRESS)
throw exeption("There is cycle between projects");
project.status = IN_PROGRESS;
for (Dependence dep_project : project.dependencies) {
BuilldProjectRec(dep_project);
}
project.status = PROCESSED;
printf("Build project: %s", project->project_name);
}
O(n)
void print_longest_adj(const vector<vector<int>>& matrix) {
const int DUMMY = -2;
const int N = matrix.size();
vector<bool> adjacent(N * N + 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int a = matrix[i][j];
int b = i+1 < N ? matrix[i+1][j] : DUMMY;
int c = j+1 < N ? matrix[i][j+1] : DUMMY;
if (a+1 == b || a+1 == c)
adjacent[a] = true;
if (b+1 == a)
adjacent[b] = true;
if (c+1 == a)
adjacent[c] = true;
}
}
int max_length = 0, max_first = 0, length = 0, first = 0;
for (int i = 0; i < adjacent.size(); i++) {
if (adjacent[i]) {
length++;
if (length == 1)
first = i;
if (length > max_length) {
max_length = length;
max_first = first;
}
} else {
length = 0;
}
}
for (int i = 0; i <= max_length; i++)
printf("%d\n", max_first+i);
}
Brute force solution: check every number begin from 1 000 000 000 by dividing on every integer from 2 to sqrt(n).
void print_5_primes_10_digit() {
for (int prime = 1000000000, count = 0; count < 5; prime++) {
bool is_prime = true;
for (int divisor = 2; divisor <= std::sqrt(prime); divisor++) {
if (prime % divisor == 0) {
is_prime = false;
break;
}
}
if (is_prime) {
printf("%d\n", prime);
count++;
}
}
}
It runs 0.006 sec on my computer.
1000000007
1000000009
1000000021
1000000033
1000000087
bool isValidWord(const std::string& str, std::vector<int> letters) {
for (int i = 0; i < str.size(); i++) {
if (--letters[str[i] - 'a'] < 0){
return false;
}
}
return true;
}
int main(int argc, char* argv[]) {
std::vector<int> letters(26);
for (int i = 2; i < argc; i++) {
letters[argv[i][0] - 'a']++;
}
std::ifstream file(argv[1]);
std::string str;
int max_size = 0;
std::list<std::string> longest_words;
while (file >> str) {
if (str.size() < max_size || !isValidWord(str, letters))
continue;
if (str.size() > max_size) {
longest_words.clear();
max_size = str.size();
}
longest_words.push_back(str);
}
for (auto w : longest_words)
std::cout << w << std::endl;
return 0;
}
O(m*n) in worst case. Enjoy.
bool canArrange(int* servers, int servers_len, int* tasks, int tasks_len) {
if (tasks_len == 0)
return true;
for (int i = 0; i < servers_len; i++) {
if (servers[i] >= tasks[tasks_len - 1]) {
servers[i] -= tasks[task_len - 1];
if (canArrange(servers, servers_len, tasks, tasks_len - 1))
return true;
servers[i] += tasks[task_len - 1];
}
}
return false;
}
O(Log(n)) solution.
int two_array_median(int a[], int b[], int N) {
if (!a || !b || N < 1)
return -1;
if (N == 1)
return (a[0]+b[0])/2;
if (N == 2)
return (std::max(a[0], b[0]) + std::min(a[1], b[1]))/2;
int m1 = one_array_median(a, N);
int m2 = one_array_median(b, N);
int mid = N/2+1;
if (m1<m2) {
return two_array_median(a+N-mid, b, mid);
} else {
return two_array_median(a, b+N-mid, mid);
}
}
int one_array_median(int a[], int N) {
if (N % 2)
return a[N/2];
else
return (a[N/2 - 1] + a[N/2])/2;
}
One pass solution.
std::string getLongestPrefix(const std::string& str) {
// Prefix of first word is whole first word.
int prefix = 0;
while (prefix < str.size() && str[prefix] != ' ') {
prefix++;
}
for (int pos = prefix+1; pos < str.size(); pos++) {
int word_prefix = 0;
while (pos < str.size() &&
word_prefix < prefix &&
str[pos] == str[word_prefix]) {
word_prefix++; pos++;
}
prefix = word_prefix;
while (pos < str.size() && str[pos] != ' ')
pos++;
}
return str.substr(0, prefix);
}
int get_median(int next_number, Heap& min_heap, Heap& max_heap) {
if (max_heap.size() && next_number < max_heap.top()) {
max_heap.enqueue(next_number);
if (max_heap.size() > min_heap.size()) {
min_heap.enqueue(max_heap.dequeue());
}
} else {
min_heap.enqueue(next_number);
if (min_heap.size() > max_heap.size()+1) {
max_heap.enqueue(min_heap.dequeue());
}
}
if (max_heap.size()==min_heap.size()) {
return (max_heap.top() + min_heap.top())/2;
} else {
return min_heap.top();
}
}
Item* get_deepest_node(Item* root) {
int max_level = -1;
Item* node = NULL;
get_deepest_node(root, 0, &max_level, &node);
return node;
}
void get_deepest_node(Item* root, int curr_level, int* max_level, Item** node) {
if (!root)
return;
if (curr_level > *max_level) {
*max_level = curr_level;
*node = root;
}
get_deepest_node(root->left, curr_level+1, max_level, node);
get_deepest_node(root->right, curr_level+1, max_level, node);
}
void replace(const char* src, const char* old_value, const char* new_value, char* dest) {
int i = 0;
int j = 0;
while (src[i]) {
if (src[i] == old_value[0]) {
int k = 1;
while (src[i+k] && old_value[k] && src[i+k]==old_value[k])
k++;
if (!old_value[k]) {
for (int m=0; new_value[m]; m++)
dest[j++] = new_value[m];
i += k;
continue;
}
}
dest[j++] = src[i++];
}
dest[j]=0;
}
int binary_serach(int* data, int size, int x) {
if (!data)
return -1;
int l = 0;
int r = size-1;
while (l<=r) {
int m = (l+r)/2;
if (data[m] == x)
return m;
if ((data[l] < data[m] && x>=data[l] && x<data[m]) ||
(data[l] > data[m] && (x>=data[l] || x<data[m])))
r=m-1;
else
l=m+1;
}
return -1;
}
Item* mergesort(Item* top) {
if (!top || !top->next)
return top;
Item* middle = top;
for (Item* p = top; p->next && p->next->next; p = p->next->next)
middle = middle->next;
Item* left_last = middle;
middle = middle->next;
left_last->next=NULL;
Item* left = mergesort(top);
Item* right = mergesort(middle);
Item** curr = ⊤
while (left || right) {
if (!right ||
(left && left->data <= right->data)) {
*curr = left;
left = left->next;
} else {
*curr = right;
right = right->next;
}
curr = &(*curr)->next;
}
return top;
}
enum Color { WHITE=0, BLACK=1, UNKNOWN=3 };
struct Item {
Color color;
Item* child_1;
Item* child_2;
Item* child_3;
Item* child_4;
};
Item* GetOverlap(Item* root_1, Item* root_2) {
if (!root_1 && !root_2)
return NULL;
Item* item = new Item;
if (!root_1 || !root_2) {
Item* root = root_1 ? root_1 : root_2;
item->color = root->color;
if (item->color == UNKNOWN) {
item->child_1 = GetOverlap(root->child_1, NULL);
item->child_2 = GetOverlap(root->child_2, NULL);
item->child_3 = GetOverlap(root->child_3, NULL);
item->child_4 = GetOverlap(root->child_4, NULL);
}
} else if (root_1->color != UNKNOWN && root_2->color != UNKNOWN) {
item->color = root_1->color | root_2->color;
} else {
item->color = UNKNOWN;
item->child_1=GetOverlap(root_1->color == UNKNOWN ? root_1->child_1 : root_1,
root_2->color == UNKNOWN ? root_2->child_1 : root_2);
item->child_2=GetOverlap(root_1->color == UNKNOWN ? root_1->child_2 : root_1,
root_2->color == UNKNOWN ? root_2->child_2 : root_2);
item->child_3=GetOverlap(root_1->color == UNKNOWN ? root_1->child_3 : root_1,
root_2->color == UNKNOWN ? root_2->child_3 : root_2);
item->child_4=GetOverlap(root_1->color == UNKNOWN ? root_1->child_4 : root_1,
root_2->color == UNKNOWN ? root_2->child_4 : root_2);
}
return item;
}
struct Node{
bool color;
Node* child_1;
Node* child_2;
Node* child_3;
Node* child_4;
};
Node* overlap(Node* root_1, Node* root_2) {
if (!root_1 && !root_2)
return NULL;
Node* node = new Node;
node->color = (root1 ? root1->color : false) |
(root2 ? root2->color : false);
node->child1 = overlap(root1 ? root1->child1 : NULL,
root2 ? root2->child1 : NULL);
node->child2 = overlap(root1 ? root1->child2 : NULL,
root2 ? root2->child2 : NULL);
node->child3 = overlap(root1 ? root1->child3 : NULL,
root2 ? root2->child3 : NULL);
node->child4 = overlap(root1 ? root1->child4 : NULL,
root2 ? root2->child4 : NULL);
return node;
}
1. Take every two consecutive words and find first difference letters in them
hat
hello
here we have the letters order a->e
For every letter of alphabet create an array where check what letters are before it.
It can be bit array. 4 bytes integer is enough for 26 letters alphabet.
26 letters * 4 bytes = 104 bytes memory.
2. Next step for every letter of alphabet count how much letters are before it. Here use array of ranks and recursion algorithm for counting not counted letters before.
int rank[26] = {-1,-1, ... -1};
int letters_before[26]; // created on 1st step
int GetRank(int letter) {
if (rank[letter] != -1)
return rank[letter];
int curr_rank = 0;
for (int i = 0; i < 26; i++) {
if (letters_before[letter] & (1 << i))
curr_rank = max(curr_rank, GetRank(i));
}
rank[letter] = curr_rank+1;
return rank[letter];
}
3. Last step sort 26 letters by rank.
big O( size_of_dictionary * size_of_word) and just 208 bytes memory!
We need get next number from those server that give min current element while don't gathering K smallest numbers. For select min number we can use min-heap datastructure size of O(M).
1. Get one number for every server and insert those numbers and server names of every numbers in min-heap.
2. From 1 to K
2.1. remove top(smallest) item in min-heap.
2.2. get new number from that server whose item was removed.
2.3. insert new item into min-heap.
3. The top of min-heap is kth smallest element.
For example we have 8 teams:
1 2 3 4 5 6 7 8
Divide they onto 2 groups and let play each team one group with each team another group:
day 1:
1 2 3 4
5 6 7 8
day 2:
1 2 3 4
6 7 8 5
day3:
1 2 3 4
7 8 5 6
day 4:
1 2 3 4
8 5 6 7
All teams one group just had games with all teams another group. But teams inside one group didn't have game between each other.
Repeat that algorithm recursively for every group
day 5:
1 2 5 6
3 4 7 8
day 6:
1 2 5 6
4 3 8 7
Once again divide every group
day 7:
1 3 5 7
2 4 6 8
That's all :-)
- zprogd June 27, 2012Create 10 linked lists of pointers at phone numbers.
Phone number 9456 will be presented in "9" and "4" and "5" and "6" linked lists at the same time.
When user press number "9" we print all items from "9" linked list.
Then user press number 6 we print all items from "9" and "6" linked lists.
For protect from printing the same number many times we can make variable "checked" for every phone number and don't print checked numbers. It work if linked list have only pointers at phone numbers.
For every phone number create 10 bit value. Set in "1" those bits whose digit presents in the phone number.
For example number 9456 will have value 1001110000
For searching match numbers check following condition:
(A & B) == B
A - value for number from phone book
B - value for typed number
Here is a test for above code:
struct Item{
int data;
Item* child;
Item* right;
Item(int i) : data(i), child(0), right(0) {}
};
int main(int argc, _char* argv[])
{
Item i12(12), i4(4), i8(8), i22(22), i1(1),i2(2),i3(3), i18(18), i24(24);
i12.child = &i4;
i4.right = &i8;
i8.right = &i22;
i4.child = &i1;
i1.right = &i2;
i2.right = &i3;
i22.child = &i18;
i18.right = &i24;
PrintThree(&i12);
return 0;
}
Hi guys,
- zprogd February 20, 2015It looks like there is only O(n) solution for arrays where arr[left] = arr[mid] = arr[right]
2, 2, 2, 2, 3, 1, 2
or
2, 3, 1, 2, 2, 2, 2
Test binary search for these arrays. You don't know where is begin of shifted array on left or on right and which side to choose for the next iteration.