0

Question : A set of numbers separated by space is passed as input. The program must print the largest snake sequence present in the numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or left is +1 or -1 of it's value. If multiple snake sequences of maximum length is possible print the snake sequence appearing in the natural input order.

Example Input/Output 1:

Input:

5 6 7 9 8 8

Output:

5 6 7 8 9 8

8 9 8 7 6 5

Example Input/Output 2:

Input:

9 8 7 5 3 0 1 -2 -3 1 2

Output:

3 2 1 0 1

void doPermute(int[] in, StringBuffer out, boolean[] used, int length, int level, StringBuffer max) {
    if (level == length) {
        int count = 0;
        for (int i = 1; i < out.length(); i++) {
            if (Math.abs(Character.getNumericValue(out.charAt(i)) - Character.getNumericValue(out.charAt(i - 1))) != 1) {
                //System.out.println(Character.getNumericValue(i) - Character.getNumericValue(i - 1) + "  " + i + "   yes");
                count++;
                break;
            }
        }
        if (count == 0) {
            max.append(out + " ");

        }

        return;
    }
    for (int i = 0; i < length; ++i) {
        if (used[i]) {
            continue;
        }
        out.append(in[i]);
        used[i] = true;
        doPermute(in, out, used, length, level + 1, max);
        used[i] = false;
        out.setLength(out.length() - 1);
    }
}

As i am using StringBuffer my code passed the test cases that contains positive value (first test case) but failed in test cases containing negative values(second test case).

Update:- I replaced stringbuffer with Integer[] and made few changes.it works fine for smaller inputs of length 8 or 9. How to make it fast for larger inputs of length 13 to 15?

7
  • 1
    How did it fail? What output did you get instead? What is your question? Have you made any effort to debug the program and narrow down where the problem might be?
    – tnw
    Jun 11, 2015 at 18:30
  • using String buffer it take -2 as - and 2 Jun 11, 2015 at 18:31
  • Can you be more detailed please? What about the rest of my questions?
    – tnw
    Jun 11, 2015 at 18:33
  • @tnw in test case 1, all are positive value, so it permute as 567889,then 567898 and so on while in case of negative value say 5 6 7 8 8 -9, it permute as 5 6 7 8 8 - 9. So it consider '-' sign as a character instead of '-9'. Jun 11, 2015 at 18:37
  • Well, your for-loop in doPermute is getting one character at a time from the StringBuffer and working on them. What makes you think it should treat - and 9 as -9? If you want to parse the contents as numbers, you need to do that.
    – azurefrog
    Jun 11, 2015 at 18:52

2 Answers 2

1

Have you tried doing the process using an array of integers?

Scanner sc = new Scanner(System.in);
String s = sc.nextLine(); //The numbers entered in string format separated by spaces
String ss = s.split(" "); //Numbers separated by space will be put as individual numbers in a String array but each number is still in string format
int l = ss.length, i = 0;
int[] n = new int[l]; //The integer array which will store the values
for(i = 0; i < l; i++)
{
    n[i] = Integer.parseInt(ss[i]);  //Has integers now instead of string numbers
}

There might be creation of a few extra arrays but then calling the Character.getNumericValue() function repeatedly can also reduce efficiency. Also might solve your StringBuffer problem.

But SkillRack is very annoying anyway.

1
  • I tried but it takes a lot of time for larger values. anything to make it fast? Jun 12, 2015 at 18:21
0

Your comparison isn't finding adjacent numbers for negative values. For example: Abs(-2) - (-3) = 5 but -2 and -3 should be adjacent. Ok. I see you're parsing - and digit separately. Given the requirement of what a snake sequence is, the longest snake sequence for "5 6 7 9 8 8" is "5 6 7". The output listed above does not correspond to the definition: " adjacent numbers such that for each number, the number on the right or left is +1 or -1 of it's value". How does "5 6 7 8 9 8" meet the definition of snake sequence for "5 6 7 9 8 8"? Sorry I couldn't help. You might want to parse the code into Integers, store the longest sequences in a map).

@Test
public void testSnake(){
    String t2 = "9 8 7 5 3 0 1 -2 -3 1 2";
    List<String> numsStr = Arrays.asList(t2.split(" "));
    List<Integer> nums = new ArrayList();
    HashMap<Integer,List<Integer> > numMap = new HashMap();

    numsStr.forEach((s) -> {
        Integer val = Integer.decode(s);
        nums.add(val);
    });

    nums.forEach((num) -> {
        System.out.println("num: " + num);
        // track longest sequence, store in numMap
    });
    // Print numMap
}
6
  • problem is with string buffer method as while executing it takes negative value as a separate character.ex (-2 as - & 2). Jun 11, 2015 at 18:49
  • "567898" for "567988" is right as their is +1 or -1 difference between the digits. Jun 12, 2015 at 4:32
  • I thought the requirement for adjacent numbers meant they had to be adjacent in the input stream. In their natural order. Jun 13, 2015 at 4:41
  • i made few changes and it worked fine but for larger value it took a lot of time. Any idea to make it faster? Jun 13, 2015 at 8:12
  • Get rid of the recursion. You have an O(n^2) recursive algorithm. You can do the solution with O(n) performance without recursion. I'm on travel and don't have my computer at the moment so can't post code. You can iterate over the input, put each item in a TreeMap<item value, num items>, track if you've used an item in a chain with numItems value, for each item, look in map and see if there are values to left and right, store longest chain in List<List<Integer>, print list of lists at the end. That's what I'd do in a nutshell. Jun 14, 2015 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.