sheng
BAN USER// Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
// For example:
// input = [(1, 4), (2, 3)]
// return 3
// input = [(4, 6), (1, 2)]
// return 3
// input = {{ 1, 4 }, { 6, 8 }, { 2, 4 }, { 7, 9 }, { 10, 15 }}
// return 11
function findStartLaterThan(sortedIntervals, value, startPos, endPos) {
var minIndex = startPos || 0
var maxIndex = endPos || sortedIntervals.length
while (maxIndex - minIndex > 0) {
var index = Math.floor((minIndex + maxIndex) / 2)
// console.debug('findStartLaterThan index=' + index)
if (sortedIntervals[index].start <= value && (!sortedIntervals[index + 1] || sortedIntervals[index + 1].start > value)) {
return index
} else if (sortedIntervals[index].start > value) {
maxIndex = index
} else {
minIndex = index
}
}
}
function insertInterval(sortedIntervals, interval) {
var index = findStartLaterThan(sortedIntervals, interval.start)
var endIndex = findStartLaterThan(sortedIntervals, interval.end, index)
if (sortedIntervals.length == 0) {
sortedIntervals.push(interval)
return
}
if (sortedIntervals[index].end >= interval.start) {
if (sortedIntervals[endIndex].end >= interval.end) {
if (index == endIndex) {
// the new interval is dropped
} else {
// index ... endIndex is merged into one, drop the new interval
sortedIntervals[index].end = sortedIntervals[endIndex].end
sortedIntervals.splice(index + 1, endIndex - index)
}
} else {
if (index == endIndex) {
sortedIntervals[index].end = interval.end
}
else {
sortedIntervals[index].end = interval.end
sortedIntervals.splice(index + 1, endIndex - index)
}
}
} else {
if (sortedIntervals[endIndex].end >= interval.end) {
if (index == endIndex) {
// Not possible
} else {
// index ... endIndex is merged into one, drop the new interval
sortedIntervals[endIndex].start = interval.start
sortedIntervals.splice(index + 1, endIndex - index - 1)
}
} else {
if (index == endIndex) {
sortedIntervals.splice(index + 1, 0, interval)
}
else {
sortedIntervals[endIndex].start = interval.start
sortedIntervals[endIndex].end = interval.end
sortedIntervals.splice(index + 1, endIndex - index - 1)
}
}
}
}
function count(randomIntervals) {
var sortedIntervals = [{ start: 0, end: 0 }]
for (var interval of randomIntervals) {
insertInterval(sortedIntervals, { start: interval[0], end: interval[1], })
}
var sum = 0
for (var interval of sortedIntervals) {
sum += interval.end - interval.start
}
return sum
}
console.log(count([[1, 4], [2, 3]]))
console.log(count([[4, 6], [1, 2]]))
console.log(count([[1, 4], [6, 8], [2, 4], [7, 9], [10, 15]]))
//LinkedList :
// Input: A > B > C > D > E
// Output: A > E > B > D > C
// A, [B,C,D,E] => [E,C,D,B]
// E, [C,D,B] => [B,D,C]
// B, [D,C] => [D,C]
class Node {
constructor(data) {
this.data = data
this.next = null
this.previous = null
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
add(data) {
let node = new Node(data)
if (!this.head) {
this.head = node
}
if (this.tail) {
this.tail.next = node
node.previous = this.tail
}
this.tail = node
this.length++
}
get(index) {
if (!this.head)
return null
if (index <= 0)
return this.head
if (index >= this.length-1)
return this.tail
let current = this.head
for (let i = 1; i <= index; i++) {
if (!current.next)
return null
current = current.next
}
return current
}
remove(index) {
let len = this.length
if(index == 0) {
let current = this.head
current.next.previous = null
this.head = current.next
this.length--
if(this.tail == current)
this.tail = current.next
current.next = null
return current
}
if (index >= len-1) {
let current = this.tail
current.previous.next = null
this.tail = current.previous
this.length--
if(this.head == current)
this.head = current.previous
current.previous = null
return current
}
let current = this.get(index)
current.previous.next = current.next
current.next.previous = current.previous
this.length--
current.next = null
current.previous = null
return current
}
switch(from, to) {
if (from == to)
return
let fromNode = this.get(from)
let toNode = this.get(to)
let data = fromNode.data
fromNode.data = toNode.data
toNode.data = data
}
print() {
let data = []
for(let current = this.head; current != null; current = current.next) {
data.push(current.data)
}
console.log(data)
}
}
const list = new LinkedList()
list.add('A')
list.add('B')
list.add('C')
list.add('D')
list.add('E')
for (let i = 1; i < list.length-2; i++) {
list.switch(i, list.length)
list.print()
}
// Given an array of numbers and position to stop, find the max value
// up to the stop. Then randomly return index of the max value.
function randomIndexOfMaxValue(data, pos) {
// Iterate to pos and find the max value
var indexes = []
var max = 0
for (var i = 0; i < Math.min(pos, data.length); i++) {
if (max < data[i]) {
max = data[i]
indexes = [i]
} else if (max == data[i]) {
indexes.push(i)
}
}
// randomly return index of max value
console.debug(indexes)
return indexes[Math.floor(Math.random() * indexes.length)]
}
console.log(randomIndexOfMaxValue([11, 30, 2, 30, 30, 30, 6, 2, 62, 62], 10))
// given an array w/ occupied slots, fill the rest slots
// e.g. given [4, 0, 0, 0, 0, 4, 0, 0], fill 0 w/ 1, 2, 3
function fillSlots(slots, digit) {
// console.debug(slots + ", digit: " + digit)
if (digit < 1)
console.log(slots)
if (slots.length == 0 || digit < 1) {
return slots;
}
var copySlots = []
var exist = false
for (var i = 0; i < slots.length - digit; i++) {
// console.debug(i+":"+slots[i] + ", digit: " + digit)
if (slots[i]) {
copySlots[i] = slots[i];
continue
}
// console.debug(copySlots)
if (slots[i + digit + 1]) {
copySlots[i] = slots[i];
continue
}
if (i + digit + 1 > slots.length - 1) {
copySlots[i] = slots[i];
continue
}
copySlots[i] = digit
for (var j = i + 1; j < slots.length; j++) {
copySlots[j] = slots[j]
}
copySlots[i + digit + 1] = digit
try {
fillSlots(copySlots, digit - 1)
// if (ret.length > 0)
// console.debug("<<< ret: " + ret)
copySlots[i] = 0
copySlots[i + digit + 1] = 0
exist = true
} catch (err) {
// console.debug(err)
copySlots[i] = 0
copySlots[i + digit + 1] = 0
}
}
if (!exist)
throw "E_INVALID_" + digit
}
function permutation(digit) {
var slots = [];
for (var i = 0; i < digit; i++) {
slots.push(0)
slots.push(0)
}
return fillSlots(slots, digit)
}
try {
permutation(7)
} catch (err) {
console.debug(err)
}
console.log('--end--')
// S = "ababab", then n=3, P= "ab"
// S = "xxxxxx", then n = 1, and P = "x"
// S = "aabbaaabba", then n = 2, and P = "aabba"
function findPattern(str) {
var pattern = '';
var n = 1;
for (var i = 0; i < str.length;) {
var step = pattern.length > 0 ? pattern.length : 1;
var test = str.substr(i, step);
if (test == pattern) {
// Possible a pattern
i += step;
n += 1;
} else {
i += 1;
pattern = str.substr(0, i);
n = 1;
}
}
return {n, pattern};
}
console.log("ababab => " + JSON.stringify(findPattern("ababab")))
console.log("xxxxxx => " + JSON.stringify(findPattern("xxxxxx")))
console.log("aabbaaabba => " + JSON.stringify(findPattern("aabbaaabba")))
// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []
function findLongestPrefix(str, index, dict, maxPrefixLen) {
var dictCopy = Object.assign({}, dict);
if (index >= str.length)
return [];
for (var i = maxPrefixLen; i > 0; i--) {
var candidate = str.substr(index, i);
if (dictCopy[candidate]) {
dictCopy[candidate]--;
try {
var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
return [candidate].concat(rest);
} catch(err) {
dictCopy[candidate]++;
}
}
}
throw error('E_INVALID_CHARS')
}
function breakWords(str, dict) {
// Get the max lengths of keys
var keys = Object.keys(dict);
var maxPrefixLen = 1;
for (var i = 0; i < keys.length; i++ ) {
if (keys[i].length > maxPrefixLen) {
maxPrefixLen = keys[i].length;
}
}
try {
return findLongestPrefix(str, 0, dict, maxPrefixLen)
} catch(error) {
return []
}
}
var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)
words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)
words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
- sheng August 22, 2019