Recent searches
Search options
Tuesday C++ interview question: The smallest missing positive integer.
Given a list of integers, determine the smallest missing positive integer. Importantly your solution must run in O(n) time, and while you are permitted to modify the input, you can only use constant additional memory.
Examples:
{3, -1, 0, 4, 1} -> 2
{1, 2, 3} -> 4
Solve it yourself: https://compiler-explorer.com/z/G7r4rebhd
Solution: https://compiler-explorer.com/z/G9h3EPaG8
compiler-explorer.comCompiler Explorer - C++
/* The problem:
Given a list of integers, determine the smallest missing
positive integer.
Importantly your solution must run in O(n) time, and while
you are permitted to modify the input, you can only use
constant additional memory.
Examples:
{3, -1, 0, 4, 1} -> 2
{1, 2, 3} -> 4
*/
int lowest_missing(std::vector<int> data) {
}
int main() {
assert(lowest_missing({1,2,0}) == 3);
assert(lowest_missing({3,4,-1,1}) == 2);
assert(lowest_missing({7,8,9,11,12}) == 1);
assert(lowest_missing({9,8,7,6,5,4,3,2,1}) == 10);
assert(lowest_missing({9,8,7,4,3,2,1}) == 5);
assert(lowest_missing({1,1}) == 2);
}