Subroutines: Interview Problem Survey

Lets say we have an algorithm which performs a check if a string is a palindrome.

bool isPalindrome(string s) {
  for(int i = 0; i < s.length()/2; i++) {
    if(s.at(i) != s.at(s.length()-i-1)) {
      return false;
    }
  }
  return true;
}

This type of solution can be a subroutine to many questions; which may require pre-processing before calling isPalindrome(). An example may be removing spaces and alphanumeric characters.

bool cleanString(string s) {
  string cleanedstr = "";
  for(char c : s) {
    if(isalnum(c)) {
      cleanedstr += tolower(c);
    }
  }
  return cleanedstr;
}

To better use the isPalindrome as a subroutine we can add additional parameters. This can help answering questions like leetcode 680; where at most one character can be deleted.

bool isPalindrome(string s, int i, int j) {
  for(;i<j;i++,j++) {
    if(s.at(i) != s.at(j)) {
      return false;
    }
  }
  return true;
}

and the parent function handles the case where we may have up to one deleted character.

bool atMostOneMissingPalendrome() {
  int i = 0;
  int j = s.length() -1;
  for(int i = 0, j = s.length()-1; i<j; i++,j++) {
    if(s.at(i) != s.at(j)) {
      return isPalendrome(s, i, j-1) || isPalendrome(s, i+1, j);
    }
  }
  return true;
}

Now a more common scenario during an interview is having to use depth-first search or breadth first search. One question where this appears is connected-components or connected islands style questions; where you are given a matrix and asked to find the number of islands or the biggest island where a '1' denotes sand presence and '0' denotes water.

example instance;

111000
100011
001010

example solution;

4

example code;

int depth_first_search(vector<vector<int>> matrix, int i, int j) {
  if(matrix.at(i).at(j) == 0) {
    return 0;
  }

  int total = 1;
  if(i+1 < matrix.size()) 
    total += depth_first_search(matrix, i+1, j);
  if(i-1 >= 0) 
    total += depth_first_search(matrix, i-1, j);
  if(j+1 < matrix.at(0).size()) 
    total += depth_first_search(matrix, i, j+1);
  if(j-1 >= 0) 
    total += depth_first_search(matrix, i, j-1);
  return total;
}

int find_largest_island_size(vector<vector<int>> matrix) {
  int max_island = 0;
  for(int i = 0; i < matix.size(); i++) {
    for(int j = 0; j < matrix.at(0).size(); j++) {
       max_island = max(max_island, depth_first_search(matrix, i, j));
    }
  }
  return max_island
}

Now we may have scenarios where instead of the classic up, down, left, right search options we have more complex operators such as in leetcode 282. Where we are given a String of numbers and a target number and can introduce binary operators which result in the expression resolving to the target number. The goal is to find all such expressions

example instance;

"332" 8

example solution;

3+3+2

example code;

class Solver {
private:
  vector<string> ans;
  int target;
  string number;
  void dfs(string path, int idx, 
    long long curr, long long prev) {

    if(idx == num.size()) {
      if(curr == target)
        ans.push_back(path);
      return;
    }

    for(int i = idx; i < num.size(); i++) {
      if(i != idx && num[idx] == '0')
        break;
      string snumber = num.substr(idx, i - idx+1)
      long long number = stoll(snumber);
      //initially we have no choice but to take the number
      if(idx == 0) {
        dfs(path+snumber, i+1, number, number);
      } else {

        dfs(path+"+"+snumber, i+1, curr+number, number);
        dfs(path+"-"+snumber, i+1, curr-number, -number); 
        // during the scenario we multiply we have to remove the
        // the previous value from our running sum
        dfs(path+"*"+snumber, i+1, curr-prev+(prev*number), prev * number);
      }
    }
  }
public:
  vector<string> getExpressions(string num, int target) {
    this->target = target;
    this->num = num;
    dfs("", 0,0,0);
    return ans;
  }
}