// https://www.jianshu.com/p/fdbcba5fe5bc
// Longest common continuous subarray
// 718. Maximum Length of Repeated Subarray
vector<string> LongestCommonContinuousHistory(vector<string>& str1,
                                              vector<string>& str2) {
  vector<vector<int>> record(str1.size() + 1, vector<int>(str2.size() + 1, 0)); 
  pair<int, int> pos;  
  int cur_max = 0;
  for (int i = 0; i < str1.size(); ++i) {
    for (int j = 0; j < str2.size(); ++j) {
      if (str1[i] == str2[j]) {
        record[i+1][j+1] = 1 + record[i][j];
        if (cur_max < record[i+1][j+1]) {
          cur_max = record[i+1][j+1];
          pos = make_pair(i, j);
        }
      }
    }
  }
  int len1 = i;
  int len2 = j;
  vector<string> ans;
  while (len1 >= 0 && len2 >= 0 && str1[len1] == str2[len2]) {
    ans.emplace_back(str1[len1]);
    --len1;
    --len2;
  }
  reverse(begin(ans), end(ans));
  return ans;
}

// 1143. Longest Common Subsequence
int longestCommonSubsequence(string text1, string text2) {
  int len1 = text1.size();
  int len2 = text2.size();
  vector<vector<int>> record(len1 + 1, vector<int>(len2 + 1, 0));
  for (int i = 0; i < len1; ++i) {
    for (int j = 0; j < len2; ++j) {
      int increment = text1[i] == text2[j] ? 1:0;
      record[i+1][j+1] = max(record[i][j] + increment, 
                         max(record[i][j+1], record[i+1][j]));
    }
  }
  return record[len1][len2];
}

// 811. Subdomain Visit Count
vector<string> splitString(string cpd, int& num) {
  string cur="";
  for(auto c:cpd) {
    if(isdigit(c)) {
      num = num*10 + c-'0';
    }    
    else 
      break;
  }    
  bool first = true;
  vector<string> ans;
  for(int ind=cpd.size()-1; ind>=0; ind--) {
    if(isalpha(cpd[ind])) 
      cur = cpd[ind]+cur; 
    else if(cpd[ind]=='.') {
      ans.push_back(cur);
      first = false;
      cur = cpd[ind]+cur;
    }    
    else
      break;
  }   
  ans.push_back(cur);
  return ans;
}    
vector<string> subdomainVisits(vector<string>& cpdomains) {
  unordered_map<string, int> rec;
  for(auto cpd:cpdomains) {
    int num=0;
    vector<string>strs = splitString(cpd, num);
    for(auto str:strs)
      rec[str] += num;
    }
    vector<string> ans;
    for(auto ele:rec) {
      ans.push_back(to_string(ele.second)+" "+ele.first);
  }    
  return ans;
}

// log files processing
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int string_to_second(const string& str) {
  return (str[1] - '0'+10*(str[0]-'0')) * 3600 + 
     (str[3] - '0'+10*(str[2]-'0')) * 60 + (str[5] - '0'+10*(str[4]-'0'));
}
pair<string, int> most_requested_resource(vector<vector<string>>& logs) {
  unordered_map<string, int> timestamps;    
  for (auto& l : logs) {
    while (l[0].size() < 6) {
      l[0] = "0" + l[0];
    }
    timestamps[l[0]] = string_to_second(l[0]);
  }    
  sort(begin(logs), end(logs), [](
      const vector<string>& v1, const vector<string>& v2) {
    return v1[0] < v2[0];  
  });
  int max_freq = 0;
  string ans;
  unordered_map<string, int> record;
  for (int i = 0, j = 0; i < logs.size(); ++i) {
    ++record[logs[i][2]];
    const auto cur_ts = timestamps[logs[i][0]];
    while (cur_ts - timestamps[logs[j][0]] > 300) {
      ++j;
      --record[logs[j][2]];
    }
    if (record[logs[i][2]] > max_freq) {
      max_freq = record[logs[i][2]];
      ans = logs[i][2];
    }
  }
  return make_pair(ans, max_freq);
}
int main() {
  vector<vector<string>> logs1 = {
    { "58523", "user_1", "resource_1" },
    { "62314", "user_2", "resource_2" },
    { "54001", "user_1", "resource_3" },
    { "200", "user_6", "resource_5" },
    { "215", "user_6", "resource_4" },
    { "54060", "user_2", "resource_3" },
    { "53760", "user_3", "resource_3" },
    { "58522", "user_22", "resource_1" },
    { "53651", "user_5", "resource_3" },
    { "2", "user_6", "resource_1" },
    { "100", "user_6", "resource_6" },
    { "400", "user_7", "resource_2" },
    { "100", "user_8", "resource_6" },
    { "54359", "user_1", "resource_3"},
  };
  vector<vector<string>> logs2 = {
      {"300", "user_1", "resource_3"},
      {"599", "user_1", "resource_3"},
      {"900", "user_1", "resource_3"},
      {"1199", "user_1", "resource_3"},
      {"1200", "user_1", "resource_3"},
      {"1201", "user_1", "resource_3"},
      {"1202", "user_1", "resource_3"},
  };
  const auto res1 = most_requested_resource(logs1);
  cout << "Most frequency resource is " << res1.first << " with " << res1.second << endl;
  const auto res2 = most_requested_resource(logs2);
  cout << "Most frequency resource is " << res2.first << " with " << res2.second << endl;
  return 0;
}
                                            
