Cisco | OA| 3 questions

Round 1

Questions:

1. 

   • Complete the balance_water function below.
   • The function is expected to return an INTEGER.
   • The function accepts INTEGER_ARRAY elements as parameter.

   #include <bits/stdc++.h>
   using namespace std;
   
   string ltrim(const string &);
   string rtrim(const string &);
   
   struct State {
       vector<int> jugs;
       int steps;
   };
   
   bool is_goal_state(const vector<int>& state, const vector<int>& goal) {
       return state == goal;
   }
   
   string state_to_string(const vector<int>& state) {
       stringstream ss;
       for (int val : state) {
           ss << val << ",";
       }
       return ss.str();
   }
   
   int balance_water(vector<int> elements) {
       vector<int> capacities(elements.begin(), elements.begin() + 4);
       vector<int> initial(elements.begin() + 4, elements.begin() + 8);
       vector<int> goal(elements.begin() + 8, elements.end());
   
       if (is_goal_state(initial, goal)) {
           return 0;
       }
   
       queue<State> q;
       unordered_set<string> visited;
   
       q.push({initial, 0});
       visited.insert(state_to_string(initial));
   
       while (!q.empty()) {
           State current = q.front();
           q.pop();
   
           for (int i = 0; i < 4; ++i) {
               for (int j = 0; j < 4; ++j) {
                   if (i != j && current.jugs[i] > 0 && current.jugs[j] < capacities[j]) {
                       int transfer = min(current.jugs[i], capacities[j] - current.jugs[j]);
                       vector<int> next_jugs = current.jugs;
                       next_jugs[i] -= transfer;
                       next_jugs[j] += transfer;
                       string next_state_str = state_to_string(next_jugs);
   
                       if (is_goal_state(next_jugs, goal)) {
                           return current.steps + 1;
                       }
   
                       if (visited.find(next_state_str) == visited.end()) {
                           q.push({next_jugs, current.steps + 1});
                           visited.insert(next_state_str);
                       }
                   }
               }
           }
       }
   
       return -1;
   }

2. 

   • Complete the find_max_elements function below.
   • The function is expected to return an INTEGER.
   • The function accepts INTEGER_ARRAY array as parameter.

   #include <bits/stdc++.h>
   using namespace std;
   
   string ltrim(const string &);
   string rtrim(const string &);
   
   int find_max_elements(vector<int> arr) {
       int target = arr[0]; // The target sum
       vector<int> elements(arr.begin() + 1, arr.end()); // The elements of the array
       int n = elements.size();
       int max_elements = 0;
   
       // Iterate through all possible subsets using bit manipulation
       for (int i = 0; i < (1 << n); ++i) {
           int sum = 0;
           int count = 0;
           for (int j = 0; j < n; ++j) {
               if (i & (1 << j)) {
                   sum += elements[j];
                   count++;
               }
           }
           if (sum == target) {
               max_elements = max(max_elements, count);
           }
       }
   
       return max_elements;
   }

3. 

   • Specific question not provided.