New, Duplicate on in Segment – Part 3

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.