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

Challenge: Find the lowest missing positive number in the sequence  RSS feed

 
Bartender
Posts: 1856
81
Android Chrome IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
Array valuesAnswer
1,3,2,5,4,6,8,107
-1,-5,-31
-10,1,52
1,3,5,4,8,6,9,7,10,112
8,10,119
7,8,96
1,1,1,2,2,3,4,4,3,5,5,7,7,96
12
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.
 
Pete Letkeman
Bartender
Posts: 1856
81
Android Chrome IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Pete Letkeman
Bartender
Posts: 1856
81
Android Chrome IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
  •  
    Sheriff
    Posts: 23868
    50
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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.
     
    Pete Letkeman
    Bartender
    Posts: 1856
    81
    Android Chrome IntelliJ IDE Java MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Piet Souris
    Master Rancher
    Posts: 3001
    105
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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...    
     
    Paul Clapham
    Sheriff
    Posts: 23868
    50
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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?"
     
    Pete Letkeman
    Bartender
    Posts: 1856
    81
    Android Chrome IntelliJ IDE Java MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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.
     
    Marshal
    Posts: 6257
    420
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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.
     
    Pete Letkeman
    Bartender
    Posts: 1856
    81
    Android Chrome IntelliJ IDE Java MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Liutauras Vilda
    Marshal
    Posts: 6257
    420
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Liutauras Vilda
    Marshal
    Posts: 6257
    420
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Naive solution in Scheme (which came first to mind)
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!