DFS - How to Succeed in Algorithms Interview


DFS - How to Succeed in Algorithms Interview

DFS vs BFS

  • DFS uses space O(h): the height of tree etc, bfs uses space O(n): the layer with max nodes
  • dfs: recursion or stack implementation
    • prune, stop early
  • in some cases, dfs may be natural and easier to implement, choose dfs

Break into Sub-problems

Variables/states

  • level
  • positions
  • visited array or set
  • in stack nodes: check cycle
  • bit mask target: state=1<<n-1

Implementation

  • Usually nee reset states (backtrack)
  • add cache: dimensions related with states

Loop in DFS

  • index from 0 to len; from 0 to i; from i to len;

Cache

Backtrack (or not)

Types

Trick

  • Remove duplicates
    • use set

Special DFS

public void cleanRoom(Robot robot) {    Set<String> visited = new HashSet<>();
    backtracking(robot, visited, 0, 0, 0);
}
int[][] dir = {{1,0}, {-1,0}, {0,1}, {0, -1}};
private void backtracking(Robot robot, Set<String> visited, int x, int y, int arrow) {
    String path = x + "-" + y;
    if (visited.contains(path)) return;
    visited.add(path);
    robot.clean();
    for (int i = 0; i < 4; i++) {
        if (robot.move()) {
            //go all the way till cannot move, then back one step
            int nx = x + dir[arrow][0];
            int ny = y + dir[arrow][1];
            backtracking(robot, visited, nx, ny, arrow);
            //trace back
            robot.turnLeft();
            robot.turnLeft();
            robot.move();
            robot.turnLeft();
            robot.turnLeft();
        }
        robot.turnLeft();// or turnRight();
        arrow = (arrow + 1) % 4;
    }
}

For loop in DFS

Classical problems

Permutations

  • LeetCode 78 - Subsets
    • bfs or dfs, or bit mask
    private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
    }   
  • LeetCode 90 - Subsets II: contains duplicates
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
  list.add(new ArrayList<>(tempList));
  for(int i = start; i < nums.length; i++){
      if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
      tempList.add(nums[i]);
      backtrack(list, tempList, nums, i + 1);
      tempList.remove(tempList.size() - 1);
  }
}
// BFS
public List<List<Integer>> subsetsWithDup(int[] num) {
  Arrays.sort(num);
  List<List<Integer>> ret = new ArrayList<>();
  ret.add(new ArrayList<Integer>());

  int size = 0, startIndex;
  for(int i = 0; i < num.length; i++) {
    startIndex = (i >= 1 && num[i] == num[i - 1]) ? size : 0;
    size = ret.size();
    for(int j = startIndex; j < size; j++) {
      List<Integer> temp = new ArrayList<>(ret.get(j));
      temp.add(num[i]);
      ret.add(temp);
    }
  }
  return ret;
}
public ArrayList<ArrayList<Integer>> permute(int[] num) {
 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 permute(num, 0, result);
 return result;
}
void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
 if (start >= num.length) {
  ArrayList<Integer> item = new ArrayList(num);
  result.add(item);
 }
 for (int j = start; j <= num.length - 1; j++) {
  swap(num, start, j);
  permute(num, start + 1, result);
  swap(num, start, j);
 }
}
public ArrayList<ArrayList<Integer>> permute(int[] num) {
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  ArrayList<Integer> element = new ArrayList<Integer>();
  boolean[] visited = new boolean[num.length];
  helper(num, result, element, visited);
  return result;
}
public void helper(int[] num, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> element, boolean[] visited) {
  if (element.size() == num.length) {
    result.add(new ArrayList<Integer>(element));
    return;
  }
  for (int i = 0; i < num.length; i++) {
    if (!visited[i]) {
      visited[i] = true;
      element.add(num[i]);
      helper(num, result, element, visited);
      element.remove(element.size() - 1);
      visited[i] = false;
    }
  }
}
public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(nums==null || nums.length==0) return res;
    boolean[] used = new boolean[nums.length];
    List<Integer> list = new ArrayList<Integer>();
    Arrays.sort(nums);
    dfs(nums, used, list, res);
    return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
  if(list.size()==nums.length){
      res.add(new ArrayList<Integer>(list));
      return;
  }
  for(int i=0;i<nums.length;i++){
      if(used[i]) continue;
      if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
      used[i]=true;
      list.add(nums[i]);
      dfs(nums,used,list,res);
      used[i]=false;
      list.remove(list.size()-1);
  }
}
// BFS
public List<List<Integer>> permuteUnique(int[] nums) {
    LinkedList<List<Integer>> r = new LinkedList<>();
    r.add(new ArrayList<Integer>());
    for(int i=0; i<nums.length; i++){
        int n = r.size();
        for(int j=0; j<n; j++){
            List<Integer> list = r.poll();
            for(int k=0; k<=list.size(); k++){
                if(k > 0 && list.get(k-1) == nums[i])
                    break;
                ArrayList<Integer> t = new ArrayList<>(list);
                t.add(k, nums[i]);//\\
                r.offer(t);
            }
        }
    }
    return r;
}
boolean isCycleUtil(int currVertex, boolean[] visited, int parent) {
  // add this vertex to visited vertex
  visited[currVertex] = true;

  // visit neighbors except its direct parent
  for (int i = 0; i < adjList[currVertex].size(); i++) {
    int vertex = adjList[currVertex].get(i);
    // check the adjacent vertex from current vertex
    if (vertex != parent) {
      // if destination vertex is not its direct parent then
      if (visited[vertex]) {
        // if here means this destination vertex is already visited
        // means cycle has been detected
        return true;
      } else {
        // recursion from destination node
        if (isCycleUtil(vertex, visited, currVertex)) {
          return true;
        }
      }
    }
  }
  return false;
}

