DEV Community: Mehran Ghamaty

Search Space: Interview Problem Survey

Mehran Ghamaty — Tue, 04 Mar 2025 01:34:17 +0000

classic binary search is used to solve many problems like leetcode 35. Where we would like to find the position we insert a given value into an already sorted list.

Example instance;

[1,3,5,6], 5

Example solution;

Example code;

function searchInsert(vector<int> list, int to_insert) {
  int pivot, left = 0; right = list.length()-1;
  while(left <= right) {
    pivot = (left+right) >> 2;
    if(list[pivot] == to_insert) {
      return pivot;
    }
    if(to_insert > list[pivot]) {
      left = pivot + 1;
    } else {
      right = pivot - 1;
    }
  }
}

Similar to depth-first search or breadth-first search. This algorithm can be used as a sub-routine when search in a space if the space is already structured.

Lets look at leetcode 778 Where we are given a slowly filling pool and must swim from one end of the pool to the next. Where we use binary search to guess our constraint; time. Then perform traditional depth-first search to reach the end.

Example instance;

[[0,2],[1,3]]

Example solution;

Example code;

class Solution {
private:
  bool possible(int time, vector<vector<int>> grid, int i, int j) 
  {
    int RN = grid.size();
    int CN = grid.at(0).size();

    if(i == RN-1 && j == CN-1) return true;

    if(i + 1 < RN && grid.at(i+1).at(j) < time) {
      return possible(time, grid, i+1, j);
    }
    if(i - 1 >= 0 && grid.at(i-1).at(j) < time) {
      return possible(time, grid, i-1, j);
    }
    if(j + 1 < CN && grid.at(i).at(j+1) < time) {
      return possible(time, grid, i, j+1);
    }
    if(j - 1 >= 0 && grid.at(i).at(j-1) < time) {
      return possible(time, grid, i, j-1);
    }
    return false;
  }
public:
  int swimInWater(vector<vector<int>> grid) {
    int L = 1, H = grid.size() * grid.at(0).size();
    while(start < max_time) {
      int M = (L+H) >> 1;
      if(!possible(M, grid, 0, 0)) {
        L = M+1;
      } else {
        H = M-1;
      }
    }
  }
}

This problem can also be solved with Dijkstra's algorithm and Union-Find. The intuition behind Dijkstra's being to first identify Optimal Sub-structure

Example Dijkstra's;

struct V {
  int v, x, y
  V(int v_, int x_, int y_) : v(v_), x(x_), y(y_) {}
  bool operator< (const V &c) const { return this.v > c.v; } 
}

