paul4156
BAN USERWe just need a node (Median) whose left and right nodes are two AVL trees (or RB trees, etc.).
1. The Median node has a goLeft flag to mentain the median position.
2. If goLeft flag is on, the next insertion should be to the left tree, otherwise to the right tree.
3. If input number is bigger than median. Insert it to the right. If goLeft is true, insert median to the left, make the smallest number from right the new median and delete it from right.
4. If input number is smaller than median. Insert it to the left. If goLeft is false, insert median to the right, make the biggest number from left the new median and delete it from left.
<?php
class AvlTree {
...
}
class Median implements SampleHandler {
public $data;
public $left;
public $right;
public $goLeft = false;
public function __construct() {
$this->left = new AvlTree();
$this->right = new AvlTree();
}
public function addNumber($number) {
if ($this->data === null) {
// First number
$this->data = $number;
return;
}
$median = $this->data;
if ($median > $number) {
$this->left->insert($number);
if ($this->goLeft === false) {
$this->right->insert($median);
$biggest = $this->left->last();
$this->data = $biggest->data;
$this->left->delete($biggest);
}
} else {
$this->right->insert($number);
if ($this->goLeft) {
$this->left->insert($median);
$smallest = $this->right->first();
$this->data = $smallest->data;
$this->right->delete($smallest);
}
}
$this->goLeft = !$this->goLeft;
}
public function median() {
return $this->data;
}
}
<?php
class Stack {
private $top = 0;
private $data = [];
public function push($char) {
$this->data[$this->top] = $char;
$this->top++;
}
public function popAll() {
$result = '';
for ($i = $this->top; $i > 0; $i--) {
$result .= $this->data[$i - 1];
}
$this->top = 0;
return $result;
}
}
function invertWord($content) {
$stack = new Stack();
for ($i = 0; $i < strlen($content); $i++) {
if ($content[$i] != ' ') {
$stack->push($content[$i]);
continue;
}
$output = $stack->popAll();
echo "$output ";
}
$output = $stack->popAll();
echo "$output\n";
}
invertWord('the boy ran');
<?php
function find(array $numbers, $len, $from, $isZero, $incremental) {
$pos = $from;
while ($pos >= 0 && $pos < $len && ($numbers[$pos] == 0) != $isZero) {
$pos += $incremental;
}
return $pos;
}
function swap(array &$numbers, $a, $b) {
$num = $numbers[$a];
$numbers[$a] = $numbers[$b];
$numbers[$b] = $num;
}
function reorder(array &$numbers) {
$len = count($numbers);
$zero = find($numbers, $len, 0, true, 1);
$nonzero = find($numbers, $len, $len - 1, false, -1);
while ($nonzero >= $zero) {
swap($numbers, $zero, $nonzero);
$zero = find($numbers, $len, $zero, true, 1);
$nonzero = find($numbers, $len, $nonzero, false, -1);
}
}
$numbers = [1, 0, 2, 0, 0, 3, 4];
reorder($numbers);
var_dump($numbers);
Only consider /* */ block, not //
<?php
function printNonComments()
{
$inComment = false;
while ($line = getNextLine()) {
$search = $inComment ? '*/' : '/*';
$pos = strpos($line, $search);
while ($pos !== false) {
if (!$inComment) echo substr($line, 0, $pos);
$line = substr($line, $pos + 2);
$inComment = !$inComment;
$search = $inComment ? '*/' : '/*';
$pos = strpos($line, $search);
}
!$inComment ? echo $line : echo "\n";
}
echo "\n";
}
$lines = [
'hello /* this is a ',
'multi line comment */ all',
];
function getNextLine()
{
global $lines;
$line = reset($lines);
if (!$line) return null;
$key = key($lines);
unset($lines[$key]);
return $line;
}
printNonComments();
I guess the main issue is not a single server can store such many integers.
So my solution is based on that assumption and requires communications between servers.
1. A server selects a mediun (say m). Then it asks each of other servers how many bigger integers each server has. If the summed number of bigger integers are just half of the total number of integers , then m is the median.
2. If not, if number of bigger integers > half of total integers, then the selected median is too small. Find the server whose number of bigger integers is largest. Use its median to try again. Keep trying until the selected median is too big.
3. Then use Newton interpolation method to narrow down and finally find the median.
<?php
function maxPosition($numbers)
{
$maxValue = 0;
$maxPositions = [];
foreach ($numbers as $index => $number) {
if ($number > $maxValue) {
$maxValue = $number;
$maxPositions = [$index];
continue;
}
if ($number < $maxValue) {
continue;
}
$maxPositions[] = $index;
}
return $maxPositions[rand(0, count($maxPositions) - 1)];
}
This question needs a tedius program. So I just list the steps for solving it.
1. Maintain a list of possible strings at all time. If the list has only one string with the required length, that is the answer.
2. If list has multiple strings, call getRandomTriplet() again. Combine the triplet with each of the strings in the list. If length overflow, delete it. A new list is formed.
3. In combining two strings (one from the list, one is a triplet). We could simply merge the two. Say 'abc' and 'def'. It can generate 'abcdef', 'dabcef', 'dabecf', 'dabefc', 'adbcef', 'adbecf', 'adbefc', 'deabcf', 'deabfc', 'deafbc', 'abdcef', 'abdecf', 'abdefc', 'daebcf', 'daebfc', 'daefbc', 'adecef', 'adefbc', 'defabc'.
If the two strings share some letters, we could use shared letters and generate shorter strings. Say 'abc' and 'dbf', we could generate 5 letter strings, 'adbcf', 'dabcf', 'adbfc', 'dabfc'.
I am still running this script and it reached 110000 so far.
- paul4156 September 12, 2014