Join Us
Loading Similar Posts
Entering edit mode
Question 1: Salesforce Workflow Configuration
Problem Statement:
Given a Salesforce workflow configuration string config consisting of digits (0-9) and placeholders (?), determine the number of ways the placeholders can be replaced with digits (0-9) such that no two adjacent workflow steps (digits) are the same.
Since the answer can be very large, return the answer modulo 10^9 + 7.
Example:
config = "1?3?"
- The first placeholder (?) can be replaced with 8 possible digits: {2, 4, 5, 6, 7, 8, 9, 0} (all digits except 1 and 3).
- The second placeholder can be replaced with 9 possible digits: {1, 2, 4, 5, 6, 7, 8, 9, 0} (all digits except 3).
This results in a total of 72 possible configurations.
Question 2: Safe Salesforce Passwords
Problem Statement:
Salesforce provides a secure system for organizations to manage their accounts and data. A password is considered safe if it satisfies the following criteria:
- The length of the password is exactly n.
- The password consists of lowercase English characters only.
- The password does not contain k or more consecutive identical characters.
Given the integers n (password length) and k (maximum allowed consecutive identical characters), calculate the total number of distinct safe passwords that can be generated. Since the number can be large, return the result modulo 10^9 + 7.
Example:
n = 2, k = 2
The total number of passwords of length 2 is 26 \times 26 = 676. There are 26 cases where k=2 consecutive characters are the same (e.g., "aa", "bb"). Thus, the answer is 676 - 26 = 650. Output is 650.
Question 3: Salesforce Data Collection
Problem Statement:
A Salesforce administrator is working on optimizing data collection for Opportunity records across multiple branches. The branches follow a hierarchical structure, forming a tree with n nodes labeled from 0 to n-1.
An array opportunityData of size n indicates whether a branch contains important Opportunity data. Specifically, opportunityData[i] is 1 if branch i holds relevant data and 0 otherwise.
To gather all Opportunity data, the admin must navigate through the branches using bidirectional paths (edges). The goal is to minimize the total distance traveled. Any data within a radius of 2 edges from a branch can be collected. For system consistency, the retrieval process must start and end at the same branch.
Determine the minimum number of edges the admin needs to traverse to collect all Opportunity data.
Entering edit mode
Problem1 -: (Salesforce Workflow Configuration) Solution
Topics Involved / Prerequisites
- Dynamic Programming (1D Space Optimized)
- Combinatorics
- Modular Arithmetic
Overview
- To find the total number of valid configurations, we can evaluate the number of ways to form a valid prefix ending in each of the 10 possible digits.
- By iterating through the string, we update our counts based on the rule that a digit cannot be placed next to an identical digit.
- Maintaining the total sum of valid configurations from the previous step allows us to compute the next step in constant time for each digit.
Approach
1. State Representation
We define an array dp of size 10, where dp[d] represents the number of valid workflow configurations up to the current character that end exactly with the digit d.
2. State Transitions
At each step i of the string, we calculate the sum of all values in dp from the previous step. Let this be total_sum.
- If the current character is a specific digit c, the only valid configurations ending at i must end in c. Thus, dp[c] = total_sum - previous_dp[c] (to avoid consecutive duplicates), and all other dp[d] become 0.
- If the current character is ?, any digit d can be placed here. For each digit d from 0 to 9, dp[d] = total_sum - previous_dp[d].
We apply the modulo operation at each addition and subtraction to prevent integer overflow.
Code
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int countWorkflows(string config) {
int n = config.length();
if (n == 0) return 0;
long long MOD = 1000000007;
vector<long long> dp(10, 0);
// Base case: First character
if (config[0] == '?') {
for (int d = 0; d <= 9; d++) {
dp[d] = 1;
}
} else {
dp[config[0] - '0'] = 1;
}
// Process remaining characters
for (int i = 1; i < n; i++) {
vector<long long> next_dp(10, 0);
long long total_sum = 0;
// Get the total valid configurations from the previous step
for (int d = 0; d <= 9; d++) {
total_sum = (total_sum + dp[d]) % MOD;
}
if (config[i] == '?') {
for (int d = 0; d <= 9; d++) {
// Total ways minus the ways ending in the same digit
next_dp[d] = (total_sum - dp[d] + MOD) % MOD;
}
} else {
int d = config[i] - '0';
next_dp[d] = (total_sum - dp[d] + MOD) % MOD;
}
dp = next_dp;
}
// Sum up all valid sequences of length n
long long ans = 0;
for (int d = 0; d <= 9; d++) {
ans = (ans + dp[d]) % MOD;
}
return ans;
}
int main() {
string config = "1?3?";
cout << "Valid Configurations: " << countWorkflows(config) << "\n"; // Output: 72
return 0;
}Time Complexity
- Time: O(N) - We iterate through the configuration string of length N exactly once. Processing the 10 possible digits at each step takes O(1) constant time.
- Space: O(1) - We only maintain two arrays of size 10 (current and next DP states), making the auxiliary space strictly constant.
Entering edit mode
Problem2-: (Safe Salesforce Passwords) Solution
Topics Involved / Prerequisites
- Dynamic Programming
- Sliding Window / Prefix Sums
- Combinatorics
Overview
- Instead of calculating invalid permutations to subtract from the total, it is much safer to directly count the valid combinations recursively.
- We can build a valid password by appending blocks of identical characters (ranging from length 1 up to k-1) to previously generated valid prefixes.
- Using a sliding window to keep track of the sum of valid prefixes allows us to perform these transitions optimally without inner loops.
Approach
1. Block Appending Logic
Let dp[i] be the number of valid passwords of length i. We can form a valid password of length i by taking a valid password of length i-j (where 1 \le j < k) and appending a block of j identical characters.
If we are forming the very first block (i-j == 0), we have 26 choices for the character. If we are appending to an already valid prefix (i-j > 0), the new block must start with a character different from the prefix's ending character, leaving exactly 25 choices.
2. Sliding Window Optimization
The formula requires us to sum the last k-1 values of dp. Instead of a nested loop, we maintain a window_sum variable. As we move forward, we add dp[i-1] to the window and subtract dp[i-k] when it falls out of range, reducing the math at each step to O(1).
C++ Code
#include <iostream>
#include <vector>
using namespace std;
int countSafePasswords(int n, int k) {
// A password must have at least 1 character to be valid
if (k <= 1) return 0;
long long MOD = 1000000007;
vector<long long> dp(n + 1, 0);
dp[0] = 1; // Base case for empty prefix
long long window_sum = 0;
for (int i = 1; i <= n; i++) {
// Add the previous valid prefix to our sliding window
window_sum = (window_sum + dp[i - 1]) % MOD;
// Remove the prefix that falls out of our allowed consecutive (k-1) window
if (i > k - 1) {
window_sum = (window_sum - dp[i - k] + MOD) % MOD;
}
// If forming the first block (total length < k), we have 26 letter choices
// for the absolute start of the string.
if (i < k) {
dp[i] = (26LL + 25LL * (window_sum - dp[0] + MOD)) % MOD;
}
// Otherwise, we only have 25 choices because the new block must start
// with a character different from the previous block's ending character.
else {
dp[i] = (25LL * window_sum) % MOD;
}
}
return dp[n];
}
Time Complexity
- Time: O(N) - We iterate from length 1 to N, performing a constant amount of math at each length via the sliding window.
- Space: O(N) - For storing the DP array up to length N (can be optimized to O(K) if space is heavily constrained).
Entering edit mode
Solution 3-: (Salesforce Data Collection) Solution
Topics Involved / Prerequisites
Graph Theory / Trees
Topological Sorting (Kahn's Algorithm Concept)
Minimum Height Trees
Overview
The core strategy relies on topological "trimming" of the tree leaves to find the absolute minimal required traversal path.
First, we continuously remove outer branches (leaves) that do not hold any important Opportunity data, leaving only the minimal subtree that spans all 1s.
Because our collection radius is 2, we can subsequently trim the leaves of this minimal subtree two more times, further shrinking the required traversal footprint.
Approach
1. Finding the Spanning Subtree
We track the degree (number of connections) of every node. We place all leaf nodes (degree exactly 1) that have opportunityData == 0 into a queue. We systematically remove these nodes, updating the degrees of their neighbors. If a neighbor becomes a leaf and also has no data, we enqueue it for removal. This leaves a minimal tree T that perfectly spans all required data points.
2. The Radius 2 Trim
Since the admin can collect data up to 2 edges away, they do not need to physically step onto the outermost edges of the minimal tree T. We perform a generic topological leaf trim on T to effectively shrink the required boundary by 1 radius. We repeat this generic leaf trim a second time to satisfy the total radius of 2.
3. Calculating Traversal
After trimming, the remaining nodes form the final required traversal path. In any tree, the number of edges is exactly Nodes - 1. Since the admin must start and return to the same branch, every required edge must be walked twice (down and back up), making the final answer 2 * (Remaining Nodes - 1).
Code-:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int minEdgesToCollectData(int n, vector<int>& edges_u, vector<int>& edges_v, vector<int>& oppData) {
if (n <= 1) return 0;
vector<vector<int>> adj(n);
vector<int> degree(n, 0);
// Build adjacency list and track node degrees
for (size_t i = 0; i < edges_u.size(); i++) {
int u = edges_u[i];
int v = edges_v[i];
adj[u].push_back(v);
adj[v].push_back(u);
degree[u]++;
degree[v]++;
}
queue<int> q;
vector<bool> removed(n, false);
int remaining = n;
// Step 1: Trim all dead-end leaves with no opportunity data
for (int i = 0; i < n; i++) {
if (degree[i] == 1 && oppData[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int curr = q.front();
q.pop();
removed[curr] = true;
remaining--;
degree[curr]--;
for (int neighbor : adj[curr]) {
if (!removed[neighbor]) {
degree[neighbor]--;
// If neighbor becomes a leaf and has no data, trim it too
if (degree[neighbor] == 1 && oppData[neighbor] == 0) {
q.push(neighbor);
}
}
}
}
if (remaining <= 1) return 0;
// Step 2: Trim the minimal tree's leaves exactly twice (for collection radius 2)
for (int step = 1; step <= 2; step++) {
queue<int> leaves;
for (int i = 0; i < n; i++) {
if (!removed[i] && degree[i] == 1) {
leaves.push(i);
}
}
while (!leaves.empty()) {
int curr = leaves.front();
leaves.pop();
removed[curr] = true;
remaining--;
degree[curr]--;
for (int neighbor : adj[curr]) {
if (!removed[neighbor]) {
degree[neighbor]--;
}
}
}
if (remaining <= 1) return 0;
}
// Total distance is walking every remaining edge twice (down and back)
return 2 * (remaining - 1);
}
Time Complexity
Time: O(N) - Processing degrees and performing the BFS-like leaf trimming accesses every node and edge a constant number of times.
Space: O(N) - We build an adjacency list and arrays for tracking node degrees and queues.
