> For the complete documentation index, see [llms.txt](https://notes.lirenxn.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://notes.lirenxn.com/2020/notes-04-03-hard-interview-question.md).

# Notes-04-03-Hard-interview-question

To sharpen your mind

### 3 Hard interview white board <a href="#id-3-hard-interview-white-board" id="id-3-hard-interview-white-board"></a>

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

#### Auto completion <a href="#auto-completion" id="auto-completion"></a>

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

```javascript
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 <a href="#k-th-largest-number" id="k-th-largest-number"></a>

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 <a href="#check-if-string-concatable-from-list-of-words" id="check-if-string-concatable-from-list-of-words"></a>

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)