yunpeng
BAN USER//
// Created by Yunpeng Xu on 8/31/17.
//
#include "backtracking.h"
void backtracking(const string s, string &tmp, int start, vector<string> &ans) {
if (!tmp.empty()) {
ans.push_back(tmp);
}
unordered_set<char> set;
for (int i = start; i < s.length(); i++) {
if (set.find(s[i]) != set.end()) continue;
tmp.push_back(s[i]);
backtracking(s, tmp, i + 1, ans);
tmp.pop_back();
}
}
bool verifyResult(vector<string> &answers, vector<string> &expected) {
unordered_map<string, int> map;
for (string ans : answers) {
map[ans]++;
}
for (string exp : expected) {
if (map.find(exp) == map.end()) return false;
map[exp]--;
if (map[exp] < 0) return false;
}
for (auto item: map) {
if (item.second != 0) return false;
}
return true;
}
void testBackTracking(void) {
string s = "abc";
vector<string> expected = {
"a", "b", "c", "ab", "bc", "ac", "abc",
};
vector<string> ans;
string tmp = "";
backtracking(s, tmp, 0, ans);
if (!verifyResult(ans, expected)) {
cout << "failed backtracking test!" << endl;
} else {
cout << "passed backtracking test!" << endl;
}
}
Two considerations:
1. the coworker's memory usage pattern may be screwed by allocating too many noncontinuous memory blocks and leaving a large percentage of unallocated memory but cannot be utilized because of the external fragmentation.
2. the design of the memory manager you developed. This may be raised by the improper design of the memory manager by taking too much space for small allocated blocks. This design causes the internal fragmentation. For example, your design doesn't optimize the structure for small blocks allocated. If only 1 byte is allocated, but in order to maintain the alignment or meta information, you need to use another 15 bytes to satisfy the goal.
- yunpeng September 01, 2017