James Routley

Divya offered to conduct a mock interview with me. She asked me to create a MemTable, which is apparently a type of KV store in which, at some interval or after some threshhold of KVs, KV store is “flushed” and saved to the disk to preserve memory.

I was able to implement it in about 30 minutes and I think it went really well! Here was the finished result, and the feedback she gave me at the end.

// interface Entry {
//   val: number,
//   count: number
// }
 
class MemTable {
	// size: number
  thresh: number
  table: Map<number, number>
  stack: number[]
  
  // Order
  // timestamps
  // don't take a note of timestamps, necessary,
  // but take note of order or insertion
 
  // qs
  // should updates change the order of insertion
  // 
 
  // impl startegy
  // for every instertion, if an update, delete and recreate in map to get the entry to the end
 
  // flishing will look at the order to make sure that the operations happen in a certain 
 
 
  // first in last out print of operations
  // updates pop order of operations to the end
  // assume that maps DON'T maintain order
 
  // I could change the structure of the value to have a property that corresponded to a count
 
  // stack [key=1, key=2, key=3]
  // insert UPDATE -> filter out the key of an element that was updated, and then add the key back to the end of the stack
 
	constructor(){
    this.table = new Map()
    this.thresh = 5
    this.stack = []
	}
 
	insert(key: number, val: number): void {
    if (!this.table.has(key) && this.table.size >= this.thresh){
      this.flush()
    }
 
    if (this.table.has(key)){
      this.stack = this.stack.filter(e=>e!==key)
    }
    
    this.stack.push(key)
    this.table.set(key, val)
  }
 
	get(key: number): number {
    if (!this.table.has(key)) return -1
    return this.table.get(key)!
  }
 
	flush(): void {
 
    this.stack.forEach((key) => {
      const val = this.get(key)
      console.log(`key: ${key},value:${val}`)
    })
    
    // empty stuff
    this.table = new Map()
    this.stack = []
  }
}
 
const memTable = new MemTable()
memTable.insert(1, 10)
memTable.insert(2, 20)
memTable.insert(3, 30)
memTable.insert(4, 40)
memTable.insert(5, 50)
memTable.insert(6, 60)
 
 
 
// feedback
 
// pos
// read error messages which was good
// understand quirks of lang
// mentioning time complexity is good
// talked through implementation methodically
 
// neg
// made comments about how something was unexpected
// Be careful of "I don't know" or "I always forget..."
// ^ normal conversationally
// I CAN go back to something and say that I DO know something
// Build / run tests earlier
// If you write a lot of code that doesn't work, that's bad
// Test AS EARLY AS POSSIBLE
 
// Instead of overwriting my tests, re-use them
// Continuity will save time, AND help me catch edge cases more reliably
// Order of operations when i write stuff - taking on more challenging things before easier things
// Consider doing order of DIFFICULTY vs order of operations
  // The reason for this is that if you get stuck, you may forget the easy thing
  // There is also a case for wishful programming here
  // psuedocde placeholders and head quickly to the easy stuff
  // return to placeholders
 
 
// hw
// Why do I need to do bang operator in the .get method?

One of the bits of critical feedback was that I didn’t know why typescript throws a type error in this function:

get(key: number): number {
    // if (!this.table.has(key)) return -1
    return this.table.get(key) ?? -1
  }

I used the ! non-null assertion operator to ignore the warning, but didn’t have an especially deep understanding of this pattern, or perhaps anti-pattern

Looking further into it, it looks like the warning exists because the get method of a Map in TypeScript returns T | undefined, where T is the type of the values stored in the map. In this case, it’s number | undefined.

This is the intellisense message I get in VScode:

Type 'number | undefined' is not assignable to type 'number'.
  Type 'undefined' is not assignable to type 'number'.ts

Apparently Typescript doesn’t really have a way to see that the above line ensures that the function won’t return undefined.

My use of the non-null assertion operator is one way to get around this.

However, there are other ways that might be better.

I can use a type assertion: return this.table.get(key) as number This essentially does the same thing as a non-null assertion operator, as far as I can tell, as it’s overriding Typescript’s type system and saying ‘trust me, this is a number.’
I can use the nullish coalescence operator:

return this.table.get(key) ?? -1

I like this option the best. It allows me to handle both lines with just one line, and take advantage the the way map.get can return undefined in the way I think it was intended to be used. It’s completely typesafe, which is dope.

It’s important to be able to tell the nullish coalescence operator (??) from the logical OR operator (||).

x ?? y returns y only if x is null or undefined.
x || y would return y for any falsy value of x, including 0 and ”

They can both be useful, but could cause serious bugs if one is substituted for another.

33) KV Store Mock Interview with Div