Package org.drip.service.common

Class ListUtil<V>

java.lang.Object
org.drip.service.common.ListUtil<V>
public class ListUtil<V>
extends java.lang.Object
ListUtil implements Generic List Utility Functions used in DROP modules. It implements the following Functions:
  • ListNode inside of ListUtil
    • ListNode Constructor
    • Retrieve the Node Value
    • Retrieve the Next Node
    • Set the Next Node
    • Set the Node Value
  • Given a linked list, rotate the list to the right by k places, where k is non-negative
  • Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity
  • Write a program to find the node at which the intersection of two singly linked lists begins
  • You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself
  • Imagine a small store that has exactly one turn-stile. It can be used by customers either as an entrance or an exit. Sometimes multiple customers want to pass through the turn-stile and their directions can be different. The ith customer comes to the turn-stile at time[i] and wants to either exit the store if direction [i] = 1 or enter the store if direction[i] = 0. Customers form 2 queues, one to exit and one to enter. They are ordered by the time when they came to the turn-stile and, if the times are equal, by their indices
    • If one customer wants to enter the store and another customer wants to exit at the same moment, there are three cases:
    • If in the previous second the turn-stile was not used (maybe it was used before, but not at the previous second), then the customer who wants to exit goes first
    • If in the previous second the turn-stile was used as an exit, then the customer who wants to leave goes first
    • If in the previous second the turn-stile was used as an entrance, then the customer who wants to enter goes first
    • Passing through the turn-stile takes 1 second
    • Write an algorithm to find the time for each customer when they will pass through the turn-stile
  • Find the k post offices located closest to you, given your location and a list of locations of all post offices available
    • Locations are given in 2D coordinates in [X, Y], where X and Y are integers
    • Euclidean distance is applied to find the distance between you and a post office
    • Assume your location is [m, n] and the location of a post office is [p, q], the Euclidean distance between the office and you is SquareRoot((m - p) * (m - p) + (n - q) * (n - q))
  • K is a positive integer much smaller than the given number of post offices

Module Computational Core Module
Library Computation Support
Project Environment, Product/Definition Containers, and Scenario/State Manipulation APIs
Package Assorted Data Structures Support Utilities
Author:
Lakshmi Krishnamurthy

  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    static class  ListUtil.ListNode<V>
    ListNode inside of ListUtil.

  • Constructor Summary

    Constructors
    Constructor Description
    ListUtil()  

  • Method Summary

    Modifier and Type Method Description
    static ListUtil.ListNode<java.lang.Integer> Add​(ListUtil.ListNode<java.lang.Integer> headNode1, ListUtil.ListNode<java.lang.Integer> headNode2)
    You are given two non-empty linked lists representing two non-negative integers.
    static <V> ListUtil.ListNode<V> IntersectingNode​(ListUtil.ListNode<V> headNode1, ListUtil.ListNode<V> headNode2)
    Write a program to find the node at which the intersection of two singly linked lists begins.
    static java.util.List<int[]> NearestOffices​(java.util.List<int[]> officeLocationList, int k)
    Find the k post offices located closest to you, given your location and a list of locations of all post offices available.
    static <V> boolean OddEvenNodeShuffle​(ListUtil.ListNode<V> head)
    Given a singly linked list, group all odd nodes together followed by the even nodes.
    static <V> ListUtil.ListNode<V> Rotate​(ListUtil.ListNode<V> head, int k)
    Given a linked list, rotate the list to the right by k places, where k is non-negative.
    static int[] TurnstilePassingTimeArray​(int[] arrivalTimeArray, int[] directionArray)
    Imagine a small store that has exactly one turn-stile.

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • ListUtil

      public ListUtil()

  • Method Details

    • Rotate

      public static <V> ListUtil.ListNode<V> Rotate​(ListUtil.ListNode<V> head, int k)
      Given a linked list, rotate the list to the right by k places, where k is non-negative.
      Type Parameters:
      V - Value Type
      Parameters:
      head - Old Head Node
      k - Nodes to Shift By
      Returns:
      The New Head Node

    • OddEvenNodeShuffle

      public static <V> boolean OddEvenNodeShuffle​(ListUtil.ListNode<V> head)
      Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
      Type Parameters:
      V - Value Type
      Parameters:
      head - Head Node
      Returns:
      TRUE - Operation successfully completed

    • IntersectingNode

      public static <V> ListUtil.ListNode<V> IntersectingNode​(ListUtil.ListNode<V> headNode1, ListUtil.ListNode<V> headNode2)
      Write a program to find the node at which the intersection of two singly linked lists begins.
      Type Parameters:
      V - Value Type
      Parameters:
      headNode1 - Head Node of List #1
      headNode2 - Head Node of List #2
      Returns:
      Head Node of the Intersection List

    • Add

      public static final ListUtil.ListNode<java.lang.Integer> Add​(ListUtil.ListNode<java.lang.Integer> headNode1, ListUtil.ListNode<java.lang.Integer> headNode2)
      You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
      Parameters:
      headNode1 - Head Node of List #1
      headNode2 - Head Node of List #2
      Returns:
      Head Node of the Added List

    • TurnstilePassingTimeArray

      public static final int[] TurnstilePassingTimeArray​(int[] arrivalTimeArray, int[] directionArray)
      Imagine a small store that has exactly one turn-stile. It can be used by customers either as an entrance or an exit. Sometimes multiple customers want to pass through the turn-stile and their directions can be different. The ith customer comes to the turn-stile at time[i] and wants to either exit the store if direction [i] = 1 or enter the store if direction[i] = 0. Customers form 2 queues, one to exit and one to enter. They are ordered by the time when they came to the turn-stile and, if the times are equal, by their indices. If one customer wants to enter the store and another customer wants to exit at the same moment, there are three cases: If in the previous second the turn-stile was not used (maybe it was used before, but not at the previous second), then the customer who wants to exit goes first. If in the previous second the turn-stile was used as an exit, then the customer who wants to leave goes first. If in the previous second the turn-stile was used as an entrance, then the customer who wants to enter goes first. Passing through the turn-stile takes 1 second. Write an algorithm to find the time for each customer when they will pass through the turn-stile.
      Parameters:
      arrivalTimeArray - Array of Arrival Times
      directionArray - Array of Entry/Exit Directions
      Returns:
      Array of Pass Times

    • NearestOffices

      public static final java.util.List<int[]> NearestOffices​(java.util.List<int[]> officeLocationList, int k)
      Find the k post offices located closest to you, given your location and a list of locations of all post offices available. Locations are given in 2D coordinates in [X, Y], where X and Y are integers. Euclidean distance is applied to find the distance between you and a post office. Assume your location is [m, n] and the location of a post office is [p, q], the Euclidean distance between the office and you is SquareRoot((m - p) * (m - p) + (n - q) * (n - q)). K is a positive integer much smaller than the given number of post offices.
      Parameters:
      officeLocationList - List of Office Coordinates
      k - k Nearest Offices
      Returns:
      List of Nearest Office Coordinates