Video Ads Insertion Facebook Python Interview Question

You're on Meta (Facebook's) Newsfeed Ads Team, working on an experiment to increase the number of video ads served up in a person's newsfeed.

The newsfeed ranking team gives you a list of which denotes what type of content their algo is planning to serve a user.

• 0 denotes a normal post
• 1 denotes a video
• 2 denotes a non-video ad

You want to insert n more video ads; however, you can't place a video ad next to an existing video otherwise users will be annoyed about Meta's newsfeed being too video-heavy. Similarly, you can't place a video ad next to a non-video ad, because you don't want to overwhelm the user with consecutive ads.

Is it possible to insert more video ads into the feed based on ?

Example 1:

Input: feed_items = [1, 2, 0, 0, 0], n = 3

Output: True

Explanation:

• The first video ad can be inserted between the third and the fourth elements.
• The second video ad can be inserted between the fourth and the fifth elements.
• The third video ad can be inserted at the end.

Thus, we can insert 3 out of 3 video ads, so we return True.

Example 2:

Input: feed_items = [1, 0, 2, 0, 1, 1, 0], n = 2

Output: False

Explanation:
The only place where we can place a video ad is at the end of , so we can't insert all 2 video ads as requested, hence we return False.

Intuition

To determine if we can place ads in a list of posts (), we’ll look for spaces between normal posts (s) where ads can go. By counting these spaces, we can see if placing ads is possible.

Algorithm

Since ads can only go between normal posts:

1. We’ll start at an imaginary index to allow placement at the start of the list.
2. For each position, we’ll check two consecutive elements, treating the first as and the next as .

• If both and are , we have a spot for an ad.
• We’ll use short-circuit evaluation to avoid out-of-range errors:
  • For , if is , Python skips .
  • Similarly, avoids checking when at the last position.

If our count of valid slots reaches , we can place all required ads and return .

Here's the code:

Counting Consecutive Zeros

Another way to find spots for ads is by counting consecutive zeros:

1. Count Consecutive Zeros: For any group of consecutive zeros, , we can place ads in between, as long as is greater than 1.
2. Consider Boundaries: Ads may also be placed at the start or end if those positions have s.

Here's is the code;