2

I went for an interview, and got a workload problem:

Problem: write a function to tell whether a series of workloads will exceed 
         the maximum workload or not

Input: MaxWorkLoad: example 10
       Timeslot and workload: example [(2, 6, 3), (3, 8, 2), ... ]
       The (2, 6, 3) is begin time, end time, and workload
       And it means from time 2 to time 6, the workload is 3
       You can treat the 2, 6 as the UNIX epoch time.
       The time may not be integers, so instead of 2, it can be 2.2
       The input can be in any time order. For example: [(20, 60, 3), (3, 8, 2)]
       The workload will "add up", so a 3 and 2 will add up to 5

Output: a boolean indicating whether the series of workload can fit in without
        exceeding MaxWorkLoad 

The short question is: does this workload problem belong to a class of algorithm, and that when the array is empty, but data keep on coming in M times and we need to tell possible or not M times, is there a better solution than O(M * M)?


Details:

If I focused on how to determine whether the time ranges will overlap with each other, it turns out it is not an easy solution.

So I am not sure whether this is suitable as an interview question, as you may either know how to solve it or you don't. If you have seen it before, you will solve it like a breeze. If you haven't seen it before, I don't think 20 minutes may be enough time for you to get unstuck.

You may want to think about how you may solve it, if you want to have some fun.

The simple solution, which I could come up with, but after 15 minutes later, actually, can be: simply use a dictionary, and use the time boundary as the key, and if it is (2, 6, 3), then just mark it as dict[2] = 3 and dict[6] = -3.

Likewise, for (3, 8, 2), then dict[3] = 2 and dict[8] = -2

