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,
- determine whether there are two distinct indices i and j in the array where nums[i] = nums[j]
- 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