drake
BAN USERSample solution in C++
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
int findDifferent(const vector<int>& v) {
unordered_map<int, int> m;
for (const auto n : v) {
++m[n];
}
for (const auto& p : m) {
if (p.second != 3) {
return p.first;
}
}
return -1;
}
int main() {
vector<int> v {1,2,3,1,2,3,1,2,3,2};
int different = findDifferent(v);
cout << different << endl;
return 0;
}
Sample solution in C++
#include <vector>
#include <iostream>
using namespace std;
int findDuplicate(const vector<int>& v) {
double sum = 0;
for (const int num: v) {
sum += num;
}
double n = v.size();
sum -= ((n-1) * n) / 2;
return (int)sum;
}
int main() {
vector<int> v {1,2,3,3,4};
int duplicate = findDuplicate(v);
cout << duplicate << endl;
return 0;
}
Solution in C++
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <stack>
using namespace std;
struct Node {
string val;
vector<Node*> children;
};
class TreeSerializer {
static char DELIM;
stringstream _serialStream;
public:
string serializeTree(const Node* const root);
Node* deserializeTree(const string& serialStr);
protected:
void serializeInner(const Node* const root);
};
char TreeSerializer::DELIM = '!';
string TreeSerializer::serializeTree(const Node* const root) {
_serialStream.str("");
serializeInner(root);
return _serialStream.str();
}
void TreeSerializer::serializeInner(const Node* const root) {
if (root == nullptr) return;
_serialStream << root->val << DELIM
<< root->children.size() << DELIM;
for (const Node* const child : root->children) {
serializeInner(child);
}
}
Node* TreeSerializer::deserializeTree(const string& serialStr) {
if (serialStr.empty()) return nullptr;
istringstream iss(serialStr);
string token;
stack<Node*> pointers;
Node* pRoot = new Node;
pointers.push(pRoot);
while (getline(iss, token, DELIM)) {
Node* pNode = pointers.top();
pointers.pop();
pNode->val = token;
getline(iss, token, DELIM);
int childrenCount = stoi(token);
pNode->children = vector<Node*>(childrenCount);
for (int i = childrenCount - 1; i >= 0; --i) {
Node* pChild = new Node;
pNode->children[i] = pChild;
pointers.push(pChild);
}
}
return pRoot;
}
int main() {
Node* root = new Node;
root->val = "root";
Node* child1 = new Node;
child1->val = "child1";
Node* child2 = new Node;
child2->val = "child2";
Node* child11 = new Node;
child11->val = "child11";
root->children.push_back(child1);
root->children.push_back(child2);
child1->children.push_back(child11);
TreeSerializer serializer;
string serial = serializer.serializeTree(root);
cout << "Serial string: " << serial << endl;
Node* deserial = serializer.deserializeTree(serial);
cout << deserial->val << endl
<< deserial->children[0]->val << endl
<< deserial->children[1]->val << endl
<< deserial->children[0]->children[0]->val << endl;
return 0;
}
Sample solution in C++
#include <memory>
#include <random>
#include <iostream>
using namespace std;
template<typename T>
struct BTreeNode {
T data;
shared_ptr<BTreeNode> left;
shared_ptr<BTreeNode> right;
explicit BTreeNode(const T& data)
: left(nullptr), right(nullptr), data(data) {}
BTreeNode()
: BTreeNode(T()) {}
};
typedef BTreeNode<int> IntNode;
typedef shared_ptr<IntNode> IntNodePtr;
template<typename RandEng>
class RandomSelector {
int _count;
IntNodePtr _choice;
RandEng _randEng;
public:
RandomSelector(const RandEng& re);
IntNodePtr selectRandom(const IntNodePtr root);
protected:
void selectRandomInner(const IntNodePtr root);
};
template<typename RandEng>
RandomSelector<RandEng>::RandomSelector(const RandEng& re)
: _count(0), _choice(nullptr), _randEng(re) {}
template<typename RandEng>
IntNodePtr RandomSelector<RandEng>::selectRandom(const IntNodePtr root) {
_count = 0;
_choice = nullptr;
selectRandomInner(root);
return _choice;
}
template<typename RandEng>
void RandomSelector<RandEng>::selectRandomInner(const IntNodePtr root) {
if (root == nullptr) return;
++_count;
uniform_int_distribution<int> dist(1, _count);
int randInt = dist(_randEng);
if (randInt == 1) {
_choice = root;
}
selectRandomInner(root->left);
selectRandomInner(root->right);
}
int main() {
// make tree
IntNodePtr node1 = make_shared<IntNode>(1);
node1->left = make_shared<IntNode>(2);
node1->right = make_shared<IntNode>(3);
// setup random number generation
random_device randDev;
mt19937 randEng(randDev());
RandomSelector<mt19937> randSelector(randEng);
IntNodePtr selection = randSelector.selectRandom(node1);
cout << "Random choice: "<< selection->data << endl;
return 0;
}
Sample solution in C++
- drake August 05, 2015