Introduction

It was the end of the 2nd educational year at Ukrainian Catholic University, beginning of a summer. I passed all my exams and naturally had a free time, so I was looking for a job. I had a couple of interviews in different companies where I had to solve different tasks. This page is dedicated to one interesting task I had to solve.

Main

I came to an interview and guys gave this task to solve.

Task

Exists an array with 99 numbers ranged from 1 to 100, all entries are different. One number is missing to complete the set of 100 numbers. Find this number.

Task: Modified

This task wasn't really interesting so I modified it a bit, to be a little bit more complex and thought-provoking. Exists an array with 99 numbers ranged from 1 to 100, entries can be same. Some numbers are missing to complete the set of 100 numbers. Find numbers which are missing and count occurrence of each present number.

Approaches

RES = [ ]
FOR i = 1 TO N
    COUNT = 0
    FOR j = 0 TO N - 1
        IF i == numbers[ j ]
            COUNT++
    RES.add( i, COUNT )

Rough complexity of this approach is O(n²·K·C), where K is time to perform one action.

RES = [ ]
COUNTER = [ N elements ]
FOR i = 0 TO N - 1
    COUNTER[ numbers[ i ] - 1 ]++
FOR i = 0 TO N
    RES.add( i + 1, COUNTER[ i ] )

Rough complexity of this approach is O(2·n·K·C), where K is time to perform one action. However, this approach needs additional memory equal to O(n).

In this illustration we've taken K equal to sec.
At the end we multiply everything by C, which represents load of PC, speed of running code, speed of erasing SVG, speed of incrementing variable...
One empty object in array takes 65.72 bytes.
Number of points, n = 100.

O(n²·K·C) = 100² · · C ≈ 10 · C
Additional memory ~ 0 mb

O(2·n·K·C) = 2 · 100 · · C ≈ 0.2 · C
Additional memory ~ mb