Write a function that takes two arrays as input, each array contains a list of A-Z; Your program should return True if the 2nd array is a subset of 1st array, or False if not.
For example: isSubset([A,B,C,D,E], [A,E,D]) = true isSubset([A,B,C,D,E], [A,D,Z]) = false isSubset([A,D,E], [A,A,D,E]) = true
This one is handy, sometimes may directly used inline. When size of superset is small, it works fine.
const isSubset = (a,b) => b.every(x => a.indexOf(x) >= 0);function isSubset(a,b){
const s = 'A'.charCodeAt(0);
let t = Array(26).fill(true);
for(let x of a) t[x.charCodeAt(0) - s] = false;
for(let x of b) if(t[x.charCodeAt(0) -s]) return false;
return true;
}The technique is the same as used in merge sort or finding unique element in an array. This modifies the original array, which may or may not be important.
function isSubset(a,b){
a.sort((x,y) => x-y);
b.sort((x,y) => x-y);
let i=0,j=0;
while(i<a.length && j<b.length){
if( a[i] < b[i]) i++;
else if( a[i] === b[j] ) i++, j++;
// if the array do not contain incompatible type
// e.g. 3 < undefined // always yield false
// this should be the case a[i] > b[i]
else return false;
}
return b.length === j;
}Assume the set of elements are orderable.
function bsearchMax(a,b,test){
// a is true and valid
while(b-a>1){
let mid = Math.floor((a+b)/2);
test(mid) ? a = mid : b = mid;
}
return a;
}
function isSubset(a,b){
a.sort( (x,y) => x-y);
for(let x of b){
let ix = bsearchMax(-1, a.length, y => a[y] <= x)
if( ix < 0 || a[ix] !== b ) return false;
}
return true;
}Depend on implementation, usually it is a hash set.
function isSubset(a,b){
let s = new Set(a);
for(let x of b) if(!s.has(x)) return false;
return true;
}Instead of checking has() on superset, we can also delete() on subset.
function isSubset(a,b){
let s = new Set(b);
for(let x of a) s.delete(x);
return s.size === 0;
}It may be worth mention that it is particularly easy to code in python.
def isSubset(a,b):
return set(b) <= set(a)function isSubset(a,b){
a.sort((a,b) => a-b);
b.sort((a,b) => a-b);
function run(ai,aj,bi,bj){
if(ai === aj) return bj-bi===0;
if(bi === bj) return true;
// out bound O( 1 )
if( b[bi] < a[ai] || a[aj] < b[bj] ) return false;
// divide both superset and subset into half
let bk = Math.floor((bi+bj)/2);
let ak = bsearchMin(ai, aj, i => b[bk] <= a[i] );
// cannot find b[bk] in a
if( ak === aj || b[bk] !== a[ak] ) return false;
return run(ai,ak,bi,bk) && run(ak,aj,bk+1,bj);
}
return run(0,a.length,0,b.length);
}function isSubset(a,b){
// pesudo code
let tree = new vEBTree();
for(let x of a) tree.add(x);
return b.every(x => tree.has(x));
}A probabilistic data structure. No false negative, but false positive. In this case, there may be wrong isSubset, but no isNotSubset.
Similar to hash set method, but with more than one hash. When superset is very large, and pre-processing is allowed. This method be handy to pass around as fast screening.
function isSubset(a,b){
// pesudo code
let s = new Set();
for(let x of a){
for(let hash of hashes) s.add(hash(x));
}
return b.every( x => hashes.every(hash => s.has(hash(x))));
}Obvisouly, subset can be divided and checked in parallel.
const cluster = require('cluster');
const nWorker = require('os').cpus().length;
const print = console.log.bind(console);
if (cluster.isMaster) {
// initialize input argument here
const a = new Array(1e6);
for (let i = 0; i < a.length; i++) a[i] = Math.floor(Math.random() * 1e10);
const b = a.slice(0, 1e4);
const batchSize = Math.ceil(b.length / nWorker);
// fork and initialize workers
let workers = [];
for (let i = 0; i < nWorker; i++) {
const worker = cluster.fork();
worker.send(['superset', a]);
workers.push(worker);
}
let doneCnt = 0;
workers.forEach((worker, i) => {
worker.on('message', isSubset => {
if (isSubset) {
doneCnt++;
if (doneCnt === nWorker) {
workers.forEach(w => w.kill());
print(true);
}
}
else {
workers.forEach(w => w.kill());
print(false);
}
});
worker.send(['subset', b.slice(i * batchSize, (i + 1) * batchSize)]);
});
}
else if (cluster.isWorker) {
let a = new Set();
process.on('message', ([cmd, arg]) => {
if (cmd === 'superset') a = new Set(arg);
else if (cmd === 'subset') {
process.send(arg.every(x => a.has(x)));
}
});
}Similar to divide and conquer, but call the two subcall in parallel.
// pesudo code
function isSubset(a,b,callback){
a.sort((a,b) => a-b);
b.sort((a,b) => a-b);
function run(ai,aj,bi,bj,done){
if(ai === aj) return bj-bi===0;
if(bi === bj) return true;
// out bound O( 1 )
if( b[bi] < a[ai] || a[aj] < b[bj] ) return false;
// divide both superset and subset into half
let bk = Math.floor((bi+bj)/2);
let ak = bsearchMin(ai, aj, i => b[bk] <= a[i] );
// cannot find b[bk] in a
if( ak === aj || b[bk] !== a[ak] ) return false;
// pesudo code
let resCnt = 0;
let thread1 = new Thread(_ => run(ai,ak,bi,bk), (err, res) => {
if(err) return done(err);
if(!res) done(null, false);
if(++resCnt === 2) done(null, true);
});
let thread2 = new Thread(_ => run(ak,aj,bk+1,bj), (err, res) => {
if(err) return done(err);
if(!res) done(null, false);
if(++resCnt === 2) done(null, true);
});
}
return run(0,a.length,0,b.length, callback);
}