Contains Close Numbers

It is another COVID-19 (Wuhan virus) pandemic day. Seems like the stats for Minnesota and Dakota Country, the county I live in, are not increasing out of control. As a matter of fact they might be in a plateau. As we speak Minnesota has 34 total deaths which represents .001% of the population, and Dakota County continues to have 3 deaths which represents .001%. Best wishes that things are getting better where ever you are.

Italy is already talking about different ways to get people back to work. Hopefully they can do it in the near future. The United States will hopefully also get back to normal in a month or two. Failure to get the economy up and running will have very bad repercussions. Let’s continue to keep social distance and slow down new COVID-19 cases.

Regarding my daily routine, not much has changed since the pandemic. I get up every day between 05:00 and 06:00 AM. Fix breakfast and sit down with my wife to consume it. I have been fixing yogurt with fruit and homemade granola and a cup of latte made with a double espresso for each for at least the past 10 years. Do the dishes, shower and go down to my home office.

As you might know I work in two-hour blocks. At the end of each block I take a 15-minute break. I walk, have water or tea, talk with my wife and head back to my office. I use a modified / adapted Deep Work technique. Now that the days are starting to get warmer, for the afternoon break my wife and I walk outside. We try keeping social distance but we seldom run into other people. The area we live in is not densely populated. It turns out that on average we see more wild life than humans. Considering the times we are living in, that is a good situation to be in.

I tend to do 4 to 5 blocks a work day and 2 on weekends. I typically reserve a block a day for learning and experimenting. At this time I am taking a course on Azure and solving programming problems that I find from different on-line sources. The other blocks are dedicated to work stuff. In some cases work also requires learning new stuff.

OK, now let’s dive into the subject of this post. I received a message from Nick White. I subscribe to his blog among others. The message pointed me to the YouTube video Palantir Coding Interview Question – containsCloseNums.

If interested, I recommend starting watching the video and collect the requirements. Stop watching when Nick starts solving the problem at hand. What I do is create a repository in GitHub and attempt a solution. Once I have one or two approaches, I watch the rest of the video. In this specific case I thought Nick might have missed something but he did not. More on this as we go over my solution.

The edited requirements follow:

Given an array of integers nums and an integer k,

  1. determine whether there are two distinct indices i and j in the array where nums[i] = nums[j]
  2. and the absolute difference between i and j is less than or equal to k.

For example,

nums[] = [0, 1, 2, 3, 5, 2] and k = 3

0  1  2  3  4  5

i        j

The output should be:

containsCloseNums(nums, k) = true

This is because for I == 2 and j == 5 the array contains the same value 2

and abs(2 – 5) = 3  which is <= k.

# **** ****
C:\Users\johnc>dir
04/08/2020  07:59 AM    <DIR>          .
04/08/2020  07:59 AM    <DIR>          ..
09/22/2019  08:00 AM    <DIR>          .eclipse
03/15/2020  08:38 AM                59 .gitconfig
04/07/2020  10:38 AM    <DIR>          .p2
09/22/2019  08:00 AM    <DIR>          .tooling
03/10/2020  03:53 PM    <DIR>          .vscode
03/10/2020  04:43 PM    <DIR>          3D Objects
03/10/2020  04:43 PM    <DIR>          Contacts
04/08/2020  07:59 AM    <DIR>          ContainsCloseNums
02/17/2020  03:52 PM    <DIR>          Documents
04/03/2020  03:20 PM    <DIR>          Downloads
09/22/2019  07:57 AM    <DIR>          eclipse
09/22/2019  07:59 AM    <DIR>          eclipse-workspace_0
03/10/2020  04:43 PM    <DIR>          Favorites
03/10/2020  04:44 PM    <DIR>          Links
03/10/2020  04:43 PM    <DIR>          Music
09/12/2019  04:36 PM    <DIR>          NCH Software Suite
04/08/2020  07:22 AM    <DIR>          OneDrive
03/10/2020  04:43 PM    <DIR>          Saved Games
03/10/2020  04:43 PM    <DIR>          Searches
03/10/2020  04:43 PM    <DIR>          Videos
04/04/2020  07:52 AM    <DIR>          workspace0

# **** ****
C:\Users\johnc>cd workspace0

# **** ****
C:\Users\johnc\workspace0>dir
04/04/2020  07:52 AM    <DIR>          .
04/04/2020  07:52 AM    <DIR>          ..
04/01/2020  08:57 AM    <DIR>          BST-Search
04/05/2020  08:32 AM    <DIR>          GraphBFS
03/29/2020  08:30 AM    <DIR>          ORCost
03/10/2020  04:24 PM    <DIR>          SortOnFrequency

# **** clone the repo ****
C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/ContainsCloseNums.git
Cloning into 'ContainsCloseNums'...
remote: Enumerating objects: 3, done.
remote: Counting objects: 100% (3/3), done.
remote: Compressing objects: 100% (2/2), done.
remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (3/3), 715 bytes | 8.00 KiB/s, done.

