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.
Write a function,which takes an array and an
index. The function should return another index,: this should
- (a), AND
arr[i] < arr[j]
- (b) there is nocloser to
arr[i] < arr[j]
In case of ties (see example below), choose the earliest (left-most)
of the two indices. If no number inis larger than
describe "#nearest_larger" do
it "handles a simple case to the right" do
nearest_larger([2,3,4,8], 2).should == 3
it "handles a simple case to the left" do
nearest_larger([2,8,4,3], 2).should == 1
it "treats any two larger numbers like a tie" do
nearest_larger([2,6,4,8], 2).should == 1
it "should choose the left case in a tie" do
nearest_larger([2,6,4,6], 2).should == 1
it "handles a case with an answer > 1 distance to the left" do
nearest_larger([8,2,4,3], 2).should == 0
it "handles a case with an answer > 1 distance to the right" do
nearest_larger([2,4,3,8], 1).should == 3
it "should return nil if no larger number is found" do
nearest_larger( [2, 6, 4, 8], 3).should == nil
def nearest_larger arr, idx
diff = 1
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
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
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 = (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
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.