Fab Fab - 5 months ago 14
Ruby Question

Ruby challange: experienced developers please reply

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

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.