subsetSum

LeetCode 46 - Permutations

  • swap with values with a larger index
private void permute(List<List<Integer>> result, int[] array, int start) {
  if (start >= array.length) {
    List<Integer> current = new ArrayList<Integer>();
    for (int a : array) {
        current.add(a);
    }
    result.add(current);
  } else {
    for (int i=start; i<array.length; i++) {
      swap(array, start, i);
      permute(result, array, start+1);
      swap(array, start, i);
    }
  }
}
private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> currentList, int index) {
    if (currentList.size() == nums.length) {
        result.add(currentList);
        return;
    }
    int n = nums[index];
    for (int i = 0; i <= currentList.size(); i++) {
        List<Integer> copy = new ArrayList<Integer>(currentList);
        copy.add(i, n);
        backtrack(result, nums, copy, index + 1);
    }
}

Include current element in different sets

Multiple DFS

public boolean pyramidTransition(String bottom, List<String> allowed) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : allowed) {
        String key = s.substring(0,2);
        if (!map.containsKey(key)) map.put(key, new ArrayList<String>());
        map.get(key).add(s.substring(2));
    }
    return helper(bottom, map);
}
private boolean helper(String bottom, Map<String, List<String>> map) {
    if(bottom.length() == 1) return true;
    for (int i = 0; i<bottom.length()-1; i++) {
        if (!map.containsKey(bottom.substring(i,i+2))) return false;
    }
    List<String> ls = new ArrayList<>();
    getList(bottom, 0, new StringBuilder(), ls, map);
    for (String s : ls) {
        if (helper(s, map)) return true;
    }
    return false;
}
private void getList(String bottom, int idx, StringBuilder sb, List<String> ls, Map<String, List<String>> map) {
    if (idx == bottom.length() - 1) {
        ls.add(sb.toString());
        return;
    }
    for (String s : map.get(bottom.substring(idx, idx+2))) {
        sb.append(s);
        getList(bottom, idx + 1, sb, ls, map);
        sb.deleteCharAt(sb.length()-1);
    }
}

public boolean pyramidTransition(String bottom, List<String> allowed) {
    Map<String,List<String>> map = new HashMap<>();
    for (String str : allowed){
        String key = str.substring(0,2);
        if (! map.containsKey(key)){
            map.put(key,new ArrayList<>());
        }
        map.get(key).add(str.substring(2));
    }
    return dfs(map,bottom,new StringBuilder(),0);
}
public boolean dfs(Map<String,List<String>> map,String bottom,StringBuilder nextBottom,int p){
    if (p == bottom.length() - 1){
        bottom = nextBottom.toString();
        nextBottom = new StringBuilder();
        p = 0;
    }
    if (bottom.length() == 1) return true;
    String key = bottom.substring(p,p + 2);
    if (map.containsKey(key)){
        for (String val : map.get(key)){
            nextBottom.append(val);
            if (dfs(map,bottom,nextBottom,p + 1)) return true;
            nextBottom.setLength(nextBottom.length() - 1);
        }
    }
    return false;
}

How remove duplicates

Hard Examples

  • LeetCode 394 - Decode String
    public String decodeString(String s) {
      StringBuilder builder = new StringBuilder();
      decodeStringRecur(s.toCharArray(),builder,0);
      return builder.toString();
    }
    public int decodeStringRecur(char[] sArr, StringBuilder builder, int start){
      if (start>=sArr.length){
          return start;
      }
      int p1 = start;
      while (p1<sArr.length && sArr[p1]!=']'){
          if (sArr[p1]<'0' || sArr[p1]>'9'){
              builder.append(sArr[p1++]);
          } else {
              int val = 0;
              while (p1<sArr.length && sArr[p1]!='['){
                  val = val*10 + (int)(sArr[p1++]-'0');
              }
              StringBuilder subBuilder = new StringBuilder();
              p1 = decodeStringRecur(sArr,subBuilder,p1+1);
              for (int i=0;i<val;i++){
                  builder.append(subBuilder);
              }
          }
      }    
      return (p1<sArr.length) ? p1+1 : p1;
    }

Hard

public List<String> addOperators(String num, int target) {
    List<String> ans = new ArrayList<String>();
    search(0, 0, 0, target, new StringBuilder(), num, ans);
    return ans;
}

private void search(int index, long last, long sum, int target, StringBuilder prefix, String s, List<String> ans) {
    if (index == s.length()) {
        if (sum == target)
            ans.add(prefix.toString());
        return;
    }    
    int len = prefix.length();
    long num = 0;
    for (int i = index; i < s.length(); i ++) {
        num = num * 10 + s.charAt(i) - '0';
        if (index == 0) {
            search(i + 1, num, num, target, prefix.append(num), s, ans);
            prefix.setLength(len);
        } else {
            prefix.append('+'); prefix.append(num);
            search(i + 1,  num, sum + num, target, prefix, s, ans);
            prefix.setLength(len);
            prefix.append('-'); prefix.append(num);
            search(i + 1, -num, sum - num, target, prefix, s, ans);
            prefix.setLength(len);
            prefix.append('*'); prefix.append(num);
            search(i + 1, last * num, sum - last + last * num, target, prefix, s, ans);
            prefix.setLength(len);
        }
        if (num == 0) break;
    }
}

Examples

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)