wjian@yahoo-inc.com
BAN USERE(T) = sum{(k - k / 3 * (i - 1) - C) * p^i * (1-p) ^ (i - 1), i = 1, 2, 3, 4} + (k - k * 4 / 3 - 0) * (1 - p)^5
static int stream_sample(int* numbers)
{
int k = 0;
int selected = 0;
while (*numbers != 0)
{
++k;
if (rand() * k < 1)
{
selected = *numbers;
}
numbers++;
}
return selected;
}
static int stream_sample(int* numbers)
{
double cur = 1;
double selected = 0;
while (*numbers != 0)
{
double new_cur = rand();
if (new_cur < cur)
{
cur = new_cur;
selected = *numbers;
}
numbers++;
}
return selected;
}
double cmp(double l, double r)
{
double e = 1e-5;
if (l < r - e)return -1;
if (l > r + e)return 1;
return 0;
}
/*
* square root of a number
* use binary search, predicate is, if m * m >= x, for all n >= m, n * n >= x
* l = 1, r = x >> 1
* stopping criteria: l >= r
* case: x = 0 , return 0
* : x = 1, return 1
* : x = 4, return 2
* : x = 9, return 3
*/
#define MAX_ITERATIONS 1000
double square_root(double x)
{
assert(x >= 0);
if (cmp(x, 1.0) <= 0)return x;
double l, r;
l = 1;r=(cmp(x, 4.0) >= 0 ? x>>1: x);
int iteration = 0;
double alpha = 1.0;
double search_space = (r - l);
double prev_search_space = (r - l) * 2;
while(cmp(l, r) < 0 && (iteration++ < MAX_ITERATIONS || (prev_search_space - search_space) * 100/prev_search_space < alpha))
{
prev_search_space = search_space;
double m = l + (r - l ) >> 1;
if (cmp(m * m, x) == 0)return m;
if (cmp(m * m , x) > 0)r = m;
else l = m;
search_space = r - l;
}
//cmp(l, r) > =0
return l;
}
/*
* given a long string str, print in line, no breaking of words, left-right, at most L characters per line
* str = ab cd ef, L = 2, output ab\ncd\nef\n
* str = ab d e hl, L = 3, output abd\nehl\n
* str = abc efg, L = 4, output abc\nefg\n
* str = a, L = 2, output a\n
*/
void format_print(const char* str, int L)
{
char buffer = new char[L];
int buffer_head = 0;
int buffer_size = 0;
for (; *str; str++)
{
if (buffer_size == L)
{
//output from buffer_head, for buffer_size
if (*str == ' ')
{
last_word_right_bound = buffer_size - 1;
}
for (int i = 0; i < buffer_size; i++)
{
printf("%c", buffer[(buffer_head + i - 1 + L) % L]);
if (i == last_word_right_bound)
{
for (int j = i + 1; j < buffer_size; j++)
{
printf(" ");
}
printf("\n");
}
}
buffer_head = buffer_size = 0;
}
{
buffer[(buffer_head + buffer_size - 1 + L) % L] = *str;
if (*str == ' ' && buffer_size > 0)
{
last_word_right_bound = buffer_size - 1;
}
buffer_size++;
}
}
if (buffer_size > 0)
{
bool only_space = true;
for (int i = 0; i < buffer_size; i++)
{
printf("%c", buffer[(buffer_head + i - 1 + L) % L]);
only_space &= (buffer[(buffer_head + i - 1 + L) == ' ');
}
for (; !only_space && i < L; i++)
{
printf(" ");
}
printf("\n");
}
}
/*
* find all pairs of numbers that sum up to k
* 2341,5 -> {(2,3), (4,1)}
* 2222,4 -> {(2, 2), (2, 2), (2, 2), (2, 2), (2, 2), (2, 2)}
* 2, 4 -> {}
*/
void find_sum_pairs(int* vec, int n, int k)
{
qsort(vec, n, sizeof(int)); //O(nlog(n))
int left, right;
left = 0;
right = n - 1;
while(left < right)
{
if (vec[left] + vec[right] == k)
{
printf("(%d, %d)\n", left, right);
for (int r = right - 1; r > left; r--)
{
if (vec[r] == vec[right])
{
printf("(%d, %d)\n", left, r);
}
}
left++;
}
else if (vec[left] + vec[right] < k)
{
left++;
}
else
{
right--;
}
}
}
#include <stdio.h>
using namespace std;
//edge case: ()
//edge case: 0)
//edge case: (00)
//edge case: (0(0(00)))
//edge case: ((00)(00))
//edge case: ((00)(((00)(00))0))
//edge case: (0)
//edge caes: (0p)
//edge case: (000)
//edge case: (0(00)
//edge case: )(00)
#define N 100
int find_depth_2(const char* str)
{
int depth = 0;
int top = -1;
char stack[N + 1] = {0};
int max_depth = -1;
const char* p;
for (p = str; *p; p++)
{
if (*p == ')')
{
if (top > 1 && stack[top] == '0' && stack[top - 1] == '0' && stack[top - 2] == '(')
{
top-=3;
stack[++top] = '0';
max_depth = (max_depth < depth ? depth : max_depth);
depth--;
}
else
{
return -1;
}
}
else
{
stack[++top] = *p;
if (*p == '(')
{
depth++;
}
}
}
if (top == 0 && stack[top] == '0')
{
return max_depth;
}
return -1;
}
int find_depth(const char* str)
{
int depth = 0;
int max_depth = -1;
int stack[N + 1] = {0};
int top = 0;
const char* p;
for (p = str; *p ; p++)
{
if (*p == '(')
{
if (stack[top] == 1)
{
stack[++top] = 2;
stack[++top] = 1;
}
else if(stack[top] == 2)
{
stack[++top] = 3;
stack[++top] = 1;
}
else if (stack[top] == 0)
{
stack[++top] = 1;
}
else
{
return -1;
}
depth++;
}
else if (*p == ')')
{
if (stack[top] == 3)
{
top--;
if (stack[top] == 2)
{
top--;
if (stack[top] == 1)
{
top--;
max_depth = (max_depth < depth ? depth : max_depth);
depth--;
continue;
}
}
return -1;
}
else
{
return -1;
}
}
else if (*p == '0')
{
if (stack[top] == 1)
{
stack[++top] = 2;
}
else if (stack[top] == 2)
{
stack[++top] = 3;
}
else
{
return -1;
}
}
else
{
return -1;
}
}
if (*p == 0 && top == 0 && stack[top] == 0)
{
return max_depth;
}
return -1;
}
int main() {
const char* test = ")(00)";
printf("%d\n", find_depth(test));
printf("%d\n", find_depth_2(test));
return 0;
}
//edge case: [1, 5]
//edge case: [1, 1]
//edge case: [2, 3], [3, 5], [3, 4]
//edge case: [3, 3], [3, 4], [2, 4], [5, 7], [6, 8]
struct interval
{
int from;
int to;
};
struct binary_node
{
struct interval interv;
struct binary_node* left;
struct binary_node* right;
};
public Interface Intervals
{
struct binary_node* root = NULL;
int left = -1;
public void add(int from, int to)
{
struct interval i;
i.from = from;
i.to = to;
struct binary_node* new_node = new struct binary_node;
new_node->interv = i;
if (left == -1 || left > new_node->interv.from)
{
left = new_node->interv.from;
}
new_node->left = new_node->right = NULL;
if (root == NULL)
{
root = new_node;
}
else
{
struct binary_node* p = NULL;
struct binary_node* cur = root;
while (cur != NULL)
{
p = cur;
if (i.from < cur->interv.from || (i.from == cur->interv.from && i.to < cur->interv.to))
{
cur = cur->left;
}
else
{
cur = cur->right;
}
}
if (i.from <= p->interv.from)
{
p->left = new_node;
}
else
{
p->right = new_node;
}
}
}
int getTotalCoveredLength()
{
int left, right, tot;
left = right = left - 1;
tot = 0;
in_order(root, left, right, tot);
return tot;
}
void in_order(struct binary_node* root, int& left, int& right, int& tot)
{
if (root != NULL)
{
in_order(root->left, left, right, tot);
int cur_left = root->interv.from;
int cur_right = root->interv.to;
//cur_left >= left
if (cur_left > right)
{
tot += cur_right - cur_left;
}
else
{
tot += (cur_right - right > 0 ? cur_right - right : 0);
}
left = (cur_left > right ? cur_left : left);
right = (right < cur_right ? cur_right: right);
int tot_right = in_order(root->right, left, right, tot);
}
}
}
#include <stdio.h>
using namespace std;
int getWeightedSum(const char* str)
{
int sum = 0;
int depth = 0;
for(;*str; str++)
{
if (*str == '{')
{
depth++;
}
else if (*str == '}')
{
depth--;
}
else if (*str != ',')
{
int nested_sum = 0;
while(*str >= '0' && *str <= '9')
{
nested_sum += nested_sum * 10 + (*str - '0');
str++;
}
sum+=nested_sum * depth;
}
}
return sum;
}
int main() {
printf("%d\n", getWeightedSum("{1, {1,{1,2,{1,2
}"));
return 0;
}
#define N 100
#define L 100
int f[N] = {0};
int m[N] = {0};
for (int i = n - 1; i >= 0; i—)
{
int s = length(word[i]);
f[i] = L - s + f[i+1];
m[i] = j;
for (int j = i + 1; j < n && s + length(word[j]) <= L; j++)
{
s += length(word[j]);
if (f[i] > L - s + f[j+1])
{
f[i] = L - s + f[j+1];
m[i] = j;
}
}
}
return f[0];
struct binary_node* flip(struct binary_node* root)
{
if(root != NULL)
{
struct binary_node* left = root->left;
struct binary_node* right = root->right;
while(left != NULL)
{
struct binary_node* left_left = left->left;
struct binary_node* left_right = left->right;
left->left = right;
left->right = root;
root = left;
left = left_left;
right = left_right;
}
}
return root;
}
- wjian@yahoo-inc.com September 21, 2014