Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Grab a Random Node (Main Thread)

Here is the interview question prompt, presented for reference.

Given a linked list, can you write a method to get a random node within it? Let's assume you're given a random node generator. The linked list will have at least 2 nodes, and may look something like this:

1 -> 2 -> 3 -> 4

The odds of getting any number between 1 and 4 inclusive should be the exactly the same.

You have access to this definition of a Linked List node:

function Node(val) {
  this.val = val;
  this.next = null;
}

Constraints

  • Length of the linked list <= 10000
  • The nodes will always contain integer values between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked over 5 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Grab a Random Node.