// https://leetcode.com/problems/backspace-string-compare/
bool backspaceCompare(string S, string T) {
  stack<char> s_stk;
  stack<char> t_stk;
  for (auto c:S) {
    if (c=='#') { 
      if(s_stk.size())
        s_stk.pop();
    }             
    else 
      s_stk.push(c);
  }
  for (auto c:T) {
    if (c=='#') {
      if (t_stk.size()) 
        t_stk.pop();
    }             
    else 
      t_stk.push(c);
  }
  if (s_stk.size()!=t_stk.size())
    return false;
  while (!s_stk.empty()) {
    if (s_stk.top()!= t_stk.top())
      return false;
    s_stk.pop();
    t_stk.pop();
  }
  return true;
}

// https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/
// 1170. Compare Strings by Frequency of the Smallest Character
int getMinFrequency(string& str) {
  int rec[26] = {0};      
  for (auto c:str) {
    ++rec[c-'a'];
  }
  int min_rec = 1;
  for (int idx = 0; idx < 26; ++idx) {
    if (rec[idx]) {
      return rec[idx];
    }
  }
  return min_rec;
}
void findMinFrequency(vector<string>& words, vector<int>& rec) {
  for (int idx = 0; idx < words.size(); ++idx) {
    rec[idx] = getMinFrequency(words[idx]);
  }
}    
int GetMinPos(int num, vector<int>& vec) {
  if (num < vec[0]) {
    return vec.size();
  }
  if (num >= vec[vec.size()-1]) {
    return 0;
  }      
  int stt_idx = 0;
  int fin_idx = vec.size()-1;
  int mid_idx = stt_idx + (fin_idx-stt_idx)/2;
  while (stt_idx <= fin_idx) {
    mid_idx = stt_idx + (fin_idx-stt_idx)/2;
    if (vec[mid_idx] <= num) {
      ++stt_idx;
    }
    else if(vec[mid_idx] > num) {
      --fin_idx;
    }
  }
  return vec.size() - (mid_idx);
}    
void findPosition(vector<int>& ans, vector<int>& que_vec, 
                  vector<int>& word_vec) {
  for (int idx = 0; idx < que_vec.size(); ++idx) {
    ans[idx] = GetMinPos(que_vec[idx], word_vec);
  }
}    
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
  vector<int> que_vec(queries.size(), 0);
  vector<int> word_vec(words.size(), 0);      
  findMinFrequency(queries, que_vec);
  findMinFrequency(words, word_vec);      
  sort(word_vec.begin(), word_vec.end());      
  vector<int> ans(queries.size(), 0);      
  findPosition(ans, que_vec, word_vec);      
  return ans;
}

