im.code.warrior
BAN USERGood. This would be the most optimal solution.
- im.code.warrior April 06, 2015lol. interviewer would faint.
- im.code.warrior March 19, 2015Stupid problem.
- im.code.warrior March 19, 2015Interviewer must be looking for multithreading.
Fetch count from all sources in parallel.
Bonus points: If machine has less than 5 cores (for 5 data sources), say 4 cores, prioritize so that first 4 data sources get the highest priority. Not sure how to do this in code.
Interviewer must be looking for multithreading.
Fetch count from all sources in parallel.
Bonus points: If machine has less than 5 cores (for 5 data sources), say 4 cores, prioritize so that first 4 cores get the highest priority. Not sure how to do this in code.
Interviewer must be looking for multithreading.
Fetch count from all sources in parallel.
Bonus points: If machine has less than 5 cores (for 5 data sources), say 4 cores, prioritize so that first 4 cores get the highest priority. Not sure how to do this in code.
Here's my binary search:
unsigned getIndexLower(const vector<float> &vec, float target){
if (vec.size() <=1 )return vec.size();
unsigned low =0, high= vec.size()-1;
while(low < high){
unsigned mid = (low+high)/2;
if (vec[mid] <= target && (mid <high && vec[mid+1] > target)){
return mid+1;
}
if (vec[mid] < target) { low = mid+1; }
else { high = mid; }
}
return low;
}
C++ code using floodfill algorithm
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;
// flood fill.
inline unsigned getKey(unsigned row, unsigned col, unsigned ncols){
return row * ncols + col;
}
template <size_t T>
void fill(char mat[][T], int i, int j, unsigned nrows, unsigned ncols, const unordered_map<unsigned, unsigned> &hash,
unordered_set<unsigned> &visited, unsigned regionId, bool diag){
if (i <0 || i >= nrows || j<0 || j>= ncols || mat[i][j] != 'x') return;
unsigned key = getKey(i,j,ncols);
if (visited.find(key) != visited.end()) return;
cout << "Visited:" << i<<"," <<j<<"\n";
visited.insert(key);
if(diag) fill(mat, i-1, j-1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i-1, j, nrows, ncols, hash, visited, regionId, diag);
if(diag) fill(mat, i-1, j+1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i, j-1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i, j+1, nrows, ncols, hash, visited, regionId, diag);
if(diag) fill(mat, i+1, j-1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i+1, j, nrows, ncols, hash, visited, regionId, diag);
if(diag) fill(mat, i+1, j+1, nrows, ncols, hash, visited, regionId, diag);
}
template <size_t T>
unsigned getNumRegions(char mat[][T], unsigned nrows, unsigned ncols, bool diag = false){
unsigned num = 0;
unordered_map<unsigned, unsigned> hash;
unordered_set<unsigned> visited;
for (unsigned i=0; i<nrows; ++i){
for (unsigned j=0; j<ncols; ++j){
unsigned key = getKey(i,j,ncols);
if (mat[i][j] != 'x' || (visited.find(key) != visited.end()) ) continue;
cout << "Fill:" << i<<"," <<j<<"\n";
fill<T>(mat, i, j, nrows, ncols, hash, visited, ++num, diag);
}
}
return num;
}
int main() {
char mat[4][3] = {
{'x','o','o'},
{'o','x','x'},
{'x','o','o'},
{'o','x','x'}
};
cout << getNumRegions<3>(mat,4,3, true) <<"\n";
cout << getNumRegions<3>(mat,4,3) <<"\n";
cout << "Done!\n";
return 0;
}
Both areO( 2^k.n) where k is the number of ? chars in str of length n. This approach is much faster and desirable than the recursive approach.
- im.code.warrior July 19, 2014Everyone seems to assume tree consists of integer or char data.
In practical applications, lots of times data structures hold some complex objects. Your algorithm should you be able to efficiently serialize and deserialize and so your approach should depend on the type of data it holds and how sparse the tree can be.
What if the tree is like a social graph? You can't hold it in memory?
What if this tree has to be sent over the wire? optimize for size of the object there even if it takes little more time to do the serialization and deserialization. etc etc..
These are the things the interviewer will be looking for.
Works, but the resulting string is bigger than doing inorder and preorder/postorder.
- im.code.warrior July 19, 2014This is the correct solution.
- im.code.warrior July 19, 2014No, the space won't be high. I think BFS or a level order is the best solution.
You have to use O(n) space anyway. Recursion is worse (stack space takes up O(n)) and if your tree is deep, you will get stack overflow error.
void printLongestRun(const string &str){
if (str.length() <=1) {
cout <<str<<"\n";
return;
}
unsigned cur =0, next=0, max =0, max_start =0;
while(str[cur]){
while (next < str.length() && str[cur] == str[next]) ++next;
unsigned end = (next != str.length()) ? next-1 : str.length()-1;
if (end - cur + 1 > max){
max = end - cur + 1;
max_start = cur;
}
cur = next;
}
cout << str << "\t=>"<<str.substr(max_start, max) << "\n";
}
void printLongestRun(const string &str){
if (str.length() <=1) {
cout <<str<<"\n";
return;
}
unsigned cur =0, next=0, max =0, max_start =0;
while(str[cur]){
while (next < str.length() && str[cur] == str[next]) ++next;
unsigned end = (next != str.length()) ? next-1 : str.length()-1;
if (end - cur + 1 > max){
max = end - cur + 1;
max_start = cur;
}
cur = next;
}
cout << str << "\t=>"<<str.substr(max_start, max) << "\n";
}
void printLongestRun(const string &str){
if (str.length() <=1) {
cout <<str<<"\n";
return;
}
unsigned cur =0, next=0, max =0, max_start =0;
while(str[cur]){
while (next < str.length() && str[cur] == str[next]) ++next;
unsigned end = (next != str.length()) ? next-1 : str.length()-1;
if (end - cur + 1 > max){
max = end - cur + 1;
max_start = cur;
}
cur = next;
}
cout << str << "\t=>"<<str.substr(max_start, max) << "\n";
}
As explained above for 2D, you have to examine atmost 5 points and for N-dimension, at most 2^N+1.
Algo to find the actual point:
For 2-D, sum of x-axis co-ordinates and y-co-ordinates should be even.
Consider a binary representation with 0 denoting even and 1 for odd. So a point can have 4 values 00,01,10,11 corresponding to both (x,y) even, (x even, y odd), (x odd, y even) and (1,1) will be both odd.
Traverse the set and as you see each point, assign a value(0,1,2 or 3) to the co-ordinate. When you find a point which also the same value, you found a matching point.
For n-dimension, instead of 00 to 11, you would have 0...0 (n zeroes) to 1...1 (n ones). i.e integer values 0 to 2^N-1. With a similar approach, you have to find if 2 points have the same value.
As explained above for 2D, you have to examine atmost 5 points and for N-dimension, at most 2^N+1.
Algo to find the actual point:
For 2-D, sum of x-axis co-ordinates and y-co-ordinates should be even.
Consider a binary representation with 0 denoting even and 1 for odd. So a point can have 4 values 00,01,10,11 corresponding to both (x,y) even, (x even, y odd), (x odd, y even) and (1,1) will be both odd.
Traverse the set and as you see each point, assign a value(0,1,2 or 3) to the co-ordinate. When you find a point which also the same value, you found a matching point.
For n-dimension, instead of 00 to 11, you would have 0...0 (n zeroes) to 1...1 (n ones). i.e integer values 0 to 2^N-1. With a similar approach, you have to find if 2 points have the same value.
As explained above for 2D, you have to examine atmost 5 points and for N-dimension, at most 2^N+1.
Algo to find the actual point:
For 2-D, sum of x-axis co-ordinates and y-co-ordinates should be even.
Consider a binary representation with 0 denoting even and 1 for odd. So a point can have 4 values 00,01,10,11 corresponding to both (x,y) even, (x even, y odd), (x odd, y even) and (1,1) will be both odd.
Traverse the set and as you see each point, assign a value(0,1,2 or 3) to the co-ordinate. When you find a point which also the same value, you found a matching point.
For n-dimension, instead of 00 to 11, you would have 0...0 (n zeroes) to 1...1 (n ones). i.e integer values 0 to 2^N-1. With a similar approach, you have to find if 2 points have the same value.
Yes stack is not good idea. We might add lot of duplicates. So hash shud be part of the solution. I think its just similar to LRU except that its most recently used instead of LRU. but same data structure would do
- im.code.warrior April 10, 2014Yes, as you guys point out reading one int at a time from each file is grossly inefficient as there might be lot of paging. Best is to read all k numbers in each file and put it into min heap of size 100k.
Also if performance if not important but speed of writing code is important (say a quick test), then we can do it one line in Unix.
Assume current dir has the files.
cat * >> out && sort -n out | head -k
Obviously algorithm wise its inefficient, but good to point out in an interview as it can be quite handy to quick jobs.
Bit operations are fast only if you could fit an integer in a register. With a huge bit stream, it need not be fast.
- im.code.warrior April 10, 2014Same as Sound Wave's solution.
Here's the pseudo code.
void printGraph(Node *root) {
static DeQueue<int> q; // this is store a path. DeQueue to access from front and back.
static set<Node*> visited;
if (NULL == root) {
// this will print the contents of q from head to tail. this is a full path.
printDeQueue(q);
return;
}
visisted.insert(root); // mark node as visited.
q.push(root->data);
Node *c;
for_each(c in root->children){
if(visited.find(c) != visited.end()) { //already visited. cycle.
printDeQueue(q); // print the path
continue;
}
q.push_back(c);
printGraph(c);
q.pop_back();
}
}
- im.code.warrior April 06, 2015