Number of Recent Calls

It is an ugly rainy and stormy day in the Twin Cities of Minneapolis and St. Paul.  It seems like the storms will resume around 03:00 PM later today. In general I shutdown all my desktop computers when there are thunderstorms. I have a couple UPS units but I have also invested time installing software and configuring them exactly the way I like it. Do not wish to change disks or re install software.

Earlier today I opened the LeetCode web site and selected the problems icon. In the search box I entered the word “recursion”. Many problems were listed. I sorted them by difficulty Easy to Difficult. I then selected problem 933. Number of Recent Calls. Time permitting, decided to tackle three problems in the three categories in the next few days.

If interested please visit the LeetCode site and read the description on this problem. The following is from the problem requirements:

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

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

Read the description a few times and it seemed like a trick question.

The problem requires one to update the following class:

class RecentCounter {

    public RecentCounter() {
    }

    public int ping(int t) {
    }
}

We are required to update the RecentCounter class to return the count of ping calls that have been made in the last 3000 milliseconds. Perhaps I got confused because I have implemented different versions of ping down to socket calls, on different software platforms. Following is a description of the Command Line Interface (CLI) that issues a call to the storage server. Note that we could send an ICMP (Internet Control Message Protocol) packet which is equivalent to a standard ping on computer systems that support TCP/IP (i.e. Linux, UNIX and Windows).

C:\>casping -?

        casping [iCAS TCP/IP]

        This command issues a "ping" to the specified iCAS.
        To determine connectivity to a storage server one should first try the TCP/IP ping utility.
        This may or may not work if the computer hosting the storage server has "ping" disabled.
        To determine connectivity at the storage server (application) level one should use the casping CLI.

        -a <ACCESS code>
        -d <DELAY in seconds>
        -h display this HELP screen
        -i send an ICMP packet to the computer hosting the storage server

        -p <storage server PORT>
        -s <storage server TCP/IP>
        -t TESTING ONLY - casping CLI hungs
        -u <USER name>

        -v run this command in VERBOSE mode

Following is a call to check if the storage server is up and running while it was up and running:

C:\>casping
{
"iCASCLI" : "SockPing",
"ServerIP" : "192.168.1.110",
"ServerPort" : 4444,
"ReturnedValue" : "WAR_SUCCESS"
}

Following is a call to check if the storage server is up and running after it has been shutdown:

C:\>casping
{
"iCASCLI" : "SockPing",
"ServerIP" : "192.168.1.110",
"ServerPort" : 4444,
"ReturnedValue" : "WAR_CONNECTION_REFUSED"
}

The call first sends an ICMP packet to check that the computer hosting the storage server is alive. Then it sends a proprietary request to the storage server software to see if the software is up and running. In the first test the storage software and up and running. In the second test the computer was up but the storage server software had been stopped.

The test scaffolding for LeetCode will send provide the following data and the ping method is supposed to return the expected result.

RecentCounter ping ping ping ping
null 1 100 3001 3002

null 1 2 3 3

As usual I like to develop software using the development tools (which change through the years and also based on the programming language I choose) that I am comfortable with. In this case I will use Java on a Windows 10 computer running the VSCode IDE.

C:\>ping -?

Usage: ping [-t] [-a] [-n count] [-l size] [-f] [-i TTL] [-v TOS]
            [-r count] [-s count] [[-j host-list] | [-k host-list]]
            [-w timeout] [-R] [-S srcaddr] [-c compartment] [-p]
            [-4] [-6] target_name

