valiente's blog

Hint for a google interview question!!
By valiente, 3 years ago, In English

Recently, I heard of a google interview question from my friend and was wondering about the solution but could come up with any. Any hints on this is appreciated. So the questions goes like this-

You are given some an array of segments (S), which basically represents time. There is no overlapping between the segments. You are given number of workers(k) who can work for q duration in one go. The workers would work for q duration straight to cover the given segments. We need to return the minimum number of uncovered segments.

Sample Test-

S — [3-12], [18-24], [30-35], k=2, q=7
OUTPUT- 1

Explanation- Segment 2 and 3 will get entirely covered.

S- [3-5], [8-9], [15-16], [17-25], [27-30] k=2, q=7, OUTPUT- 2

Explanation- Segment 1 and 2 will get covered by one worker, then either segment 3 or 5 can be covered by the other worker

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

want to make some clarification.

first, in test case 2, how can [17,25] be covered if the q=7?

second, can one segment be covered by different workers?
for example, if there is only one segment, [0,14], k=2, q=7, will output be 0? Thank you.

I think this is probably a dynamic programming question.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, yes you are correct, [17,25] cannot be covered. Will update the post. For the 2nd question, yes one segment can be covered by multiple workers, so output would be 0.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by valiente (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by valiente (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

My thoughts about this question.

Each worker start time must follow one of the two rules

1, the end of another worker

2, the start of the segment.

then we can define dp(i,rest_k) as the maximum segments that start time is i_th segment and totally rest_k workers

then we calculate what the maximum segments it can be covered by j consecutive workers start from i_th segment. we iterate j from 1 to rest_k

The time complexity is O(n*log(n)*k^2), n is the number of segments. Binary search is needed to find the next start after j consecutive workers from i_th segments.

The answer should be n-dp(0,k)

I think maybe there is solution that have better time complexity.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Cool problem and nice solution by hxu10! I could only think of a solution which uses the time in the DP state (which can be huge so that's bad).

This solution reminds me a lot of the problem Box Factory from CodeJam 2012 Round1C. It also requires this same trick of not using the number of boxes/toys (which is up to $$$10^{16}$$$) in the state but instead thinking about what the last "not completely used" element is, and using all of the other elements completely.

→ Reply