undefined | Better HN

0 pointsjosephorjoe9y ago0 comments

I have stopped applying to companies that require these forms for an initial application submission, but recently I was asked to fill one out after a few email exchanges, a phone interview, and an online coding test.

We were about 2 weeks into the process at this point, and I was interested in the position and they seemed interested in me.

Next step was a technical phone interview, but before doing that they just needed me to fill out a formal application...

In this case, it doesn't matter much as I did not do well on the technical interview (got hit with a tricky algorithm question that I didn't know the trick for).

But it also probably didn't help my case much that I put down a fairly high number in their 'desired salary' field on the form -- basically I put down the top number I thought I could expect them to pay for this position.

0 pointsjosephorjoe9y ago0 comments

We were about 2 weeks into the process at this point, and I was interested in the position and they seemed interested in me.

Next step was a technical phone interview, but before doing that they just needed me to fill out a formal application...

In this case, it doesn't matter much as I did not do well on the technical interview (got hit with a tricky algorithm question that I didn't know the trick for).

0 comments

3 comments · 1 top-level

pryelluw9y ago· 2 in thread

Mind posting the algo question? I enjoy solving those :)

josephorjoeOP9y ago

It was a variation on Max Subarray, but instead of finding a contiguous max subarray you could (but didn't have to) skip every other number (but cannot skip 2 consecutive numbers).

So for [1, -1, 2, -1, 3, -1] you could take [1, 2, 3], but for [-1, -1, -5, -20, -10, -1, -3] you would end up with [-1, -5, -10, -1]. Input values and ranges are large enough that brute forcing won't work.

colorint9y ago

Well, the answer for an array of all negative numbers is to choose no elements, or if you must choose one, to choose the maximum single element. But presumably you solve it with the normal algorithm but with one level of look-behind. Something like,

  function maxsum(arr)
    local max2 = function(a, b) if a > b then return a else return b end end
    local max3 =
      function(a, b, c)
        if a > b and a > c then return a
        elseif b > c then return b
        else return c end end
    local best = 0
    local best_here = 0
    local i = 2
    while i <= table.maxn(arr) do
      best_here = max3(0, best_here + arr[i], best_here + arr[i-1])
      best = max2(best, best_here)
      if arr[i] > arr[i-1] then i = i + 2 else i = i + 1 end
    end
    return best
  end

  print(maxsum{1, -1, 2, -2, 3, -3, -4, 4, -5})

Assuming this algorithm is correct (it worked for my couple of test cases), the main trickiness is that you have to skip two elements if you choose the current one, to make sure that you don't double-choose.

1 more reply

j / k navigate · click thread line to collapse