Win a copy of Spring in Action (5th edition) this week in the Spring forum!

- Post Reply Bookmark Topic Watch Topic
- New Topic

programming forums
Java
Mobile
Certification
Databases
Caching
Books
Engineering
Micro Controllers
OS
Languages
Paradigms
IDEs
Build Tools
Frameworks
Application Servers
Open Source
This Site
Careers
Other
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Bear Bibeault
- Devaka Cooray
- Liutauras Vilda
- Jeanne Boyarsky

Sheriffs:

- Knute Snortum
- Junilu Lacar
- paul wheaton

Saloon Keepers:

- Ganesh Patekar
- Frits Walraven
- Tim Moores
- Ron McLeod
- Carey Brown

Bartenders:

- Stephan van Hulst
- salvin francis
- Tim Holloway

posted 4 months ago

Given an array of ints find the lowest positive number value missing from the sequence.

Remember that the answer must be a single positive int even if the values in the array are negative.

Examples:

The array will always have int values and will never be null.

The size of the array will vary as shown above.

The array may not be sorted and it may have duplicate values.

Don't forget to handle the edge cases of MAX_INT and MIN_INT appearing in the sequence.

Remember that the answer must be a single positive int even if the values in the array are negative.

Examples:

Array values | Answer |
---|---|

1,3,2,5,4,6,8,10 | 7 |

-1,-5,-3 | 1 |

-10,1,5 | 2 |

1,3,5,4,8,6,9,7,10,11 | 2 |

8,10,11 | 9 |

7,8,9 | 6 |

1,1,1,2,2,3,4,4,3,5,5,7,7,9 | 6 |

1 | 2 |

The size of the array will vary as shown above.

The array may not be sorted and it may have duplicate values.

Don't forget to handle the edge cases of MAX_INT and MIN_INT appearing in the sequence.

“The strongest of all warriors are these two — Time and Patience.” ― Leo Tolstoy, War and Peace

posted 4 months ago

Time yourself, from start to finish how long did it take to you program?

This was actually a sample test problem provided to me as part of an online test for an job interview.

I was only given 30 minutes, plus it had to be Java 8 compatible, but for this diversion any language will do.

This was actually a sample test problem provided to me as part of an online test for an job interview.

I was only given 30 minutes, plus it had to be Java 8 compatible, but for this diversion any language will do.

“The strongest of all warriors are these two — Time and Patience.” ― Leo Tolstoy, War and Peace

posted 4 months ago

That would be a one-liner, were it not for one slight problem:

in the examples you give, it looks like the positive number to be inserted must be bigger than the minimum of the given sequence, and that seems a reasonable requirement.

However, example 6 (7, 8, 9) gets 6 as solution, while I would have expected 10. If that requirement that I just mentioned needs not to hold, then why is not 1 the solution? Nowhere do I see a requirement that all elements must be consecutive. Can you elaborate a little?

in the examples you give, it looks like the positive number to be inserted must be bigger than the minimum of the given sequence, and that seems a reasonable requirement.

However, example 6 (7, 8, 9) gets 6 as solution, while I would have expected 10. If that requirement that I just mentioned needs not to hold, then why is not 1 the solution? Nowhere do I see a requirement that all elements must be consecutive. Can you elaborate a little?

posted 4 months ago

Sorry if I did not explain this problem properly, perhaps I have worded the title incorrectly so please let me try again.

Complete the sequence and/or find the missing number from the sequence:

If the sequence is missing a number then find the lowest positive number. If the sequence contains consecutive numbers then create/find the start of the sequence which is stated to be (lowest value of sequence -1) Zero is neither positive or negative. Any sequence which contains only negative numbers should return 1. All values are considered integer values. The input will never be null. The values may not be sorted. There may be duplicate values.

Complete the sequence and/or find the missing number from the sequence:

“The strongest of all warriors are these two — Time and Patience.” ― Leo Tolstoy, War and Peace

posted 4 months ago

So (8, 10, 11) --> 9 because the sequence contains consecutive numbers 10, 11 and therefore the answer is 9, or because the sequence is missing a number and therefore the answer is 9?

I'm feeling that "contains consecutive numbers" is a bit ambiguous; does that mean what I just said or does it require the sequence to contain only consecutive numbers?

Actually it must mean the latter, otherwise the result for (6, 7, 10, 11) would be undetermined.

Pete Letkeman wrote:

If the sequence contains consecutive numbers then create/find the start of the sequence which is stated to be (lowest value of sequence -1)

So (8, 10, 11) --> 9 because the sequence contains consecutive numbers 10, 11 and therefore the answer is 9, or because the sequence is missing a number and therefore the answer is 9?

I'm feeling that "contains consecutive numbers" is a bit ambiguous; does that mean what I just said or does it require the sequence to contain only consecutive numbers?

Actually it must mean the latter, otherwise the result for (6, 7, 10, 11) would be undetermined.

posted 4 months ago

I'm not too sure anymore add it's been a few days since I first read it and I am not able to go back to the test site as this was part of a job interview test.

“The strongest of all warriors are these two — Time and Patience.” ― Leo Tolstoy, War and Peace

Piet Souris

Master Rancher

Posts: 3001

105

posted 4 months ago

Why? 5 and 9 would fit the bill, but 5 is smaller than 9, so it would be 5.