# **** ****
C:\Users\johnc\workspace0>cd ContainsCloseNums

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>dir
04/08/2020  08:00 AM    <DIR>          .
04/08/2020  08:00 AM    <DIR>          ..
04/08/2020  08:00 AM               173 README.md

# **** contents of the README.md file ****
C:\Users\johnc\workspace0\ContainsCloseNums>type README.md
# ContainsCloseNums
Palantir coding interview question in Java

For additional information regarding this code please visit my blog post at:

T.B.D.

Enjoy;

John

As I mentioned, I started at GitHub.com and created a new repository for this post. Once it was created I went to my Windows 10 machine and cloned the repository.

Please note that the README.md file points to a non existing post. After all is said and done and I complete this post using WordPress, I will go back and update the README.md file.

0 1 2 3 5 2
3

true
true


0 1 2 3 5 4
3

false
false


0 1 2 3 5 2
2

false
false


1 2 3 4 5 6 7 8 9
3

false
false


1 2 3 4 5 2 7 2 8 9 
2

true
true


0 1 2 3 1 3
2

true
true

The test cases start with a list of integers. That line is followed by a single number that contains the value of k. Our solution displays twice the result. I implemented two solutions, one using an array and the other using a hash map. Of course both methods should return the same results.

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

        // **** read line with integers ****
        String[] is = sc.nextLine().trim().split(" ");

        // **** create array of integers ****
        Integer[] arr = new Integer[is.length];

        // **** populate array of integers ****
        for (int i = 0; i < is.length; i++) {
            arr[i] = Integer.parseInt(is[i]);
        }

        // **** read k ****
        int k = Integer.parseInt(sc.nextLine().trim());

        // **** check and return result ****
        System.out.println(containsCloseNums1(arr, k));
        System.out.println(containsCloseNums2(arr, k));

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

We open a scanner to read the parameters for our test. We read the first line and split the integers into an array of strings. After our array is created we populate it with the binary values. We then ready the value for k.

We are ready to process the data. We have two possible solutions. The most obvious and probably worse case would be the one using two nested loops. I decided to skip that one. Nick covers it in his video.

It seems this approach executes in O(n * log(n)).

    /**
     * Check for close numbers.
     * Using Arrays method(s) - O(n * log(n))
     */
    static boolean containsCloseNums1(Integer[] arr, int k) {
    
        // **** get a list of the array ****
        List<Integer> lst = Arrays.asList(arr);

        // **** traverse the list of integers - O(n) ****
        for (int i = 0; i < lst.size() - 1; i++) {

            // **** get index of last occurrance of this integer - O(log(n)) ****
            int j = lst.lastIndexOf(lst.get(i));

            // **** check if requirements match ****
            if ((i != j) && (Math.abs(i - j) <= k)) {
                return true;
            }
        }

        // **** not found ****
        return false;
    }

We start by getting a list representation backed by the original integer array. We then traverse the array looking for the possible duplicate. With the index in hand we can then compare the difference with k.

    /**
     * Check for close numbers.
     * Using hash map. O(n)
     */
    static boolean containsCloseNums2(Integer[] arr, int k) {

        // **** ****
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

        // **** traverse array O(n) ****
        for (int i = 0; i < arr.length; i++) {

            // **** check if integer is not in the hash map O(1) ****
            if (!hm.containsKey(arr[i])) {
                hm.put(arr[i], i);
            } else {
                
                // **** get index ****
                int j = hm.get(arr[i]);

                // **** check if requirements match ****
                if ((i != j) && (Math.abs(i - j) <= k)) {
                    return true;
                } else {

                    // **** update hash map ****
                    hm.put(arr[i], i);
                }
            }
        }

        // **** not found ****
        return false;
    }

This implementation uses a similar approach to the one presented by Nick White. We start by declaring a hash map. We traverse the array pushing the current array entry. If the value is already in the hash map we check if the indices meet the requirements.

This approach seems to execute in O(n) which is faster than the first one.

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>git status
On branch master
Your branch is up to date with 'origin/master'.

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        Solution.java

nothing added to commit but untracked files present (use "git add" to track)

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>git add Solution.java

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>git status
On branch master
Your branch is up to date with 'origin/master'.

Changes to be committed:
  (use "git restore --staged <file>..." to unstage)
        new file:   Solution.java

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>git commit -m "solution with two cases"
[master 0c60956] solution with two cases
 1 file changed, 102 insertions(+)
 create mode 100644 Solution.java

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
  (use "git push" to publish your local commits)

nothing to commit, working tree clean

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 12 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.08 KiB | 1.08 MiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/ContainsCloseNums.git
   ff8304b..0c60956  master -> master

# **** ****
C:\Users\johnc\workspace0\ContainsCloseNums>git log
commit 0c60956ff84b1b3d32537c1b175f10813c7179e5 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Wed Apr 8 09:28:55 2020 -0500

    solution with two cases

commit ff8304bb29f3408b84d4370e087181879d09f7e4
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date:   Wed Apr 8 07:58:56 2020 -0500

    Create README.md

When done we commit our changes and push them to our GitHub repository.

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, refresh your knowledge and enhance your developer toolset!

One last thing, thanks to all 548 subscribers to my blog!!!

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.