tobi
BAN USER#include <string>
#include <iostream>
using namespace std;
void interleave(const string &a, const string &b, const string &prefix = string()) {
if (!a.empty())
interleave(a.substr(1), b, prefix + a.substr(0, 1));
if (!b.empty())
interleave(a, b.substr(1), prefix + b.substr(0, 1));
if (a.empty() && b.empty())
cout << prefix << "\n";
}
int main() {
interleave("AB", "CD");
}
C++ solution
vector<int> array_plusplus(const vector<int> &a) {
// up to which position propagates carray
int p = (int)a.size()-1;
while (p >= 0 && a[p] == 9)
--p;
// create result and copy for i<p and add +1 for i>=p
int offset = (p < 0 ? 1 : 0);
vector<int> res(a.size() + offset, 1);
for (int i = 0; i < (int)a.size(); ++i)
res[i+offset] = (a[i] + (i>=p))%10;
return res;
}
write through cache: write simultaneously in cache and underlying memory
look aside cache: read simultaneously from cache and underlying memory, use whatever is found first
They both have similar concepts in accessing more than one level in the cache hierarchy at once. They both try to improve speed:
* write-through by avoiding write back of full cache lines when there are no more free
* look aside by also reading 'through' the cache instead of first trying the cache and then the next level (that would be t_cache+t_mem instead of min(t_cache, t_mem))
They both do this optimization at the cost of higher bandwidth usage on underlying memory; they access the next cache hierarchy level on every write or read.
[Don't confuse look aside cache with TLB/Translation lookaside buffer. Thats an ordinary cache for a special puropse.]
C++ DP solutions with O(n) space and O(1) space
- tobi January 15, 2015