Does 'consecutive' mean both in value AND in position? So, {1, 5, 6} would give 4, just like {1, 6, 5}? And, what about {7, 9, 8}?

But my half hour is nearly up. Since a cat in trouble makes crazy jumps (Dutch saying), I'd start by looking at the positive values, looking for the first index i for which there is a j such that a[j] = a[i] + 1, and for which a[i] - 1 is missing from the sequence, taking extra measures when a[i] = 1 or when such an i does not exist.

I'd throw the positive elements in a map<Value, original index> to speed up the lookups. Of course not a TreeMap, since then I would be sorting the sequence. Or is that not considered sorting?

With exercises like this I'd expect that company to pay 'decent' salaries, though...

Paul Clapham wrote:(...)Actually it must mean the latter, otherwise the result for (6, 7, 10, 11) would be undetermined.

Why? 5 and 9 would fit the bill, but 5 is smaller than 9, so it would be 5.

Does 'consecutive' mean both in value AND in position? So, {1, 5, 6} would give 4, just like {1, 6, 5}? And, what about {7, 9, 8}?

But my half hour is nearly up. Since a cat in trouble makes crazy jumps (Dutch saying), I'd start by looking at the positive values, looking for the first index i for which there is a j such that a[j] = a[i] + 1, and for which a[i] - 1 is missing from the sequence, taking extra measures when a[i] = 1 or when such an i does not exist.

I'd throw the positive elements in a map<Value, original index> to speed up the lookups. Of course not a TreeMap, since then I would be sorting the sequence. Or is that not considered sorting?

With exercises like this I'd expect that company to pay 'decent' salaries, though...

posted 4 months ago

Yes, you're right, I was posting in a hurry because I was being called to go out and update the car insurance.

I interpreted "The values may not be sorted" as "It is possible that the values given are not in increasing order" rather than "It is forbidden to sort the values". But I could be wrong. English is a wonderfully (terribly) ambiguous language which makes it more important for the programmer to ask "Did you mean X or Y when you said that?"

Piet Souris wrote:

Paul Clapham wrote:(...)Actually it must mean the latter, otherwise the result for (6, 7, 10, 11) would be undetermined.

Why? 5 and 9 would fit the bill, but 5 is smaller than 9, so it would be 5.

Yes, you're right, I was posting in a hurry because I was being called to go out and update the car insurance.

I'd throw the positive elements in a map<Value, original index> to speed up the lookups. Of course not a TreeMap, since then I would be sorting the sequence. Or is that not considered sorting?

I interpreted "The values may not be sorted" as "It is possible that the values given are not in increasing order" rather than "It is forbidden to sort the values". But I could be wrong. English is a wonderfully (terribly) ambiguous language which makes it more important for the programmer to ask "Did you mean X or Y when you said that?"

posted 4 months ago

This is what was meant.

I'm not too sure how to define 'consecutive' in this instance.

Paul Clapham wrote:I interpreted "The values may not be sorted" as "It is possible that the values given are not in increasing order"

This is what was meant.

I'm not too sure how to define 'consecutive' in this instance.

“The strongest of all warriors are these two — Time and Patience.” ― Leo Tolstoy, War and Peace

posted 3 months ago

All the examples and answers are in agreement to me based on the constraints you have specified, except the last one.

When the array value is 1, why the answer is 2 and not 0?

As per rule No. 2 - If the sequence contains consecutive numbers then create/find the start of the sequence which is stated to be (lowest value of sequence -1)

[edit] maybe because in your initial post is: "Remember that the answer must be a single positive int even if the values in the array are negative." (rule No. 3 says, that 0 is neither positive or negative)

But then kind of messes up things to me what the rules are.

Pete Letkeman wrote:

Complete the sequence and/or find the missing number from the sequence:

If the sequence is missing a number then find the lowest positive number. If the sequence contains consecutive numbers then create/find the start of the sequence which is stated to be (lowest value of sequence -1) Zero is neither positive or negative. Any sequence which contains only negative numbers should return 1. All values are considered integer values. The input will never be null. The values may not be sorted. There may be duplicate values.

All the examples and answers are in agreement to me based on the constraints you have specified, except the last one.

When the array value is 1, why the answer is 2 and not 0?

As per rule No. 2 - If the sequence contains consecutive numbers then create/find the start of the sequence which is stated to be (lowest value of sequence -1)

[edit] maybe because in your initial post is: "Remember that the answer must be a single positive int even if the values in the array are negative." (rule No. 3 says, that 0 is neither positive or negative)

But then kind of messes up things to me what the rules are.

posted 3 months ago

Let me reply with a question.

If zero is neither positive or negative and you are given the number one, what is the lowest whole positive number to make a sequence of more then one number?

This is an edge case scenario.

Perhaps I supplied this example by mistake.

I have forgotten all the examples from this challenge.

If zero is neither positive or negative and you are given the number one, what is the lowest whole positive number to make a sequence of more then one number?

This is an edge case scenario.

Perhaps I supplied this example by mistake.

I have forgotten all the examples from this challenge.

“The strongest of all warriors are these two — Time and Patience.” ― Leo Tolstoy, War and Peace

posted 3 months ago

Ok, let’s trust 2 is correct answer as sequence couldn’t be called as such if there were only one number in it. So now we know clear rules.

posted 3 months ago

Naive solution in Scheme (which came first to mind)

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!