// 1. Find rectangle: 给一个2d image array, 里面有0, 1. 0 代表rectangle, 每个rectangle都会有1隔开
// 2. Find shape
function findOneRectangle(board) {
  if (!board || board.length === 0 || board[0].length === 0) {
    return [];
  }
  const result = [];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] === 0) {
        result.push([i, j]);
        let height = 1, width = 1;
        while (i + height < board.length && board[i + height][j] === 0) {
          height++;
        }
        while (j + width < board[0].length && board[i][j + width] === 0) {
          width++;
        }
        result.push([i + height - 1, j + width - 1]);
        break;
      }
      if (result.length !== 0) {
        break;
      }
    }
  }
  return result;
}
function findMultipleRectangle(board) {
  if (!board || board.length === 0 || board[0].length === 0) {
    return [];    
  }
  const result = [];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] === 0) {
        const rectangle = [[i, j]];
        board[i][j] = 1;
        let height = 1, width = 1;
        while (i + height < board.length && board[i + height][j] === 0) {
          height++;
        }
        while (j + width < board[0].length && board[i][j + width] === 0) {
          width++;
        }
        for (let h = 0; h < height; h++) {
          for (let w = 0; w < width; w++) {
            board[i + h][j + w] = 1;
          }
        }
        rectangle.push([i + height - 1, j + width - 1]);
        result.push(rectangle);
      }
    }
  }
  return result;
}
// Flood fill
function findMultipleShapes(board) {
  if (!board || board.length === 0 || board[0].length === 0) {
    return [];    
  }
  const result = [];
  const floodFillDFS = (x, y, shape) => {
    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] === 1) {
      return;
    }
    board[x][y] = 1;
    shape.push([x, y]);
    floodFillDFS(x + 1, y, shape);
    floodFillDFS(x - 1, y, shape);
    floodFillDFS(x, y - 1, shape);
    floodFillDFS(x, y + 1, shape);
  };
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] === 0) {
        shape = [];
        floodFillDFS(i, j, shape);
        result.push(shape);
      }
    }
  }
  return result;
}

// 以往面经原题，一个公司打卡时间记录，输出某人个一小时内超过三次记录，如果某个人有多个结果，输出最多的那个一小时记录 
/* https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=720802&highlight=Robinhood%2Bkarat           
原始问题是给name和timestamp，返回所有在一小时内打卡超过三次的name和对应的timestamp。一个tricky的点是timestamp是24小时制，比如855代表8:55am，1325代表1:35pm，在比较时间的时候不能直接相减，而要先做转化。
follow up是给name, timestamp和action (Enter or Exit)，找出在同一时间里都在房间里超过两次以上的group里人最多的那个group，返回里面的所有人和对应的interval. Scanline to do this. */
给 list of [name, time], time is string format: '1300' //下午一点
return: list of names and the times where their swipe badges within one hour. if there are multiple intervals that satisfy the condition, return any one of them.
name1: time1, time2, time3...
name2: time1, time2, time3, time4, time5...
example:
input: [['James', '1300'], ['Martha', '1600'], ['Martha', '1620'], ['Martha', '1530']]
output: {
'Martha': ['1600', '1620', '1530']
}

We are working on a security system for a badged-access room in our company's building.

We want to find employees who badged into our secured room unusually often. We have an unordered list of names and entry times over a single day. Access times are given as numbers up to four digits in length using 24-hour time, such as "800" or "2250".

Write a function that finds anyone who badged into the room three or more times in a one-hour period, and returns each time that they badged in during that period. (If there are multiple one-hour periods where this was true, just return the first one.)

badge_times = [
  ["Paul",     "1355"],
  ["Jennifer", "1910"],
  ["John",      "830"],
  ["Paul",     "1315"],
  ["John",     "1615"],
  ["John",     "1640"],
  ["John",      "835"],
  ["Paul",     "1405"],
  ["John",      "855"],
  ["John",      "930"],
  ["John",      "915"],
  ["John",      "730"],
  ["John",      "940"],
  ["Jennifer", "1335"],
  ["Jennifer",  "730"],
  ["John",     "1630"],
  ["Jennifer",    "5"]
]

Expected output (in any order)
  John:  830  835  855  915  930
  Paul: 1315 1355 1405  

We are working on a security system for a badged-access room in our company's building.

We want to find employees who badged into our secured room unusually often. We have an unordered list of names and entry times over a single day. Access times are given as numbers up to four digits in length using 24-hour time, such as "800" or "2250".

Write a function that finds anyone who badged into the room three or more times in a one-hour period, and returns each time that they badged in during that period. (If there are multiple one-hour periods where this was true, just return the first one.)

badge_times = [

  ["John",      "730"],
  ["John",      "830"], 830
  ["John",      "835"],
  ["John",      "855"],
  ["John",      "915"],
  ["John",      "930"], 930
  ["John",      "940"],
  ["John",     "1615"],
  ["John",     "1640"],
  ["John",     "1630"],

  ["Paul",     "1355"],
  ["Jennifer", "1910"],
  ["Paul",     "1315"],
  ["Paul",     "1405"],
  ["Jennifer", "1335"],
  ["Jennifer",  "730"],
  ["Jennifer",    "5"]
]

