outco warmup

linked_list.js

class Node {
  constructor(id) {
    this.id = id;
    this.next = null;
  }
}

let head = new Node(5);
// head.next = new Node(3);
// head.next.next = new Node(22);
// head.next.next.next = new Node(4);
// head.next.next.next.next = new Node(71);


// console.log(head);



function randomNode(head) {
  let result = head.id;
  let count = 0;
  
  let current = head;
  
  while (current !== null) {
    count++;
    if (Math.random() < (1 / count)) {
      result = current.id;
    }
    current = current.next;
  }
  
  return result;
}



function prove() {
  let i = 1000;
  
  let lib = {};
  
  while (i--) {
    let result = randomNode(head);
    if (lib[result] === undefined) {
      lib[result] = 1;
    } else {
      lib[result] += 1;
    }
  }
  
  return lib;
}


console.log(prove());