I have explicitly added the term “Unsorted” array but the interviewer may not say this piece of information and expect from you to ask this as a cross-question. Asking cross-questions and getting clarity on expectation or requirement is an evaluation criterion in many companies. But keep in mind – Ask valid questions. Asking more and less both are not good.
Let’s think what we understand from the above question and what needs to be asked
- The question says “Closest Value Of A Given Number in Unsorted Array“, it means array is an integer array and it is unsorted.
- Many may understand here that we need to look for a number which is lesser than the target number which is not expected. A closet number to target can be target number itself or smaller than the target or greater than the target.
- You need to write logic that will work for both sorted and unsorted. Do not just confuse with term unsorted here.
- Ask if an array contains negative numbers. I will show how this matters.
- You can ask for the duplicate elements in the array as well.
- There may be a tie. For example:- Numbers 2 & 4 both are equally closer to number 3. You can ask here which is expected. First or last. In the below examples, I have taken the first number as output.
Let’s see how negative numbers in array matters.
How many whole numbers are between 5 and 10? It is 5 numbers including 5.
How many whole numbers are between – 5 and 5? It is 10 numbers including -5.
How we can calculate it?
By taking the difference of target and number i.e. target – number or number – target. Negative or positive difference will indicate the direction to move ( left or right). For this program, we are not worrying about nature of difference so we will use absolute value. We can use Maths.abs() here.
10-5 = 5
5 – ( -5) = 10
So we need to calculate the actual distance from the target element properly. For example – If we have a target element as 10 then the actual distance of -5 to 10 is 10 while the actual distance of 5 to 10 is 5. It means 5 is closer to 10 than -5.
You should have got some idea of logic from the above concept of “distance“. If we can get the absolute distance of all elements of the array to the target element and pick the smallest (or closest) one then we have output.
Covering edge cases is an important step and it is also a part of evaluating coding tests. Let’s think of edge cases for this problem. Only edge case I can think of if an array is empty.
- Put a check on the length of the array. If it is zero, terminate the execution or whatever interviewer is expecting to do. We will terminate the program in this case.
- Let’s assume the 0th indexed element is the closest to the target element. Get the absolute distance of the 0th element to target. If the absolute distance is zero that means you got the target number itself and there is no need to check for other elements in the array. If the absolute distance is not zero, start iterating array.
- Start iterating array from the first index ( Not from 0th as I preassume in step 2 above). Take the absolute distance of the first indexed element to the target number. If the absolute distance is zero that means you got the target number itself and there is no need to check for other elements in the array. If the absolute distance is not zero then check if this value of the absolute distance is smaller than the 0th indexed number’s absolute distance. If it is smaller it means you got another more closest number and update assumed indexed i.e. 0th to 1st and old value of absolute distance to the new value. If it is not smaller then proceed for the next number in the array.
- Repeat about the process for all numbers of the array.
Suppose we have a target element as 10 and there are two numbers -9 and 5 in array in sequence. Let’s calculate the distance with signs.
-9 – 10 = -19 & 5 – 10 = -5
When we perform step 2 above and compare both distances as -5 < -19 then we will get false and we will not update the assumed index to 1 from 0. This is not correct behavior. Obviously 5 is closer to 10 than -9. But due to negative difference out logic failed. This is the reason we need to find absolute difference i.e. |-5| < |-19|.
package LeetCodeEasyPrograms;
public class FindClosestNumberOfGivenNumberInAnUnsortedArray {
private static int getClosetNumberOfTarget(int[] dataArray, int target) {
if (dataArray.length == 0) {
System.out.println("Empty Array. Terminating program.");
System.exit(1);
}
// Assume 0th element in array is the closest number to target
int indexOfClosestNumberToTarget = 0;
// Get the absolute distance of 0th element to target
int absoluteDistanceOfNumberToTarget = Math.abs(dataArray[indexOfClosestNumberToTarget] - target);
// If absolute distance is zero, no need to iterate remaining element of array
// as no other number will be closest to target
if (absoluteDistanceOfNumberToTarget == 0)
return indexOfClosestNumberToTarget;
// Iterate through remaining element
for (int i = 1; i < dataArray.length; i++) {
// Get the absolute distance of ith element to target
int deltaOfCurrentElement = Math.abs(dataArray[i] - target);
// If absolute distance is zero, no need to iterate remaining element of array
// as no other number will be closest to target
if (deltaOfCurrentElement == 0)
return i;
// If current absolute distance is smaller than previously assumed number,
// replace it
else if (deltaOfCurrentElement < absoluteDistanceOfNumberToTarget)
{
indexOfClosestNumberToTarget = i;
absoluteDistanceOfNumberToTarget = deltaOfCurrentElement;
}
}
// Once iteration is over and reaches here, current value of
// indexOfClosestNumberToTarget index will be closest to target
return indexOfClosestNumberToTarget;
}
public static void main(String[] args) {
System.out.println("++++++++++++++++++++++++++++++++++++++++++");
int a[] = {6, 2, 4, 9, 1 };
System.out.println(a[getClosetNumberOfTarget(a, 5)]);
System.out.println(a[getClosetNumberOfTarget(a, -1)]);
System.out.println(a[getClosetNumberOfTarget(a, 8)]);
System.out.println("++++++++++++++++++++++++++++++++++++++++++");
int b[] = {11, -2, 4, 15, 96, 6, 87,90, -9};
System.out.println(b[getClosetNumberOfTarget(b, 11)]);
System.out.println(b[getClosetNumberOfTarget(b, 95)]);
System.out.println(b[getClosetNumberOfTarget(b, 89)]);
System.out.println(b[getClosetNumberOfTarget(b, 88)]);
System.out.println(b[getClosetNumberOfTarget(b, -7)]);
System.out.println("++++++++++++++++++++++++++++++++++++++++++");
int c[] = {100};
System.out.println(c[getClosetNumberOfTarget(c, 101)]);
System.out.println("++++++++++++++++++++++++++++++++++++++++++");
int d[] = {6,2,4,9,1};
System.out.println(d[getClosetNumberOfTarget(d, 3)]);
System.out.println(d[getClosetNumberOfTarget(d, 5)]);
System.out.println(d[getClosetNumberOfTarget(d, -1)]);
System.out.println("++++++++++++++++++++++++++++++++++++++++++");
int e[] = { -1, 2, 11, 76, 2 };
System.out.println(e[getClosetNumberOfTarget(e, 5)]);
System.out.println(e[getClosetNumberOfTarget(e, 3)]);
System.out.println(e[getClosetNumberOfTarget(e, 1)]);
System.out.println(e[getClosetNumberOfTarget(e, 0)]);
System.out.println("++++++++++++++++++++++++++++++++++++++++++");
}
}
++++++++++++++++++++++++++++++++++++++++++ 6 1 9 ++++++++++++++++++++++++++++++++++++++++++ 11 96 90 87 -9 ++++++++++++++++++++++++++++++++++++++++++ 100 ++++++++++++++++++++++++++++++++++++++++++ 2 6 1 ++++++++++++++++++++++++++++++++++++++++++ 2 2 2 -1 ++++++++++++++++++++++++++++++++++++++++++
You can clone the GIT repo from here.
If you have any doubt, feel free to comment below.If you like my posts, please like, comment, share and subscribe.#ThanksForReading
#HappyLearning