Ruby challenge: experienced developers opinions

Question

I'm working on some ruby problems geared towards new developers, but I would like the opinions of experienced developers on this. Sorry for the long post, and I really appreciate your time and opinions.

Problem Question

Write a function, nearest_larger(arr, i) which takes an array and an index. The function should return another index, j: this should satisfy:

• (a) arr[i] < arr[j], AND
• (b) there is no j2 closer to i than j where arr[i] < arr[j].

In case of ties (see example below), choose the earliest (left-most) of the two indices. If no number in arr is larger than arr[i], return nil.

Difficulty: 2/5

Rspec Test

describe "#nearest_larger" do
  it "handles a simple case to the right" do
    nearest_larger([2,3,4,8], 2).should == 3
  end

  it "handles a simple case to the left" do
    nearest_larger([2,8,4,3], 2).should == 1
  end

  it "treats any two larger numbers like a tie" do
    nearest_larger([2,6,4,8], 2).should == 1
  end

  it "should choose the left case in a tie" do
    nearest_larger([2,6,4,6], 2).should == 1
  end

  it "handles a case with an answer > 1 distance to the left" do
    nearest_larger([8,2,4,3], 2).should == 0
  end

  it "handles a case with an answer > 1 distance to the right" do
    nearest_larger([2,4,3,8], 1).should == 3
  end

  it "should return nil if no larger number is found" do
    nearest_larger( [2, 6, 4, 8], 3).should == nil
  end
end

Solution

def nearest_larger arr, idx
diff = 1
  loop do
    l = idx - diff
    r = idx + diff
    return l    if (l >= 0) && (arr[l] > arr[idx])
    return r    if (r < arr.length) && (arr[r] > arr[idx])
    return nil  if (l < 0) && (r >= arr.length)
    diff += 1
  end
end

Feedback

