• Problem 1 . given many pairs , output all the conflict pairs
``````struct Interval {
int index; //event number
int start;
int end;
};

bool compare(Interval& a, Interval& b) {
return a.start == b.start ? a.index < b.index : a.start < b.start;
}

void ConflictPair(vector<Interval>& event, int n) {
sort(event.begin(), event.end(), compare);
for (int i = 0; i < len; i++) {
int s = i + 1, e = len - 1;
int cur = i;
while (s < = e) {
int mid = (s + e) / 2;
/** check overlap event index **/
if (event[mid] .start > event[i].end) {
end = mid - 1;
}
else {
cur = mid;
s = mid + 1;
}
}
for(int j = i + 1; j <= cur; j++) {
/***** output the event[i] conflict with the event[j]   ***/
}
}
}
``````

Problem 2

UTF-8 Validation

Uses 1-4 bytes to represent a character, subjected to the following rules:

1. For 1-byte character, the first bit is a 0, followed by its unicode code.
2. For n bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

Please see this for more details about UTF-8 variable width encoding rules here:
http://stackoverflow.com/a/6339292/490463

``````bool valid_utf8(vector<unsigned char>& data) {
int count = 0;
for(auto c : data) {
if(count == 0) {
/** set the remained the utf-8 char count **/
if((c >> 5) == 0b110)  count = 1;
else if((c >> 4) == 0b1110)   count = 2;
else if((c >> 3) == 0b11110)  count = 3;
else if((c >> 7))   return false;
} else {
if((c >> 6) != 0b10)   return false;
count--;
}
}
return count == 0;
}
``````

• Problem 3 Given a 2d array, find the submatrix which has the largest sum.
``````int max_sub_rect(const vector<vector<int>>& matrix) {
if(matrix.empty() || matrix[0].empty())  return 0;
int row = matrix.size(),  col = matrix[0].size();
vector<vector<int>>  col_sum = matrix;
/*** calculate the accumulated sum of the col elements ***/
for(int i = 1; i < row; i++) {
for(int j = 0; j < col; j++) {
col_sum[i][j] += col_sum[i-1][j];
}
}

int result = 0;
for(int i = 0; i < row; i++) {
for(int j = 0; j <=i; j++) {
int sum = 0;
for(int k = 0; k < col; k++) {
/** get the col-sum at col k **/
int temp = j == 0 ? col_sum[i][k] : col_sum[i][k] - col_sum[j-1][k];
sum += temp;
result = max(result, sum);
sum = max(sum , 0);
}
}
}
return result;
}
``````

• Problem 4 Pacific Atlantic problem
``````void   dfs(Point pt, uunordered_map<Point, bool>& visited, vector<vector<int>>& matrix) {
vector<Point> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for(auto dir : dirs) {
Point new_p = { dir.x + pt.x,  dir.y + pt.y };
if(new_p.x < 0 || new_p.x >= matrix.size() ||
new_p.y < 0 || new_p.y >= matrix[0].size()){
continue;
}
if(matrix[new_p.x][new_p.y] < matrix[pt.x][pt.y] || visited.count(new_p) {
continue;
}
visited[new_p] = true;
dfs(new_p, visited, matrix);
}
}

vector<Point> flowing_water(vector<vector<int>>& matrix) {
int n = matrix.size();
unordered_map<Point, bool> visited_1;
/*** up ***/
for(int i = 0; i < n; i++) {
visited_1[{0, i}] = true;
search({0, i}, visited_1, matrix);
}
/*** left ***/
for(int i = 0; i < n; i++) {
visited_1[{i, 0}] = true;
search({i, 0}, visited_1, matrix);
}

unordered_map<Point, bool> visited_2;
/*** down ***/
for(int i = 0; i < n; i++) {
visited_2[{n - 1, i}] = true;
search({n - 1, i}, visited_2, matrix);
}
/*** right ***/
for(int i = 0; i < n; i++) {
visited_2[{i, n - 1}] = true;
search({i, n - 1}, visited_2, matrix);
}

vector<Point>  result;
for(auto p : visited_1) {
if(visited_2.count(p.first))
result.push_back(p.first);
}
return result;
}

``````

• @fight.for.dream This should be moved to under the "Interview Questions"->"Google" category. I've moved it to the correct category, please take note of this in future.

• Where are the problems? I pretty much just see solutions.

• Problem 4 Pacific Atlantic problem

• @StefanPochmann You can see the problem description above each solution. However, some of the descriptions are very vague.

• @1337c0d3r Ok, I see some of the Chinese (?) has been replaced by English now. Problem 1 still doesn't make sense, though, and problem 4 is only a useless name. And problem 2 really needs to be translated (I assume it describes the details of UTF-8, which I doubt many people would know).

• @fight.for.dream Could you provide more information for the first and the fourth problem?
Thank you

• @StefanPochmann

Problem 1 is: Given a list of appointments as `pair<start_time, end_time>` return all the conflicting appointments. `O(nlogn)` solution using an interval tree.

I suspect this is Problem 4.

• @babhishek21 i don't think that interval tree was used in the soluiton above

• @elmirap You are right. He didn't. Instead, he used sorting + binary search, which is just as good.

• @babhishek21 could you please state the problem here? Maybe it's worth adding it to the problem base.

• @agave I suppose it is:
Given n appointments, find all conflicting appointments. Example :
Input: appointments[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}
Output: Following are conflicting intervals
[3,7] Conflicts with [1,5]
[2,6] Conflicts with [1,5]
[5,6] Conflicts with [3,7]
[4,100] Conflicts with [1,5]
That's why @babhishek21 suggested interval tree for nlog(n) solution. I will code it when I have some time.
You could insert it in the library
@fight-for-dream can you confirm this?

• @elmirap I meant the Pacific Atlantic problem. Also, we should definitely upload Tilt Game - it's been asked again to another guy.

• @agave I see, sorry

• @agave,please take a look at :
https://www.careercup.com/question?id=5162862051852288. It might be the problem

• @elmirap Ok, so basically we start from points on the shores and from each we do bfs/dfs and mark points as Pacific/Atlantic. So at the end the points with both P/A will be the divide. Right?

``````antlantic *
pacific #

* * * * *
*  1 2 2 3 (5)  #
*  3 2 3(4)(4) #
*  2 4 (5) 3 1  #
* (6)(7) 1 4 5  #
*  (5) 1 1  2 4 #
#  #  # #  #
It seems that solution points are these from which water fall in antlantic and in pacific.What is time complexity of your solution?``````

• @agave is right. That will do the trick. @fight-for-dream has pretty much written the same.

Using HashSet-like DS, it takes `2*O(m*n)` for discovery with dfs and `O(m*n)` for finding intersection between two sets. Additionally we need `2*O(m*n)` extra space (worst case being when all heights are equal).

So time complexity: `O(m*n)`, space complexity: `O(m*n)`.

• @babhishek21 I can't see the point why you are talking about bfs,dfs and so on, when the algorithm could be summarized as a traversal by rows and traversal by columns

• @elmirap what do you mean by traversal? and yes, it would be `O(m*n)` time.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.