Nima
BAN USER1. Central server asks which computer has highest top ten and receives that. Highest is defined as bigger tenths element (minimum of top ten).
2. Sever ask each computer for corresponding URLs, it just received, and computers remove those URLs from their list.
3. Server updates its top then with received URLs.
4. Repeat this until no computer has bigger top ten than server top ten divided by number of computers.
Iterate for each valid two start of staves and each valid stave length. Start from bigger length to smaller though. During iteration store sum, weighted sum, and weighted sum of reverse in matrices. So, the calculation requires iteration only at edges and can be computed otherwise in constant time. Time complexity : O(n^3), Space complexity O(n^2):
//staff.h:
#include <iostream>
#include <string>
#include <vector>
class Staff
{
size_t pos0;
size_t pos1;
size_t len;
std::string str;
bool reverse;
std::vector<std::vector<size_t> > sum; //sum for a postion with a length [postion][length]
std::vector<std::vector<size_t> > weighted_sum; //weighted sum for a postion with a length [postion][length]
std::vector<std::vector<size_t> > reverse_weighted_sum; //if the sequence is reversed, weighted sum
// for a postion with a length [postion][length]
bool mass_center();
void max();
public:
operator bool() const;
Staff(const string m_str);
Staff(const Staff& staff);
friend ostream& operator<<(ostream& stream, const Staff& a);
};
std::ostream& operator<<(std::ostream& stream, const Staff& a);
//staff.cc:
#include <string>
#include <cassert>
using namespace std;
#include "staff.h"
ostream& operator<<(ostream& stream, const Staff& a)
{
if (a)
stream<< a.pos0<< " "<< a.pos1<< " "<< a.len;
else
cout<< "No Staff"<< endl;
return stream;
}
Staff::Staff(const string m_str): pos0(0), pos1(0), len(0), str(m_str)
, sum(m_str.length(), vector<size_t>(m_str.length())), weighted_sum(m_str.length(), vector<size_t>(m_str.length())),
reverse_weighted_sum(m_str.length(), vector<size_t>(m_str.length()))
{
max();
}
Staff::Staff(const Staff& staff): pos0(staff.pos0), pos1(staff.pos1), len(staff.len),
str(staff.str), reverse(staff.reverse)
{}
Staff::operator bool() const
{
return pos1 && len;
}
bool Staff::mass_center()
{
if (len == str.length() / 2 || pos1 + len == str.length())
{
sum[pos0][len]= 0;
sum[pos1][len]= 0;
weighted_sum[pos0][len]= 0;
weighted_sum[pos1][len]= 0;
reverse_weighted_sum[pos0][len]= 0;
reverse_weighted_sum[pos1][len]= 0;
for(size_t d= 1; d<= len; d++)
{
int m= str[pos0 + d - 1] - '0';
int m1= str[pos1 + d - 1] - '0';
sum[pos0][len]+= m;
sum[pos1][len]+= m1;
weighted_sum[pos0][len]+= m * d;
weighted_sum[pos1][len]+= m1 * (d + len);
reverse_weighted_sum[pos0][len]+= m * (len - d + 1);
reverse_weighted_sum[pos1][len]+= m1 * (2 * len - d + 1);
}
}
else
{
int m= str[pos0 + len] - '0'; // number just after this stave
int m1= str[pos1 + len ] - '0';
int prev_len= len + 1;
int d= 1;
sum[pos0][len]= sum[pos0][prev_len] - m;
sum[pos1][len]= sum[pos1][prev_len] - m1;
weighted_sum[pos0][len]= weighted_sum[pos0][prev_len] - m * d;
weighted_sum[pos1][len]= weighted_sum[pos1][prev_len] - m1 * (d + prev_len);
reverse_weighted_sum[pos0][len]= reverse_weighted_sum[pos0][prev_len] - m * (prev_len - d + 1);
reverse_weighted_sum[pos1][len]= reverse_weighted_sum[pos1][prev_len] - m1 * (2 * prev_len - d + 1);
}
int whole_sum= sum[pos0][len] + sum[pos1][len];
float center= (float)(weighted_sum[pos0][len] + weighted_sum[pos1][len]) / whole_sum;
float center1= (float)(reverse_weighted_sum[pos0][len] + weighted_sum[pos1][len]) / whole_sum;
float ideal_center= len + .5;
if (center == ideal_center /*< 0.000000000001*/)
{
reverse= false;
return true;
}
else if (center1 == ideal_center /*< 0.000000000001*/)
{
reverse= true;
return true;
}
else
return false;
}
void Staff::max()
{
Staff max_staff(*this);
size_t str_len= str.length();
for(pos0= 0; pos0< str_len; pos0++)
{
for(len= (str_len - pos0)/ 2; len>= 1 && max_staff.len< len; len--)
{
for(pos1= pos0+ len; pos1< str_len - len + 1; pos1++)
{
if (pos0 == 0 && pos1 == 8 && len == 4)
cout<< len<< endl;
if (mass_center() && max_staff.len< len)
{
//printf("\tpos0 %d pos1 %d len %d reverse %d\n", pos0, pos1, len, reverse);
max_staff= *this;
break;
}
}
}
}
*this= max_staff;
}
int main(int argc, char* argv[])
{
/*123456789 1234*/
Staff a("41111921111119");
cout<< a<< endl;
Staff a1("131251141231");
cout<< a1<< endl;
}
1- Find median in each server
2- Find median of the medians which ends up with two numbers since count is even
3- Find median of numbers within range of the above two number in each server
4- Repeat step 2 and 3 until each sever has no more than two numbers within the range, the two numbers are the final median.
Time O(n), Space O(n)
- Nima December 21, 20201. Put every char of anagram in hash data structure
2. Iterate through string.
a. If current char is in hash,
a1.Remove the char from hash. If hash is empty(), return true
b. If not, reset hash, repeat a1.