Ditto. This post covers the continuation of the original proposed (by me) challenge to HackerRank. Seems that I made the mistake to generate the post New, Duplicate or in Segment – Part 2 which describes this challenge. As you can verify I did not suggested a solution. Apparently that was enough to disqualify this entry. Next time I come up with a proposed challenge will not post a thing about it.
This challenge is similar to the previous version New, Duplicate or in Segment – Part 3 with the exception that in this case we need to display the value of the number or the segment. Due to this fact the previous solution would not fit the bill.
Please read the description of the challenge in the previous post, use the constraints in this one, and go for it.
The expected constraints are:
1 <= T <= 200
1 <= L < H <= 10000
1 <= C <= 10000
L <= integer <= H
T is the number of test cases per pass. L is the lowest integer value expected. H is the highest integer value expected. C is the count of integers in a test case. The last line contains a space separated set of C integers.
Following is output from the console of the Eclipse Neon .3 IDE:
1 1 11 17 9 4 4 1 1 4 10 10 8 8 1 9 8 7 10 5 1 New 9 New 4 Duplicate 4 New 1 Duplicate 1 Duplicate 4 Segment [9:10] Segment [9:10] Segment [8:10] Segment [8:10] Duplicate 1 Segment [8:10] Segment [8:10] Segment [7:10] Segment [7:10] Segment [4:5] Duplicate 1
Please pause reading, attempt to solve the challenge, and then continue with my solution in Java 8 which follows:
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;
/**
*
*/
class Segment {
// **** ****
int begin;
int end;
/**
* Constructor
*/
public Segment(int begin, int end) {
this.begin = begin;
this.end = end;
}
/**
*
*/
public String toString() {
String str = "";
str = this.begin + " -> " + this.end;
return str;
}
}
/**
*
*/
class InSegment {
// **** members ****
int low = 0;
int high = 0;
ArrayList<Segment> arr = null;
/**
* Constructor.
*/
public InSegment(int low, int high) {
this.low = low;
this.high = high;
this.arr = new ArrayList<Segment>();
}
/**
*
*/
public String toString() {
String str = "";
for (Segment segment : arr) {
str += segment.toString() + ", ";
}
if (str.length() > 0) {
str = str.substring(0, str.length() - 2);
}
return str;
}
/**
*
*/
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);
}
// **** empty array ****
if (arr.size() == 0) {
Segment segment = new Segment(n, n);
arr.add(segment);
response.append("New " + n);
}
// **** non-empty array ****
else {
// **** look for n in the sorted array ****
for (int i = 0; i < arr.size(); i++) {
// **** get the current segment ****
Segment cs = arr.get(i);
int begin = cs.begin;
int end = cs.end;
// **** n way before this segment (new) ****
if (n <= begin - 2) { Segment segment = new Segment(n, n); arr.add(i, segment); response.append("New " + n); break; } // **** n just before this segment (extend segment low) **** else if (n == (begin - 1)) { cs.begin = n; arr.set(i, cs); response.append("Segment [" + cs.begin + ":" + cs.end + "]"); break; } // **** n in this segment (duplicate OR in this segment) **** else if ((n >= begin) && (n <= end)) {
if (begin == end) {
response.append("Duplicate " + n);
} else {
response.append("Segment [" + begin + ":" + end + "]");
}
break;
}
// **** n just after this segment (extend segment high) ****
else if (n == end + 1) {
// **** update n (if needed) ****
if (i + 1 < arr.size()) {
Segment ns = arr.get(i + 1);
if (n + 1 == ns.begin) {
n = ns.end;
arr.remove(i + 1);
}
}
// **** ****
cs.end = n;
// **** ****
arr.set(i, cs);
response.append("Segment [" + cs.begin + ":" + cs.end + "]");
break;
}
}
}
// **** n not inserted yet ****
if (response.length() == 0) {
Segment segment = new Segment(n, n);
arr.add(segment);
response.append("New " + n);
}
// ???? display the array ????
// System.out.println("add <<< arr: " + arr.toString());
// **** return the response string ****
return response.toString();
}
}
/**
*
*/
public class Solution {
/**
* Test code.
*/
public static void main(String[] args) {
// ???? used to switch between challenge and test case generation ????
final boolean GEN_ELEMENTS = false;
// ???? used to display sequence for test case generation ????
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();
// **** instantiate the class ****
InSegment inSegment = new InSegment(L, H);
// **** count of integers to process ****
int C = sc.nextInt();
// ???? allocate array for input for test case generation ????
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 the integer ****
else {
i = sc.nextInt();
}
// **** process the 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();
}
}
As with the previous challenge, the solution allows you to generate test cases.
If you have comments or questions regarding this or any other post in this blog, please do not hesitate and leave a message at the end of this post. I will respond as soon as possible.
Enjoy;
John
Follow me on Twitter: @john_canessa