class Solution {
private:
  priority_queue<V> pq;
  int M;
  int N;  
public:
  int swimInWater(vector<vector<int>> grid) {
    M = grid.size();
    N = grid.at(0).size();

    pq.push(V(grid[0][0], 0,0));
    vector<vector<bool>> seen(M, vector<int>(N));
    int res = 0;
    seen[0][0] = true;

    while(!pq.empty()) {
      V p = pq.top(); 
      pq.pop();
      res = max(res, p.v);
      if(p.x == M - 1 && p.y == N - 1) {
        return res;
      }
      if(p.x + 1 < M && !seen[p.x+1][p.y]) {
        seen[p.x+1][p.y] = true;
        pq.push(V(grid[p.x+1][p.y], p.x, p.y);
      }
      if(p.x - 1 < M && !seen[p.x-1][p.y]) {
        seen[p.x-1][p.y] = true;
        pq.push(V(grid[p.x-1][p.y], p.x, p.y);
      }
      if(p.y + 1 < M && !seen[p.x][p.y+1]) {
        seen[p.x][p.y+1] = true;
        pq.push(V(grid[p.x][p.y+1], p.x, p.y);
      }
      if(p.y - 1 < M && !seen[p.x][p.y-1]) {
        seen[p.x][p.y-1] = true;
        pq.push(V(grid[p.x][p.y-1], p.x, p.y);
      }
    }
  }
}

This differences between this question and network delay where we already used Dijsktra's is that we only care about reaching the end node, so instead of keep track of the largest ingress to the node we check if we have seen the node before.

Another method being union-find, which more directly answers the question is the groups which connect the start to end node.

Optimal Substructure: Interview Problem Survey

Mehran Ghamaty — Sat, 01 Mar 2025 19:28:13 +0000

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.Wikipedia

In other words optimal solutions to sub-problems form the overall optimal solution.

Here we can use the property of optimal sub-structure to explore the space of all possible entries into a phone pad leetcode [17].

example instance;

"232"

example solution;

["ada","adb","adc","aea","aeb","aec","afa","afb","afc","bda","bdb","bdc","bea","beb","bec","bfa","bfb","bfc","cda","cdb","cdc","cea","ceb","cec","cfa","cfb","cfc"]

example code;

class Solver {
  unordered_map<char, string> operators = {
    {'2', "abc"}, {'3', "def"}, {'4', "ghi"},
    {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
    {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
  }
  vector<string> SOLUTION;
  string packetNumber;

  //in order depth-first-search
  void depthFirstSearch(int index, string path) {
    if(path.length() == packet_number.length()) {
      solution.push_back(path);
      return
    }

    map<char, string>::iterator letters_iterator = operators.find(string[index]);
    for(char c : letters_iterator.second) {
      path.push_back(c);
      depthFirstSearch(index+1, path);
      path.pop_back();
    }
  }
public:
  vector<string> letterCombinations(string digits) {
    if(digits.length() == 0) {
      return SOLUTION;
    }
    packetNumber = digits;
    depthFirstSearch("", 0);
    return SOLUTION;
  }
}

Here the solution requires going through all possible state changes and should be seen as a graph where the number of nodes are 2^4*n where n is the number of digits in the input and we know and it's safe to assume n < "a relatively small constant" so we can bound or algorithm to be constant.

In this type of question we care about "revealing the search space" which should include a paper-napkin style verification the space is calculable.

next we can take a leetcode [743] which can be solved using Dijkstra's algorithm.

This is one of the properties in the ever famous Dijkstra's short path algorithm having optimal substructure we can take advantage of to not search the entire space of traversing the graph, the neat thing of Dijkstra's is we get to keep the structure to re-use.

Here the example being calculating Network Delay from one node to another.

class Solver {
private:
  struct comp { 
    bool operator()(const pair<int, int>& a, const pair<int, int> b) {
      return a.second > b.second;
    }
  }
public:
  networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int,int>>> graph(n+1);
    for(auto& t : times) {
      graph[t[0]].emplace_back(make_pair(t[1], t[2]));
    }

    vector<int> total_cost_to_travel(n+1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int,int>>, comp> pq;

    pq.push(make_pair(k, 0));
    total_cost_to_travel[k] = 0;

    int vertex_count = 0, maximum_delay = -1;
    while(not pq.empty()) {
      pair<int, int> edgeIn = pq.top(); pq.pop();
      if(total_cost_to_travel[edgeIn.first] < edgeIn.second) {
        continue;
      }
      ++vertex_count;
      maximum_delay = max(maximum_delay, total_cost_to_travel[edgeIn.first]);

      for(pair<int, int> edgeOut : graph[edgeIn.first]) {
        int edgeWeight = total_cost_to_travel[edgeOut.first];
        if(edgeWeight > edgeOut.second + edgeWeight) {
          total_cost_to_travel[edgeOut.first] = edgeOut.second + edgeWeight;
          pq.push(make_pair(edgeOut.first, tc[edgeOut.first]));
        }
      }
    } 
    return vertex_count == n ? maximum_delay : -1;
  }
}

Subroutines: Interview Problem Survey

Mehran Ghamaty — Fri, 28 Feb 2025 20:46:31 +0000

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;

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;
  }
}

Trees: Interview Problem Survey

Mehran Ghamaty — Wed, 26 Feb 2025 22:14:36 +0000

Learning how to traverse a tree can answer a huge number of interview questions; At the high level there are two main ways of traversing a Tree depth first search and breadth first search.

To give some meat to our article let's give our Nodes a definition;

template<typename T>
struct MyTreeNode {
  unique_ptr<T> value;
  shared_ptr<MyTreeNode> left;
  shared_ptr<MyTreeNode> right;
  MyTreeNode(): val(make_ptr(nullptr)), left(make_ptr(nullptr)), right(make_ptr(nullptr)) {}
  MyTreeNode(T val): val(make_ptr(pulltr), left(make_ptr(nullptr)), right(make_ptr(nullptr)) {}
  MyTreeNode(T val, MyTreeNode left, MyTreeNode right): val(make_ptr(pulltr), left(make_ptr(left)), right(make_ptr(right)) {}
}

Lets start with breadth-first search since this non-recursive solution is sometimes easier to debug during a stressful interview, even if it's slightly more difficult to remember.

template<typename T>
void breadth_first_search(shared_ptr<MyTreeNode> root,
    const std::function<void(T)>& predicate) {
  if(root.get() == nullptr()) {
    return;
  }

  vector<shared_ptr<MyTreeNode>> queue;
  queue.push(root);

  while(!queue.empty()) {
#ifdef pre-order
    predicate(queue.front().value.get());
    queue.pop();
#endif

    if(root.left.get() != nullptr) {
      queue.push(root.left);
    }

#ifdef in-order
    predicate(queue.front().value.get());
    queue.pop();
#endif

    if(root.right.get() != nullptr) {
      queue.push(root.right);
    }

#ifdef post-order
    predicate(queue.front().value.get());
    queue.pop()
#endif
  }

}

Next example would be depth-first search;

template<typename T>
void depth_first_search(shared_ptr<MyTreeNode> root,
    const std::function<void(T)>& predicate) {'
  if(root.get() != nullptr) {
    return;
  }

  // if pre-order
#ifdef pre-order
  predicate(root.value.get());
#endif
  if(root.left.get() != nullptr) {
    depth_first_search(root.left);
  }  

#ifdef in-order
  predicate(root.value.get());
#endif

  if(root.right.get() != nullptr) {
    depth_first_search(root.right);
  }

#ifdef post-order
  predicate(root.value.get());
#endif

}

Now these two algorithm serve as the basis for many problems.