4 ms·

Solution is just to have two indices into it leapfrogging as they find the next biggest one, right, and sum at the end if they've moved? Why would you sort?

tempestn 12y ago
My thoughts exactly. O(n) vs O(nlog(n)). Or even if you don't have formal comp sci experience, it seems intuitive that sorting the entire array (which I specify could be large) just to get the two highest values is overkill. Want to apply to our full stack developer position? Edit: Out of curiosity, what would you initialize the two tracking variables to?
- Blackthorn 12y ago
  Initialization is language dependent, of course :-)
- angersock 12y ago
  So, both variables are just indices, so we'll just start them at the first and second elements in the array. The smaller of the two we'll start marching forward, comparing against the value at the larger. Once the value is larger, we'll start marching the other one forward until we hit the end of the array. At this point, I realize that if we just reuse the indices, life becomes difficult if we don't encounter a larger value later in the array and hence we lose the smaller of the two largest values. So, instead, let's start with three indices (Biggest,Biggerest,Curr), set at the first, second, and third positions. So, now, we'll just move the Curr index forward, and if it encounters a value larger than the the current largest value, we'll set the index of the Biggerest into the Biggest and the index of the Curr into the Biggerest. We can then continue until we hit the end of the array, and add the values under the Biggest and Biggerest indices. I think that'll work. EDIT: For cleanliness' sake, we could init the Curr and Biggerest to both point at the second element of the array, but there may be a little special-case code there to worry about and I'm not awake enough yet for that. :)
  - tempestn 12y ago
    That sounds about right. Initializing the variables to the first two elements in the array is something very few people think to do. Most people set them to 0, which obviously doesn't work if the array doesn't contain at least two positive values. Of course, Blackthorn is also right that it's language-dependent. Most languages give you negative infinity, or treat null or false as negative infinity in comparisons, which makes things simpler.

tempestn 12y ago

My thoughts exactly. O(n) vs O(nlog(n)). Or even if you don't have formal comp sci experience, it seems intuitive that sorting the entire array (which I specify could be large) just to get the two highest values is overkill. Want to apply to our full stack developer position? Edit: Out of curiosity, what would you initialize the two tracking variables to?

Blackthorn 12y ago
Initialization is language dependent, of course :-)
angersock 12y ago
So, both variables are just indices, so we'll just start them at the first and second elements in the array. The smaller of the two we'll start marching forward, comparing against the value at the larger. Once the value is larger, we'll start marching the other one forward until we hit the end of the array. At this point, I realize that if we just reuse the indices, life becomes difficult if we don't encounter a larger value later in the array and hence we lose the smaller of the two largest values. So, instead, let's start with three indices (Biggest,Biggerest,Curr), set at the first, second, and third positions. So, now, we'll just move the Curr index forward, and if it encounters a value larger than the the current largest value, we'll set the index of the Biggerest into the Biggest and the index of the Curr into the Biggerest. We can then continue until we hit the end of the array, and add the values under the Biggest and Biggerest indices. I think that'll work. EDIT: For cleanliness' sake, we could init the Curr and Biggerest to both point at the second element of the array, but there may be a little special-case code there to worry about and I'm not awake enough yet for that. :)
- tempestn 12y ago
  That sounds about right. Initializing the variables to the first two elements in the array is something very few people think to do. Most people set them to 0, which obviously doesn't work if the array doesn't contain at least two positive values. Of course, Blackthorn is also right that it's language-dependent. Most languages give you negative infinity, or treat null or false as negative infinity in comparisons, which makes things simpler.