Cassidoo’s Interview question of the week | 443

Learning Resources
1

Hello :waving_hand:

This week question is about moving numbers. Here it is.

Given an integer array and a number n, move all of the ns to the end of the array while maintaining the relative order of the non-ns. Bonus: do this without making a copy of the array!

Example:

$ moveNums([0,2,0,3,10], 0)
$ [2,3,10,0,0]

You can share your solutions under this post.

Happy coding :heart:

1 Like
2 
a.reject { it == n } + a.select { it == n }

(unless it needs to be super-performant)

edit: nah

a.partition { it == n }.reverse.flatten
4 Likes
3

My attempt:

require 'minitest/autorun'

def move_nums(arr, item, in_place: false)
  sort_method = in_place ? "sort_by!" : "sort_by" 
  arr.public_send(sort_method) { it == item ? 1 : 0 }
end

class TestQuestion < Minitest::Test
  def test_move_nums
    assert_equal [2, 3, 10, 0, 0], move_nums([0,2,0,3,10], 0)
    assert_equal [0, 2, 0, 3, 10], move_nums([0,2,0,3,10], 10)
    assert_equal [0, 0, 3, 10, 2], move_nums([0,2,0,3,10], 2)
    assert_equal [0, 1], move_nums([0,1], 1234)
    assert_equal [1, 3, 2, -10, -10, -10], move_nums([-10, 1, 3, -10, 2, -10], -10)
  end

  def test_move_nums_in_place!
    arr = [0, 2, 0, 3, 10]
    move_nums(arr, 0, in_place: true)

    assert_equal [2, 3, 10, 0, 0], arr
  end
end
4

My (naive) implementation:

def move_nums(ary, num)
  new_ary      = []
  nums_to_move = []

  ary.map do |element|
    element == num ? nums_to_move << element : new_ary << element
  end

  new_ary + nums_to_move
end

p move_numbers([0, 2, 0, 3, 10], 0) # => [2, 3, 10, 0, 0]
5

I thought of a similar implementation as @charlie, borrowed @katafrakt’s insight for the name, and wrapped it in a refinement just for fun.

module FlatReversePartition
  refine Enumerable do
    def flat_reverse_partition(el)
      sort_by { (it == el) ? 1 : 0 }
    end

    def flat_reverse_partition!(el)
      sort_by! { (it == el) ? 1 : 0 }
    end
  end
end

# Tests

using FlatReversePartition

[0, 2, 0, 3, 10].flat_reverse_partition(0).then do
  p it
  raise unless it == [2, 3, 10, 0, 0]
end

[0, 2, 0, 3, 10].then do
  it.flat_reverse_partition!(0)
  p it
  raise unless it == [2, 3, 10, 0, 0]
end
6

My simple solution below (no bonus points for me :frowning:)

def moveNums(numbers, n)
  count = numbers.count(n)
  numbers.delete(n)
  numbers + Array.new(count, n)
end
7

It would be interested to see if modification in-place would actually be faster than using methods from the standard library that make a copy of the array.

2 Likes
8

.reverse does not preserve the integer order. Swap that for a != and you’re golden.

a.partition{|e| e != ‘n’ }.flatten

9

partition produces array with two arrays as elements. reverse just swaps them, without touching the content of inner arrays. But you are right that using != is a better solution here.

10

:person_facepalming: When I retyped rather than copied your solution while I was playing I reversed it to .flatten.reverse which behaves quite differently. My apologies.

11

Good to see many replies under this post. I am so happy :slight_smile: I had to force myself not to look at your answers, lest they influence what I’m doing. :smiley: here my solution.

def move_nums(array, number)
  return unless array.include? number

  write = 0

  array.each do |element|
    if element != number
      array[write] = element
      write += 1
    end
  end

  (write...array.length).each { |i| array[i] = number }

  array
end
2 Likes
12

Use it and pray that this sort_by implementation turns out to be the stable one :wink:

13

Good catch! I guess I didn’t get the job… :smiling_face_with_tear:

1 Like