Optimizing Array Processing with Ruby Techniques | CodeSignal Learn

Optimizing Array Processing with Ruby Techniques | CodeSignal Learn

Introduction

Hello there! Are you ready to tackle another engaging problem today? We have a practical task that will enhance your problem-solving skills. This task involves working with arrays, leveraging Ruby hashes, sorting, and using techniques such as the two-pointer method that we've covered in previous Ruby lessons. Let's dive in!

Task Statement

Our task is as follows. Suppose you have two equally long arrays, a and b, with a length varying from 1 to 1000, with each element being a unique positive integer ranging from 1 up to 1,000,000. Your challenge is to craft a Ruby method that identifies the closest number in array b to 2 * b[i] for each i . Upon finding this number, say for a specific i, it is b[j], we need to construct a new array using a[j] values in the order of increasing i . Consider this example: Ruby a = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110] b = [4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100] After executing your method, the resulting array should be: Ruby [80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110] Let's walk through the first few steps: The first item in b is 4 at index 0 . Double of this number is 8 . The closest number to 8 in array b is 8 itself, located at index 7 . The number at the same index in array a is 80, so we add 80 to our new array. The second item in b is 12 at index 1 . Double of this number is 24 . The closest number to 24 in b is 25, found at index 9 . The corresponding value in a at this index is 100 . Thus, 100 is added to our new array. The third item in b is 3 at index 2 . Double of this number is 6 . The closest number to 6 in b is 6 itself, found at index 4 . The corresponding value in a is 50 . Therefore, 50 is added to our new array. Proceed similarly for the remaining elements in b .

Solution Building: Step 1

Begin by creating a sorted list from array b. This list will comprise pairs of values from b and their corresponding indices. Here, each pair's value represents the element in b, while the index denotes its location in array b. This sorted list acts similarly to a hash map, organizing data for efficient retrieval and traversal. Here's the initial part of our Ruby method: Rubydef find_and_replace(a, b) b_sorted = b.map.with_index { |val, idx| [val, idx] }.sort_by { |pair| pair[0] } end In this Ruby code, we utilize map.with_index to create an array of pairs. Each pair comprises a value from b and its index. The sort_by method then arranges these pairs based on their values in ascending order.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 2

With our sorted list ready, we now initialize a right pointer j and a result array res. The pointer j helps maintain our search within the boundaries of b_sorted, while res holds our final output. def find_and_replace(a, b) b_sorted = b.map.with_index { |val, idx| [val, idx] }.sort_by { |pair| pair[0] } j = 0 # Initialize right pointer res = Array.new(a.length, 0) # Initialize the result array end

Solution Building: Step 3

Here's where we implement the main logic. We iterate over each item in b_sorted using its index i. For every item, we calculate the target, which is twice the value of the current item in b_sorted. We adjust j until it points to the closest number smaller than the target (2 * b_sorted[i][0]). This continues while j is within bounds and the next number is closer to the target. def find_and_replace(a, b) b_sorted = b.map.with_index { |val, idx| [val, idx] }.sort_by { |pair| pair[0] } j = 0 # Initialize right pointer res = Array.new(a.length, 0) # Initialize the result array b_sorted.each_with_index do |val, i| target = 2 * b_sorted[i][0] # The target is twice the current number in the sorted B while j < b_sorted.length - 1 && b_sorted[j + 1][0] < target j += 1 # Move right pointer to find a number smaller than or equal to the target end if j < b_sorted.length - 1 && (b_sorted[j + 1][0] - target).abs < (target - b_sorted[j][0]).abs j += 1 # Move pointer if next number is closer end res[b_sorted[i][1]] = a[b_sorted[j][1]] end end

Solution Building: Step 4

In this final step, we use the indices from b_sorted to modify the corresponding elements in array a. The right pointer j helps determine which element from a goes into res based on the same index relation. def find_and_replace(a, b) b_sorted = b.map.with_index { |val, idx| [val, idx] }.sort_by { |pair| pair[0] } j = 0 # Initialize right pointer res = Array.new(a.length, 0) # Initialize the result array b_sorted.each_with_index do |val, i| target = 2 * b_sorted[i][0] # The target is twice the current number in the sorted B while j < b_sorted.length - 1 && b_sorted[j + 1][0] < target j += 1 # Move right pointer to find a number smaller than or equal to the target end if j < b_sorted.length - 1 && (b_sorted[j + 1][0] - target).abs < (target - b_sorted[j][0]).abs j += 1 # Move pointer if next number is closer end res[b_sorted[i][1]] = a[b_sorted[j][1]] end res end And there you have it! You've successfully crafted a Ruby method capable of producing the required output. This method iteratively replaces each element in array a according to the defined logic and returns the modified array.

Ruby

def find_and_replace(a, b)
  b_sorted = b.map.with_index { |val, idx| [val, idx] }.sort_by { |pair| pair[0] }
  
  j = 0  # Initialize right pointer
  res = Array.new(a.length, 0)  # Initialize the result array
end

Ruby

def find_and_replace(a, b)
  b_sorted = b.map.with_index { |val, idx| [val, idx] }.sort_by { |pair| pair[0] }
  
  j = 0  # Initialize right pointer
  res = Array.new(a.length, 0)  # Initialize the result array
  
  b_sorted.each_with_index do |val, i|
    target = 2 * b_sorted[i][0]  # The target is twice the current number in the sorted B
    while j < b_sorted.length - 1 && b_sorted[j + 1][0] < target
      j += 1  # Move right pointer to find a number smaller than or equal to the target
    end
    if j < b_sorted.length - 1 && (b_sorted[j + 1][0] - target).abs < (target - b_sorted[j][0]).abs
      j += 1  # Move pointer if next number is closer
    end
    res[b_sorted[i][1]] = a[b_sorted[j][1]]
  end
end

Ruby

def find_and_replace(a, b)
  b_sorted = b.map.with_index { |val, idx| [val, idx] }.sort_by { |pair| pair[0] }
  
  j = 0  # Initialize right pointer
  res = Array.new(a.length, 0)  # Initialize the result array
  
  b_sorted.each_with_index do |val, i|
    target = 2 * b_sorted[i][0]  # The target is twice the current number in the sorted B
    while j < b_sorted.length - 1 && b_sorted[j + 1][0] < target
      j += 1  # Move right pointer to find a number smaller than or equal to the target
    end
    if j < b_sorted.length - 1 && (b_sorted[j + 1][0] - target).abs < (target - b_sorted[j][0]).abs
      j += 1  # Move pointer if next number is closer
    end    
    res[b_sorted[i][1]] = a[b_sorted[j][1]]
  end

  res
end