Number of Recent Calls

šŸ  ā¬…ļø āž”ļø

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

  • RecentCounter() Initializes the counter with zero recent requests.
  • int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

Input [ "RecentCounter ", "ping ", "ping ", "ping ", "ping "] [[], [1], [100], [3001], [3002]] Output [null, 1, 2, 3, 3]

Explanation RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1], range is [-2999,1], return 1 recentCounter.ping(100); // requests = [1, 100], range is [-2900,100], return 2 recentCounter.ping(3001); // requests = [1, 100, 3001], range is [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Constraints:

  • 1 <= t <= 109
  • Each test case will call ping with strictly increasing values of t.
  • At most 104 calls will be made to ping.
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, iostat_end
    implicit none
    type(RecentCounter) :: recentCounter
    integer :: t, n, i, status
    character(len=:), allocatable :: line

    ! Read input from stdin
    do
        read (unit=input_unit, fmt='(A)', iostat=status) line
        if (status == iostat_end) exit
        if (status /= 0) then
            write (unit=error_unit, fmt='(2A)') 'error: ', trim(line)
            stop 1
        end if
        backspace input_unit
        read (unit=input_unit, fmt=*) t
        n = recentCounter%ping(t)
        write (unit=output_unit, fmt='(I0)') n
    end do

contains

    type RecentCounter
        integer :: count = 0
        integer, dimension(:), pointer :: requests => null()
    contains
        procedure :: ping
    end type RecentCounter

    integer function ping(this, t) result(n)
        class(RecentCounter), intent(inout) :: this
        integer, value :: t
        integer :: i, j

        ! Check if we need to reallocate the array
        if (.not. associated(this%requests)) then
            allocate(this%requests(100))
        else if (size(this%requests) < size(this%requests) + 1) then
            allocate(this%requests(size(this%requests)*2))
        end if

        ! Increment the count
        this%count = this%count + 1

        ! Shift the requests down by one position
        do i = this%count, 2, -1
            this%requests(i) = this%requests(i-1)
        end do

        ! Store the new request
        this%requests(1) = t

        ! Count the number of requests in the past 3000 ms
        n = 0
        do i = 1, this%count
            if (this%requests(i) >= t - 3000) then
                n = n + 1
            end if
        end do
    end function ping

end program main
āŒ Compiled
āŒ Executed
āŒ Correct 
module recent_counter

    implicit none

    type :: RecentCounter
        integer :: count = 0
        integer :: last_ping = 0
    contains
        procedure :: ping
    end type RecentCounter

contains

    function ping(this, t) result(count)
        class(RecentCounter), intent(inout) :: this
        integer, intent(in) :: t
        integer :: count

        this%count = this%count + 1
        this%last_ping = t

        if (t - 3000 <= this%last_ping) then
            count = this%count
        else
            count = 0
        end if
    end function ping

end module recent_counter

program main
    use recent_counter
    implicit none

    integer :: t
    type(RecentCounter) :: recent_counter

    ! Example 1
    recent_counter = RecentCounter()
    t = 1
    write (*,*) recent_counter%ping(t)
    t = 100
    write (*,*) recent_counter%ping(t)
    t = 3001
    write (*,*) recent_counter%ping(t)
    t = 3002
    write (*,*) recent_counter%ping(t)

    ! Example 2
    recent_counter = RecentCounter()
    t = 1
    write (*,*) recent_counter%ping(t)
    t = 100
    write (*,*) recent_counter%ping(t)
    t = 3001
    write (*,*) recent_counter%ping(t)
    t = 3002
    write (*,*) recent_counter%ping(t)

    ! Example 3
    recent_counter = RecentCounter()
    t = 1
    write (*,*) recent_counter%ping(t)
    t = 100
    write (*,*) recent_counter%ping(t)
    t = 3001
    write (*,*) recent_counter%ping(t)
    t = 3002
    write (*,*) recent_counter%ping(t)

end program main
šŸŒ Data from online sources 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def increasingBST(root):
    def inorder(node):
        nonlocal prev
        if not node: return

        inorder(node.left)
        prev.right = node
        prev = node
        node.left = None
        inorder(node.right)

    dummy = TreeNode(0)
    prev = dummy
    inorder(root)
    return dummy.right

The algorithm uses a recursive inorder traversal of the given binary search tree. It starts by visiting the left child, if any, and then processes the root node, and finally the right child. The important part of this traversal is the processing of each node. When a node is encountered, its left pointer is set to null and its right pointer is set to the current node being processed.

The algorithm maintains a prev variable to keep the previous node encountered during the inorder traversal. Initially, we have a dummy node, and during the traversal, we set the right pointer of the prev node to the current node and update the prev node to the current node.

Finally, after the traversal, the right child of the dummy node points to the root of the modified tree.

šŸŒ Data from online sources 
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
};

void inorder(TreeNode* node, TreeNode*& prev) {
    if (node == nullptr) return;

    inorder(node->left, prev);
    prev->right = node;
    prev = node;
    node->left = nullptr;
    inorder(node->right, prev);
}

TreeNode* increasingBST(TreeNode* root) {
    TreeNode dummy(0);
    TreeNode* prev = &dummy;
    inorder(root, prev);
    return dummy.right;
}

The algorithm uses a recursive inorder traversal of the given binary search tree. It starts by visiting the left child, if any, and then processes the root node, and finally the right child. The important part of this traversal is the processing of each node. When a node is encountered, its left pointer is set to null and its right pointer is set to the current node being processed.

The algorithm maintains a prev variable to keep the previous node encountered during the inorder traversal. Initially, we have a dummy node, and during the traversal, we set the right pointer of the prev node to the current node and update the prev node to the current node.

Finally, after the traversal, the right child of the dummy node points to the root of the modified tree.