Options:
    -t             Ping the specified host until stopped.
                   To see statistics and continue - type Control-Break;
                   To stop - type Control-C.
    -a             Resolve addresses to hostnames.
    -n count       Number of echo requests to send.
    -l size        Send buffer size.
    -f             Set Don't Fragment flag in packet (IPv4-only).
    -i TTL         Time To Live.
    -v TOS         Type Of Service (IPv4-only. This setting has been deprecated
                   and has no effect on the type of service field in the IP
                   Header).
    -r count       Record route for count hops (IPv4-only).
    -s count       Timestamp for count hops (IPv4-only).
    -j host-list   Loose source route along host-list (IPv4-only).
    -k host-list   Strict source route along host-list (IPv4-only).
    -w timeout     Timeout in milliseconds to wait for each reply.
    -R             Use routing header to test reverse route also (IPv6-only).
                   Per RFC 5095 the use of this routing header has been
                   deprecated. Some systems may drop echo requests if
                   this header is used.
    -S srcaddr     Source address to use.
    -c compartment Routing compartment identifier.
    -p             Ping a Hyper-V Network Virtualization provider address.
    -4             Force using IPv4.
    -6             Force using IPv6.

The ping CLI sends an ICMP packet to the specified host and waits a default time for it to return with and ACK. In this case the author of the problem decided to use the name “ping” which is not related to the CLI. The t is not an argument to the operation (i.e., delay). It is just the time on the timeline in which the call to the method is performed.

With that clarification, the problem seems a lot simpler to understand.

As you see, LeetCode provides the test scaffolding. You so not need to deal with it. In my case I developed one so I can work the problem on my computer using my selected tools.  The test scaffolding is NOT part of the solution!

/**
 * Test scaffolding.
 */
class Solution {

    /**
     * Test scaffolding.
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read list of calls ****
        String[] calls = sc.nextLine().split(" ");

        // **** read list of arguments for calls ****
        String[] times = sc.nextLine().split(" ");

        // **** instantiate RecentClass object ****
        RecentCounter obj = new RecentCounter();

        // **** loop making the calls ****
        int i = 0;
        for (String call : calls) {

            // **** skip if not a ping ****
            if (!call.equals("ping")) {
                System.out.print("null ");
            } else {

                // **** convert string to binary ****
                int t = Integer.parseInt(times[i]);

                // **** issue ping call ****
                int count = obj.ping(t);

                // **** display count ****
                System.out.print(count + " ");
            }

            // **** increment index ****
            i++;
        }

        // **** close scanner ****
        sc.close();
    }
}

We open a scanner, read the first input line and split it into names of calls. We need that because the first call in the list is the name of the class which has nothing to do with the problem. It seems that it was done just to add confusion.

We then read the line with the times in which the “ping” call will be made. As I mentioned before, it has nothing to do with how the call will behave, it is just the time at which the call is being made.

We instantiate the class and then loop skipping all calls except the ones named “ping”. Note that we keep and index to make sure we associate the proper call with the proper time. I believe I should have defined the index in the “for” loop. I have already submitted the code to LeetCode so I will not alter it.

/**
 * 
 */
class RecentCounter {

    // **** members ****
    Queue<Integer> q = null;
    

    /**
     * Constructor
     */
    public RecentCounter() {
        this.q = new LinkedList<Integer>();
    }


    /**
     * Return the number of pings that have been made from 
     * 3000 milliseconds ago until now.
     *
     * t represents some time in milliseconds.
     */
    public int ping(int t) {

        // **** add ping to the head of the queue ****
        this.q.add(t);

        // ???? ????
        // System.out.println("\nping <<< q: " + q.toString());

        // **** remove pings(s) from the tail of the queue ****
        while (q.peek() < (t - 3000)) {
            this.q.remove();
        }

        // ???? ????
        // System.out.println("ping <<< q: " + q.toString());

        // **** return the number of elements in the queue ****
        return this.q.size();
    }
}

I added a linked list in which we will keep the time at which a call to the ping method is made. The constructor shows that we will use a linked list. A linked list implements a FIFO. New values are inserted at the head and old values are retrieved from the tail. A FIFO is commonly named a queue.

In the ping method, we insert at the head of the queue, the time at which the call was made. We then loop removing all entries (if any) that are older than 3000 milliseconds. When done, we return the number of entries remaining in the queue.

Given the way the problem was presented, I would call it a trick question. In my humble opinion that has nothing to do with computer science. I should have given the problem thumbs down, but decided not to do so. In addition, if English is not your first language, perhaps you might have added another dimension to the complexity.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 1,675 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.