1. How would you go about working towards a solution for this problem? (what's your process?)
2. In your opinion do find the Problem Question clear and easy to understand?
3. How long should it take you to solve this problem? (10min, 20min, ...?)
4. Do agree with the level of difficulty? (Keep in mind this is geared towards new developers)
5. If willing: please post your own solution, showcasing your style of solving this problem.

I decided to post this question because I know how easy it can be for new developer to get stuck on a problem and not know what to write first. I'm hoping your responses will give an insight on how you would work through a problem that you perceive as a challenge.

Answer 1

I have not an experienced developer, or even an inexperienced one, but I will give you my thoughts anyway.

1 How would you go about working towards a solution for this problem? (what's your process?)

I would look to break into pieces, but surely everyone does that. For example, here the values in the array are only used to pull out the indices of elements that are larger, so I'd see the first problem as pulling out the indices and the second problem as dealing with the indices alone. I'd further simplify the latter by subtracting i from each index so that j and be compared to k like so: if j.abs < k.abs ..., rather than if (j-i).abs < (k-i).abs.... In choosing among different approaches, I tend to look for the one that is most easily understood ("reads best").

2. In your opinion do find the Problem Question clear and easy to understand?

Yes.

3. How long should it take you to solve this problem?

I refuse to answer on the grounds that it would surely incriminate me.

4. Do you agree with the level of difficulty?

It seems about right. It would be a "beginner" problem at rubeque.com.

5. If willing: please post your own solution, showcasing your style of solving this problem.

Sure.

def nearest_larger(arr, i)
  ret = nearest_to_zero( arr.each_with_index
                            .select { |e,j| e > arr[i] }
                            .map    { |_,j| j-i        } )
  ret ? ret + i : nil
end

I looked at two ways of writing nearest_to_zero(). The first is short, direct and clear, but inefficient, using sort!:

def nearest_to_zero(a)
  a.sort! { |j,k| (j.abs == k.abs) ? j <=> k : j.abs <=> k.abs }
  a.any? ? a.first : nil
end

More efficient, but not as pretty:

def nearest_to_zero(a)
  neg, pos = a.partition { |e| e < 0 }    
  case
  when neg.empty?
    pos.empty? ? nil : pos.first
  when pos.empty?
    neg.last
  else
    pos.last.abs < neg.last.abs ? pos.first : neg.last
  end 
end

For arr = [2,5,4,8,10], i = 2, the following steps are performed by nearest_larger():

a   = arr.each_with_index.select { |e,j| e > arr[i] } # => [[5,1],[8,3],[10,4]] 
b   = a.map { |_,j| j-i }                             # => [-1,1,2] 
ret = nearest_to_zero(b)                              # => -1 
ret ? ret + i : nil                                   # => 1 

In the first nearest_to_zero(), if two indices have equal absolute value (meaning they are equally close to i before the transformation), the tie goes to the index with the lower vlaue; else it is the index with the smaller absolute value.

In the second nearest_to_zero():

neg, pos = [-1,1,2].partition {|e| e < 0} #  => [[-1],[1,2]]

The rest should be self-explanatory.

I had read about rspec, but had not used it before. It was about time that it did. My code passed.

Answer 2

How would you go about working towards a solution for this problem? (what's your process?)

Start with a simple example, e.g. one of the tests. It is discovered that if the array element arr[i-1] is greater than arr[i] then you can immediately return i-1 as the answer. So you can just check in succession: i-1, i+1, i-2, i+2, i-3, i+3 etc. and return the first index that satisfies the inequality.

In your opinion do find the Problem Question clear and easy to understand?

Yes; the tests help but it only confirmed my understanding from the worded problem.

How long should it take you to solve this problem? (10min, 20min, ...?)

For a student in a test/classroom environment, no more than 10min. Depending on how much preparatory material they have had before this, maybe even less.

Do agree with the level of difficulty? (Keep in mind this is geared towards new developers)

Yes, 2/5 seems right.

If willing: please post your own solution, showcasing your style of solving this problem.

def nearest_larger( a, i )
  2.upto([i,a.length-i].max << 1) do |k|
    j = (k&1).zero? ? i - (k>>1) : i + (k>>1)
    return j if 0 <= j && j < a.length && a[i] < a[j]
  end
  return nil
end

---

Addendum: Thinking in Bits

This addendum will go through in greater detail the problem solving that went into the above solution for the benefit of new programmers.

As was mentioned in the answer to Question #1 above, the return value of nearest_larger is the first index j for which a[i] < a[j] as j iterates through the sequence

i-1, i+1, i-2, i+2, i-3, i+3, ...

This opens the way to a sub-problem, which is how to generate this sequence of numbers. When actually writing the program, I used comments as a "scratch pad", and in the code had something like this:

# -1, 1, -2, 2, -3, 3, ...            (Sequence G)

from which the prior sequence is constructed by just adding i to each term. Call this Sequence G. Now this is where a "binary intuition" would come into play. Consider a simple sequence of binary numbers that increases by one after each term, shown in Column A, and the familiar decimal representation is shown in Column B:

   A   B     C   D   E   F
----------------------------
0000   0   000   0   0   0
0001   1   000   1   0   0
0010   2   001   0   1  -1
0011   3   001   1   1   1
0100   4   010   0   2  -2
0101   5   010   1   2   2
0110   6   011   0   3  -3
0111   7   011   1   3   3

Now split the bits in each number into two groups: all the bits other than bit 0 (the right-most bit) as shown in Column C, and bit 0 shown in Column D. In other words, concatenate C and D to get A. The decimal representation of C is in column E. Notice that column D conveniently flips between 0 and 1, just as in Sequence G the numbers flip between negative and positive. We will use this to construct column F, which is the same as E, except when D is 0 make F negative. Finally, if we just start in the above table at A=0010 (or B=2) then Column F gives us the above Sequence G.

So now how do we get Column F from A in code? This is where bit operations come in to play.

C = A >> 1 - The >> right-shift operator shifts the bits on the LHS (left-hand side) by RHS (right-hand side). In this case, each value A is shifted to the right one place. The right-most bit is lost. Mathematically, it is the same as dividing by 2 and dropping the remainder in this case (B/2 == E with remainder dropped.)

D = A & 1 - The & is the bitwise AND operator. By "anding" A with 1, we select only bit 0; see the link in the prior sentence for more detail. This gives us Column D.

Putting this together in the code, we'll have k be the iteration variable that starts at 2 and increments by 1 each time. Then the above analysis gives us j:

j = (k&1).zero? ? i - (k>>1) : i + (k>>1)

The first value for j which is both in bounds and for which a[i] < a[j] holds is automatically the answer, so it can be returned immediately:

return j if 0 <= j && j < a.length && a[i] < a[j]

Finally, if there are no valid values for j then return nil. Other than calculating a lower upper-bound for k, which is left as a homework problem, that is the entirety of the nearest_larger function.

In actual practice, for a problem like this, a readable solution as posed in the OP is preferable since it is more clear and accessible to a wider group of programmers. This present approach was motivated by an opportunity to demonstrate the use of bit operations.