@elyasin That is not true. Maps are implemented as redblack tree which guarantee lgN insertion and is an amortized constant. Refer http://www.cplusplus.com/reference/map/map/insert/ complexity section.
varun44
@varun44
Posts made by varun44

RE: C++ simple map based NLogN

RE: Google onsite interview questions
@pisskidney It is always encouraged to clarify and ask concepts and doubts you have. I did not know what a Toeplitz was until the interviewer explained it to me. It can be reasonable to expect that there will be very vague questions in which the candidate is expected to clarify every detail before solving.

RE: Google onsite interview questions
@nidhirastogi @heidixia I am not a new grad, I have a good number of years of experience and a background in distributed systems, so I was very much expecting those kinds of questions. I was surprised as well when I was informed by the recruiter just before the day of the interview that google's "interviewing slate" whatever that may be, has changed and they weren't going to ask me any system design questions.
I have edited my post to highlight making sure of this with the recruiters so that this wasn't a one off instance.
Note: This interview was at the San Bruno Youtube office.

RE: Google onsite interview questions
Solution for 4:
Preprocess the matrix m[i][j] and have a second matrix wherein:sum[i][j] = sum[i][j1] + sum[i1][j]  sum[i1][j1] + m[i][j] whenever i1, j 1 are valid.
Then,
Query(row1, col1, row2, col2) =
Consider m[i][j]1 2 3 4 5 6 7 8 9
Then sum[i][j]
1 3 6 5 12 21 12 27 45
Now Query(1,1,2,2) = sum[2][2]  sum[0][2]  sum[2][0] + m[0][0] = 28
Query(1,1,2,1) = sum[2][1]  sum[2][0]  sum[0][1] + m[0][0]= 13
Query(2,1,2,1) = sum[2][1]  sum[1][1]  sum[2][0] + m[1][0] = 8Thus we can see a general algorithm for Query:
Assuming row2 >= row1 && col2 >= col1 Query(row1, col1, row2, col2) = sum[row2][col2] sum[row11][col1]  sum[row1][col1  1] + m[row1  1][col1  1], whenever row1 1 and col1  1 are valid. Thus query is O(1) operation
Similarly, update(x, y, val) will have to update the sum matrix as follows:
Let diff = m[x][y]  val
Apply diff to sum[i][j] = sum[i][j] + diff where i ranges from x to M  1(M being number of rows in m), j ranges from y to N  1(N being number of columns in N)
Update is O(MxN) order. 
Google onsite interview questions
I recently went through a Google interview and wanted to contribute the questions I faced.
Note: Google has apparently changed its interview slate, there weren't any system design interviews and all are coding questions. Might have to verify this clearly with your recruiters.
Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.
eg: 11122333 : Missing number 2
11122233344455666 Missing number 5 
Given a compressed string in which a number followed by [] indicate how many times those characters occur, decompress the string
Eg. : a3[b2[c1[d]]]e will be decompressed as abcdcdbcdcdbcdcde.
Assume the string is well formed and number will always be followed by a []. 
Given a tree representation of a html parsed output, wherein every block is a node in the tree, find if two html docs contain the same text.
struct Node { string value; bool isMetadata; vector<Node*> children; };
For eg, consider the two documents
<html><head>sample</head><body>Hello world
</body></html> will be represented as Node1: value sample, children: <body> isMetadata: true Node2: value: <body> children:isMetadata: true Node3: value:
: children: Hello world isMetadata: true Node4: value Hello world isMetadata: false
and a second document
<html><body>Hello world</body></html>and both documents are equivalent since they contain the same data.
Note: the case of both documents fitting in memory is trivial, since it is just walking this tree list, consolidating data and comparing. As a follow up, solve the case where the whole documents may not be able to fit in memory.
 Given a 2D matrix M X N, support two operations:
Query(row1, col1, row2, col2) such that I get the sum of all numbers in the rectangle ((row1, col1), (row1, col2), (row2, col1), (row2, col2)) and
Update(row, col) to a new number
And query is a very frequent operation and update is a rare operation, so query should be really fast, but update can be slower.
Follow up: How would you solve this in a distributed fashion
 Verify if a given matrix is a Toeplitz matrix:
Follow up, assume that the whole matrix cannot be fit in memory and should be read from a file, assume that a few rows and all columns can be read in, how to verify?


RE: c++ O(N*lgM) solution
@dribvurhd good point. Thanks for the insight.

RE: C++ Solution using merge sort
This is interesting since if we do the same approach using simple merge sort (iterate over elements and count, then do a merge), we get time limit exceeded. However internally sort uses quicksort so you are able to clear the cases here. I would think the worst case can still be > n^2 since we are essentially counting across each half arrays each iteration and doing a sort again (since each sort would be nlogn)

C++ a different approach (12ms beats 100%)
class Solution { vector<int> solution; public: void helper(TreeNode* node, int cl) { if (node == NULL) { return; } if (solution.size() < cl + 1) { solution.push_back(node>val); } else { if (solution[cl] < node>val) { solution[cl] = node>val; } } helper(node>left, cl+1); helper(node>right, cl+1); } //vector<int> largestValues(TreeNode* root) { vector<int> findValueMostElement(TreeNode* root) { if(root == NULL) { return solution; } helper(root, 0); return solution; } };

46ms Fanin C++ solution
Fan in solution similar to Facebook feed approach
class Twitter { long tweetTS{0}; map<int, set<int>> followers; map<int, deque<pair<int, int>>> userfeed; void getLatestTweets(map<int, int, std::greater<int>>& tweets, deque<pair<int, int>>& feedData) { for (int i = 0; i < 10 && i < feedData.size(); ++i) { tweets.insert(pair<int, int>(feedData[i].second, feedData[i].first)); } } public: /** Initialize your data structure here. */ Twitter() { } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { userfeed[userId].push_front(pair<int, int>(tweetId, tweetTS++)); } /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */ vector<int> getNewsFeed(int userId) { auto& users = followers[userId]; map<int, int, std::greater<int>> tweets; getLatestTweets(tweets, userfeed[userId]); for (auto i:users) { getLatestTweets(tweets, userfeed[i]); } vector<int> result; for (auto i: tweets) { if (result.size() == 10) { break; } result.push_back(i.second); } return result; } /** Follower follows a followee. If the operation is invalid, it should be a noop. */ void follow(int followerId, int followeeId) { if (followerId == followeeId) { return; } followers[followerId].insert(followeeId); } /** Follower unfollows a followee. If the operation is invalid, it should be a noop. */ void unfollow(int followerId, int followeeId) { if (followerId == followeeId) { return; } if (followers.find(followerId) == followers.end()) { return; } if (followers[followerId].find(followeeId) == followers[followerId].end()) { return; } followers[followerId].erase(followeeId); } };

C++ simple map based NLogN
class Solution { public: vector<string> findRelativeRanks(vector<int>& nums) { map<int, int, std::greater<int>> order; for (int i = 0; i < nums.size(); i++) { order.insert(pair<int, int>(nums[i], i)); } vector<string> solution(nums.size(), ""); int i = 1; for(auto itr = order.begin(); itr != order.end(); itr++, i++) { switch (i) { case 1: solution[itr>second] = "Gold Medal"; break; case 2: solution[itr>second] = "Silver Medal"; break; case 3: solution[itr>second] = "Bronze Medal"; break; default: solution[itr>second] = std::to_string(i); break; } } return solution; } };