DSA 4.2 - Interview Problems

---

Problem 1 Partition to K Equal Sum Subsets

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Example

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Brute Force Approach

Objective

Determine if it is possible to divide the array into k non-empty subsets with equal sums.

Idea

• Generate all possible combinations of subsets.
• Check if each subset has an equal sum.
• Keep track of the count of subsets with equal sums.

Brute Force Code

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) return false; // If total sum is not divisible by k, return false
    vector<bool> visited(nums.size(), false);
    return canPartition(nums, k, 0, 0, sum / k, visited);
}

bool canPartition(vector<int>& nums, int k, int start, int currentSum, int targetSum, vector<bool>& visited) {
    if (k == 0) return true; // All subsets are formed
    if (currentSum == targetSum) return canPartition(nums, k - 1, 0, 0, targetSum, visited);

    for (int i = start; i < nums.size(); ++i) {
        if (!visited[i]) {
            visited[i] = true;
            if (canPartition(nums, k, i + 1, currentSum + nums[i], targetSum, visited)) return true;
            visited[i] = false;
        }
    }
    return false;
}

---

Partition to K Equal Sum Subsets optimization using DP

Observation

The backtracking approach still has overlapping subproblems, suggesting a dynamic programming solution.

Approach

• Create a DP table (dp) with size 1 << nums.size(). Each bit of the mask represents whether an element is included in the subset.
• Iterate through all possible states of the DP table (i represents the current state).
• For each state, iterate through the elements of the array (nums[j]).
• Check if the j-th element is not already included in the current state ((i & (1 << j)) == 0).
• Check if the previous state (dp[i ^ (1 << j)]) is valid, and adding the j-th element does not exceed the target sum.
• If conditions are met, update the current state (dp[i]) by adding the j-th element.
• Break the inner loop if a valid subset is found.
• If the last state of the DP table (dp.back()) is equal to 0, return true; otherwise, return false.

Optimized DP Code

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) return false;
    int targetSum = sum / k;
    sort(nums.rbegin(), nums.rend());
    vector<int> dp(1 << nums.size(), -1);
    dp[0] = 0;

    for (int i = 1; i < (1 << nums.size()); ++i) {
        for (int j = 0; j < nums.size(); ++j) {
            if ((i & (1 << j)) && dp[i ^ (1 << j)] != -1 && (dp[i ^ (1 << j)] + nums[j] <= targetSum)) {
                dp[i] = (dp[i ^ (1 << j)] + nums[j]) % targetSum;
                break;
            }
        }
    }

    return dp.back() == 0;
}

Complexity Analysis

Time Complexity: O(2^n * n), where n is the size of the input array.
Space Complexity: O(2^n).

---

Problem 2 Flatten Binary Tree to Linked List

Given the root of a binary tree, the task is to flatten the tree into a "linked list" using the same TreeNode class. The flattened "linked list" should follow the same order as a pre-order traversal of the binary tree.

Example

Consider the binary tree:

    1
   / \
  2   5
 / \   \
3   4   6

After applying the flatten function, the tree is transformed into:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Approach 1: Brute Force

In a brute force approach, we can perform a pre-order traversal of the binary tree and construct a new linked list using the elements in the order of traversal. This can be done by traversing the tree and creating a new node for each encountered element, linking the nodes in pre-order.

Code

public class Solution {
    public TreeNode flatten(TreeNode root) {
        if (root == null) {
            return null;
        }

        List<Integer> preorderList = new ArrayList<>();
        preOrderTraversal(root, preorderList);

        TreeNode dummy = new TreeNode(0);
        TreeNode current = dummy;

        for (int val : preorderList) {
            current.right = new TreeNode(val);
            current = current.right;
        }

        return dummy.right;
    }

    private void preOrderTraversal(TreeNode node, List<Integer> list) {
        if (node != null) {
            list.add(node.val);
            preOrderTraversal(node.left, list);
            preOrderTraversal(node.right, list);
        }
    }
}

Complexity Analysis

Time complexity: O(n)
The pre-order traversal visits each node once.

Space complexity: O(n)
The space required for the pre-order traversal list is proportional to the number of nodes in the tree.

---

Flatten Binary Tree to Linked List Optimized Approach

The strategy is to recursively flatten the right subtree first, and then handle the left subtree. If a node has a left child, it means there is a subtree on the left that needs to be flattened. To preserve the structure, the right child of the current node is linked to the rightmost node of the left subtree before making the left child the new right child. The left child is set to null after this operation.

Code

public class Solution {
    public TreeNode flatten(TreeNode root) {
        if (root != null) {
            // Flatten the right subtree first
            flatten(root.right);
            
            // Check if there is a left child
            if (root.left != null) {
                // Flatten the left subtree
                flatten(root.left);
                
                // Find the rightmost node in the left subtree
                TreeNode node = root.left;
                while (node.right != null) {
                    node = node.right;
                }
                
                // Attach the right subtree to the rightmost node of the left subtree
                node.right = root.right;
                
                // Make the left child the new right child
                root.right = root.left;
                
                // Set the left child to null
                root.left = null;
            }
        }
        return root;
    }
}

