srterpe
BAN USERLook up an interval O(1)
Insert a new, non-overlapping interval O(n)
Insert an interval that partially overlaps some existing interval(s) O(n + k) where `k` is the number of overlapping intervals.
function IntervalCache () {
this.intervals = {}
}
IntervalCache.prototype.find = function (interval) {
return this.intervals[interval.join(',')]
}
IntervalCache.prototype.insert = function (interval) {
var intersections = []
for (var key in this.intervals) {
if (({}).hasOwnProperty.call(this.intervals, key)) {
if ((interval[1] >= this.intervals[key][0] && interval[1] <= this.intervals[key][1]) ||
(interval[0] >= this.intervals[key][0] && interval[0] <= this.intervals[key][1]) ||
(interval[0] < this.intervals[key][0] && interval[1] > this.intervals[key][1])) {
intersections.push(this.intervals[key])
delete this.intervals[key]
}
}
}
if (intersections.length === 0) {
this.intervals[interval.join(',')] = interval
return
}
var min = interval[0]
var max = interval[1]
while (intersections.length) {
interval = intersections.pop()
if (interval[0] < min) {
min = interval[0]
}
if (interval[1] > max) {
max = interval[1]
}
}
this.intervals[[min, max].join(',')] = [min, max]
}
var cache = new IntervalCache()
cache.insert([25,100])
cache.insert([250,550])
cache.insert([1000, 1200])
cache.insert([400, 700])
cache.insert([30, 60])
console.log(cache)
function isPrime (n) {
var d = 2
var factors = []
while (d * d <= n) {
var isFactor = false
var pow = 0
while (n % d === 0) {
isFactor = true
n /= d
pow += 1
}
if (isFactor) {
factors.push({ factor: d, pow: pow })
}
d += 1
}
if (n > 1) {
factors.push({ factor: n, pow: 1 })
}
return factors.length === 1 && Math.abs(factors[0].pow) === 1
}
module.exports = function (A) {
A.sort(function (a, b) {
if (a < b) {
return -1
} else if (a > b) {
return 1
}
return 0
})
var i, j
i = j = 0
var min = Infinity
for (; i < A.length;) {
var a = A[i]
if (isPrime(Math.abs(a))) {
j = i + 1
while (!isPrime(Math.abs(A[j])) && j < A.length) {
j++
}
if (j >= A.length) {
// No more primes
return min
}
var b = A[j]
var d = Math.abs(a - b)
if (min > d) {
min = d
}
i = j
} else {
i++
}
}
return min
}
function parseBrace (s) {
var modifier = ''
var i = 0
while (s.charAt(i).match(/[0-9]/)) {
modifier += s.charAt(i++)
}
var S = []
if (s.charAt(i) !== '[') {
throw new Error()
}
var j = i
S.push(s.charAt(j))
var argument = ''
while (S.length) {
j++
if (s.charAt(j) === '[') {
S.push(s.charAt(j))
} else if (s.charAt(j) === ']') {
S.pop()
}
if (S.length) {
argument += s.charAt(j)
}
}
return {
modifier_length: modifier.length,
modifier: parseInt(modifier, 10),
argument: argument
}
}
function tokenize (s) {
var tokens = []
var i = 0
while (i < s.length) {
if (s.charAt(i).match(/[0-9]/)) {
var token = parseBrace(s.slice(i))
i += token.modifier_length + 2 + token.argument.length
tokens.push(token)
} else {
tokens.push({argument: s.charAt(i++)})
}
}
return tokens
}
function parse (s) {
var tokens = tokenize (s)
var final = []
tokens.reverse()
while (tokens.length) {
var token = tokens.pop()
if (token.modifier_length) {
var moreTokens = tokenize(token.argument)
for (var j = 0; j < token.modifier; ++j) {
for (var k = moreTokens.length - 1; k > -1; --k) {
tokens.push(moreTokens[k])
}
}
} else {
final.push(token)
}
}
var S = ''
for (var i = 0; i < final.length; ++i) {
S += final[i].argument
}
return S
}
var s = '3[a2[bd]g4[ef]h]'
// s = '2[bd]g4[ef]h'
var solution = parse(s)
console.log(solution)
console.log("abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh")
$ node parse-braces.js
abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh
abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh
I don't understand why you even need a data structure for this at all:
Your req handler could simply look at the req time at the moment it responds and if the current time - req time > 1000ms just call req.write(429). req.close(). To me, that seems far simpler and faster than building a data structure to handle this.
/**
* `Snake` has three (3) possible commands: forward (F), right (R),
* and left (L).
* - F moves the head of the snake forward one (1) cell in the direction
* the head is currently facing
* - R moves the snake head to the right. The head can only move a
* maximum of 90 degrees from the base of the neck.
* - L rotates the snake head to the left. Again, the head can only
* rotate a maximum of -90 degrees from the base of the neck.
*
* The snake has a `head` which is located on a particular cell.
* Model this as an array of length 2 which contains [i, j] the
* coordinates that the head is currently located.
*
* The snake has a tail which is an arbitrary length array of
* 2-tuples that functions as a queue where the top of the queue
* is the [i,j] pair that represents the last segment of the tail.
*
* When the snake moves forward the last 2-tuple is popped from
* the tail and the previous head is enqueued, the new head is set
* explicitly.
*
* When the snake enters a space occupied by an apple the snake
* is considered to have "grown" therefore enqueue the previous
* head coordinates in the tail, set the new coordinates for the
* head and do not pop the last element for the tail.
*
* If the snake's next forward move would take it either into a
* "wall" or "edge" of the map or into a space already occupied
* by some segment of it's tail the snake is considered to be
* killed and the game is over.
*
* The grid itself may be represented by an MxN array of characters.
*/
Use a modified quick sort partition function:
function partition (index, A) {
var i = 0
var j = A.length - 1
var partition = A[index]
while (i <= j) {
while (A[i] < partition) {
i++
}
while (A[j] > partition) {
--j
}
if (i <= j) {
if (A[i] !== A[j]) {
return false
}
// Don't need all this...
//
// var tmp = A[j]
// A[j] = A[i]
// A[i] = tmp
// i++
// j--
}
}
return true
}
module.exports = function (sequence) {
for (var i = 0; i < sequence.length; ++i) {
if (partition(i, sequence)) {
return sequence[i]
}
}
return null
}
var sequence = [4, 3, 2, 7, 12, 11, 15, 22, 18, 9, 13]
var solution = module.exports(sequence)
console.log(solution)
module.exports = function (n) {
var S = ''
for (var i = 1; i < n; ++i) {
if (i % 2 !== 0) {
for (var j = 0; j < n - 1; ++j) {
S += i + ' '
}
S += (i + 1)
S += '\n'
} else {
S += (i + 1) + ' '
for (j = 0; j < n - 1; ++j) {
S += i + ' '
}
S += '\n'
}
}
return S
}
Using a hashmap is the obvious solution for O(n) time and O(n) extra space.
Without extra space you can sort the array in O(nLogn) then the following algorithm
procedure find_sum_k
for i in 0..Array.length - 1
let p = k - Array[i]
try find `j` index of `p` in Array via binary search
if j return true
}
return false
O(nlogn) time complexity, no additional space.
return false
These bowling rules seems weird: strike is usually 10 points plus the total of your next two balls. Which means if you throw three strikes in a row frame 1 is 30 points, frame 2 is 20 points plus your next ball and frame 3 is 10 pts plus the next 2 balls. For the max possible best score for a game of 300 pts.
Spare is also worth 10 points but you only add the total of your next 1 ball thrown. The rules as give don't make any sense to me since they don't suggest a cascade effect.
module.exports = function (s) {
var S = []
for (var i = 0; i < s.length; ++i) {
var char = s.charAt(i)
var j = S.length - 1
if (char === '\'' || char === '\"') {
if (S[j] === char) {
S.pop()
} else {
S.push(char)
}
continue
}
if (char === '(' || char === '{') {
S.push(char)
}
if (char === ')') {
if (S[j] === '(') {
S.pop()
continue
} else {
return false
}
}
if (char === '}') {
if (S[j] === '{') {
S.pop()
continue
} else {
return false
}
}
}
return S.length === 0
}
var s = '\"A(\'\')B\"'
var solution = module.exports(s)
console.log(solution)
Use a regular expression in `g` mode, also deal with the substring 'b'
module.exports = function (s, l) {
var tmp = []
for (var i = 0; i < l.length; ++i) {
if (l[i] === 'b') {
tmp.unshift('b')
} else {
tmp.push(l[i])
}
}
for (i = 0; i < tmp.length; ++i) {
s = s.replace(new RegExp(tmp[i], 'g'), '<b>$&</b>')
}
return s
}
var solution = module.exports('HelloWorld HelloWorld', ['el', 'b', 'rl'])
console.log(solution)
Any valid topological sort of the graph will suffice.
function sort (G, vertex, visited, stack) {
var v = G.vertex(vertex)
var i = v.id()
visited[i] = true
var neighbors = v.neighbors()
for (var j = 0; j < neighbors.length; ++j) {
var w = G.vertex(neighbors[j])
if (!visited[w.id()]) {
sort (G, neighbors[j], visited, stack)
}
}
stack.push(vertex)
}
module.exports = function (G, vertex) {
var S = []
var visited = []
for (var i = 0; i < G.length; ++i) {
visited[i] = false
}
sort(G, vertex, visited, S)
return S
}
var G = [
[0, 1, 0, 0],
[0, 0, 1, 1],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
var vertexes = ['A', 'B', 'C', 'D']
G.vertex = function (v) {
var i = vertexes.indexOf(v)
return {
id: function () {
return i
},
neighbors: function () {
var neighbors = []
var row = G[i]
for (var j = 0; j < row.length; ++j) {
if (row[j]) {
neighbors.push(vertexes[j])
}
}
return neighbors
}
}
}
var solution = module.exports(G, 'A')
console.log(solution)
$ node topological-sort.js
[ 'C', 'D', 'B', 'A' ]
Use encodeURIComponent:
{{
function serialize (S) {
var s = []
for (var i = 0; i < S.length; ++i) {
s.push(encodeURIComponent(S[i])
}
return s.join(';')
}
function deserialize (s) {
var S = s.split(';')
for (var i = 0; i < S.length; ++i) {
S[i] = decodeURIComponent(S[i])
}
return S
}
}}}
This solution rests on calculating the required distance of the next move given a direction and the current position (i,j) in the matrix.
var rightWas = null
var downWas = null
function calculateNextDistance(direction, i, j, matrix) {
var distance = 0
switch (direction) {
case 'right':
// Label the columns of the matrix (1, 2, 3...n).
// Starting from a `virtual` 0th column (at index -1),
// when you go `right` you will always go row length of
// the matrix - (2 * column #) elements
var row_length = matrix[0].length
distance = row_length - (2 * (j + 1))
rightWas = distance
break
case 'left':
// When you go left, you will always need to do
// so a distance of -1 of the distance you went
// right
distance = rightWas - 1
break
case 'down':
// Label the rows (0, 1, 2..n-1). When going `down`
// you will always go column length of the matrix
// - ((2 * row #) + 1) elements
var column_length = matrix.length
distance = column_length - ((2 * i) + 1)
downWas = distance
break
case 'up':
// The distance you need to go back up is
// always -1 of the distance you went down.
distance = downWas - 1
break
default:
throw new Error('Unknown direction specified.')
}
return distance
}
module.exports = function (matrix) {
var i = 0
var j = -1
var direction = ['right', 'down', 'left', 'up']
var offset = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0]
]
var k = 0
var solution = ''
if (!matrix.length || !matrix[0].length) {
return solution
}
var d = calculateNextDistance(direction[k], i, j, matrix)
// While there is still remaining distance to go, keep going.
while (d > 0) {
for (var q = 0; q < d; ++q) {
i += offset[k][0]
j += offset[k][1]
solution += matrix[i][j] + ' '
}
k++
if (k >= direction.length) {
k = 0
}
d = calculateNextDistance(direction[k], i, j, matrix)
}
return solution
}
var matrixes = [[
// NxN Matrix
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
], [
// NxM Matrix (N < M)
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
[10, 11, 12]
], [
// NxM Matrix (N > M)
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
], [
// NxM Matrix (M = 1)
[1, 2, 3, 4]
], [
// NxM Matrix (N = 1)
[1],
[2],
[3],
[4]
], [
// Empty Matrix
]
]
for (var m = 0; m < matrixes.length; ++m) {
var solution = module.exports(matrixes[m])
console.log(['CASE #', m + 1, ': ', solution].join(''))
}
$ node spiral.js
CASE #1: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
CASE #2: 1 2 3 6 9 12 11 10 7 4 5 8
CASE #3: 1 2 3 4 8 12 11 10 9 5 6 7
CASE #4: 1 2 3 4
CASE #5: 1 2 3 4
CASE #6:
The trivial O(n^2) solution is for each index `i` in haystack iterate to `j` (where `j` == `i` + `needle.length`) and determine if the substring(i,j) is an anagram of needle.
This is an O(n) solution:
function clone (target) {
var o = {}
for (var key in target) {
if (({}).hasOwnProperty.call(target, key)) {
o[key] = target[key]
}
}
return o
}
module.exports = function (needle, haystack) {
var i, j, NEEDLE = {}
var solutions = []
for (i = 0; i < needle.length; ++i) {
if (NEEDLE[needle.charAt(i)]) {
NEEDLE[needle.charAt(i)]++
} else {
NEEDLE[needle.charAt(i)] = 1
}
}
i = j = 0
var l = needle.length
for (; i <= haystack.length - l;) {
var o = clone(NEEDLE)
var char = haystack.charAt(i)
// if the character is not in needle then increment
// `i` and continue this does not start a possible
// anagram
if (!o[char]) {
i++
continue
}
o[char]--
var valid = true // is this substring from i, j of length l
// a valid anagram
for (j = 1; j < l;) {
char = haystack.charAt(i + j)
if (!o[char]) {
valid = false
break
}
o[char]--
j++
}
if (!valid) {
i++
continue
}
solutions.push(i)
// The current substring haystack(i,j) of length l
// is a valid anagram
// it stands to reason that if charAt(j + 1) === charAt(i)
// then that is a valid anagram too.
j = i + l - 1
while (haystack.charAt(j + 1) === haystack.charAt(i) && j + 1 < haystack.length) {
i++
j++
solutions.push(i)
}
i++
}
return solutions
}
var needle = 'abc'
var haystack = 'dabcabebacab'
var solutions = module.exports(needle, haystack)
console.log(solutions)
west12as, assuming you know the query in advance that would probably be the best solution.
Assuming you don't:
I would think your "dictionary" should be an array of objects that map the word to a corresponding suffix-trie of the word. This will allow you to quickly determine if the query is a substring of a particular word, and the suffix-trie can also provide the index of the substring within in the word.
This doesn't solve the problem of searching millions of dictionary entries though.
Depending on the distribution of characters in the dictionary entries (is it common to have "a", "b", "c" but not "abc", etc) you might be able to create a hashmap where the values are indexes into the dictionary array and the keys are hashed by taking only the unique letters in each string and alphabetizing them "abcabcf" -> "abcf". Then you could create another suffix-trie for each of these keys and quickly determine that a given key's indexes _might_ contain the searched for query:
"abcf" contains substring "abc" -> points to indexes D[0, 1]
D[0] = { word: "fabc", "trie": X}
D[1] = {word: "facb", "trie": Y
...
D[1M] = {word: "qpert", "trie": Z }
Only need to search the suffix-tries of D[0], D[1] for "abc"
Of course this offers little benefit if it's quite common to have the chars "a", "b", "c" somewhere but not necessarily as a sequence.
/**
* Given an `N`x`N` Boolean matrix, find how many true
* regions there are in the matrix.
*/
// Define a `true region` as any contiguous set of
// true elements such that the true elements are
// touching either horizontally, vertically, or
// diagonally.
// For each `i`,`j` element in the matrix, if it is
// `true` mark it as "unvisited" and put it in the
// search set.
// Set `r` to be 0, the number of unique regions.
// While there are elements in the search set,
// take an element from the search set, if it
// is "visited", discard it, if it is "unvisited"
// mark it as "visited", and put it in the
// working set and increment `r`.
// While there are elements in the working set,
// take the next element from the working set,
// if it has any `true` neighbors among it's
// 8 possible neighbors, mark those neighbors
// as "visited" and add them to the working
// set.
// Return `r` the number of contiguous true regions of
// the `N`x`N` matrix.
Runtime for this is O(n x m) where `n` is the number of integers in all lists and `m` is the number of unique pairs of lists. Worst case performance is when all lists are exactly the same.
function hash (pair) {
return pair.join(',')
}
function pair (list) {
var i = 0
var j = i + 1
var pairs = []
for (; j < list.length; j = ++i + 1) {
while (j < list.length) {
pairs.push([list[i], list[j++]])
}
}
return pairs
}
module.exports = function (lists) {
var i = 0
var list_ids = []
for (; i < lists.length; ++i) {
list_ids[i] = i
}
var list_pairs = pair(list_ids)
var pair_map = {}
for (i = 0; i < list_pairs.length; ++i) {
pair_map[hash(list_pairs[i])] = 0
}
var elements = {}
for (i = 0; i < lists.length; ++i) {
var list = lists[i]
for (var j = 0; j < list.length; ++j) {
var element = list[j]
if (!elements[element]) {
elements[element] = [i]
} else {
var l = elements[element].length
if (elements[element][l - 1] !== i) {
elements[element].push(i)
}
}
}
}
for (var key in elements) {
if (({}).hasOwnProperty.call(elements, key)) {
element = elements[key]
if (element.length > 1) {
var pairs = pair(element)
for (i = 0; i < pairs.length; ++i) {
var pair_hash = hash(pairs[i])
pair_map[pair_hash]++
}
}
}
}
var solutions = []
for (key in pair_map) {
if (({}).hasOwnProperty.call(pair_map, key)) {
if (pair_map[key] >= 3) {
solutions.push(key)
}
}
}
return solutions
}
var solutions = module.exports([
[1, 2, 3, 4, 5, 6],
[2, 7, 4, 5],
[2, 5, 1, 11, 12],
[11, 13, 15, 12, 4, 7, 2]
])
console.log(JSON.stringify(solutions))
I'm a bit confused about the last part.
The MAX 32-bit Int is `2147483647`. 'Z' is only `134217700`. Therefore, give a random distribution of inputs a significant number of possible inputs would divide into 'Z' at least once....therefore it makes sense to have an algorithm like:
var s = ''
while (input < 0) {
for ( x = Z..A ) {
if (input >= x.value) {
input -= x.value
s += x.char
continue
}
}
And you may as well memoize it while you do it.
- srterpe January 09, 2017function traverse (node, path, length) {
if (!node) {
return {
path: path,
length: length
}
}
var l = traverse(node.left, path, length)
var r = traverse(node.right, path, length)
var o = {}
if (l.length >= r.length) {
path = l.path
length = l.length
direction = ' L'
} else {
path = r.path
length = r.length
direction = ' R'
}
o.length = ++length
o.path = (path.length ? direction + '->' : '') + path
o.path = node.value + o.path
return o
}
module.exports = function (root) {
var path = ''
var length = 0
return traverse(root, path, length)
}
var c = {}
c.value = 3
c.right = c.left = null
var b = {}
b.value = 7
b.right = b.left = null
var a = {}
a.value = 2
a.left = null
a.right = c
var root = {}
root.value = 4
root.left = a
root.right = b
var longest = module.exports(root)
console.log(longest.path, ', ', longest.length)
Time: O(n + m)
Space: O(n + m)
module.exports = function (A, B) {
// Let's assume that A & B are both sorted, if not
// we have to deal with it.
var T = []
// Merge the arrays into T
// maintaining the order
var i, j
i = j = 0
for (; i < A.length; ++i) {
if (j >= B.length) {
T.push({ value: A[i], source: A })
continue
}
if (A[i] < B[j]) {
T.push({ value: A[i], source: A })
} else {
while (B[j] < A[i]) {
T.push({ value: B[j++], source: B })
}
T.push({ value: A[i], source: A })
}
}
for (; j < B.length; ++j) {
T.push({ value: B[j], source: B })
}
var delta = Infinity
for (i = 0, j = 1; j < T.length; ++i, ++j) {
// If we care to restrict this delta to different source arrays...
if (T[i].source === T[j].source) {
console.log('Skipping `' + T[i].value + '` & `' + T[j].value + '`')
continue
}
var d = [Math.abs(T[i].value - T[j].value), Math.abs(T[j].value - T[i].value)]
for (var k = 0; k < d.length; ++k) {
if (d[k] === 0) {
return 0 //`0` is of course the minimum delta
}
if (d[k] < delta) {
delta = d[k]
}
}
}
return delta
}
var A = [-3, 1, 999]
var B = [-1, 2, 3]
var delta = module.exports(A, B)
console.log(delta)
// $ node minimum-delta.js
// Skipping `2` & `3`
// 1
module.exports = function (haystack, needle) {
var i, j, m
i = 0
j = haystack.length - 1
m = Math.floor(haystack.length / 2)
while (i <= j) {
if (haystack[m] === needle) {
return true
}
if (haystack[m] < needle) {
i = m + 1
} else {
j = m - 1
}
m = i + Math.floor((j - i + 1) / 2)
}
return false
}
var A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for (var i = 0; i < 12; ++i) {
var bool = module.exports(A, i)
console.log('Searching for `' + i + '`, .... ' + bool)
}
// $ node binary-search.js
// Searching for `0`, .... false
// Searching for `1`, .... true
// Searching for `2`, .... true
// Searching for `3`, .... true
// Searching for `4`, .... true
// Searching for `5`, .... true
// Searching for `6`, .... true
// Searching for `7`, .... true
// Searching for `8`, .... true
// Searching for `9`, .... true
// Searching for `10`, .... true
// Searching for `11`, .... false
function traverseDiagonal(n, m, matrix, sequence) {
while (matrix[n][m] !== undefined) {
sequence.push(matrix[n][m++])
if (matrix[--n] === undefined) {
return
}
}
}
module.exports = function (matrix) {
var sequence = []
var N = matrix.length
var M = matrix.length > 0 ? matrix[0].length : null
if (M === null) {
throw new Error('Length of `M` cannot be zero.')
}
var m, n
m = n = 0
for (; n < N; ++n) {
traverseDiagonal(n, m, matrix, sequence)
}
n--
m++
for (; m < M; ++m) {
traverseDiagonal(n, m, matrix, sequence)
}
return sequence
}
var matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
var sequence = module.exports(matrix)
console.log(sequence.toString())
module.exports = function (n, m) {
var N = n.toString()
var M = m.toString()
// generate mins
var minN, minM, maxN, maxM
minN = minM = maxN = maxM = ''
for (var i = 0; i < N.length; ++i) {
var char = N.charAt(i)
if (char === '6') {
char = '5'
}
minN += char
}
for (i = 0; i < M.length; ++i) {
char = M.charAt(i)
if (char === '6') {
char = '5'
}
minM += char
}
//generate maxes
for (var i = 0; i < N.length; ++i) {
var char = N.charAt(i)
if (char === '5') {
char = '6'
}
maxN += char
}
for (i = 0; i < M.length; ++i) {
char = M.charAt(i)
if (char === '5') {
char = '6'
}
maxM += char
}
minN = parseInt(minN, 10)
minM = parseInt(minM, 10)
maxN = parseInt(maxN, 10)
maxM = parseInt(maxM, 10)
console.log(n, m, minN, minM, maxN, maxM)
return {
min: minN + minM,
max: maxN + maxM
}
}
var ans = module.exports(645, 666)
console.log(ans)
function magicFunction (char, font) {
return font.getDimensions(char)
}
var fonts = [/* font1, font2, font3, .... */]
module.exports = function (s, screenWidth, screenHeight) {
// Assume fonts are sorted largest to smallest...
for (var i = 0; i < fonts.length; ++i) {
var font = fonts[i]
var screenRemainingHeight = screenHeight
var screenRemainingWidth = screenWidth
var maxCharacterHeightLine = 0
var lineWidth = 0
for (var j = 0; j < s.length; ) {
var char = s[j]
var d = magicFunction(char, font)
if (d.height <= screenRemainingHeight) {
maxCharacterHeightLine = max(maxCharacterHeightLine, d.height)
lineWidth += d.width
if (lineWidth > screenRemainingWidth) {
// Start a new line
// don't increment j
lineWidth = 0
screenRemainingHeight -= maxCharacterHeightLine
} else {
// it fits on this line, get next character in `s`
++j
}
} else {
// Decrease the font-size
break
}
}
if (j === s.length) {
return font.size
}
}
return -1
}
This solution is `O(M(n+k))` where `M` is the length of the dictionary, `n` is the average length of a word in the dictionary (in English language that would be 5.1) and `k` is the length of the input string. More efficient irl, as the length of `k` grows.
/**
* Given a string and dictionary of words, form a word by removing
* minimum number of characters. Characters can be removed `in-order`
* only.
*/
module.exports = function (dictionary, S) {
var map = {}
for (var i = 0; i < dictionary.length; ++i) {
var l = dictionary[i].length
map[l] = map[l] || []
map[l].push(dictionary[i])
}
l = S.length
while (l > 0) {
var spelled = []
var offset = S.length - l
if (map[l]) {
var words = map[l]
for (i = 0; i < words.length; ++i) {
var bool = true
var chars = {}
for (j = 0 + offset; j < S.length; ++j) {
chars[S.charAt(j)] = ++chars[S.charAt(j)] || 1
}
for (var j = 0; j < words[i].length; ++j) {
var word = words[i]
var c = word.charAt(j)
if (chars[c]) {
chars[c]--
} else {
bool = false
break
}
}
if (bool) {
spelled.push(words[i])
}
}
}
--l
if (spelled.length) {
l = 0
}
}
return spelled.length ? spelled : -1
}
var dictionary = [
'bit',
'tab',
'cat',
'dog',
'rabbit',
'hat',
'car',
'harm',
'giraffe'
]
var Z = module.exports(dictionary, 'abbitcar')
console.log(Z) // => 'car'
Z = module.exports(dictionary, 'dtbarbi')
console.log(Z) // => 'rabbit'
Z = module.exports(dictionary, 'farigfe')
console.log(Z) // => 'giraffe'
Z = module.exports(dictionary, 'ablonol')
console.log(Z) // => -1
function length (A) {
return A.length
}
function peek (A) {
return A[length(A) - 1]
}
function push (A, x) {
return A.push(x)
}
function pop (A) {
return A.pop()
}
module.exports = function (A) {
var B = []
if (length(A) === 1) {
// A is trivially sorted...
return A
}
push(B, pop(A))
// B is trivially sorted in descending order
while (length(A)) {
var a = pop(A)
var b = peek(B)
var i = 0
while (b < a) {
push(A, pop(B))
b = peek(B)
++i
}
push(B, a)
for (; i > 0; --i) {
push(B, pop(A))
}
}
// A is empty, B is in descending order
while (length(B)) {
push(A, pop(B))
}
return A
}
var A = module.exports([4, 7, 2, 8, 1, 6, 5])
console.log(A)
module.exports = function (L) {
var A = [];
var ptr = L;
while (ptr.next) {
ptr = ptr.next;
A.push(ptr.value)
}
for (var i = A.length - 1, ptr = L.next; i > -1; --i, ptr = ptr.next) {
if (A[i] !== ptr.value) {
return false
}
}
return true
}
var ans = module.exports({
next: {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: null
}
}
}
});
console.log(ans);
function getChildren (map, name, level) {
if (level === 1) {
return map[name]
}
var children = []
for (var i = 0; i < map[name].length; ++i) {
children = children.concat(getChildren(map, map[name][i], level - 1));
}
return children;
}
module.exports = function (A, name, level) {
var map = {}
for (var i = 0; i < A.length; ++i) {
var child = A[i][0];
var father = A[i][1];
map[father] = map[father] || [];
map[father].push(child);
}
var children = getChildren(map, name, level);
return [children, children.length];
}
var children = module.exports([
['Ram', 'Syam'],
['Akil', 'Syam'],
['Nikil', 'Ram'],
['Subhash', 'Ram'],
['Karthik', 'Akil']
], 'Syam', 2);
console.log(children);
var data = {
'AAA': ['BBB', 'CCC', 'EEE'],
'CCC': ['DDD'],
}
function rootManagers (data) {
var subordinates = {}
for (var manager in data) {
if (({}).hasOwnProperty.call(data, manager)) {
data[manager].sort()
for (var i = 0; i < data[manager].length; ++i) {
subordinates[data[manager][i]] = true
}
}
}
var rootLevelManagers = []
for (manager in data) {
if (({}).hasOwnProperty.call(data, manager)) {
if (!subordinates[manager]) {
rootLevelManagers.push(manager)
}
}
}
return rootLevelManagers.sort()
}
//console.log(rootManagers(data))
function print(employee, data, level) {
var A = []
A[level] = '-'
A.push(employee)
A = A.join(' ')
console.log(A)
var subordinates = data[employee]
if (!subordinates) {
return
}
for (var i = 0; i < subordinates.length; ++i) {
print(subordinates[i], data, level + 1)
}
}
function employeeList (data) {
var rootLevelManagers = rootManagers(data)
for (var i = 0; i < rootLevelManagers.length; ++i) {
print(rootLevelManagers[i], data, 0)
}
}
employeeList(data)
function findNextTargetChar (target, S, from) {
for (var i = from; i < S.length; ++i) {
if (S[i] === target) {
return i
}
}
return -1
}
function chunkedPalindrome (S) {
var midpoint = Math.ceil(S.length / 2)
if (S.length === 1) {
return '(' + S + ')'
}
var a, b
a = 0
var p, q
p = midpoint
var done = false
while (!done) {
p = findNextTargetChar(S[a], S, p)
if (p === -1) {
return '(' + S + ')'
}
b = a
q = p
var l = S.length - q
var match = true
for (var i = 0; i < l; ++i) {
if (S[b+i] === S[q+i]) {
} else {
match = false
p++
break
}
}
if (match) {
done = true
}
}
return [
'(',
S.slice(a,b + i),
')',
chunkedPalindrome(S.slice(b + i, q)),
'(',
S.slice(p, q + i),
')'
].join('')
}
console.log(chunkedPalindrome('merchant'))
console.log(chunkedPalindrome('volvo'))
console.log(chunkedPalindrome('ghiabcdefhelloadamhelloabcdefghi'))
console.log(chunkedPalindrome('ghighiabcdefhelloadamhelloabcdefghighi'))
function check (pattern, string) {
var map = {}
for (var i = 0; i < pattern.length; ++i) {
if (map[pattern[i]] === undefined) {
map[pattern[i]] = null
}
}
var string = string.split(' ')
if (pattern.length !== string.length) {
return false
}
for (i = 0; i < string.length; ++i) {
if (!map[pattern[i]]) {
map[pattern[i]] = string[i]
} else {
if (map[pattern[i]] !== string[i]) {
return false
}
}
}
return true
}
var pattern = ['a', 'b', 'b', 'a']
var string = 'cat dog dog cat'
console.log(check(pattern, string))
ZoomBA Guy (NoOne):
I don't think this is the most efficient way in this case. I believe the # of possible permutations of sorted characters grows at a faster rate as length of character array increases (n!) than the dictionary likely would (which probably has max 50,60,100K words).
I propose this, which is O(p*(n +m)) where p is the length of the dictionary, n is the length of the character array, and m is the average word length of the dictionary.
function valid (chars, dict) {
var spellables = []
for (var j = 0; j < dict.length; ++j) {
var map = {}
for (var i = 0; i < chars.length; ++i) {
if (map[chars[i]]) {
map[chars[i]] += 1
} else {
map[chars[i]] = 1
}
}
var bool = true
for (var k = 0; k < dict[j].length; ++k) {
if (!map[dict[j].charAt(k)]) {
bool = false
break
} else {
map[dict[j].charAt(k)]--
}
}
if (bool) {
spellables.push(dict[j])
}
}
console.log(spellables)
}
valid(['e', 'o', 'b', 'a', 'm', 'g', 'l'], [
'go',
'bat',
'me',
'eat',
'goal',
'boy',
'run'
]);
function copy (A, i, j) {
var B = []
for (var k = 0; i <= j; ++i, ++k) {
B[k] = A[i]
}
return B
}
function shiftForward (A, i, j) {
var d = j - i + 1
var k = j + 1
for (; k < A.length; ++k) {
for (var l = 1; l <= d; ++l) {
A[k - l] = A[k]
}
}
}
function shiftBack (A, i, j) {
var d = j - i + 1
var k = j - d
for (; k >= 1; --k) {
for (var l = 1; l <= d; ++l) {
A[k + l] = A[k]
}
}
}
function write(A, B, i, j) {
var k = 0
for (; k < B.length; ++k) {
A[i + k] = B[k]
}
}
function type2 (A, i, j) {
var B = copy(A, i, j)
shiftForward(A, i, j)
write(A, B, A.length - 1 - (j - i))
}
function type1(A, i, j) {
var B = copy(A, i, j)
shiftBack(A, i, j)
write(A, B, 1)
}
//var A = [null, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
//type1(A, 3, 4)
//type2(A, 1, 2)
//
//console.log(A)
function query (N, M) {
var A = [null]
for (var i = 1; i <= N; ++i) {
A[i] = i
}
for (i = 0; i < M.length; ++i) {
var q = M[i].split(' ')
for (var j = 0; j < q.length; ++j) {
q[j] = parseInt(q[j], 10)
}
if (q[0] === 1) {
type1(A, q[1], q[2])
} else {
type2(A, q[1], q[2])
}
}
console.log(A)
}
query(10, [
'1 3 5',
'2 1 2'
])
function select (M, stacks, selections) {
var selecteds = []
if (!M) {
return selections
} else {
var _stacks = stacks
var stacks = []
for (var i = 0; i < _stacks.length; ++i) {
stacks[i] = _stacks[i].slice()
}
var _selections = selections
for (i = 0; i < stacks.length; ++i) {
var stack = stacks[i]
var popped = stack.pop()
selections = _selections.slice()
selections.push(popped)
selecteds.push(select(M - 1, stacks, selections))
}
var local_max = 0;
var local_selected = null
for (i = 0; i < selecteds.length; ++i) {
var selected = selecteds[i]
var sum = 0
for (var j = 0; j < selected.length; ++j) {
sum += selected[j]
}
if (sum > local_max) {
local_max = sum
local_selected = selected
}
}
return local_selected
}
}
function selectMaximum (M, stacks) {
var selected = select(M, stacks, [])
var sum = 0
for (var i = 0; i < selected.length; ++i) {
sum += selected[i]
}
console.log(selected, sum)
}
selectMaximum(3, [[1,1,100,3],[2000,2,3,1],[10,1,4]])
Seems weird. I would say convert to min-heap and while you are looking at each node calculate the sum of the tree. Then pop-off `k` elements from the min-heap and subtract from the sum. But there's an implicit tree traversal there.
I don't see how you can calculate the sum of tree whose nodes you can't look at? Seems like a problem with the question.
var input = [[5,5], [2,2], [3,3], [3,4], [1,1]]
function addUnique () {
var args = [].slice.call(arguments)
var A = args.shift()
for (var i = 0; i < args.length; ++i) {
var found = false
for (var j = 0; j < A.length; ++j) {
if (A[j] === args[i]) {
found = true
break
}
}
if (!found) {
A.push(args[i])
}
}
}
function slope (point1, point2) {
return (point2[1] - point1[1])/(point2[0] - point1[0])
}
function intercept (point, m) {
var y = point[1]
var x = point[0]
// y = mx + b
// y - mx = b
// b = y -mx
return y - m * x
}
function find (points) {
var map = {}
for (var i = 0; i < points.length; ++i) {
var point = points[i]
for (var j = i + 1; j < points.length; ++j) {
var m = slope (point, points[j])
var b = intercept(point, m)
var equation = 'y=' + m + 'x+' + b
map[equation] = map[equation] || []
addUnique(map[equation], point, points[j])
}
}
var longest = ''
for (var key in map) {
if (({}).hasOwnProperty.call(map, key)) {
longest = longest || key
if (map[key].length > map[longest].length) {
longest = key
}
}
}
return [longest, map[longest].length, map[longest]]
}
console.log(find(input))
/**
* Given a number, return the count of numbers having non-repeating
* digits till that number starting from 1.
*
* ("Non-repeating digits" is ambiguous.
* Let's assume it means two consecutive digits can not be the same.
* If it means that all digits are unique the logic is very similar as well.)
*
*/
function count (n) {
var A = []
var i = 0
var r = n / (Math.pow(10, i))
while (r > 1) {
A[i++] = true
r = n / (Math.pow(10, i))
}
if (A.length === 1) {
console.log('Answer:' + n)
return
}
console.log(A)
var l = A.length - 1
for (i = 0; i < l; ++i) {
if (i === 0) {
A[i] = 9 // 9 ways to select 1 number 1-9
continue
}
A[i] = 10 - 1 // 10 ways to select any next digit
// except can't select the previous
// digit = 10 -1 = 9 ways
}
console.log(A)
var B = []
// Calculate out the sum for each of the powers of 10
// except the highest power of 10
// given n = 3456
// 1->9 9 ways
// 10->99 81 ways
// 100->999 729 ways
// etc.
for (i = 0; i < l; ++i) {
if (i === 0) {
B[0] = A[0]
} else {
B[i] = A[i] * B[i - 1]
}
}
console.log(B)
l = A.length - 1
// For the remainder we need to deal with each power of 10
// separately:
// 1000-2999
// 3000-3399
// 3400-3449
// 3450-3456
for (; l >= 0; l--) {
var base = Math.pow(10, l)
var to = Math.floor(n /base) * base
to -= l === 0 ? 0 : 1
console.log(to)
to = '' + to //convert to string
var sum = 1
for (i = 0; i <= l; ++i) {
sum = to.charAt(to.length - 1 - i) * sum
}
console.log(sum)
B.push(sum)
}
console.log(B)
sum = 0
// now sum everything up.
for (i = 0; i < B.length; ++i) {
sum += B[i]
}
console.log('Answer:' + sum)
}
count(3456) //Ans: 2562
count(7) //Ans: 7
count(22) //Ans: 20
count(100) //Ans: 90
count(99) //Ans: 90
count(37) //Ans: 34
Change calculate to reverse-polish notation:
calculate (operator, operand, operand, ...)
define an operator as an interface which exposes a #doOperation(operand...) method.
Operator.doOperation takes responsibility to ensure the correct # of operands are present and do the particular operation so
And whala, no matter how many operators your calculator supports, the code never changes.
- srterpe March 22, 2017