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