Round 1
Questions:
Problem 1:
Alex is a TikTok influencer who loves shopping online and sharing his latest hauls with his followers. He’s super excited about buying several products from an e-commerce website to feature in his next video. Each item on his shopping list has its own price, and Alex wants to show his followers how to get the best deals.
Alex has a number of discount vouchers that he can use on any of his purchases. These vouchers offer a unique discount mechanism: the more vouchers used on a single item, the greater the discount. For instance, for each voucher used on an item, the price of that item is halved. If multiple vouchers are used on the same item, the price is halved repeatedly.
The discount can be represented by the following formula:
discounted price = p / 2^k
where:
- p is the original price of the item.
- k is the number of vouchers used on that item.
Example - Input:
vouchersCount = 3 prices = [8, 2, 13]
Output:
9
Solution:
- 13 / 2^2 = 3
- 8 / 2^1 = 4
- 2 / 2^0 = 2
Total = 4
I suspect this can be solved using DP? Correct me if I am wrong.
Candidate's Approach
The candidate suggests that dynamic programming (DP) could be a potential approach to solve this problem, considering the repeated halving of prices based on the number of vouchers used.
Interviewer's Feedback
No feedback provided.
Problem 2:
TikTok is organizing a grand TikTok event and wants to optimize the content delivery routes for the users. They have numServers servers numbered from 1 to numServers. The servers will be arranged in a sequence as follows: [1, 2, 3, ... , numServers]. The company has a list of numDisconnectedPairs pairs of servers that are not directly connected. Any pair not present in this list are directly connected. A subsegment of the route starting from server start and ending at server end is [start, start+1, start+2, ... , end]. A subsegment of the route is called good when all pairs of servers in that segment are directly connected. TikTok wants to know how many pairs (start, end) there are (1 ≤ start ≤ end ≤ numServers), such that the subsegment starting from server start and ending at server end is good.
Note: Servers can be reused across different subsegments. Each subsegment is considered independently, so a server can be part of multiple "good" subsegments. For example, if a server 3 is part of a "good" subsegment [2, 3, 4], it can still be reused in another "good" subsegment, like [3, 4, 5].
Example - Input:
numServers = 4 numDisconnectedPairs = 2 disconnectedPairs = [[1, 2], [2, 3]]
Output:
5
Solution:
- [1]
- [2]
- [3]
- [4]
- [3, 4]
Total = 5
I don't remember the constraints for these problems, but assuming worst constraints, how to solve these problems? Approach or code would be greatly appreciated.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.