lucifer1986
BAN USER- 3of 3 votes
AnswersSuppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.
- lucifer1986 in United States
The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.| Report Duplicate | Flag | PURGE
Google Data Structures
I would suppose the four points was given by their coordinates like (x,y)
solution would be first pick up one point, mark it with start_point, then compare it with the rest 3, check if there 1 point has the same x with start_point, mark it as horizontal_point, calculate their distance as width, then check the rest 2 points to see there is 1 point has the same y, mark it as vertical_point, calculate their distance as height, if the remaining last point has the same x with vertical_point and same y with horizontal point, it is a rectangle and if with==height it is a square.
#include <list>
#include <math.h>
struct Point
{
int x = 0;
int y = 0;
};
enum class RectType
{
Square,
Rectangle,
NotRect
};
RectType checkRect(Point* p1, Point* p2, Point* p3, Point* p4)
{
std::list<Point*> cache;
Point* start_p = p1;
cache.push_back(p2);
cache.push_back(p3);
cache.push_back(p4);
Point* horizontal_p = nullptr;
std::list<Point*>::iterator it = cache.begin();
while(it != cache.end())
{
if ((*it)->x == start_p->x)
{
horizontal_p = (*it);
cache.erase(it++);
break;
}
it++;
}
if (!horizontal_p)
return RectType::NotRect;
int width = abs(horizontal_p->y - start_p->y);
Point* vertical_p = nullptr;
std::list<Point*>::iterator it = cache.begin();
while (it != cache.end())
{
if ((*it)->y == start_p->y)
{
vertical_p = (*it);
cache.erase(it++);
break;
}
it++;
}
if (!vertical_p)
return RectType::NotRect;
int height = abs(vertical_p->x - vertical_p->x);
if ((*cache.begin())->x == vertical_p->x && (*cache.begin())->y == horizontal_p->y)
{
if (height == width)
return RectType::Square;
return RectType::Rectangle;
}
return RectType::NotRect;
}
You need to traverse the tree by level, so use BFS would do the job, but standard BFS would not work because it do not have clear boundary on each level, the key is using 2 queues, code is like:
std::queue<Node*> queues[2];
vector<int> sizes;
int cur_queue_index = 0;
int next_queue_index =1;
if (root) {
queues[0].push(root);
} else {
return;
}
cout << "[";
int sum = 0;
while (!queue[cur_queue_index].empty()) {
const node * const current_node = queues[cur_queue_index].front;
queues[cur_queue_index].pop();
sum += current_node->value;
if(current_node->left) {
queues[next_queue_index].push(current_node->left);
}
if(current_node->right) {
queues[next_queue_index].push(current_node->right);
}
if(queue[cur_queue_index].empty())
{
cout << sum << ",";
sum = 0;
swap(next_queue_index, cur_queue_index);
}
}
cout << "]";
requirement is O(n) or less
- lucifer1986 August 30, 2015
Each city could be a node and every node has a list of neighbor node(so it become a tree-like structure and every node could be the root), this is a easy approach when n is not big(as in the problem it is less than 105)
- lucifer1986 September 29, 2015