Question 302453 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Minimum Sum of Multiple Indeces in an Array

Just BOMBED a Hacker Rank question for a job application and I’m so upset because I feel like I was onto something but couldn’t figure it out:

Write a function that when given an expected_load of requests to
servers, and an array of servers in which all indeces are powers of 2
([1, 1, 2, 4, 8, etc.]), return the minimum number of servers required
to equal the expected_load of requests. If there is no combination
which would equal the expected_load exactly, return a -1.

I’m pretty sure I botched the actual words of the question but it would go something like this:

function(10, [1, 2, 4, 8, 16]) {
  some stuff
}

returns 2 (the number of servers required, in this case server[1] and server[3])

i’m assuming you need a count for the number of servers being required but i couldn’t figure out how to keep track of that as WELL as the sum of everything as you kept adding up….I started with:

getMinServers(expected_load, server_array){
  for (let i = 0; i <= server_array.length, i++){
    for (let j = i+ 1; j <= server_array.length; j++ {
      if (server[i] + server[j] === expected_load){
        **this is where my brain craps out**
      }
    }
  }
}

I need to a way to count the number of indeces in the array whose VALUES add up exactly to the expected load…so you need to track the current sum of the indeces, as well as the sum of indeces used/necessary and my brain just would not work

Tags:

2

Answers


  1. 0

    you would just start with a very high power of two, if that is not larger than expected_load just double it until youve fouind one that is higher, then just subtract from expected_load and increment by one, next check if it is higher, if so, half it and check again until it is not anymore, subtract again and add 1. do so until you end up at 0. the counter is the amount of servers.

    Login or Signup to reply.
  2. 0

    Based on the info you provided, I probably would have tackled it a little differently. I’m sure my implementation is missing a few nuanced cases though.

    const determineNumServers = (load: number, serverCapacities: number[]) => {
    // Sort into descending order
    const sortedCaps: number[] = serverCapacities.sort((a: number, b: number) => b - a);
    // Setup some variables to help with looping
    let idx = 0;
    let matchedLoad = 0, matchedServerCount = 0;
    while (matchedLoad != load) {
        // Chip away at the matched load, trying to use larger capacities first
        const cap = sortedCaps[idx];
        if (cap + matchedLoad <= load) {
            matchedLoad += cap;
            matchedServerCount++;
        }
        idx++;
    }
    // If we matched the expected load, return the number of nodes, otherwise -1
    return matchedLoad == load ? matchedServerCount : -1;
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search