Skip to content

Instantly share code, notes, and snippets.

@lazywithclass
Last active March 21, 2017 04:07
Show Gist options
  • Save lazywithclass/e7f6237f51e70c386997dbf168adce78 to your computer and use it in GitHub Desktop.
Save lazywithclass/e7f6237f51e70c386997dbf168adce78 to your computer and use it in GitHub Desktop.
[RC Diary] Interview preps, emptying the backlog (-88)

[RC Diary] Interview preps, emptying the backlog (-88)

Mock interviews

Print path in a graph

function getNeighbours(node) {
  if (node === 'C') return ['B', 'D']
  if (node === 'B') return ['Z', 'D']
  if (node === 'D') return ['E']
  if (node === 'E') return []
  if (node === 'Z') return []
  if (node === 'A') return ['B', 'C']
}

function isPath(start, end, path) {
  if (start == end) return console.log(path)
  getNeighbours(start).forEach(function(neighbour) {
    path.push(neighbour)
    isPath(neighbour, end, path.slice())
  })
  return false
}

isPath('C', 'E', [])

For some reason this does not work as I was expecting, or better, recursion doesn't work as I expected, so I am going to investigating on this and come back later.

Find anagrams of a word in an array

So for example given [ 'cat', 'hello', 'act', 'hell', 'tac' ] it should return [ 'cat', 'act', 'tac' ].

I did a naive implementation with O(n^2) time complexity, using

let isAnagram = (a, b) => 
  a.length === b.length && 
    a.split('').sort().join('') ==== b.split('').sort().join('')

and then two for loops paying attention that I

  • would not add an item to the array more than once
  • compared the correct strings moving forward the two indexes

Lazy evaluation

I've found a few useful resources:

What made it click for me was this example in SO:

// Not lazy
var add = (x, y) => x + y
var result = add(1, 2)  // Immediately evaluates to 3

// Lazy
var addLazy = (x, y) => () => x + y;
var result = addLazy(1, 2)  // Returns a thunk which *when evaluated* results in 3.

Where a thunk is a function that doesn't accept anything and returns something.

Out of the tar pit

13/66 pages.

Skip list

Faster linked lists.

This was one of the few times I've read an article in Wikipedia and understood right away what it was telling me:

A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly used values for p are 1/2 or 1/4). On average, each element appears in 1/(1-p) lists, and the tallest element (usually a special head element at the front of the skip list) in all the lists.

Average time complexity is O(logn) in average case while is O(n) in the worst case.

One other good resource is geeks for geeks.

Find the apartment

Found.

Plans

For the weekend

  • videos from Chomsky - find which ones are the best and get them
  • visual representation of Djikstra algorithm
  • "check that parens are balanced" exercise
  • make sure you find a solution for "print path in grap"

Backlog

  • still need some attention needed for timsort, radix sort
  • chapter 3 of the little schemer in Clojure
  • allow some time to think
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment