bokuto_alright's blog

Snowflake OA Problems. Tough DP
By bokuto_alright, history, 5 months ago, In English

both problems here: https://leetcode.com/discuss/interview-question/5497148/snowflake-intern-oa-questions

Can anyone please give hints for the 2nd problem, I have no clue how to approach it. Thank you

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Denote '0' for the zero-adjacent processor, '1' for the one-adjacent processor, and '2' for the two-adjacent processor. Then, each valid sequence of deployments results in a unique string of '0', '1', 'and '2'. We'll call such a string valid.

In a valid string, ignoring '1's, we see that '0' and '2' must "alternate", starting and ending with '0' (e.g. if you remove '1's in a valid string, then the sequence must look something like "020202020"). Furthermore, it is easy to see that any string that satisfies this corresponds to a valid sequence of deployments.

Then, setting up a DP recurrence should be relatively straightforward with this observation.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Think about applying all the possibilities of the types of adjacent and how for applying one type of operation on i, it affects on i+1.

It can be solved using dp

For example If want no adjacent on i, then it is bound for i+1 to be either one adjacent or two adjacent.

Or if I want i to be two adjacent then it bound for i+1 to be no adjacent or one adjacent

→ Reply