{{ message }}

Instantly share code, notes, and snippets.

lazywithclass/blog-post.md

Last active Mar 21, 2017
[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:

```// 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.

13/66 pages.

Skip list

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.

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