UPVOTE IF THIS HELPED YOU
Question 2:
For a string s, which consists only of characters '0' and '1', find the number of subsequences of length 5, which are palindromes.
As the answer can be large, return the answer modulo (10 ^ 9 + 7)
Note:
• A palindrome is a string that reads the same backward as forward.
• A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
• Two subsequences are considered different if the indices of the string that forms the subsequences are different.
Example
s = "0100110"
Using 1-based indexing, the 5 subsequences are
• indices (1, 2, 3, 6, 7) -> 01010
• indices (1, 2, 3, 5, 7) -> 01010
• indices (1, 2, 4, 6, 7) -> 01010
• indices (1, 2, 4, 5, 7) -> 01010
• indices (1, 2, 5, 6, 7) -> 01110
5 modulo (10^9+7)=5
Function Description:
Complete the function getPalindromesCount in the editor with the following parameter:
string s: the binary string
Returns
int: the number of subsequences of length 5 which are palindromes, modulo (10^9 + 7).
Constraints
• 5 ≤ |s| ≤10^5
• All characters in s are either 0 or 1.
▼Input Format For Custom Testing
The first and only line contains a string, s.
▼ Sample Case 0
Sample Input For Custom Testing
STDIN FUNCTION
010110 -> s = "010110"
Sample Output:
3
Explanation:
Palindromic subsequences with their indices
• (1, 2, 3, 4, 6) -> 01010
• (1, 2, 3, 5, 6) -> 01010
• (1, 2, 4, 5, 6) -> 01110
▼ Sample Case 1
Sample Input For Custom Testing
STDIN FUNCTION
01111 -> s = "01111"
Sample Output
0
Explanation:
There is no palindrome subsequence of length 5.
Question 3:
Implement a prototype of a friend recommendation system for a social media application.
There are n users indexed from 0 to n-1, and m friendships are represented as a 2d array, friendships, where the ith friendship is a connection between users friendships[i][0] and friendships[i][1].
A user x is suggested as a friend to user yif:
- x and y are not already friends
- x and y have the maximum number of common friends (friends that both x and y are connected to)
- If multiple users satisfy conditions 1 and 2, the user with the minimum index is recommended
Given n and friendships, for each of the n users, find the index of the friend that should be recommended to them. If there is no recommendation available, report -1.
Example
Suppose n = 5, m = 5, and connections = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
Table:
| User | Max Common Friends With | Recommendation
| 0 | 3(1, 2) | 3
| 1 | 2(0, 3) | 2
| 2 | 1(0, 3) | 1
| 3 | 0(1, 2) | 0
| 4 | 2(3),1(3) | 1(minimum index)
Hence the answer returned is [3, 2, 1, 0, 1].
Function Description:
Complete the function getRecommendedFriends in the editor with the following parameters:
int n: the number of users
int friendships[m][2]: the friendships between the users
Constraints:
• 1 ≤ n ≤ 10^5
• 0 ≤ m ≤2.5 x 10^5
• 0 ≤ friendships[i][0], friendships [1][1] ≤ n
• There are no self-loops or multiple edges.
• Each user has a maximum of 15 friends.
• The network of friends might be disjoint.
Input Format For Custom Testing
The first line contains an integer, n.
The next line contains an integer, m, the size of friendships.
The next line contains a constant integer, 2, the size of friendships[i].
Each line i of the m subsequent lines contains two integers friendships[i][0] and friendships[i][1].
▼ Sample Case 0
STDIN FUNCTION
3 → n = 3
3 → m = 3
2
0 1-> friendships = [[0, 1], [1, 2], [2, 0]]
1 2
2 0
Sample Output
-1
-1
-1
Explanation:
Since everyone is friends with each other, no recommendation can be made.
▼ Sample Case 1
STDIN FUNCTION
3 → n = 3
2 → m = 2
2
0 1-> friendships = [[0, 1], [0, 2]]
0 2
Sample Output
-1
2
1