Expected output (in any order)
  John:  830  835  855  915  930
  Paul:  1315 1355 1405

n: length of the badge records array
p: number of people in the input

length of each array   
    worst   length of list = n
    avg     length of list = n/p

worst
    O(n) + O(nlogn) => O(nlogn)

Space
    O(n)

"""
def findFreqBadge(badge_times):
    badges = {}
    ans = {}
    #1 process the badge_times and store in a map
    for badgeTime in badge_times:
        name = badgeTime[0]
        time = int(badgeTime[1])
        if name not in badges:
            badges[name] = []
            badges[name].append(time)
        else:
            badges[name].append(time)
#     print(badges)

    #2 process each entry in the map
    for name in badges:   
        times = sorted(badges[name])
        badgeTimes = [] # updated for traversing within 1hrs

        if len(times) < 3:
            continue

        startTime = times[0]
        endTime = startTime + 100

        for time in times:
            if time > endTime:
                if len(badgeTimes) >= 3:
                    break
                # update startTime and endTime
                startTime = badgeTimes[len(badgeTimes)-1]
                endTime = startTime + 100
                badgeTimes.clear()
                badgeTimes.append(startTime)
                badgeTimes.append(time)
                continue
            badgeTimes.append(time)

        if len(badgeTimes) >= 3:
            ans[name] = badgeTimes
            continue

    return ans
print(findFreqBadge(badge_times))
    
    
// badge access,follow up看 desktop保存的图片
badge第一题（more than 3 times within one hour）先聊了solution，然后开始写代码debug了一会跑了test case聊了time/space complexity。然后badge 第二题（largest group）
// 题目：https://www.1point3acres.com/bbs/thread-720802-1-1.html  

vector<vector<string>> InvalidBadgeRecords(vector<vector<string>>& records) {
  unordered_set<string> enters;
  unordered_set<string> exits;
  unordered_map<string, int> records_map;
  
  for (const auto [name, action] : records) {
    if (action == "enter") {
      if (records_map[name] == 1) {
        enters.insert(name);
      } else {
        records_map[name] = 0;
      }
    } else {
      if (!record_map[name]) {
        exits.insert(name);
      } else {
        records_map[name] = 0;
      }
    }
  }                          
  vector<vector<string>> ans;
  ans.push_back(vector<string>(enters.begin(), enters.end()));     
  ans.push_back(vector<string>(exits.begin(), exits.end()));                
  return ans;            
}   

// same with the logs.

// Course schedule
// Course schedule
// 选课三件套
// 第一题是找overlap，第二题是给一条选课路径return中间的课程，第三题是多条选课路径return所有中间课程 all midpoints of course path
// 大意就是给定一堆course pair
/*
pair[0]是要上pair[1]之前必须完成的prerequisite
跟leetcode course schedule一样
这样你就有一个上课的roadmap
从每个root node(没有prerequiste的课)到每个leaf node（没有后续的课）会有很多种path
把全部的path的第n/2个node找出来（A->B->C, return B) 也就是中点
给一个array，里面是（prerequisite，course）的pair，要求return中间的课。
第一问限定只有一个chain，follow up就是一个graph了。
在30分钟之内很难想到optimal的解，两道都brute force了。第一题写了O(n)，follow up写了一个O(2^n), 其实可以O(n^2)。 */
// 第一题是给<student name, course name> tuples返回每两个学生一起上的课。
// 给一堆<prereq course name, course name> tuples返回这条线中间的course coding
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>
unordered_map<string, vector<string>> CourseOverlap(const vector<pair<string, string>>& courses) {
  unordered_map<string, unordered_set<string>> record;
  for (const auto& course : courses) {
    record[course.first].insert(course.second);
  }
  unordered_map<string, vector<string>> ans;
  for (auto it1 = record.begin(); it1 != record.end(); ++it1) {
    auto it2 = it1;
    ++it2;
    while (it2 != record.end()) {
      for (const auto& it3 : it1->second) {
        if (it2->second.find(it3) != it2->second.end()) {
          ans[it1->first + " " + it2->first].emplace_back(it3);
        }
      }
      ++it2;
    }
  }
  return ans;
}  

// one chain to output the mid
string FindMidCourse(vector<vector<string>>& courses) {
  unordered_map<string, int> records;
  unordered_set<string> courses_set;
  for (const auto& c : courses) {
    ++records[c[1]];
    courses_set.insert(c[0]);
    courses_set.insert(c[1]);
  }
  string head;
  for (const auto& c : courses_set) {
    if (courses_set.find(c) == courses_set.end()) {
      head = c;
      break;
    }
  }
  int len = (courses_set.size() + 1) / 2;
  while (len > 0) {
    head = records[head];
    --len;
  }
  return head;
}

// Multiple-graph for the mid
vector<string> FindMidCourses(vector<vector<string>>& courses) {
  unordered_map<string, int> indegrees;
  unordered_set<string> courses_set;
  unordered_map<string, vector<string>> graph;
  for (const auto& c : courses) {
    ++indegrees[c[1]];
    courses_set.insert(c[0]);
    courses_set.insert(c[1]);
    graph[c[0]].emplace_back(c[1]);
  }
  vector<string> ans;
  queue<string> starts;
  for (const auto& c : courses_set) {
    if (indegrees[c] == 0) {
      starts.push(c);
    }
  }
  while (!starts.empt()) {
    vector<string> tmp;
    DFS(graph, 0, tmp);
  }
  return ans;
}
vector<int> DFS(const string root, unordered_map<string, vector<string>>& graph, int depth, vector<int>& ans) {
  if (graph.find(root) == graph.end()) return {0};
  unordered_set<int> lens;
  for (const auto& c : graph[root]) {
    auto res = DFS(c, graph, depth + 1, ans);
    for (const auto l : res) {
      lens.insert(l + 1);
      if (l == depth) {
        ans.push_back(root);
      }
    }
  }
  return vector<int>(begin(lens), end(lens));
}

// Ads Conversion Rate
// Purchase / Ads_clicks_all。点击了广告之后有购买的。

// reflow字符串
function wordWrap(words, maxLen) {
  if (!words || words.length === 0) {
    return [];
  }
  const result = [];
  let i = 0;
  while (i < words.length) {
    let remain = maxLen;
    let count = 0;
    while (i < words.length) {
      if (remain - words[i].length < 0) {
        break;
      }
      count++;
      remain -= words[i++].length + 1;
    }
    result.push(words.slice(i - count, i).join('-'));
  }
  return result;
}
// 68. Text Justification
string Generate(const int num) {
  if (!num) return "";
  else if (num == 1) return " ";
  const string& space_str = Generate(num/2);
  return space_str + space_str + (num&1?" ": "");
}  
  
vector<string> fullJustify(vector<string>& words, int max_width) {
  vector<string> ans;
  vector<string> cur;
  int cur_len = 0;
  for (const auto& word :words) {
    if (word.size() + cur_len + cur.size() <= max_width) {
      cur.emplace_back(word);
      cur_len += word.size();
    } else {
      string str;
      int rem = cur.size() == 1? 0 : (max_width - cur_len) % (cur.size() - 1);
      int space = cur.size() == 1? max_width - cur_len : (max_width - cur_len) / (cur.size() - 1);
      string space_str = Generate(space);
      string rem_str = Generate(1);
      for (int i = 0, j = 0; i < cur.size() - 1; ++i, ++j) {
        string cur_space = space_str;
        if (j < rem) {
          cur_space += rem_str;
        }
        str += cur[i] + cur_space;
      }
      str += cur.back();
      if (cur.size() == 1)
        str += space_str;
      ans.emplace_back(str);
      cur_len = word.size();
      cur.clear();
      cur.emplace_back(word);
    }
  }
  if (!cur.empty()) {
    string space_str = max_width >= cur_len + cur.size()?Generate(max_width - cur_len - cur.size()):"";
    string str;
    for (const auto& s : cur) {
      str += s + " ";
    }
    str = str.substr(0, max_width);
    str += space_str;
    ans.emplace_back(str);
  }
  return ans;
}

// calculator
// 224. Basic Calculator
pair<string, int> Parse(const string& s) {
  int new_idx = 0;
  stack<int> stk;
  int val = 0;
  int inc_size = 0;
  string res;
  string tmp = s;
  while (new_idx < tmp.size()) {
    if (tmp[new_idx] == '(')
      stk.push(new_idx);
    else if (tmp[new_idx] == ')') {
      const int left = stk.top();
      stk.pop();
      val = calculate(tmp.substr(left+1, new_idx - left - 1));
      const auto new_val = to_string(val);
      tmp = tmp.substr(0, left) + new_val + tmp.substr(new_idx + 1);
      const int tmp_inc_size = new_idx - left + 1 - new_val.size();
      new_idx -= tmp_inc_size;
      inc_size += tmp_inc_size;  
      res += new_val;
    } else {
      res += tmp[new_idx];
    }
    if (stk.empty())
      break;
    ++new_idx;
  }
  return { tmp.substr(0, new_idx+1), new_idx + inc_size};
}  
int calculate(string s) {
  int res = 0;
  char op = '+';
  int tmp = 0;
  bool has_num = false;
  
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == '(') {
      const auto [str, index] = Parse(s.substr(i));
      tmp += calculate(str);
      i += index;
      has_num = true;
    } else if (s[i] >= '0' && s[i] <= '9') {
      tmp = tmp*10 - '0' + s[i];
      has_num = true;
    } else if (s[i] == ' '){
      continue;
    } else {
      const bool is_con = !has_num?true:false;
      res += op == '-'? -1 * tmp : tmp;
      tmp = 0;
      op = is_con? (s[i] == op?'+':'-') : s[i] == '-'?'-':'+';
      has_num = false;
    }
  }
  res += op == '-'? -1 * tmp : tmp;
  return res;
}
// 227. Calculator ii
int calculate(string s) {
  int s_len = s.size();    
  int cur_res = 0;
  int fin_res = 0;
  char ope = '+';
  int cur_num = 0;   
  for (int idx = 0; idx < s_len; ++idx) {
    if (isdigit(s[idx])) {
      cur_num = cur_num*10 + (s[idx] - '0');
    }
    if (s[idx] == '*' || s[idx] == '/' || s[idx] == '+' 
        || s[idx] == '-' || idx == s_len - 1) {
      switch(ope) {
        case '+': cur_res += cur_num; break;
        case '-': cur_res -= cur_num; break;
        case '*': cur_res *= cur_num; break;
        case '/': cur_res /= cur_num; break;    
      }              
      if (s[idx] == '-' || s[idx] == '+' || s_len - 1 == idx) {
        fin_res += cur_res;
        cur_res = 0;      
      }          
      cur_num = 0;
      ope = s[idx];
    }
  }              
  return fin_res;
}
// 772. Basic Calculator III
class Solution {
public:
    string parserString (string s, int idx, int & new_idx) {
        int num_brance = 1;
        string str = "";
        
        for (int i = idx; i < s.size(); ++i) {
            if (s[i] == '(') {
                ++num_brance;
            }
            else if (s[i] == ')') {
                --num_brance;
            }
            
            if (!num_brance) {
                new_idx = i;
                return str;
            }
            
            str += s[i];
        }
        
        return str;
    }
    
    
    int calculate(string s) {
        int s_len = s.size();
        long long cur_num = 0;
        int cur_res = 0;
        int fin_res = 0;
        char ope = '+';
        
        for (int idx = 0; idx < s_len; ++idx) {
            if (s[idx] == '(') {
                int new_idx = 0;
                string str = parserString(s, idx+1, new_idx);
                cur_num = calculate(str);
                idx = new_idx;
            }
            
            if (isdigit(s[idx])) {
                cur_num = cur_num*10 + (s[idx] - '0');
            }
            
            if (s[idx] == '+' || s[idx] == '-' || s[idx] == '*' ||
                s[idx] == '/' || s_len == idx + 1) {
                switch(ope) {
                    case '+': cur_res += cur_num; break;
                    case '-': cur_res -= cur_num; break;
                    case '*': cur_res *= cur_num; break;
                    case '/': cur_res /= cur_num; break;    
                }
                if (s[idx] == '-' || s[idx] == '+' || s_len - 1 == idx) {
                    fin_res += cur_res;
                    cur_res = 0;
                }
                
                ope = s[idx];
                cur_num = 0;
            }
        }
        
        return fin_res;
    }
};
// 770. Basic Calculator IV


// matrix puzzle
// for each row/column to see if the instruction is valid or not.

// grand parents
// Graph: child -> parents.

// meetings 
// Is there free time. 759. Employee Free Time

// sparse vector
// list

// Find treasure
// Simple BFS.

// https://juejin.cn/post/6844904085913600008
// https://www.jianshu.com/p/fdbcba5fe5bc