I received a message from HackerRank indicating that they would not be able to use the New, Duplicate or in Segment proposed (by me) challenge because I had already made a post in my blog. I thought it would be fine if I did not describe a possible solution. I guess I was wrong.
Within the specified range label each received integer as “New” if the integer is being processed for the first time, “Duplicate” is the integer is not in a segment but has been processed before or “In segment” if the integer is part of a segment of two or more integers.
A line with the number of test cases T followed by a line with two integers representing the low L and high H range of the expected values. The next line contains the count C of input integers followed by the actual integers.
Constraints:
1 <= T <= 100
1 <= L < H <= 1000
1 <= C <= 2000
L <= I <= H
For each integer in the set print the integer I followed by the string “New” if the integer has not been processed before, “Duplicate” if the integer has been processed before but is not in a segment and “In segment” if the integer is in a segment of two or more monotonically ascending values.
Following is a capture of the console of the Eclipse Neon .3 IDE:
1 1 7 11 3 6 6 1 3 4 2 2 4 2 5 New New Duplicate New Duplicate In segment In segment In segment In segment In segment In segment
Please spend a couple minutes verifying that the associated input produces the expected output before proceeding.
Following is the solution to this challenge written in Java 8:
import java.util.Random;
import java.util.Scanner;
/**
*
*/
class InSegment {
// **** members ****
int low = 0;
int high = 0;
boolean arr[] = null;
/**
* Constructor.
*/
public InSegment(int low, int high) {
this.low = low;
this.high = high;
this.arr = new boolean[high - low + 1];
}
/**
* Add value and return response.
* Responses: "New", "Duplicate" and "In segment"
*/
public String add(int n) {
// **** ****
StringBuilder response = new StringBuilder();
// **** check range ****
if ((n < this.low) || (n > this.high)) {
throw new IllegalArgumentException("add <<< illegal n: " + n);
}
// **** normalize n ****
n -= this.low;
// **** check if n is already in the array (for starters) ****
if (arr[n] == false) {
// **** flag value is in array ****
arr[n] = true;
// **** ****
response.append("New");
} else {
response.append("Duplicate");
}
// **** check segment at start ****
if (n == 0) {
if (arr[n + 1]) {
response.setLength(0);
response.append("In segment");
}
}
// **** check segment at end ****
else if (n == (this.high - this.low)) {
if (arr[n - 1]) {
response.setLength(0);
response.append("In segment");
}
}
// **** check segment between ends ****
else {
if (arr[n - 1] || arr[n + 1]) {
response.setLength(0);
response.append("In segment");
}
}
// **** return response string ****
return response.toString();
}
}
/**
*
*/
public class Solution {
/**
* Test code.
*/
public static void main(String[] args) {
// ???? used to switch between challenge and test cases generation ????
final boolean GEN_ELEMENTS = false;
// ???? ????
int input[] = null;
// **** generate pseudo random integers in specified range ****
Random rand = new Random(1234);
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** number of test cases ****
int T = sc.nextInt();
// **** loop once per test case ****
int i;
for (int t = 0; t < T; t++) {
// **** limits ****
int L = sc.nextInt();
int H = sc.nextInt();
// **** ****
InSegment inSegment = new InSegment(L, H);
// **** count of integers to process ****
int C = sc.nextInt();
// ???? allocate array for input (to generate test cases only) ????
if (GEN_ELEMENTS) {
input = new int[C];
}
// **** loop processing integers ****
for (int c = 0; c < C; c++) {
// **** generate a pseudo random integer in the specified range ****
if (GEN_ELEMENTS) {
i = L + Math.abs(rand.nextInt(H - L));
input = i;
}
// **** read integers ****
else {
i = sc.nextInt();
}
// **** process integer ****
System.out.println(inSegment.add(i));
}
// ???? display input values (to generate test cases only) ????
if (GEN_ELEMENTS) {
System.out.print("main <<< input: ");
for (int c = 0; c < C; c++) {
System.out.print(input + " ");
}
System.out.println();
}
}
// **** close scanner ****
sc.close();
}
}
Please generate additional test cases to verify your solution. If you encounter a test case that is not covered with my solution please let me know. I will fix my code.
If you have comments or questions regarding this or any other post in this blog, please do not hesitate and leave me a message. I will reply to it as soon as possible.
Enjoy;
John
Follow me on Twitter: @john_canessa