(and actually, if we treat the time endpoint as inclusive, then we won't have dict[8] = -2 but have dict[9] = -2, treating it as dropping some workload at time 9 instead of at 8)

And then, once you have the whole dictionary, now loop through each key in the dictionary, in sorted order, and keep a CurrentWorkLoad number as the work load. So when you see dict[2] as 3, add 3 to CurrentWorkLoad, and when you see dict[3], add the 2 to CurrentWorkLoad, and when you see dict[6], add the -3 to CurrentWorkLoad.

So as soon as CurrentWorkLoad is greater than MaxWorkLoad, then you can return false right away. Otherwise, at the end of the loop, simply return true.

And what if there is (2, 6, 3) and (6, 8, 1), meaning that the endpoint can "overlap" at the time 6? So I came up with, either use an array to remember all the values when it collides at 6, or, simply add up the values. So the first time you see (2, 6, 3), then dict[6] is -3, and when you see (6, 8, 1), then dict[6] += 1 and becomes -2.

So if in JavaScript, it is like

dict[beginTime] ||= 0;    // if not defined, then set it to 0
dict[beginTime] += workload;

dict[endTime] ||= 0; 
dict[endTime] -= workload;

and the rest of the algorithm will stay the same.

So the time complexity for the array size N is O(N log N), because we need to sort the keys.

The interviewer then asked me, what if this operation is repeated M times?

So for example, if the initial array is empty, but data keep on coming in, for M times, and M can be a million or ten million. Then what is the time complexity? I initially said then it is O(M * M log M), but later on found out it could be O(M * M), because we don't need to sort the keys every time. We can just "insert" the key in an already sorted list.

Is there a class of algorithm or problem solving that is related to this and have a solution better than O(M * M)?

  • 1
    Possible duplicate of What is O(...) and how do I calculate it? – Robert Harvey Jan 19 '17 at 22:34
  • it is not a duplicate of that question. If you say it is a duplicate, you can say for any algorithm question, it always is a duplicate of that question – nopole Jan 19 '17 at 23:07
  • I think for a bounded set of times, that could be done in O(n), using a sparse array (no sorting). However you over looked “The time may not be integers, so instead of 2, it can be 2.2”. – ctrl-alt-delor Jan 20 '17 at 9:02
3

Asking "does the workload problem belong to a class of algorithms" makes not much sense - the problem itself is not an algorithm. However, I assume your real question is to which class of algorithms your proposed solution belongs.

I see this in the category of sweep line algorithms. Though yours is not really a geometric problem, the main idea is the same: take alle relevant points "where something changes" on the x-axis (here the time line), sort them in ascending order, and then process them from left to right. In this processing step, some kind of "state" is changed at each relevant point in time. In geometric problems, this kind of state is often a geometric set of points or something similar, in your case it is simply the total workload.

The only thing I would change in your algorithm is, I would not use a dictionary as container. A simple list of number pairs ("point in time", "workload change") will do it, ordered by their first value. That does not change much to your solution, especially not the running time, it just avoids problems with duplicate keys.

  • Doesn't putting numbers in the correct order problem belong to the class of "sorting" algorithms? – nopole Jan 20 '17 at 17:45
  • @太極者無極而生: sure, but I don't think one would classify the algorithm as a whole as a sorting algorithm. Sorting is IMHO just one part of the algorithm. – Doc Brown Jan 20 '17 at 20:01
  • maybe a more exact phrase is, does the workload problem belong to a certain class of computer science problem? – nopole Jan 21 '17 at 7:08
  • @太極者無極而生: "sweep line algorithms" belong to computational geometrie, which belongs to computer science. – Doc Brown Jan 21 '17 at 7:37
  • hm... if you convert the (2, 6, 3) into (2, 3) and (6, -3), then it looks like so simple a problem. If the interviewer gave the input in such form, it is almost a no-brainer to solve it... so the tough part of the problem is just to convert the input into a different format? hm... i still don't like this question if it is an interview question – nopole Jan 21 '17 at 11:45
2

I actually thought of a possible solution that should be O(M log M), but it is after a little bit of thinking for the goal of optimization. I don't think the short 20 minutes in an interview really mean anything whether you think of it or not. Sometimes you also wanted to be more friendly and social when you talk during the interview, so the logical side of you might not be running at full speed.

Here is my solution:

  1. Just break down the data point (123, 456.7, 10) into two items: (123, 10) and (456.7, -10) to signify the increase of workload, and the decrease of workload.

  2. Now, you just keep a data structure of: at which time, the work load becomes what value. So for example, when you see (123, 10), then set or increase workload[123] by 10. (but how do you know what workload is at time 123 or right before time 123? See the description in step 6 later on). (the wordload is a dictionary / hash).

  3. So if the workload in step 2 exceed the maximum workload, you can already return false (and not add this "task", I suppose, because it exceeds the maximum workload -- meaning undo (2) or just do this test before doing the increase in step (2))

  4. Likewise, set or decrease workload[456.7] by 10.

  5. Maintain a binary tree of these time-points. So this tree will now have leaf node of 123 and 456.7. Note that when you search or insert to this binary tree, it is O(log M).

  6. Now you can repeat step (1) for the next data point. But so note that in step (1), how do you find out whether it exceeds or not? It is by doing a search in the binary tree. For example, when the next data point is (234, 345, 20), then search for 234 in the binary tree for the equal or less leaf node. Now you will see the 123, and use the workload[123] to know of the existing workload, when it is reaching time 234.

Doing so, with M data points entering as a data stream, the time to tell yes or no, should be O(M log M).

1

Not sure exactly what you mean about data coming in for M times. If we assume an endless stream of N timeslot/workload triplets. The best I come up with is also O(N*N). My main difference is that I do not use a dictionary/hashtable.

Basic idea: Initially we have 0 timeslots and there is no violation of MaxWorkLoad. On each new timeslot, find all overlapping timeperiods, and check if the new addition causes a violation. Worst case this all the current entries overlap.

If we use a sorted structure, we can sort entries by primarily begin time, with end time secondary (and for microoptimisation largest workload as the third priority). Then when we add a new timeslot (xBegin, xEnd, workload) we can find the right bound (and also do the insertion) in log N time, by comparing the xEnd with yBegin for the already inserted y. Then we sum the workload left until the end (we have to). If the sum at any point is larger than MaxWorkLoad then return true otherwise return false. Worst case we have to sum over N elements each time, which we would have to anyway if we just looped through all.

If the granularity of the workload is fixed, for example integers, and M is max workload then this changes to O(min(N*M, N*N)), because during the sum at most M entries will be processed.

I don't think in general you can do better than O(N*N). You must remember all N values received at any moment (unless they agree on start and end time), in order to determine any future violation.

The most related problem I can think of is the Lecture Hall Assignment problem (in the bottom) which is O(N*N). To convert (xBegin, xEnd, K), to lecture hall activities, make K copies of (xBegin, xEnd). Going the other direction we can reduce the decision variant of the lecture hall assignment problem to your problem. For each activity make a timeslot with the workload set to 1. The lecture hall decision problem is satisfiable with P halls, if your corresponding problem is satisfiable with MaxWorkLoad = P. If we believe the decision version of the lecture hall problem is also at least O(N*N), then so is your problem.

  • yes, the last part of my question... if (2000, 300000, 3) comes in, then it is one time. So if this kind of data comes in 1,000,000 times, then M is 1,000,000. – nopole Jan 20 '17 at 2:02
  • Are you sure you can find the overlapping efficiently? So if (1, 10000000000, 88) comes in, it may overlap with 20000 sets of earlier data – nopole Jan 20 '17 at 2:03
  • I made a minor edit to my search since it was broken. You can certainly find any overlapping efficiently. But you can not be sure how many overlaps. So regardless of how easy it is to find the overlapping timeslots, worst case it is all of them. – senevoldsen Jan 20 '17 at 12:49
  • Unfortunately I don't have reputation to make comments on other answers. But unless I misunderstand: @Lucas idea of splitting the segments is interesting. However, worst case, you create two new segments, and have to update all those inside, which all current in worst case - and that is for each timeslot. Then that operation on N elements alone N times make it O(N*N)? @richard's solution would only work if you do not add more data again. Otherwise it becomes equivalent to mine and @ 太極者無極而生 ? – senevoldsen Jan 20 '17 at 12:57
0

Yet another way to do it.

Since the examiner asked "what if this operation is repeated M times?" I would go with a database algorithm to keep the data and minimize the need of recalculation of the past every time a new observation came in.

My approach is that the workload is a line segment. When a new observation came, break the existing line segments on the database to match and increase the load only for the segments inside the new observation. I did this way mostly for fun. It is an interesting concept and will need a lot more test cases to see if my math has no side-effects.

If I not mistaken the performance will be something like O(log2 N) profile. Being N the size of the table. Which depends on the data. If there is a lot of overlap that may not grow with the number of observations. In a real world case we may even delete periods too old because this out-of-order behavior that is in the problem statement is probably in the recent data.

By the way, I code that in about 20 minutes. But I already did programs with line segment intersection on the database 12 year ago.

The problem you presented:

Problem: write a function to tell whether a series of workloads will exceed 
         the maximum workload or not

Input: MaxWorkLoad: example 10
       Timeslot and workload: example [(2, 6, 3), (3, 8, 2), ... ]
       The (2, 6, 3) is begin time, end time, and workload
       And it means from time 2 to time 6, the workload is 3
       You can treat the 2, 6 as the UNIX epoch time.
       The time may not be integers, so instead of 2, it can be 2.2
       The input can be in any time order. For example: [(20, 60, 3), (3, 8, 2)]
       The workload will "add up", so a 3 and 2 will add up to 5

Output: a boolean indicating whether the series of workload can fit in without
        exceeding MaxWorkLoad 

My code

drop schema if exists t1 cascade;
create schema t1;
set search_path='t1';
create table segment
(
    start_dt bigint,
    end_dt bigint,
    load bigint
);
create index segment_idx_start_dt on segment(start_dt);
create index segment_idx_end_dt on segment(end_dt);

create or replace function segment_add(bigint,bigint,bigint) returns void as $$
declare
    xr1 record;
    xr2 record;
    xr3 record;
    xs bigint;
begin
    raise info 'segment_add(%,%,%)', $1, $2, $3;
    -- select all segments where the $1 is in (one or zero)
    select into xr1 * from segment where $1 > start_dt and $1 < end_dt;
    if xr1 is not null then
        -- Split the segment on point $1
        raise info 'add % % % ($1)', xr1.start_dt, $1, xr1.load;
        raise info 'add % % % ($1)', $1, xr1.end_dt, xr1.load;
        insert into segment values 
            ( xr1.start_dt, $1, xr1.load ),
            ( $1, xr1.end_dt, xr1.load );   

        raise info 'del % %', xr1.start_dt, xr1.end_dt;     
        delete from segment where start_dt = xr1.start_dt and end_dt=xr1.end_dt;        

    end if;

    -- select all segments where the $2 is in (one or zero)
    select into xr2 * from segment where $2 > start_dt and $2 < end_dt;
    if xr2 is not null then
        -- split the segment on pont $2
        raise info 'add % % % ($2)', xr2.start_dt, $2, xr2.load;
        raise info 'add % % % ($2)', $2, xr2.end_dt, xr2.load;
        insert into segment values 
            ( xr2.start_dt, $2, xr2.load ),
            ( $2, xr2.end_dt, xr2.load );

        raise info 'del % %', xr2.start_dt, xr2.end_dt;         
        delete from segment where start_dt = xr2.start_dt and end_dt=xr2.end_dt;        

    end if;

    -- add segments that does not exist yet
    xs = $1;
    for xr3 in 
        select * from segment where start_dt between $1 and $2 order by start_dt
    loop
        if xs < xr3.start_dt then
            -- there is no segment before the space 
            raise info 'add % % % (2)', xs, xr3.start_dt, 0;        
            insert into segment values (xs,xr3.start_dt,0);         
        end if;
        xs = xr3.end_dt;
    end loop;

    if xs < $2 then
        raise info 'add % % % (3)', xs, $2, 0;      
        insert into segment values (xs,$2,0);
    end if;     

    -- now I must have all the fragment created.... I just need to update it
    update
        segment
    set
        load = load + $3
    where
        start_dt >= $1 and end_dt <= $2
    ;

end
$$ language 'plpgsql';

select segment_add(0,4000,6000);
select segment_add(1000,10000,5000);
select segment_add(12000,15000,5000);
select segment_add(13000,14000,6000);
-- the answer should have 0-1 1-4 4-10 12-13 13-14 14-15
select * from segment order by start_dt;
0

If we also consider “The time may not be integers, so instead of 2, it can be 2.2”, then the best I could do is O(n log n), with this algorithm.

  • add field is_started=false
  • Sort by start time
  • foreach item in queue
    • if not item.is_started
      • increment load (+ item.load)
      • mark item as started
      • reinsert in queue, key on appropriate-time (end_time if is_started else start_time)
    • else
      • decrement load (- item.load)
      • discard item
    • check load

This is algorithm to solve your problem.

  • What are you using to sort in O(n log n)? How are you getting O(n log n) with iterating and insert in a sorted queue? – paparazzo Jan 20 '17 at 15:06
  • There are plenty of sorts that can work in O(n log n), then we iterate O(n), re-inserting record in to queue only doubles n. This gives n log n + 2n = O(n log n) – ctrl-alt-delor Jan 20 '17 at 15:48
  • But you are not just inserting in the queue. You sorting on appropriate-time and that is not O(1). – paparazzo Jan 20 '17 at 15:50
  • Ah you are correct insertion in log n, that gives us n log n + 2n log n = O(n log n) – ctrl-alt-delor Jan 20 '17 at 16:24
  • isn't this almost the same as my original algorithm? except you keep on reinserting and re-sorting – nopole Jan 21 '17 at 7:06
-4

O(n)

Pretty simple

  • Create an array for load for each slot
  • Read the input and add the load for each slot
    For 3, 5, 7 just add 7 to 3, 4, and 5 slots

Does not require sorted input

public static bool WorkLoadN(int[,] workload, int max)
{
    int rowCount = workload.GetLength(0);
    int colCount = workload.GetLength(1);
    int[] loadNet = new int[rowCount];
    int start;
    int end;
    int load;
    bool underMax = true;
    for (int i = rowCount - 1; i >= 0; i--)  // process in reverse order to show it does not need order
    {
        start = workload[i, 0];
        end = workload[i, 1];
        if (end > rowCount - 1)
            end = rowCount - 1;
        load = workload[i, 2];
        for (int j = start; j <= end; j++)
            loadNet[j] += load;
    }
    Debug.WriteLine("");
    for (int i = 0; i < rowCount; i++)
    {
        Debug.WriteLine("loadNet[{0}] {1}", i, loadNet[i]);
        if (loadNet[i] > max)
        {
            Debug.WriteLine("max exceeded loadNet[{0}] {1}", i, loadNet[i]);
            underMax = false;
        }
    }
    return underMax;
}

// this is just the test code to test
public static void WorkLoadTestN()
{ 
    int rowCount = 20;
    int max = 100;
    int[,] workload = new int[rowCount, 3];
    for (int i = 0; i < rowCount; i++)
    {
        workload[i, 0] = i;
        workload[i, 1] = i + rand.Next(1, max / 6);
        workload[i, 2] = rand.Next(max / 4);
        Debug.WriteLine("intput start {0}  end {1}  load {2}", i, workload[i, 1], workload[i, 2]);
    }
    bool underMax = WorkLoadN(workload, max);
}
  • can you use a higher language if possible... not very sure of C/C++/C# syntax... and are you sure it will do it in O(N)? (1) what if the time is 2.2, 2.8, etc? (2) what if there are 2 million time slots and workload, with the first million of them small slots, such as (5, 6, 11) and (7, 8, 20), and then, the second million of records are really big slots, such as (1, 1000000000, 2), and (0, 3000000000000, 20), so for these big slots, don't you have to fill in a lot of entries in an array? More than 2,000,000 if you have to fill to entry 3000000000000 – nopole Jan 21 '17 at 2:34
  • It passes the loop once - yes is it is O(n). What if the second set is not really big time slot. Really 3000000000000. You refer to array in your question so silly me I assume it will fit in an array. – paparazzo Jan 21 '17 at 2:43
  • well, it says in the question it is UNIX time, so as of right now it is 1484968798, but it can be future scheduling too, so nothing can prevent it being a really big number. And what about 2.2, 2.2222? – nopole Jan 21 '17 at 3:20
  • Lot of stuff in the question. Good day. Sorry you did not get the job. – paparazzo Jan 21 '17 at 3:37
  • as I said, I really don't think this question is suitable for a short interview session – nopole Jan 21 '17 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.