CareerCup

#include<iostream>
#include<string>
#include<list>
#include<unordered_map>

using namespace std;

list<char> generate_maximum_palindrom(const string& str){
    list<char> palindrom {};
    unordered_map<char, int> counter {};
    int largest_odd = -1;
    char largest_odd_char = ' ';
    
    for(char c:str){
        counter[c] ++;
        
        if(counter[c] % 2 != 0 && counter[c] > largest_odd){
            largest_odd_char = c;
            largest_odd = counter[c];
        }
    }
    
    if(largest_odd > -1){
        while(counter[largest_odd_char]--){
            palindrom.push_back(largest_odd_char);
        }
    }
        
    for(auto it = counter.begin(); it != counter.end(); it++){
        while(it->second >= 2){
            palindrom.push_back(it->first);
            palindrom.push_front(it->first);
                
            it->second -= 2;
        }
    }
    
    
    return palindrom;
}

int main(){
    string str = "akjhadajsoadjaoiwjewaodjaosid";
    
    for(char c : generate_maximum_palindrom(str))
        cout << c;
    cout << endl;
}

#include<iostream>
#include<vector>
#include<unordered_map>
#include<list>


using namespace std;

struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
};

void bfs(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& parents, vector<TreeNode*>& leafs){
    if(root->left == nullptr && root->right == nullptr) {
        leafs.push_back(root);
        return;
    }
    
    if(root->left != nullptr){
        parents[root->left] = root;
        bfs(root->left, parents, leafs);
    }
    
    if(root->right != nullptr){
        parents[root->right] = root;
        bfs(root->right, parents, leafs);
    }
}

TreeNode* make_node(int value, list<TreeNode>& nodes){
    nodes.push_back({value});
    return &nodes.back();
}

void draw_path(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parents){
    while(parents.find(leaf) != parents.end()){
        cout << leaf->value << " <-- ";
        leaf = parents[leaf];
    }
    
    cout << leaf->value;
}

int main(){
    
    list<TreeNode> nodes{};
    TreeNode* root = make_node(0, nodes);
    root->left = make_node(1, nodes);
    root->right = make_node(2, nodes);
    root->left->right = make_node(3, nodes);
    
    unordered_map<TreeNode*, TreeNode*> parents {};
    vector<TreeNode*> leafs{};
    
    bfs(root, parents, leafs);
    
    for(TreeNode* leaf:leafs){
        draw_path(leaf, parents);
        cout << endl;
    }
}

we can shuffle the input array randomly then insert It's item one by one to the binary search tree.
we get o(n) for shuffling + o(n lgn) for making the BST.

#include<iostream>
#include<vector>
#include<unordered_set>
#include<random>

using namespace std;

int range_random(int i, int j, const unordered_set<int>& excluded){
    int n = j-i - (int)excluded.size();
    
    random_device rd;
    default_random_engine gen(rd());
    
    uniform_int_distribution<> dis(0, n);
    
    int idx = dis(gen);
    
    for(int k = i; k<j+1; k++){
        if(excluded.find(k) == excluded.end()){
            idx --;
        }
        
        if(idx == -1){
            return k;
        }
    }
    
    throw "there is not any free value which has not excluded";
}

int main(){
    unordered_set<int> excluded {};
    
    int first_digit = range_random(1, 9, excluded);
    excluded.insert(first_digit);
    int second_digit = range_random(0, 9, excluded);
    excluded.insert(second_digit);
    int third_digit = range_random(0, 9, excluded);
    excluded.insert(third_digit);
    
    for(int i = 1; i<10 ; i+=2){
        excluded.insert(i);
    }
    
    int forth_digit = range_random(0, 9, excluded);
    
    cout << first_digit << second_digit << third_digit << forth_digit << endl;
}

#include<iostream>
#include<vector>

using namespace std;

struct Cylander {
    int index;
    int height;
};

void robo_rotate(vector<Cylander>& lst, int left, int right){
    for(;left<right; left++, right--){
        Cylander temp = lst[left];
        lst[left] = lst[right];
        lst[right] = temp;
    }
}

void robo_sort(vector<Cylander>& lst){
    for(int left = 0; left< lst.size(); left++){
        Cylander min = lst[left];
        int min_index = left;
        for(int right = left+1; right < lst.size(); right++){
            if(min.height > lst[right].height || (min.height == lst[right].height && min.index > lst[right].index)){
                min_index = right;
                min = lst[right];
            }
        }
        
        robo_rotate(lst, left, min_index);
    }
}

int main(){
    vector<Cylander> cylanders(6);
    cylanders[0] = {0, 1};
    cylanders[1] = {1, 7};
    cylanders[2] = {2, 6};
    cylanders[3] = {3, 7};
    cylanders[4] = {4, 4};
    cylanders[5] = {5, 2};
    
    robo_sort(cylanders);
    
    for(int i=0; i< 6; i++){
        cout << "(" << cylanders[i].height << "," << cylanders[i].index  << ") ";
    }
    
    cout << endl;
}

bool is_on(int a, int i){
    return a & (1 << i);
}

void toggle(int& a, int i, int j){
    int mask_i_j = 0;
    
    mask_i_j = mask_i_j | ((1 << (j+1)) -1);
    mask_i_j = mask_i_j & ~((1 << i) - 1);
    
    int x = a & mask_i_j;
    x =  (~x) & mask_i_j;
    a = a & (~mask_i_j);
    a = a | x;
}

int main(){
    int a = 0;
    toggle(a, 1, 3);
    
    for (int i = 8; i>=0; i--){
        cout << (is_on(a, i) ? "1" : "0");
    }
    
    cout << endl;

}

int const P = 3;
typedef array<int, P> MyObject;

vector<unordered_map<int, list<MyObject>>> find_all_matches(vector<MyObject>& lst){
    vector<unordered_map<int, list<MyObject>>> maps(P);
    
    for(int p = 0; p < P; p++){ //for each property of my object
        for(int i = 0; i<lst.size(); i++){ // for each object
            if(maps[p].find(lst[i][p]) != maps[p].end()){
                maps[p][lst[i][p]].push_back(lst[i]);
            } else {
                maps[p][lst[i][p]] = list<MyObject>{};
                maps[p][lst[i][p]].push_back(lst[i]);
            }
        }
    }
    
    return maps;
}