Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
Example
For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;
There is no one element in this array that can be removed in order to get a strictly increasing sequence.
For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.
You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
The code I wrote works for all cases except for one:
The nonworking case is a hidden case so I have no idea what case where I would have an infinite loop. Can you see the reason for such an error?
So, you say the problem is that on some inputs you'd run into infinite (non ending) program?Sergiu Dobozi wrote:The nonworking case is a hidden case so I have no idea what case where I would have an infinite loop.
I see problem if sequence is either empty or null, so you don't check for those, but these cases wouldn't cause anything infinite. Please clarify or better copy paste exact text from where you take this challenge.
 X 2
I think it's your sorted method that's the problem.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Junilu Lacar wrote:Why do you assume it's an infinite loop that's the problem? Any array with less than three elements will probably fail a test because it will result in your sorted() method returning true. I doubt that a zero or oneelement array should be considered as an increasing sequence. To tell if you have a strictly increasing sequence, you need at least two elements, don't you?
I think it's your sorted method that's the problem.
This is what Code Fights gives me as an error:
"Execution time limit exceeded on test 26: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input."
So I assumed that it is referring to an infinite loop.
What you do, lets say on input {1, 2, 7, 4, 0, 5, 6, ... N1}. You copy whole array and then checking if it's sorted. But you know right away after 2, 7, 4, ... 0... that this combination can't be sorted, but you still going to copy the rest of the elements.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
[edit] hm.. that might won't work in some cases.. don't know about that now
 1
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Liutauras Vilda wrote:Thinking a bit in a rush now, but i think you just need to find first element which is smaller than previous, then skip that and check if the rest elements are greater than the one before you skipped, and that is it I think.
[edit] hm.. that might won't work in some cases.. don't know about that now
This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.
This is my implementation:
Junilu Lacar wrote:Liutauras is correct about long arrays. I tried with 50K numbers and it took a few seconds to complete on my Mac. This code will eventually fail for long arrays, depending on how impatient the test harness is.
Thank you for testing it. I'm at work so I don't have access to any programming software.
Now I know that at least there was no logical problem.
As Junilu writes, if an array is already sorted, then the progrram will terminate very quickly, since the first attempt will be succesfull, However, with an average array, run time will go up dramatically. For instance try:
This will very quickly end. But when running with the outcommented line will probably get you the time exceeds error.
Another way, find the two biggest elements and write down their indices. Now, if these indices are the two highest indices (array.length  1 and array.length  2), then what can you conclude? And what if these indices are not the highest two indices? That will give you a O(N) solution, if I'm not mistaken (which has a positive probability...)
Edit: well, the above is not correct, but it is in the right direction...
That's not true.Sergiu Dobozi wrote:This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.
Let me rephrase all that from a different end, I might wasn't clear enough. Find first element which is equal greater than next, skip that element, record that you removed/skipped one already, if that happens again, return false, otherwise true.
Sergiu Dobozi wrote:
This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.
But it's a start point.
There are two situations, both of which can be initially spotted using Liutauras' suggestion.
10,20,30,20,40,50
in which you want to remove the low value, which can be spotted by the fact that 30 < 40, so 20 is the odd one out.
and your example
1, 2, 3, 4, 99, 5, 6
in which you spot the issue on the '5', but because 99 > 6 then it's the 99 that goes.
That should be a pretty simple check.
So, search as per Liutauras' idea, then check either side of the first value you hit where currentValue < previousValue...if previousValue < nextValue then remove currentValue...if previousValue > nextValue, remove previousValue.
There's probably other issues, but it's a start.
Dave Tolls wrote:
Sergiu Dobozi wrote:
This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.
But it's a start point.
There are two situations, both of which can be initially spotted using Liutauras' suggestion.
10,20,30,20,40,50
in which you want to remove the low value, which can be spotted by the fact that 30 < 40, so 20 is the odd one out.
and your example
1, 2, 3, 4, 99, 5, 6
in which you spot the issue on the '5', but because 99 > 6 then it's the 99 that goes.
That should be a pretty simple check.
So, search as per Liutauras' idea, then check either side of the first value you hit where currentValue < previousValue...if previousValue < nextValue then remove currentValue...if previousValue > nextValue, remove previousValue.
There's probably other issues, but it's a start.
I will have to try out everyone's suggestions as soon as possible.
If there is a case where {1000, 20, 30, 40} and I have to check 1000 with a previous value, I can't do that because I would have to compare with sequence[1]. So is this method really possible to implement?
I used ChronoUnits and LocalDateTime so I might not be doing it right but I don't see much delay on the console.
and here's my output:
0 secs 52 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 197 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
I suppose the first test always takes a hit for loading and other kinds of startup overhead. The 197 millis was for the Integer.MAX_VALUE / 8 long array of sequential numbers. Couldn't use the max because I was running out of memory for the array.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Sergiu Dobozi wrote:This is my implementation:
[100, 1, 2]
**Fail**
[1, 2, 4, 100, 4]
**Fail**
[1]
**Fail**
[2, 1]
**Fail**
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Sergiu Dobozi wrote:
I will have to try out everyone's suggestions as soon as possible.
If there is a case where {1000, 20, 30, 40} and I have to check 1000 with a previous value, I can't do that because I would have to compare with sequence[1]. So is this method really possible to implement?
Others may work differently, but I always suggest getting the basics down first (Junilu's tests are good for that).
Handle the edge cases once you've handled the general case.
In my opinion, trying to write something outright that covers all cases tends to result in you writing nothing.
Dave Tolls wrote:I always suggest getting the basics down first (Junilu's tests are good for that). Handle the edge cases once you've handled the general case.
Minds that think alike...
Ironically, I missed one test case that you pointed out, Dave: [10, 20, 30, 40, 20, 50]
Sure enough, when I ran it, my implementation failed. It actually took me a while to figure out how to cover this one but with some refactoring to clarify intent, the code eventually pointed me to the right solution. I found a very good example of how too many implementation details can make it difficult to catch and eradicate a bug. I will share my solution once we see one from OP that passes all the tests I wrote.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
Test cases that should return true
Test cases that should return false
I'm wondering if anyone disagrees with my test cases? Obviously Junilu and I disagree on one of them.
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.
Carey Brown wrote:
What is meant by "strictly"? (I'm assuming I can ignore this.) Does each number have to be 1 more than the one before it? (assume: no)
I think the second is what defines "strictly", that is, each number must be at least one more than the previous one, if there is one. "Nonstrictly" speaking, you'd allow repeats of the same number.
Does the interval between successive pairs have to be the same? (assume: no) Is a single number, e.g. [1], a "sequence"? (assume: no)
I made the same assumptions.
[1, 2, 4, 100, 4] // I disagree w/ Junilu on this one, I'd drop the last '4'[/code]
I'm wondering if anyone disagrees with my test cases? Obviously Junilu and I disagree on one of them.
You're correct to disagree with me on this one. I do, too. That was a mistake and it's a faulty test because it has another solution than the one being tested. I actually spent literally 30 minutes refactoring my code to clarify intent before I realized this. I should have read your post earlier; I could have saved myself the frustration.
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Here's the test cases that have come up so far:
The results for the OP's algorithm:
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.
I've fixed my algorithm as per failing cases. Since the beginning problem looked very simple, to come up with a starting algorithm took me around 10 minutes, oh well, I guess simple problem is simple as long as you have all possible different scenarios covered within tests.
On friday I wrote for myself around 15 test cases, but haven't covered failing ones  that gave me a lesson, how poor test cases can ruin the algorithm correctness and make you believe algorithm is free of bugs.
Now, that algorithm became a bit more complicated, I'm no longer happy how it reads. So next step of mine going to be a refactoring.
Would be interesting to know OP's progress if he finished and got all tests passing version, so we could share our algorithms and then might continue discussion on how to make them more elegant.
You showed up just in time for the waffles! And this tiny ad:
The WEB SERVICES and JAXRS Course
https://coderanch.com/t/690789/WEBSERVICESJAXRS