Complexity Analysis

Time complexity: O(n) - The function visits each node once.
Space complexity: O(h) - The space complexity is dominated by the recursion stack, which is proportional to the height of the binary tree (h). In the worst case, for a skewed tree, it could be O(n), but in balanced trees, it is typically O(log n). The in-place transformation is done without using additional space proportional to the number of nodes in the tree.

---

Problem 3 Insert Delete GetRandom O(1)Approach

Implement the RandomizedSet class:

• RandomizedSet() Initializes the RandomizedSet object.
• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Approach

For implementing the RandomizedSet class, we can use both an unordered map (mymap) and a vector (list). This combination allows for constant-time average complexity for the insert, remove, and getRandom operations.

vector (list):

• Stores the elements of the set.
• Indices of elements in this vector correspond to their positions in the set.

unordered_map (mymap):

• Used for mapping elements to their indices in the vector.
• Key: Element in the set.
• Value: Index of the element in the vector.

Insert Operation:

• Check if the value exists in the set using mymap.
• If the value exists, return false.
• If the value doesn't exist:
  • Add the value to mymap with its index in list.
  • Append the value to the end of list.
  • Return true to indicate a successful insertion.

Remove Operation:

• Check if the value exists in the set using mymap.
• If the value exists:
  • Retrieve the index of the value in list from mymap.
  • Swap the value to be removed with the last value in list.
  • Update mymap to reflect the new index of the last value.
  • Remove the last element from list.
  • Erase the value from mymap.
  • Return true to indicate a successful removal.
• If the value doesn't exist, return false.

GetRandom Operation:

• Generate a random index within the current size of list.
• Return the element at the randomly selected index.

Code

#include <unordered_map>
#include <vector>
#include <cstdlib>

class RandomizedSet {
private:
    std::unordered_map<int, int> mymap;
    std::vector<int> list;

public:
    RandomizedSet() {
        // Constructor: Initialize member variables.
    }

    bool insert(int val) {
        // If the value already exists, return false.
        if (mymap.count(val) != 0)
            return false;

        // Insert the value to the map with its index in the list.
        mymap[val] = list.size();

        // Add the value to the list as well.
        list.push_back(val);
        return true;
    }

    bool remove(int val) {
        // Check if the value exists in the map.
        if (mymap.count(val) != 0) {
            // Get the index of the value in the list.
            int index = mymap[val];

            // Swap the value to be removed with the last value in the list.
            int lastValue = list.back();

            // Replace the value at the given index with the last value.
            list[index] = lastValue;

            // Remove the last element from the list.
            list.pop_back();

            // Update the index of the last value in the map to reflect its new position.
            mymap[lastValue] = index;

            // Remove the value from the map.
            mymap.erase(val);
            return true;
        }
        return false;
    }

    int getRandom() {
        // Generate a random index within the current size of the list.
        int randomIndex = std::rand() % list.size();
        return list[randomIndex];
    }
};

Complexity Analysis

Insert and Remove

• Average time complexity is O(1) due to constant-time operations of mymap and list.

GetRandom

• Time complexity is O(1) since it involves random index generation and retrieval from list.

Space Complexity

• O(n) where n is the number of elements in the set, as both mymap and list grow with the size of the set.

---

Problem 4 Best Time to Buy and Sell Stocks III

You are given an array A, where the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit you can achieve by completing at most 2 transactions. Note that you cannot engage in multiple transactions at the same time, meaning you must sell the stock before buying again.

Example

Input: [3, 3, 5, 0, 0, 3, 1, 4]

Output: 6

Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), then buy on day 7 (price = 1) and sell on day 8 (price = 4). Total profit = 3 + 3 = 6.

Brute Force Solution

One way to approach this problem is to consider every possible pair of transactions and calculate the profit for each pair. Keep track of the maximum profit obtained. However, this approach would have a time complexity of O(n^4), making it impractical for large inputs.

Optimal Solution Approach

To optimize the solution, we can observe that we need to keep track of four variables for each day:

FirstBuy: The minimum price when buying for the first time.
FirstSell: The maximum profit when selling for the first time.
SecondBuy: The minimum price when buying for the second time.
SecondSell: The maximum profit when selling for the second time.
For each day, we simultaneously update these variables based on the current stock price.

Optimal Solution Code

int maxProfit(const vector<int> &A) {
    int FirstBuy = INT_MAX, FirstSell = 0, SecondBuy = INT_MAX, SecondSell = 0;

    for (int i = 0; i < A.size(); i++) {
        int b1 = FirstBuy, s1 = FirstSell, b2 = SecondBuy, s2 = SecondSell;

        FirstBuy = min(b1, A[i]);
        FirstSell = max(s1, A[i] - b1);
        SecondBuy = min(b2, A[i] - s1);
        SecondSell = max(s2, A[i] - b2);
    }

    return max(FirstSell, SecondSell);
}