Test results - Codility

Tasks Details

medium

1. DreamTeam

Divide developers into two teams to maximize their total contribution.

Task Score

100%

Correctness

100%

Performance

100%

A company has employed N developers (numbered from 0 to N−1) and wants to divide them into two teams. The first is a front-end team with F developers. The second is a back-end team with N−F developers. If the K-th developer is assigned to the front-end team then their contribution is A[K], and if they are assigned to the back-end team then their contribution is B[K]. What is the maximum sum of contributions the company can achieve?

Write a function:

function solution(A, B, F);

that, given two arrays A, B (consisting of N integers each) and the integer F, returns the maximum sum of contributions the company can achieve.

Examples:

1. Given A = [4, 2, 1], B = [2, 5, 3] and F = 2, the function should return 10. There should be two front-end developers and one back-end developer. The 0th and 2nd developers should be assigned to the front-end team (with contributions 4 and 1) and the 1st developer should be assigned to the back-end team (with contribution 5).

2. Given A = [7, 1, 4, 4], B = [5, 3, 4, 3] and F = 2, the function should return 18. The 0th and 3rd developers should be assigned to the front-end team and the 1st and 2nd developers should be assigned to the back-end team.

3. Given A = [5, 5, 5], B = [5, 5, 5] and F = 1, the function should return 15. The 0th developer can be assigned to the front-end team and the 1st and 2nd developers can be assigned to the back-end team.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..200,000];

arrays A and B have equal lengths;

each element of array A is an integer within the range [0..1,000];

F is an integer within the range [0..N].

Solution

Programming language used JavaScript

Time spent on task 22 minutes

Notes

not defined yet

Code: 16:18:31 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A, int[] B, int F) {
        // write your code in Java SE 8
    }
}

Code: 16:18:37 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, F) {
    // write your code in JavaScript (Node.js 8.9.4)
}

Code: 16:18:42 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');


function solution(A, B, F) {  
  if (F > (A.length/2)) {
    return solution(B, A, B.length-F);
  }
  if (F === 0) {
      return B.reduce((total, current) => total + current);
  }
  if (F === A.length) {
    return A.reduce((total, current) => total + current);
  }

  let tradeOffs = tradeOff(A, B);
  let trades = mostAdvantageous(tradeOffs, F)
  let count = 0;
  for (let i = 0; i < A.length; i++) {
    if (trades[i]) {
      count += A[i];
    } else {
      count += B[i];
    }
  }
  return count;
}

function tradeOff(A, B) {
  let tradeOffs = [];
  for (let i = 0; i < A.length; i++) {
    tradeOffs[i] = A[i] - B[i];
  }
  return tradeOffs;
}

class Heap {
  constructor() {
    this.storage = [0];
    this.size = 0;
  }
  insert(obj) {
    this.storage.push(obj);
    this.size += 1;
    this._bubble_up(this.size);
  }
  delete() {
    let prevHead = this.storage[1];
    this.storage[1] = this.storage[this.size];
    this.size -= 1;
    this.storage.pop();
    this._sift_down(1);
    return prevHead;
  }
  get_max() {
    return this.storage[1];
  }
  get_size() {
    return this.size;
  }
  _bubble_up(index) {
    while (Math.floor(index / 2) > 0) {
      if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
        [ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
      } else {
        break;
      }
      index = Math.floor(index / 2);
    }
  }
  _sift_down(index) {
    while ((index * 2) <= this.size) {
      let max_child = this._max_child(index);
      if (this.storage[index].value < this.storage[max_child].value) {
        [ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
      } else {
        break;
      }
      index = max_child;
    }
  }
  _max_child(index) {
    if (index * 2 + 1 > this.size) {
      return index * 2;
    } else {
      if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
        return index * 2;
      } else {
        return index * 2 + 1;
      }
    }
  }
}

