Dev.to

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= 0) total += depth_first_search(matrix, i, j-1); return total; } int find_largest_island_size(vector 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 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 getExpressions(string num, int target) { this->target = target; this->num = num; dfs("", 0,0,0); return ans; } }

Feb 28, 2025 - 22:07
 0
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

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

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> 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> 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 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 getExpressions(string num, int target) {
    this->target = target;
    this->num = num;
    dfs("", 0,0,0);
    return ans;
  }
}
Read More

Tags:

Previous Article

DeepSeek - Recap

Next Article

How to build a secure project management platform with Next.js, Clerk, and Neon

Related Posts

Zod and Data modelling

Zod and Data modelling

Feb 25, 2025  0

Day 1133 : Tight

Day 1133 : Tight

Apr 3, 2025  0

A 2-Approximation Algorithm for Dominating Sets

A 2-Approximation Algorithm for Dominating Sets

Mar 27, 2025  0