Notes-04-03-Hard-interview-question

To sharpen your mind

3 Hard interview white board

Ref: https://www.youtube.com/watch?v=QGVCnjXmrNg

Auto completion

Given a list of strings, with typed in partial query, output potential words.

In ['dog', 'dark', 'cat', 'door', 'dodge', 'do'], with input do, ['dog', 'door', 'dodge'] should be returned (NOT 'do'), number of letter k, list size n

Bruto iteration

Iterate for each letter input, O(kn)

Use trie

• For search: O(k) + O(n) = O(n)

• For build: O(ln), l being the average length of words

class Node{
	constructor(value, children){
		this.value = value;
		this.children = children || {};
	}

	addChild(node){
		this.children[node.value] = node;
	}
}

class Solve{
	constructor(data){
		this.trie = this.build(data);
	}

	rebuild(data){
		this.trie = this.build(data);
	}

    // Snippet build trie
	build(data){
		const root = new Node('');
		for(let word of data){
			let nodeItr = root;
			for(let letter of word){
				if(!nodeItr.children[letter]){
					nodeItr.children[letter] = new Node(letter);
				}
				nodeItr = nodeItr.children[letter]	
			}
			nodeItr.children['EOF'] = new Node('EOF');
		}
		return root;
	}

	getMatch(prefix, selfIncluded){
		let nodeItr = this.trie;
		let res = [];
		// Snippet: Traverse trie
		for(let letter of prefix){
			if(!nodeItr.children[letter]){
				return res;
			}
			nodeItr = nodeItr.children[letter];
		}
		res = this.getChildren(nodeItr).map(child => prefix + child.substr(1))
		if(!selfIncluded){
			res = res.filter(s => s !== prefix);
		}
		return res;
	}
	
	// Snippet recursion
	getChildren(node){
	    // End Condition
		if(node.value === 'EOF'){
			return [''];
		}
		// Do recurrsion
		const children = Object.keys(node.children).reduce((acc, key) => {
			return acc.concat(this.getChildren(node.children[key]));
		}, []);
		return children.map(child => node.value + child);
	}
}

// Tests
pb = new Solve(["do","dod","dog",'dark',"apple","dodge","door","doddle"]);
pb.getMatch('do');

pb.getMatch('dod');

pb.getMatch('dod', true);

Gotchas

• in Node REPL, use process.pwd() to check pwd

• in Node REPL, use require() works the same as in a file, if it does not work, check path

• in Node REPL, use require.cache = {} to reset the cache otherwise following require will use the cache

• in Node, use module.exports to properly export

K-th largest Number

Given list of numbers [5,7,2,3,4,1,6], find 3-th largest number

Bruto

• Traverse k times of array, each time return the largest one, O(kn)

• Sort first then get index, O(nlog)

(Max) Heap

• For build: O(n), average complexity from Calculus

• For search: pop k times, each pop traverse the tree depth logn: O(klogn)

Partition

1. Pick the last number as delimiter

2. Partition the array as left smaller right larger

3. Partition the right(larger) partition until the size of large partition (sum of right partitions) equals k

Check if string concatable from list of words

Given ['cats', 'cat', 'dog'] and "catsdog", get true as catsdog = cats + dog, case also possible as ahardlongword = a + hard + long + word

Bruto

c atsdog
    a tsdog
        t sdog
        ts dog
        tsd og
        tsdo g
            ...
    at sdog
    ats dog
    atsd og
    atsdo g
ca tsdog ...
cat sdog ...
cats dog ...
catsd og ...
catsdo g ...

O(n2^m)