# 2009-GHP-RM-WEB-FT Cookie Jar: Hash Tables, Algorithmic Thinking

## Put your question in a '##' tag below :point_down:

## From Ben: The Tortoise and Hare Algorithm is the most efficient way to solve the Looper problem. However, if we didn't use that algorithm, we could have used a Hash Table to our advantage here.

const isLoop = (linkedlist) => {
  // We use Map because JavaScript objects
  // Can't take objects as keys
  // Maps function the same way as objects
  let lookup = new Map()
  let currentNode = linkedlist.head
  while (currentNode !== null) {
    // Check if they key (the node) exists
    if (lookup.has(currentNode)) {
      return true
    } else {
      // Set the key to a value of 0 since we don't care about the value here
      lookup.set(currentNode, 0)
    }
    currentNode = currentNode.next
  }
  return false
}

## can you explain memoization like I am 5?

## Answer

We are going to do an example together after we get back from lunch!

But using Nicole's GPS example: We want to store a route from work to home so that every time we open up the GPS and we are at work, the GPS doesn't need to recalculate the route. Calculate once so we don't need to calculate it again and just grab it from storage.

Note: This, of course, is an over simplification of GPS as there are other factors to consider when calculating GPS routes like traffic, road obstructions, construction, etc.

## Re: Looper section in Pair Exercise: The two bottom hints specifically suggest setting one of the runners to the beginning of the list. Why?

## Answer

Lemme know if you can see [this diagram](https://drive.google.com/file/d/1CJxMNnTTs51vAkew2KFolNmSyZc1CxBr/view?usp=sharing). Make a copy of it for your own studying. This diagram shows all the steps of the Tortoise and Hare algorithm including the extra credit.

When we start one of the runners (pointers) from the beginning, one of the other things we need to do is "change the speed" of the fast runner to only step through one at a time. Once you step through, they will actually meet at the start of the cycle. Try it with other linked lists that have cycles. There is math behind why this works that is explained in [this video](https://drive.google.com/file/d/1CJxMNnTTs51vAkew2KFolNmSyZc1CxBr/view?usp=sharing).

Do lemme know if you want me to explain it further.

## I am not sure what ' jumps[i] = Math.min(jumps[i], jumps[j] + 1) ' means: to my understanding, jumps[j] is inifinity? So what does comparing a jumps[i](a reachable past jump), with inifinity + 1?

## also Here is my code

const minJumps = arr => {
  let minJumpArray = [0]
  let tempTrack = []
  for (let j = 1; j < arr.length; j++) {
    for (let i = 0; i < j; i++) {
      if (i + arr[i] >= j) {
        tempTrack.push(minJumpArray[i] + 1)
      }
    }
    minJumpArray.push(Math.min(...tempTrack))
    tempTrack = []
  }
  return minJumpArray[minJumpArray.length - 1]
};

## it past the test but not sure if it is right.

## Answer