Skip to content

Instantly share code, notes, and snippets.

@binshi
Created May 18, 2017 10:42
Show Gist options
  • Save binshi/450c7f2460ef13655d330197ed1ab9f9 to your computer and use it in GitHub Desktop.
Save binshi/450c7f2460ef13655d330197ed1ab9f9 to your computer and use it in GitHub Desktop.
Given a variable length array of integers, partition them such that the even integers precede the odd integers in the array. Your must operate on the array in-place, with a constant amount of extra space. The answer should scale linearly in time with respect to the size of the array.
object Main {
def sortOddEven(numbers:Array[Int]) = {
println(numbers.mkString(","))
var left = 0
var right = numbers.length - 1
while (left < right) {
//Increment left index till we see an odd
while (numbers(left) % 2 == 0 && left < right)
left+=1
//Decrement right index till we see an even
while (numbers(right) % 2 == 1 && left < right)
right-=1
//swap the odd and even positions
if (left < right) {
val temp = numbers(left)
numbers(left) = numbers(right)
numbers(right) = temp
left+=1
right-=1
}
}
numbers
}
def main(args: Array[String]): Unit = {
println(sortOddEven(args(0).split(",").map(_.toInt)).mkString(","))
}
}
@gitowiec
Copy link

gitowiec commented Jul 19, 2017

@binshi What's the source of this and Compute100 problems? Google job interview? Best regards

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment