Test results - Codility

Tasks Details

easy

1. Dominator

Find an index of an array such that its value occurs at more than half of indices in the array.

Task Score

100%

Correctness

100%

Performance

100%

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

function solution(A);

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Solution

Programming language used JavaScript

Time spent on task 9 minutes

Notes

not defined yet

Code: 02:16:48 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) {
        // write your code in Java SE 8
    }
}

Code: 02:16:51 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) {
    // write your code in JavaScript (Node.js 8.9.4)
}

Code: 02:18:02 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    console.log(A)
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.076 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

[ 3, 4, 3, 2, 3, -1, 3, 3 ]

Code: 02:19:04 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    for(let num of A){
        map[num]
    }
}

Code: 02:19:31 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
      map[v] && map[v]  
    })
}

Code: 02:19:41 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
      map[v] ? map[v]  
    })
}

Code: 02:19:52 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
      map[v] ? map[v] : i;  
    })
}

Code: 02:20:04 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
      map[v] ? map[v].push(v) : [i];  
    })
}

Code: 02:20:13 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
      map[v] ? map[v].push(i) : [i];  
    });
    
    console.log(map)
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

{}

Code: 02:20:29 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
    console.log(map)
      map[v] ? map[v].push(i) : [i];  
    });
    
    console.log(map)
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

{}
{}
{}
{}
{}
{}
{}
{}

Code: 02:20:37 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
    console.log(map,)
      map[v] ? map[v].push(i) : [i];  
    });
    
    console.log(map)
}

Code: 02:20:39 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
    console.log(map,v,i)
      map[v] ? map[v].push(i) : [i];  
    });
    
    console.log(map)
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

{} 4 1
{} 3 2
{} 2 3
{} 3 4
{} -1 5
{} 3 6
{} 3 7
{}

Code: 02:21:07 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
    console.log(map,v,i)
      map[v] ? map[v].push(i) : map[v] = [i];  
    });
    
    console.log(map)
}

Code: 02:21:08 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
    console.log(map,v,i)
      map[v] ? map[v].push(i) : map[v] = [i];  
    });
    
    console.log(map)
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.076 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

{} 4 1
{ '4': [ 1 ] } 3 2
{ '3': [ 2 ], '4': [ 1 ] } 2 3
{ '2': [ 3 ], '3': [ 2 ], '4': [ 1 ] } 3 4
{ '2': [ 3 ], '3': [ 2, 4 ], '4': [ 1 ] } -1 5
{ '2': [ 3 ], '3': [ 2, 4 ], '4': [ 1 ], '-1': [ 5 ] } 3 6
{ '2': [ 3 ], '3': [ 2, 4, 6 ], '4': [ 1 ], '-1': [ 5 ] } 3 7
{ '2': [ 3 ], '3': [ 2, 4, 6, 7 ], '4': [ 1 ], '-1': [ 5 ] }

Code: 02:21:13 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = {};
    A.reduce((acc,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];  
    });
    
    console.log(map)
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.076 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

{ '2': [ 3 ], '3': [ 2, 4, 6, 7 ], '4': [ 1 ], '-1': [ 5 ] }

Code: 02:21:38 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    console.log(map)
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.076 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

{ '2': [ 3 ], '3': [ 0, 2, 4, 6, 7 ], '4': [ 1 ], '-1': [ 5 ] }

Code: 02:22:14 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    
    
    console.log(map)
}

Code: 02:22:29 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        
    }
    
    console.log(map)
}

Code: 02:22:53 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(item > A.length/2)
    }
    return -1;
}

Code: 02:23:06 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(item > A.length/2) return 
    }
    return -1;
}

Code: 02:23:21 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return map[item];
    }
    return -1;
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'object' found

Code: 02:23:38 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) console.;
    }
    return -1;
}

Code: 02:23:40 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) console.log(map[item]);
    }
    return -1;
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got -1, but dominator exists, for example on position 6

0.076 s

WRONG ANSWER, got -1, but dominator exists, for example on position 6

stdout:

[ 0, 2, 4, 6, 7 ]

Code: 02:23:48 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return ...map[item];
    }
    return -1;
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.120 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

solution.js:12
        if(map[item].length > A.length/2) return ...map[item];
                                                 ^^^

SyntaxError: Unexpected token ...
    at createScript (vm.js:80:10)
    at Object.runInNewContext (vm.js:135:10)
    at getSolution (/tmp/exec.js:392:29)
    at Promise.resolve.then (/tmp/exec.js:426:34)
    at <anonymous>
    at process._tickCallback (internal/process/next_tick.js:188:7)
    at Function.Module.runMain (module.js:686:11)
    at startup (bootstrap_node.js:187:16)
    at bootstrap_node.js:608:3

Code: 02:23:55 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return map[item];
    }
    return -1;
}

Code: 02:24:17 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return (...map[item]);
    }
    return -1;
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

solution.js:12
        if(map[item].length > A.length/2) return (...map[item]);
                                                        ^

SyntaxError: Unexpected token [
    at createScript (vm.js:80:10)
    at Object.runInNewContext (vm.js:135:10)
    at getSolution (/tmp/exec.js:392:29)
    at Promise.resolve.then (/tmp/exec.js:426:34)
    at <anonymous>
    at process._tickCallback (internal/process/next_tick.js:188:7)
    at Function.Module.runMain (module.js:686:11)
    at startup (bootstrap_node.js:187:16)
    at bootstrap_node.js:608:3

Code: 02:24:22 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return map[item];
    }
    return -1;
}

Analysis

expand all Example tests

▶

example
example test

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, integer expected, 'object' found

Code: 02:24:40 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return map[item][];
    }
    return -1;
}

Code: 02:24: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

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return map[item][0];
    }
    return -1;
}

Analysis

expand all Example tests

▶

example
example test

✔

0.072 s

Code: 02:25:02 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

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return map[item][0];
    }
    return -1;
}

Analysis

expand all Example tests

▶

example
example test

✔

0.072 s

Code: 02:25:05 UTC, js, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const map = A.reduce((map,v,i)=>{
      map[v] ? map[v].push(i) : map[v] = [i];
      return map;
    },{});
    
    for(let item in map){
        if(map[item].length > A.length/2) return map[item][0];
    }
    return -1;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example
example test

✔

0.072 s

expand all Correctness tests

▶

small_nondominator
all different and all the same elements

✔

0.068 s

▶

small_half_positions
half elements the same, and half + 1 elements the same

✔

0.072 s

▶

small
small test

✔

0.072 s

0.068 s

▶

small_pyramid
decreasing and plateau, small

✔

0.072 s

▶

extreme_empty_and_single_item
empty and single element arrays

✔

0.068 s

▶

extreme_half1
array with exactly N/2 values 1, N even + [0,0,1,1,1]

✔

0.068 s

0.072 s

▶

extreme_half2
array with exactly floor(N/2) values 1, N odd + [0,0,1,1,1]

✔

0.072 s

▶

extreme_half3
array with exactly ceil(N/2) values 1 + [0,0,1,1,1]

✔

0.072 s

expand all Performance tests

▶

medium_pyramid
decreasing and plateau, medium

✔

0.088 s

▶

large_pyramid
decreasing and plateau, large

✔

0.200 s

▶

medium_random
random test with dominator, N = 10,000

✔

0.084 s

▶

large_random
random test with dominator, N = 100,000

✔

0.156 s