zombie
BAN USERTrie is a good solution. Another solution is postfix array.
1. Generate a postfix array based on input string. Time complexity O(n). Space complexity O(n). n is the length of the stream.
2. Sort the postfix array. Time complexity O(n*lgn*t). t is the average character comparison number in sort. Space complexity O(lgn), the maximize stack number in quick sort.
3. Iterate the list of words. Do binary search in postfix array. Time complexity O(lgn*k). k is the maximize length of word.
Overall time complexity: O(n*lgn*t). space complexity O(lgn).
bool lessStr(const char * s1, const char * s2) {
return strcmp(s1, s2) <= 0;
}
bool equalStr(const char * s1, const char * s2) {
int sz1 = strlen(s1);
int sz2 = strlen(s2);
if(sz1 < sz2) return false;
int i = 0;
while(i < sz2) {
if(s1[i] != s2[i]) return false;
i ++;
}
return true;
}
int binarySearchLeftIndex(const char * postfix[], int lo, int hi, const char * s) {
int start = lo;
int end = hi;
while(start < end) {
int mid = start + (end - start) / 2;
if(equalStr(postfix[mid], s)) {
end = mid;
}
else if(lessStr(postfix[mid], s)) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return equalStr(postfix[start], s) ? start : -1;
}
int binarySearchRightIndex(const char * postfix[], int lo, int hi, const char * s) {
int start = lo;
int end = hi;
while(start < end - 1) {
int mid = start + (end - start) / 2;
if(equalStr(postfix[mid], s)) {
start = mid;
}
else if(lessStr(postfix[mid], s)) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return equalStr(postfix[end], s) ? end :
equalStr(postfix[start], s) ? start : -1;
}
void f(string & s, vector<string> & v) {
int sz = s.size();
if(0 == sz) return ;
const char * postfix[sz];
for(int i = 0; i < sz; i ++) {
postfix[i] = s.c_str() + i;
}
sort(postfix, postfix + sz, lessStr);
for(int i = 0; i < v.size(); i ++) {
int leftIndex = binarySearchLeftIndex(postfix, 0, sz - 1, v[i].c_str());
if(-1 == leftIndex) {
printf("count of %s is: %d\n", v[i].c_str(), 0);
continue;
}
int rightIndex = binarySearchRightIndex(postfix, 0, sz - 1, v[i].c_str());
printf("count of %s is: %d\n", v[i].c_str(), rightIndex - leftIndex + 1);
}
}
1. variant algorithm of normal binary search
int bsearchFirst(vector<int> a, int val) {
if(0 == a.size()) return -1;
int s = 0;
int e = a.size() - 1;
while(s < e) {
int m = (s + e) / 2;
if(a[m] == val) {
e = m;
}
else if(a[m] > val) {
e = m - 1;
}
else {
s = m + 1;
}
}
return (val == a[s]) ? s : -1;
}
int bsearchLast(vector<int> a, int val) {
if(0 == a.size()) return -1;
int s = 0;
int e = a.size() - 1;
while(s < e - 1) {
int m = (s + e) / 2;
if(a[m] == val) {
s = m;
}
else if(a[m] > val) {
e = m - 1;
}
else {
s = m + 1;
}
}
return (val == a[e]) ? e : (val == a[s]) ? s : -1;
}
/// Using Some Method Like mid-order Trans
TNode * kth_largest(TNode * root, int k, int & count)
{
if(NULL == root) return NULL;
TNode * r1 = kth_largest(root->right, k, count);
if(NULL != r1) return r1;
count ++;
if(k == count) return root;
TNode * r2 = kth_largest(root->left, k, count);
if(NULL != r2) return r2;
return NULL;
}
/// Just another recursive solution. Who know iterative solution? Plz show me.
int print_vec_char(vector<char> & one)
{
for(int i = 0; i < one.size(); i ++) printf("%c", one[i]);
printf("\n");
return 0;
}
int gen_string(string & s, int sel, vector<char> & one)
{
if(sel == s.size()) {
print_vec_char(one);
return 0;
}
if(s[sel] == '0') return 0;
/// 1.0 using one char
one.push_back(s[sel] - '1' + 'a');
gen_string(s, sel + 1, one);
one.pop_back();
/// 2.0 using two char
if(sel <= s.size() - 2) {
int t = (s[sel] - '0') * 10 + (s[sel+1] - '0');
if(t <= 26) {
one.push_back(t + 'a' - 1);
gen_string(s, sel + 2, one);
one.pop_back();
}
}
return 0;
}
/// How About Using Recursion Solution
struct Node
{
int val;
Node * left;
Node * right;
Node(int v = 0) : val(v), left(NULL), right(NULL)
{
}
};
int find_path_imp(Node * root, int val, vector<int> & one, vector< vector<int> > & res)
{
if(0 == val) return 0;
if(NULL == root) return 0;
if(root->val < val) {
vector<int> lone = one;
lone.push_back(root->val);
find_path_imp(root->left, val - root->val, lone, res);
vector<int> rone = one;
rone.push_back(root->val);
find_path_imp(root->right, val - root->val, rone, res);
return 0;
}
else if(root->val == val) {one.push_back(root->val); res.push_back(one); one.pop_back(); return 0;}
else return 0;
}
int print_res(vector<int> & l, int v, vector<int> & r)
{
for(int i = 0; i < l.size(); i ++) printf("%d ", l[i]);
printf("%d ", v);
for(int i = 0; i < r.size(); i ++) printf("%d ", r[i]);
printf("\n");
return 0;
}
int find_path(Node * root, int val)
{
if(NULL == root) return 0;
if(root->val == val) {
/// 1.0 result path include rootnode
/// 2.0 result path just in left child
printf("%d\n", root->val);
find_path(root->left, val);
}
else if(root->val < val) {
/// 1.0 result path include rootnode
/// 2.0 result path just in left child
/// 3.0 result path just in right child
int left = val - root->val;
vector<int> lone, rone;
vector< vector<int> > lres, rres;
for(int i = 0; i <= left; i ++) {
lres.clear(); rres.clear();
find_path_imp(root->left, i, lone, lres);
find_path_imp(root->right, left - i, rone, rres);
vector<int> empty;
if(0 == i) lres.push_back(empty);
if(left == i) rres.push_back(empty);
for(int li = 0; li < lres.size(); li ++) {
for(int ri = 0; ri < rres.size(); ri ++) {
print_res(lres[li], root->val, rres[ri]);
}
}
}
find_path(root->left, val);
find_path(root->right, val);
}
else {
/// 1.0 result path just in left child
find_path(root->left, val);
}
return 0;
}
/// How About recursion Sulition
struct Node
{
int val;
Node * left;
Node * right;
Node(int v) : val(v), left(NULL), right(NULL)
{
}
};
bool is_in_tree(Node * root, Node * n)
{
if(NULL == root) return false;
if(root == n) return true;
return is_in_tree(root->left, n) || is_in_tree(root->right, n);
}
Node * common_ancestor(Node * root, Node * n1 , Node * n2)
{
if((root == n1) || (root == n2)) return root;
bool is_n1_in_left = is_in_tree(root->left, n1);
bool is_n2_in_left = is_in_tree(root->left, n2);
if(is_n1_in_left && is_n2_in_left) return common_ancestor(root->left, n1, n2);
else if(is_n1_in_left && !is_n2_in_left) return root;
else if(!is_n1_in_left && is_n2_in_left) return root;
else return common_ancestor(root->right, n1, n2);
}
struct Node {
int sum;
int index;
Node() : sum(0), index(0) {}
};
bool lessx(const Node & l, const Node & r)
{
return ((l.sum == r.sum) && (l.index < r.index)) || (l.sum < r.sum);
}
int run()
{
int A[] = {1, 4, -7, 2, 1, 2, -2, -10};
int sz = sizeof(A)/sizeof(A[0]);
Node B[sz]; B[0].sum = A[0];
for(int i = 1; i < sz; i ++) {
B[i].sum = B[i-1].sum + A[i];
B[i].index = i;
}
sort(B, B + sz, lessx);
Node old; old.sum = (1 << 31) - 1; old.index = 0;
int i = 0;
while(i < sz) {
if((old.sum == B[i].sum) && (B[i].index - old.index >= 2)) {
for(int j = old.index + 1; j <= B[i].index; j ++) printf("%d ", A[j]);
printf("\n");
break;
}
old = B[i++];
}
return 0;
}
int run()
{
///const char * str = "yahoo";
///const char * str = "yoy";
///const char * str = "World";
const char * str = "mahesh";
int size = strlen(str);
int m[size][size];
memset(m, 0, sizeof(m));
int len = 2;
for(len = 2; len <= size; len ++) {
for(int i = 0; i + len <= size; i ++) {
int e = i + len - 1;
int m1 = 1 + m[i][e-1];
int m2 = (1 << 31) - 1;
if(str[i] == str[e]) {
if(i+1 <= e-1) m2 = m[i+1][e-1];
else m2 = 0;
}
int m3 = 1 + m[i+1][e];
int mx = (m1 < m2) ? m1 : m2;
mx = (mx < m3) ? mx : m3;
m[i][i+len-1] = mx;
}
}
/*
for(int i = 0; i < size; i ++) {
for(int j = 0; j < size; j ++) printf("%d ", m[i][j]);
printf("\n");
}
*/
printf("%d \n", m[0][size-1]);
return 0;
}
x + y + z = d
x/72 + y/64 + z/56 = 4; (1)
x/56 + y/64 + z/72 = 14/3; (2)
from (1) and (2)
56x + 63y + 72z = 16128; (1')
72x + 63y + 56z = 18816; (2')
from(1') and (2')
(2') - (1') => x - z = 168;
63(x + y + z) - 7x + 9z = 16128; (1'')
63(x + y + z) - 7z + 9x = 18816; (2'')
(1'') + (2'') => 63*2(x + y + z) - 2(x - z) = 34944;
So x + y + z = 280 KM
/// Using Merge Sort Method
int run()
{
/// (1<<31)-1 is an append item
int A[] = {2, 4, 6, 8, (1<<31) - 1};
int B[] = {1, 3, 5, 70, (1<<31) - 1};
int C[] = {40, 50, 60, 70, 80, (1<<31) - 1};
int sz1 = sizeof(A)/sizeof(A[0]);
int sz2 = sizeof(B)/sizeof(B[0]);
int sz3 = sizeof(C)/sizeof(C[0]);
int i = 0, j = 0, k = 0;
int minx = (1 << 31) - 1;
while((i < sz1) && (j < sz2) && (k < sz3)) {
int k1 = A[i], k2 = B[j], k3 = C[k];
int m = abs(k1 - k2);
m = m < abs(k2 - k3) ? abs(k2 - k3) : m;
m = m < abs(k1 - k3) ? abs(k1 - k3) : m;
minx = minx < m ? minx : m;
int m1 = k1 < k2 ? k1 : k2;
m1 = m1 < k3 ? m1 : k3;
if(m1 == k1) i ++;
else if(m1 == k2) j ++;
else k ++;
if((i == sz1 - 1) && (j == sz2 - 1) && (k == sz3 - 1)) break;
}
printf("minx is : %d\n", minx);
return 0;
}
/// Using BST Method
struct Node
{
int val;
int cnt;
Node * left;
Node * right;
Node(int v = 0, int n = 1) : val(v), cnt(n), left(NULL), right(NULL)
{
}
};
Node * insert_bst(Node * root, int v)
{
if(NULL == root) {
Node * r = new Node(v);
return r;
}
Node * cur = root;
while(cur) {
if(cur->val == v) {
cur->cnt ++;
break;
}
else if(cur->val < v) {
if(NULL == cur->right) {
cur->right = new Node(v);
break;
}
cur = cur->right;
}
else {
if(NULL == cur->left) {
cur->left = new Node(v);
break;
}
cur = cur->left;
}
}
return root;
}
int run()
{
///int A[] = {1, 3, 5, 2, 2, 2};
///int A[] = {2, 1, 3, 5, 2, 2};
int A[] = {2, 1, 2, 3, 2, 5};
int more = A[0];
for(int i = 1; i < sizeof(A)/sizeof(A[0]); i ++)
{
if((A[i] == more) || (A[i] == A[0])) {printf("X number is : %d\n", A[i]); break;}
else more = A[i];
}
return 0;
}
/// Assume Result is : a1a2a3...an
/// Satisfy the condition: a1a2a3...an , a2a3a4....ana1, ...., ana1a2....an-1 Not Match Any
/// anan-1...a1, ..., a1anan-1...a2
/// Using BruteForce
int shift(int m[], int n)
{
int t = m[0];
for(int i = 0; i < n - 1; i ++) m[i] = m[i + 1];
m[n - 1] = t;
return 0;
}
bool equal_arr(int a[], int b[], int n)
{
int i = 0;
for(i = 0; i < n; i ++) if(a[i] != b[i]) break;
return (i == n);
}
bool is_match(int a[], int b[], int n)
{
bool ok = true;
for(int i = 0; i < n; i ++)
{
shift(a, n);
for(int j = 0; j < n; j ++)
{
shift(b, n);
if(equal_arr(a, b, n)) {ok = false; break;}
}
if(!ok) break;
}
return ok;
}
int gen_arr(int a[], int x)
{
for(int i = 0; i < 32; i ++)
{
a[i] = (x & (1 << i)) ? 1 : 0;
}
return 0;
}
int run()
{
int a[100], b[100];
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
int N = 3;
bool ok = false;
while(1)
{
if(N > 100) break;
int x = (1 << N) - 1;
for(int i = 0; i <= x; i ++)
{
gen_arr(a, i);
for(int j = 0; j < N; j ++) b[j] = a[N - j - 1];
if(is_match(a, b, N)) {
ok = true; break;
}
if(ok) break;
}
if(ok) break;
N ++;
}
for(int i = 0; i < N; i ++) {
printf("%c ", a[i] ? 'B' : 'W');
}
printf("\n");
return 0;
}
int next(int k)
{
/// 1.0 low bit -> high bit find patern 01 in m'th bits
/// 2.0 change patern 01 -> 10
/// 3.0 set bits 0 -> m-1 to 0......1 (0 bit before 1 bit)
int cnt = 0, res = 0;
for(int i = 0; i < 31; i ++) {
int m1 = (k & (1 << i)) ? 1 : 0;
int m2 = (k & (1 << (i + 1))) ? 1 : 0;
if((m1 == 1) && (m2 == 0)) {
if(i<=29) res = k & ~((1 << (i + 2)) - 1); ///< set i+2 -> 31
else res = 0;
res |= 1 << (i + 1); ///< set i+1 and i (10)
res |= (1 << cnt) - 1; ///< set 0 -> i - 1
break;
}
if(m1 == 1) cnt ++;
}
return res;
}
/// Using BitMap
#define SET_BIT(m, k) (m[k/8] |= (1 << (k % 8)))
#define IS_BIT_SET(m, k) (m[k/8] & (1 << (k % 8)))
#define CLR_BIT(m, k) (m[k/8] ^= (1 << (k % 8)))
int run()
{
const int ARRAY_SIZE = 1000;
int A[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i ++) A[i] = i + 1;
A[3] = 1; /// A[3] = 4, before
char * m = new char[ARRAY_SIZE/8 + 1];
memset(m, 0, ARRAY_SIZE/8 + 1);
for(int i = 0; i < ARRAY_SIZE; i ++) {
SET_BIT(m, A[i]);
}
for(int i = 1; i <= ARRAY_SIZE; i ++) {
if(IS_BIT_SET(m, i) == 0) printf("%d is missing\n", i);
}
delete [] m;
m = NULL;
return 0;
}
int run()
{
int A[] = {4, 2, 5, 8, 1, 7, 9, 4, 6};
int N = sizeof(A) / sizeof(A[0]) - 1;
print_v(A, sizeof(A) / sizeof(A[0]));
for(int i = 0; i <= N; i ++) {
if(f(A[i])) continue;
else {int t = A[i]; A[i] = A[N]; A[N] = t; N --; i --;}
}
print_v(A, sizeof(A) / sizeof(A[0]));
return 0;
}
int run()
{
int A[] = {4, 2, 5, 8, 1, 7, 9, 4, 6};
int N = sizeof(A) / sizeof(A[0]) - 1;
print_v(A, sizeof(A) / sizeof(A[0]));
for(int i = 0; i <= N; i ++) {
if(f(A[i])) continue;
else {int t = A[i]; A[i] = A[N]; A[N] = t; N --; i --;}
}
print_v(A, sizeof(A) / sizeof(A[0]));
return 0;
}
/// Using DP
/// m[i+1][j] = 1 /// IF m[i][j-A[i+1]] = 1
/// m[i+1][j] = 0; /// IF m[i][j-A[i+1]] = 1
/// Time Complexity O(N * S) Space Complexity O(S)
int run()
{
///int A[] = {12, 4, 7, 1, 6, 3, 3};
///int A[] = {12, 100};
int A[] = {3, 3, 2, 2, 2};
int s = 0;
for(int i = 0; i < sizeof(A) / sizeof(A[0]); i ++) {
s += A[i];
}
print_v(A, sizeof(A) / sizeof(A[0]));
int m[s/2 + 1];
memset(m, 0, sizeof(m));
for(int i = 0; i < sizeof(A) / sizeof(A[0]); i ++) {
for(int k = s/2; k >= 0; k --) {
if(m[k] && (k + A[i] < s/2 + 1)) m[k + A[i]] = 1;
}
m[A[i]] = 1;
///print_v(m, s/2 + 1);
}
int i = 0;
for(i = s/2; i >= 0; i --) {
if(m[i]) break;
}
printf("s : %d i : %d\n", s, i);
return 0;
}
/// Using Dynamic Programming
/// t[ix][iy] = map[ix-1][iy-1] + max(t[ix-1][iy], t[ix-1][iy])
inline int max(int a, int b)
{
return (a < b) ? b : a;
}
int apple_collect()
{
int map[4][4] = {
{10, 9, 1, 2},
{3, 4, 3, 4},
{1, 2, 5, 8},
{8, 2, 3, 5}
};
int t[5][5];
memset(t, 0, sizeof(t));
int ix = 0, iy = 0;
for(ix = 1; ix <= 4; ix ++)
{
for(iy = 1; iy <= 4; iy ++)
{
int mx = max(t[ix-1][iy], t[ix][iy-1]);
mx += map[ix-1][iy-1];
t[ix][iy] = mx;
}
}
return t[4][4];
}
#include <iostream>
#include <vector>
using namespace std;
template <class VT>
class Stack
{
public:
Stack()
{
}
~Stack()
{
}
VT top()
{
if(size() > 0) return list_[size() - 1];
else return 0;
}
int push(VT v)
{
list_.push_back(v);
return 0;
}
void pop()
{
if(size() > 0) list_.pop_back();
}
int size()
{
return list_.size();
}
private:
vector<VT> list_;
};
/// Using a temp stack to reverse_stack
void reverse_stack(Stack<int> & stack)
{
if(stack.size() == 0) return;
int size = stack.size();
int top_v = 0;
Stack<int> stack_x;
while(size)
{
top_v = stack.top();
stack.pop();
int step = size - 1;
while(step)
{
stack_x.push(stack.top());
stack.pop();
step --;
}
stack.push(top_v);
while(stack_x.size())
{
stack.push(stack_x.top());
stack_x.pop();
}
size --;
}
}
/// Using 2 stacks to reverse stack
void reverse_stack_2(Stack<int> & stack)
{
Stack<int> stack_x, stack_y;
while(stack.size())
{
stack_x.push(stack.top());
stack.pop();
}
while(stack_x.size())
{
stack_y.push(stack_x.top());
stack_x.pop();
}
while(stack_y.size())
{
stack.push(stack_y.top());
stack_y.pop();
}
}
The substring of the given string matchs below numbers
0 0 1 -- a
0 1 0 -- b
0 1 1 -- ab
1 0 0 -- c
1 0 1 -- ac
1 1 0 -- bc
1 1 1 -- abc
/// C++ code below
void print(char * str, int s)
{
int one = 1;
int i = 0, len = strlen(str);
for(i = 0; i < len; i ++)
{
if(s & (one << i)) cout<<str[i];
}
cout<<endl;
}
int generate_substring(char * str)
{
if(NULL == str) return -1;
int s = 1, len = strlen(str);
while(len)
{
s *= 2;
len --;
}
s -= 1;
while(s)
{
print(str, s);
s --;
}
return 0;
}
Using Dynamic Programing
m[i][j] meas s[i..j] is palindrome
1. m[j-1][j] = 1, if s[j] = s[j-1]
2. m[j-2][j] = 1, if s[j] = s[j-2]
3. m[k][j] = 1(k < j-2), if m[k+1][j-1] && s[k] == s[j]
Time O(n*n), Space O(n*n);
void solve()
{
string s1 = "abbcacbca";
int m[MAX_SIZE][MAX_SIZE];
memset(m, 0, sizeof(m));
int i = 0, j = 0;
for(i = 1; i < s1.size(); i++)
{
if(s1[i] == s1[i-1])
{
m[i-1][i] = 1;
print(s1, i-1, i);
}
else if((i-2 >= 0) && (s1[i] == s1[i-2]))
{
m[i-2][i] = 1;
print(s1, i-2, i);
}
for(j=i-2; j>=0; j --)
{
if(!m[j][i-1]) continue;
if((j>=1) && (s1[j-1] == s1[i]))
{
if(!m[j][i])
{
m[j][i]= 1;
print(s1, j-1, i);
}
}
}
}
for(i=0; i<s1.size(); i++)
{
for(j=0; j<s1.size(); j++)
cout<<m[i][j]<<" ";
cout<<endl;
}
}
/// -- Time Complexity is O(2*max(n,m)), where n is size of root1, and m is size of root2, let me know of any errors.
void inorder(struct node * root, int min, int max)
{
if(root == NULL) return;
inorder(root->left, min, max);
if((min <= root->val) && (root->val <=max))cout<<root->val<<" ";
inorder(root->right, min, max);
}
void print(struct node * root1, struct node * root2, int min, int max)
{
if((root1 == NULL) && (root2 == NULL)) return ;
if(root1 != NULL && root2 == NULL) {inorder(root1, min, max); return ;}
if(root2 != NULL && root1 == NULL) {inorder(root2, min, max); return ;}
if(root1->val < root2->val)
{
print(root1->left, root2, min, root1->val);
if((root1->val >= min) && (root1->val <= max)) cout<<root1->val<<" ";
print(root1->right, root2, root1->val, max);
}
else
{
print(root2->left, root1, min, root2->val);
if((root2->val >= min) && (root2->val <= max)) cout<<root2->val<<" ";
print(root2->right, root1, root2->val, max);
}
}
Time(n2), Space(n2)
----------------------------------------
int f(int n, int k)
{
int f[100][100] = {{0}};
f[0][0] = f[1][1] = 1;
int i = 0, j = 0;
for(i = 0; i < 100; i++) f[i][0] = 1;
for(i = 1; i <= n; i ++)
{
for(j = 1; j <= k; j++)
{
if((i == j)) {continue;}
if((i == 2) && (j > 1)) {continue;}
if(i/2+1 < j) {continue;}
f[i][j] = f[i-2][j-1] + f[i-1][j];
}
}
return f[n][k];
}
// Using semaphone and mutex in AllowMany function and Using mutex in AllowOne function
void AllowMany() {
if(semaphore_count == 0) mutex.Acquire();
semaphore_count ++;
// Here is the critical section that must be protected
semaphore_count ++;
if(semaphore_count == 0) mutex.Release();
}
// Will lock out any client, including callers to the other method.
void AllowOne() {
mutex.Acquire();
// Here is the critical section that must be protected
mutex.Release();
}
Rephenryhokinsh, Android test engineer at ABC TECH SUPPORT
I’m Henry, I am Children's librarian in Rolling Thunder .My Work involves the responsibility for supervising the children ...
Repmarygaustria, Analyst at ADP
I am Mary from Los Angeles, USA. I am working as a Manager in Fragrant Flower Lawn Services company. I ...
Repkiyanshak, Associate at Adobe
I am a skilled software developer and have 5 years experience as a data coder operator. I have certain skills ...
/*
Given a string S, print the longest substring P such that P > S lexicographically.
You may assume that such substring exists.
Solution:
1. Scenario one.
There is a character which greater than the first character and all characters between first character and this character are equal to first character.
xxxxxyabcdefg return "xxxxyabcdefg"
2. Other scenario.
input string: "xxxbxxxaxxxc"
2.1 "....xxxaxxxc vs "xxxbxxxaxxxc"
2.2 "........xxxc" vs "xxxbxxxaxxxc". skip "....xxxa" subtring, and compare from "xxxc"
Time complexity O(n).
*/
- zombie April 18, 2016