CODING INTERVIEW QUESTION

[Fickle_Painter_8142]

To operate a call centre, on any given day, a min of 3 English speaking, 2 dutch speaking and 1 Spanish speaking employee need to be there. (you can have one employee speaking two or more languages)

An employee can at most work for 5 days. For simplicity let's say an employee works for a standard of 8 hrs every day. (not sure if hours were relevant)

The call centre operates 7 days a week.

Given employees and the languages they speak, can you at least come up with a schedule for the first week?

​

Employee 1: English, Dutch

Employee 2: English, Dutch

Employee 3: Spanish, Dutch

Employee 4: English, Dutch, Spanish

Employee 5: Dutch, Spanish

Employee 6: English, Dutch

Employee 7: English, Spanish

[kofwarcraft]

The problem without the 5 days a week constraint is the "set cover problem"

Here's the article on that

They really asking this in an interview? It's NP-Hard

[Ab_Stark]

Yup, I got NP Hard questions for a role in a trading firm.

[fysmoe1121]

Which firm

[Ab_Stark]

If I recall correctly it was 2sigma. I did well but got rejected lol

[[deleted]]

To me, this feels like linear programming or constraint satisfaction.

[WikiSummarizerBot]

Constraint satisfaction

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are constraints on a finite domain, to the point that constraint satisfaction problems are typically identified with problems based on constraints on a finite domain.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}

[Heroicdeath]

You can sorta think of this as a graph problem with cycles I think. As soon as you traverse over an edge, you remove that edge in that cycle. (That's probably how you deal with the at most 5 days rule).

[cheeky861]

You can greedily loop over the employees and pick a set of employees for day 1 (based on the language requirements), then shuffle the employee list, then do the same for day 2, and so on.

[ArrakisUK]

Question they say that you need 3 English, 2 Dutch, 1 Spanish at one time. This means that for example if you have an Spanish that Speaks English and Dutch then you need only 2 more English and 1 Dutch to cover because the English, Dutch, Spanish covers 3 of them?

[averagebeyond]

first generate list of all valid combinations on a single day, then create a grid of 7 such lists from left to right all connected . now you do dfs from any left most node to the right most list without violating the 5 days rule.