40 - Lightbulb Challenge

Julian had a lightbulb challenge for me that was really cool. It turned into this bifurcating thought experiment about how, by various methods of “procrastination”, the performance tradeoffs of one method could be offloaded to another.

It was also another really interesting foray into how saving “diffs” or a history of changes is often a powerful method for saving only the information you need rather than mutating a huge amount of information in memory before you need to.

I have seen this concept come up also in two interviews I’ve had, so its certainly relevant.

// time: 
// lightbulbs of length n
// all lightbulbs start off
// my goal: class for system that has two operations:
// - isOn: returns true if a lightbulb at given index is on, otherwise false
lightbulb
// -toggle: toggles ALL lightbulbs in a range
Start, end
 
// binary search or some sort of tree could be helpful
 
// Brainstorm for more performant toggle
// encoded ranges
// start and end, is start or end in any existing range
 
// the array could be a set of numbers that records the range of that value and it’s alternating
 
// initial array of the starting values
// an array of ranges that represent changes in the form of a list of indexes that a toggle would be performed on
// apply all of the toggles that were on the index we were interested in
// we’d have to search n ranges that had been saved, and apply all of
// -> stack of tuples
// stack of all the indexes that would be effected
 
‘’’
//Stack
let arr = [1,2,3]
let last_el = arr.pop()
last_el = 1
 
//Queue 
let first_el = arr.shift()
first_el = 1
arr = [2,3]
‘’’
 
 
// toggle can remain performant by only passing a start and end of a range
// isOn, it can iterate through all of the tuples
// it can create a new data structure that instead of ranges of types ,all of the indexes in a queue
 
Note
// shift is really expensive
 
class LightSystem {
constructor(bulbNumber: number){
this.bulbs: boolean[]: array(bulbNumber).fill(false)
this.changes: boolean[][]
iterate through len of changes, and do this:
// changes = [[0,2], [3, 7], [0,1]]
// range = changes.shift()
// range = [0,2]
// changes = [[3, 7], [0,1]]
}
 
isOn(bulbIndex: number){
	If (bulbIndex < 0 || bulbIndex > this.bulbs.length){
throw new Error(“Index supplied to isOn method is out of range”)
}
 
	//return this.bulbs[bulbIndex]
	const initialValue = this.bulbs[bulbIndex]
	for (let i = 0; i < this.changes; i++){
		const start = this.changes[i][0]
		const end = this.changes[i][1
	if (bulbIndex >= start && bulbIndex <= end){
	this.bulbs[bulbIndex] = !this.bulbs[bulbIndex]
}
}
 
if (initialValue !== this.bulbs[bulbIndex]){
	this.changes.push([bulbIndex, bulbIndex])
}
 
return this.bulbs[bulbIndex]]
}
 
toggle(start: number, end: number){
	// inclusive of start and end
	for (const index of [start, end]){
	if (index < 0 || index > this.bulbs.length){
throw new Error(“Index supplied to isOn method is out of range”)
}
}
 
// For (let i = start; i <= end; i++){
//	this.bulbs[i] = !this.bulbs[i]
// }
this.change.push([start, end])
}
 
 
	
}
 
 
 
Notes
What is less than O(n) called??
 
//