function mostAdvantageous(tradeOffs, F) {
  let max = new Heap();
  for (let i = 0; i < tradeOffs.length; i++) { 
    let current = { index: i, value: tradeOffs[i] }
    max.insert(current);
  }
  let returnedMax = {};
  let i = 0;
  while (i < F) {
    returnedMax[max.get_max().index] = max.get_max().value;
    max.delete();
    i++;
  }
  return returnedMax;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.120 s

▶

example2
Second example test.

✔

0.116 s

▶

example3
Third example test.

✔

0.116 s

Code: 16:39:33 UTC, js, verify, result: Passed

show code in pop-up

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');


function solution(A, B, F) {  
  if (F > (A.length/2)) {
    return solution(B, A, B.length-F);
  }
  if (F === 0) {
      return B.reduce((total, current) => total + current);
  }
  if (F === A.length) {
    return A.reduce((total, current) => total + current);
  }

  let tradeOffs = tradeOff(A, B);
  let trades = mostAdvantageous(tradeOffs, F)
  let count = 0;
  for (let i = 0; i < A.length; i++) {
    if (trades[i]) {
      count += A[i];
    } else {
      count += B[i];
    }
  }
  return count;
}

function tradeOff(A, B) {
  let tradeOffs = [];
  for (let i = 0; i < A.length; i++) {
    tradeOffs[i] = A[i] - B[i];
  }
  return tradeOffs;
}

class Heap {
  constructor() {
    this.storage = [0];
    this.size = 0;
  }
  insert(obj) {
    this.storage.push(obj);
    this.size += 1;
    this._bubble_up(this.size);
  }
  delete() {
    let prevHead = this.storage[1];
    this.storage[1] = this.storage[this.size];
    this.size -= 1;
    this.storage.pop();
    this._sift_down(1);
    return prevHead;
  }
  get_max() {
    return this.storage[1];
  }
  get_size() {
    return this.size;
  }
  _bubble_up(index) {
    while (Math.floor(index / 2) > 0) {
      if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
        [ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
      } else {
        break;
      }
      index = Math.floor(index / 2);
    }
  }
  _sift_down(index) {
    while ((index * 2) <= this.size) {
      let max_child = this._max_child(index);
      if (this.storage[index].value < this.storage[max_child].value) {
        [ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
      } else {
        break;
      }
      index = max_child;
    }
  }
  _max_child(index) {
    if (index * 2 + 1 > this.size) {
      return index * 2;
    } else {
      if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
        return index * 2;
      } else {
        return index * 2 + 1;
      }
    }
  }
}

function mostAdvantageous(tradeOffs, F) {
  let max = new Heap();
  for (let i = 0; i < tradeOffs.length; i++) { 
    let current = { index: i, value: tradeOffs[i] }
    max.insert(current);
  }
  let returnedMax = {};
  let i = 0;
  while (i < F) {
    returnedMax[max.get_max().index] = max.get_max().value;
    max.delete();
    i++;
  }
  return returnedMax;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.072 s

▶

example2
Second example test.

✔

0.072 s

▶

example3
Third example test.

✔

0.072 s

expand all User tests

▶

test_data1

✔

0.072 s

OK
function result: 8

▶

test_data2

✔

0.072 s

OK
function result: 8

▶

test_data3

✔

0.072 s

OK
function result: 6

User test case 1:

[[3, 2, 1], [5, 2, 1], 0]

User test case 2:

[[3, 2, 1], [5, 2, 1], 1]

User test case 3:

[[3, 2, 1], [5, 2, 1], 3]

Code: 16:39:59 UTC, js, verify, result: Passed

show code in pop-up

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');


function solution(A, B, F) {  
  if (F > (A.length/2)) {
    return solution(B, A, B.length-F);
  }
  if (F === 0) {
      return B.reduce((total, current) => total + current);
  }
  if (F === A.length) {
    return A.reduce((total, current) => total + current);
  }

  let tradeOffs = tradeOff(A, B);
  let trades = mostAdvantageous(tradeOffs, F)
  let count = 0;
  for (let i = 0; i < A.length; i++) {
    if (trades[i]) {
      count += A[i];
    } else {
      count += B[i];
    }
  }
  return count;
}

function tradeOff(A, B) {
  let tradeOffs = [];
  for (let i = 0; i < A.length; i++) {
    tradeOffs[i] = A[i] - B[i];
  }
  return tradeOffs;
}

class Heap {
  constructor() {
    this.storage = [0];
    this.size = 0;
  }
  insert(obj) {
    this.storage.push(obj);
    this.size += 1;
    this._bubble_up(this.size);
  }
  delete() {
    let prevHead = this.storage[1];
    this.storage[1] = this.storage[this.size];
    this.size -= 1;
    this.storage.pop();
    this._sift_down(1);
    return prevHead;
  }
  get_max() {
    return this.storage[1];
  }
  get_size() {
    return this.size;
  }
  _bubble_up(index) {
    while (Math.floor(index / 2) > 0) {
      if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
        [ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
      } else {
        break;
      }
      index = Math.floor(index / 2);
    }
  }
  _sift_down(index) {
    while ((index * 2) <= this.size) {
      let max_child = this._max_child(index);
      if (this.storage[index].value < this.storage[max_child].value) {
        [ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
      } else {
        break;
      }
      index = max_child;
    }
  }
  _max_child(index) {
    if (index * 2 + 1 > this.size) {
      return index * 2;
    } else {
      if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
        return index * 2;
      } else {
        return index * 2 + 1;
      }
    }
  }
}

function mostAdvantageous(tradeOffs, F) {
  let max = new Heap();
  for (let i = 0; i < tradeOffs.length; i++) { 
    let current = { index: i, value: tradeOffs[i] }
    max.insert(current);
  }
  let returnedMax = {};
  let i = 0;
  while (i < F) {
    returnedMax[max.get_max().index] = max.get_max().value;
    max.delete();
    i++;
  }
  return returnedMax;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.068 s

▶

example2
Second example test.

✔

0.068 s

▶

example3
Third example test.

✔

0.068 s

expand all User tests

▶

test_data1

✔

0.068 s

OK
function result: 8

▶

test_data2

✔

0.068 s

OK
function result: 8

▶

test_data3

✔

0.068 s

OK
function result: 6

User test case 1:

[[3, 2, 1], [5, 2, 1], 0]

User test case 2:

[[3, 2, 1], [5, 2, 1], 1]

User test case 3:

[[3, 2, 1], [5, 2, 1], 3]

Code: 16:40:01 UTC, js, final, score: 100

show code in pop-up

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');


function solution(A, B, F) {  
  if (F > (A.length/2)) {
    return solution(B, A, B.length-F);
  }
  if (F === 0) {
      return B.reduce((total, current) => total + current);
  }
  if (F === A.length) {
    return A.reduce((total, current) => total + current);
  }

  let tradeOffs = tradeOff(A, B);
  let trades = mostAdvantageous(tradeOffs, F)
  let count = 0;
  for (let i = 0; i < A.length; i++) {
    if (trades[i]) {
      count += A[i];
    } else {
      count += B[i];
    }
  }
  return count;
}

function tradeOff(A, B) {
  let tradeOffs = [];
  for (let i = 0; i < A.length; i++) {
    tradeOffs[i] = A[i] - B[i];
  }
  return tradeOffs;
}

class Heap {
  constructor() {
    this.storage = [0];
    this.size = 0;
  }
  insert(obj) {
    this.storage.push(obj);
    this.size += 1;
    this._bubble_up(this.size);
  }
  delete() {
    let prevHead = this.storage[1];
    this.storage[1] = this.storage[this.size];
    this.size -= 1;
    this.storage.pop();
    this._sift_down(1);
    return prevHead;
  }
  get_max() {
    return this.storage[1];
  }
  get_size() {
    return this.size;
  }
  _bubble_up(index) {
    while (Math.floor(index / 2) > 0) {
      if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
        [ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
      } else {
        break;
      }
      index = Math.floor(index / 2);
    }
  }
  _sift_down(index) {
    while ((index * 2) <= this.size) {
      let max_child = this._max_child(index);
      if (this.storage[index].value < this.storage[max_child].value) {
        [ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
      } else {
        break;
      }
      index = max_child;
    }
  }
  _max_child(index) {
    if (index * 2 + 1 > this.size) {
      return index * 2;
    } else {
      if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
        return index * 2;
      } else {
        return index * 2 + 1;
      }
    }
  }
}

function mostAdvantageous(tradeOffs, F) {
  let max = new Heap();
  for (let i = 0; i < tradeOffs.length; i++) { 
    let current = { index: i, value: tradeOffs[i] }
    max.insert(current);
  }
  let returnedMax = {};
  let i = 0;
  while (i < F) {
    returnedMax[max.get_max().index] = max.get_max().value;
    max.delete();
    i++;
  }
  return returnedMax;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N)) or O(N)

expand all Example tests

▶

example1
First example test.

✔

0.072 s

▶

example2
Second example test.

✔

0.072 s

▶

example3
Third example test.

✔

0.072 s

expand all Correctness tests

▶

one_developer
N = 1.

✔

0.072 s

▶

small_simple
N = 6, 7. Two small simple tests.

✔

0.072 s

▶

small_random
N = 20. Small random tests.

✔

0.072 s

▶

small_A_always_bigger
N = 20. A[i] > B[i].

✔

0.072 s

0.076 s

0.072 s

▶

small_bigger_and_smaller_differences
N = 20. Some developers have small difference between A[i] and B[i].

✔

0.072 s

expand all Correctness/performance tests

▶

medium_random
N = 300. Medium random tests.

✔

0.072 s

0.076 s

▶

medium_A_always_bigger
N = 300. A[i] > B[i].

✔

0.072 s

0.076 s

▶

medium_bigger_and_smaller_differences
N = 300. Some developers have small difference between A[i] and B[i].

✔

0.072 s

0.084 s

0.076 s

expand all Performance tests

▶

large_random
N = 200,000. Large random tests.

✔

0.480 s

0.548 s

0.560 s

▶

large_A_always_bigger
N = 200,000. A[i] > B[i].

✔

0.532 s

0.512 s

0.440 s

▶

large_bigger_and_smaller_differences
N = 200,000. Some developers have small difference between A[i] and B[i].

✔

0.488 s

0.408 s

0.480 s

▶

max_tests
N is maximal, upper corner cases.

✔

0.172 s

0.280 s

0.172 s