yingsun1228
BAN USER- 1of 1 vote
AnswersGiven N arrays with sizeof N, and they are all sorted, if it does not allow you to use extra space, how will find their common datas efficiently or with less time complexity?
- yingsun1228 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
Answersthere are two arrays named A and B , both of them with k size, they are sorted in acsending order. could you find k-th smallest combinations of ai, bj -->(ai+bj) . 0<=i,j <k.
- yingsun1228 in United States
for example: a = {1, 3, 6} b = {4, 5, 6} then we will get 1 + 4 = 5, 1 + 5 = 6, and 1 + 6 = 7,the result is 5,6,7. does it make you understood? and could anybody do it with less time and space complexity.
Hi guys, thanks for all your suggestions and idea, and finally I get my answer and here are my c++ codes, time complexity is O(k*lgk), and space complexity is O(k):
#include<iostream>
using namespace std;
typedef struct node{
int row;
int col;
int data;
}Node, *PNode;
void swap(PNode &a, PNode &b) {
PNode temp = a;
a = b;
b = temp;
}
void adjust_min_heap(PNode *bin, int i, int k) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int min_index;
if(left < k && bin[left]->data < bin[i]->data) {
min_index = left;
} else {
min_index = i;
}
if(right < k && bin[right]->data < bin[min_index]->data) {
min_index = right;
}
if(min_index != i) {
swap(bin[i], bin[min_index]);
adjust_min_heap(bin, min_index, k);
}
}
void build_min_heap(PNode *bin, int k) {
for(int i = k / 2; i >= 0; i--) {
adjust_min_heap(bin, i, k);
}
}
int *get_k_th_minimum(int *a, int *b, int k) {
PNode *bin = (PNode*)malloc(sizeof(PNode) * k);
int *result = (int*)malloc(sizeof(int) * k);
memset(result, 0, sizeof(int) * k);
int i;
int count = 0;
for(i = 0; i < k; i++) {
bin[i] = (Node*)malloc(sizeof(Node));
bin[i]->row = i;
bin[i]->col = 0;
bin[i]->data = a[i] + b[0];
}
build_min_heap(bin, k);
while(count < k) {
result[count++] = bin[0]->data;
bin[0]->col += 1;
bin[0]->data = a[bin[0]->row] + b[bin[0]->col];
adjust_min_heap(bin, 0, k);
}
for(i = 0; i < k; i++) {
free(bin[i]);
}
free(bin);
return result;
}
void main() {
int a[] = {1, 2, 4};
int b[] = {5, 9, 11};
int k = 3;
int *p = get_k_th_minimum(a, b, k);
for(int i = 0; i < k; i++) {
cout << p[i] << " ";
}
free(p);
getchar();
}| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm
thanks for your coding, well done.
- yingsun1228 December 18, 2014great idea, thanks.
- yingsun1228 December 18, 2014This is my resolution and I shall explain why i use nextChar to solve this situation: abc, when I use sprintf, the point b will be replaced by '\0', so the while will terminated, so I need record this char.
#include<string>
#include<iostream>
using namespace std;
void compressStr(char* pStr) {
int count;
char* p = pStr;
char* pNewStr = pStr;
char temp, nextChar;
while (*p) {
count = 0;
temp = *p;
while (*p == temp) {
count++;
p++;
}
nextChar = *p;
if (count > 1) {
sprintf(pNewStr, "%d%c", count, temp);
} else {
sprintf(pNewStr, "%c", temp);
}
pNewStr += strlen(pNewStr);
*pNewStr = nextChar;
}
}
int main(int argc, char* argv[]) {
char str[] = "aaabbbcccd";
compressStr(str);
cout << str << endl;
cin.get();
return 0;
}
This is my resolution, and it takes only one iteration.
#include<string>
#include<iostream>
using namespace std;
void moveSpaceToStart(char* pStr) {
int length = strlen(pStr);
int count = length - 1;
int i = length - 1;
while (i >= 0) {
if (' ' != pStr[i])
pStr[count--] = pStr[i];
i--;
}
while (count >= 0) {
pStr[count--] = ' ';
}
}
int main(int argc, char* argv[]) {
char str[] = "this is a test.";
moveSpaceToStart(str);
cout << str << endl;
cin.get();
return 0;
}
I think this is simple, just use the defination of bst that the data of the root is smaller than the data stored in its left child if there is left child, and the same the data store in its rigth child is larger than the data of root, then check this recursively and finally you will get the result, here are my codes, if there is anything wrong, please let me know, thank you!
#include<iostream>
using namespace std;
typedef struct tree_node_s {
int data;
struct tree_node_s* lchild;
struct tree_node_s* rchild;
}tree_node_t;
tree_node_t* createNode(int data) {
tree_node_t* node = (tree_node_t*)malloc(sizeof(tree_node_t));
node->data = data;
node->lchild = NULL;
node->rchild = NULL;
return node;
}
bool isBST(tree_node_t* root) {
if (NULL == root)
return true;
bool left = true;
bool right = true;
if (root->lchild) {
if (root->data > root->lchild->data) {
left &= isBST(root->lchild);
} else {
return false;
}
}
if (root->rchild) {
if (root->data < root->rchild->data) {
right &= isBST(root->rchild);
} else {
return false;
}
}
return left & right;
}
int main(int argc, char* argv[]) {
tree_node_t* root = createNode(10);
root->lchild = createNode(7);
root->rchild = createNode(19);
root->lchild->lchild = createNode(4);
root->lchild->rchild = createNode(8);
root->rchild->lchild = createNode(13);
root->rchild->rchild = createNode(21);
if (isBST(root))
cout << "yes" << endl;
else
cout << "non" << endl;
cin.get();
return 0;
}
Good solution, I support that you can traverse both trees at the same time, and it should be synchronism, if the trees are same, at every steps, the value are equal, else they are not same.
- yingsun1228 June 18, 2013I think this can be done in linear time, we keep two pointers: one is slow and the other is fast, slow move forward one step and fast move forward two steps, then when fast is null or fast->next is null, slow points to the middle node of the list, at the same time, we use stack to keep nodes the slow has ever pointed to. Then move to slow to next, and compare the top value of stack with the value slow points to until slow is null or stack is empty. here are my codes:
#include<iostream>
#include<stack>
#include<string>
using namespace std;
typedef struct node_s {
char val;
struct node_s* next;
}node_t;
node_t* createList(char* s) {
node_t* head = NULL;
node_t* temp = NULL;
node_t* p = NULL;
while (*s) {
p = (node_t*)malloc(sizeof(node_t));
p->val = *s;
p->next = NULL;
if (NULL == head) {
head = p;
} else {
temp->next = p;
}
temp = p;
s++;
}
return head;
}
void destroyList(node_t* head) {
node_t* p = head;
while (p) {
head = p->next;
free(p);
p = head;
}
}
bool isPalindrome(node_t* head) {
stack<node_t*> m_stack;
node_t* slow = head;
node_t* fast = head;
m_stack.push(slow);
while (fast->next && fast->next->next) {
slow = slow->next;
m_stack.push(slow);
fast = fast->next;
fast = fast->next;
if (NULL == fast->next)
m_stack.pop();
}
slow = slow->next;
node_t* temp = NULL;
while (slow && !m_stack.empty()) {
temp = m_stack.top();
m_stack.pop();
if (slow->val != temp->val)
return false;
slow = slow->next;
}
if (slow || !m_stack.empty())
return false;
return true;
}
int main(int argc, char* argv[]) {
char s[] = "12345678987654321";
node_t* head = createList(s);
if (isPalindrome(head))
cout << "yes" << endl;
else
cout << "non" << endl;
destroyList(head);
cin.get();
return 0;
}
@kumarreddy72, first thanks for your reminding, and I changed my program above, you can test it in any cases.
- yingsun1228 June 09, 2013Thanks, and I get that.
- yingsun1228 June 09, 2013A very nice solution!
- yingsun1228 June 09, 2013I think this problem can be solved without using recursive and within linear time. This problem is same as the problem that a given binary tree is whether a complete binary tree or not. we can do level traversal of the binary tree, and before traverse a level we compute the expected nodes than we visit at current level by the level previous, that means double the count of nodes of previous level, then when we visit current level and keep a count. After traverse current level, we compare current nodes count and expected, if they are equal,then we set expected = count * 2, then do traverse of next level. Here is my code:
#include<iostream>
#include<vector>
using namespace std;
typedef struct tree_node_s {
int value;
struct tree_node_s* lchild;
struct tree_node_s* rchild;
}tree_node_t;
tree_node_t* createNode(int value) {
tree_node_t* node = (tree_node_t*)malloc(sizeof(tree_node_t));
node->value = value;
node->lchild = NULL;
node->rchild = NULL;
return node;
}
bool is_complete_bin_tree(tree_node_t* root) {
int cur = 0;
int last = 0;
int count = 0;
int node_has_child = 0;
int node_non_child = 0;
int expected = 0;
if (NULL == root)
return true;
vector<tree_node_t*> vec;
tree_node_t* node = NULL;
vec.push_back(root);
while (cur < vec.size()) {
last = vec.size();
count = 0;
node_has_child = 0;
node_non_child = 0;
while (cur < last) {
node = vec[cur];
cout << node->value << " ";
cur++;
count++;
if (node->lchild || node->rchild) {
node_has_child++;
} else {
node_non_child++;
}
if (node->lchild)
vec.push_back(node->lchild);
if (node->rchild)
vec.push_back(node->rchild);
}
if (node_non_child > 0 && node_non_child < count)
return false;
cout << endl;
if (count >= expected) {
expected = node_has_child;
} else {
return false;
}
}
return true;
}
int main(int argc, char* argv[]) {
tree_node_t* root = createNode(1);
root->lchild = createNode(2);
root->rchild = createNode(3);
root->lchild->lchild = createNode(4);
root->lchild->rchild = createNode(5);
root->rchild->lchild = createNode(6);
root->rchild->rchild = createNode(7);
if (is_complete_bin_tree(root))
cout << "yes" << endl;
else
cout << "non" << endl;
cin.get();
return 0;
}
#include<iostream>
using namespace std;
/*
How to check if a binary tree is a binary search tree
*/
typedef struct node_s {
int value;
struct node_s *left;
struct node_s *right;
}BSTNode, *BSTree;
int tree_search(BSTree T, int value, BSTNode **p, BSTNode *f) {
if(!T) {
*p = f;
return 0;
} else {
if(T->value == value) {
*p = T;
return 1;
} else if(value < T->value) {
return tree_search(T->left, value, p, T);
} else {
return tree_search(T->right, value, p, T);
}
}
}
int tree_insert(BSTree *T, int value) {
BSTNode *p = NULL;
if(!tree_search(*T, value, &p, NULL)) {
BSTNode *s = (BSTNode*)malloc(sizeof(BSTNode));
s->value = value;
s->left = NULL;
s->right = NULL;
if(!(*T))
*T = s;
else if(value < p->value)
p->left = s;
else
p->right = s;
return 1;
}
return 0;
}
bool is_bst = true;
void check_tree_is_bst(BSTree T) {
if(T) {
check_tree_is_bst(T->left);
if(T->left) {
if(T->left->value > T->value) {
is_bst = false;
return;
}
}
if(T->right) {
if(T->right->value < T->value) {
is_bst = false;
return;
}
}
check_tree_is_bst(T->right);
}
}
int main(int argc, char *argv[]) {
int a[] = {5, 9, 13, 4, 6, 7, 34, 12, 25, 16};
int len = sizeof(a) / sizeof(int);
int i;
BSTree T = NULL;
for(i = 0; i < len; i++)
tree_insert(&T, a[i]);
check_tree_is_bst(T);
if(is_bst)
cout << "yes" << endl;
else
cout << "no" << endl;
return 0;
}
I use kmp to make it, and I think first you should compute the length of target like 'BC' and then length of repalce strings like 'U', 'UV', 'UVW' and compare them to decide when find the target string, whether copy the string forward or backword, here is my program, time complexity is near to O(n) and space complexity is using by kmp of O(targe), and there is anything wrong, please let me know, thanks.
#include<iostream>
using namespace std;
/*
In an interview I was asked a question on strings. The problem is given a string s1= "ABCDBCCDABCD".
and a pattern "BC". we have to replace this pattern with other string ("UVW" or "U"or "uv").
Do this without creating new string.
Take the case to replace "BC" with following
a) "uvw" s1=AUVWDUVWCDAUVWD .
b) "U" s1=AUDUCDAUD .
c) "UV" s1=AUVDUVCDAUVD
*/
void get_next(char *p, int len, int *next) {
int j = -1;
int i = 0;
next[i] = -1;
while(i < len - 1) {
if(j == -1 || p[i] == p[j]) {
++i;
++j;
if(p[i] != p[j])
next[i] = j;
else
next[i] = next[j];
} else {
j = -1;
}
}
}
char *kmp_search(char *src, char *pattern) {
int i = 0;
int j = 0;
int len_s = strlen(src);
int len_p = strlen(pattern);
int *next = (int*)malloc(sizeof(int) * len_p);
memset(next, 0, sizeof(int) * len_p);
get_next(pattern, len_p, next);
while(i < len_s && j < len_p) {
if(j == -1 || src[i] == pattern[j]) {
++i;
++j;
} else {
j = next[j];
}
}
free(next);
if(j >= len_p)
return src + i - len_p;
else
return NULL;
}
void string_replacement(char *src, char *target, char *replace) {
int direction = 0; // move forward or backward: 0 for forward, 1 for backward
int move_len = 0;
char *p = NULL;
int len_t = strlen(target);
int len_r = strlen(replace);
char *temp_old = NULL;
char *temp_new = NULL;
char *temp = NULL;
if(!src || !target || !replace) {
cout << "check input" << endl;
return;
}
if(len_r > len_t)
direction = 1;
p = kmp_search(src, target);
while(p) {
temp = replace;
move_len = strlen(src) - (p - src) - len_t;
temp_old = p + len_t;
temp_new = p + len_r;
if(direction) {
while(move_len > 0) {
*(temp_new + move_len - 1) = *(temp_old +move_len - 1);
move_len--;
}
} else {
while(*temp_old)
*temp_new++ = *temp_old++;
*temp_new = '\0';
}
while(*temp)
*p++ = *temp++;
p = strstr(src, target);
}
}
int main(int argc, char *argv[]) {
char src[30] = "ABCDBCCDABCD";
char target[] = "BC";
char replace[] = "U";
string_replacement(src, target, replace);
cout << src << endl;
cin.get();
return 0;
}
I have an O(n) solution, please check the answer of mine below. I am using kmp search, more faster than you said.
- yingsun1228 March 24, 2013I think this time complexity is O(M * avg_len(word)), M this the num of words and space complexity maybe a constant value for O(26) or O(52).I also solve this problem by myself using hash map. My idea is that first compute the count of appearance of every alpha in the set by hash mapping, then keep a temp length value: temp_len and temp pointer to record the longest word and its pointer at present, then to every word do like this, and finally we will get the answer we want:
#include<iostream>
using namespace std;
char *get_longest_str(char *set, char *str[], int n) {
int set_len = strlen(set);
int hash[26];
int i, j;
int final_len = 0;
int temp_len = 0;
char *ret = NULL;
for(i = 0; i < n; i++) {
memset(hash, 0, sizeof(int) * 26);
for(j = 0; j < set_len; j++)
hash[set[j] - 'a']++;
temp_len = strlen(str[i]);
for(j = 0; j < temp_len; j++)
hash[str[i][j] - 'a']--;
for(j = 0; j < 26; j++) {
if(hash[j] < 0)
break;
}
if(j >= 26) {
if(temp_len > final_len) {
final_len = temp_len;
ret = str[i];
}
}
}
return ret;
}
int main(int argc, char *argv[]) {
char *str[] = {"abacus", "deltoid", "gaff", "giraffe", "microphone", "reef", "qar"};
char set[] = {'a', 'e', 'f', 'f', 'g', 'i', 'r', 'q'};
int n = sizeof(str) / sizeof(char*);
char *ret = get_longest_str(set, str, n);
cout << ret << endl;
cin.get();
return 0;
}
I also support that O(lgn) solution is not existing, but I try O(k) algorithm and I think I made it, here is my program in c, if there is anything wrong, please let me know about, thanks.
#include<iostream>
using namespace std;
typedef struct node_s {
int value;
struct node_s *left;
struct node_s *right;
}BSTNode, *BSTree;
static int tree_size = 0;
int tree_search(BSTree T, int value, BSTNode **p, BSTNode *f) {
if(!T) {
*p = f;
return 0;
} else {
if(T->value == value) {
*p = T;
return 1;
} else if(value < T->value) {
return tree_search(T->left, value, p, T);
} else {
return tree_search(T->right, value, p, T);
}
}
}
int tree_insert(BSTree *T, int value) {
BSTNode *p = NULL;
if(!tree_search(*T, value, &p, NULL)) {
BSTNode *s = (BSTNode*)malloc(sizeof(BSTNode));
s->value = value;
s->left = NULL;
s->right = NULL;
if(!(*T))
*T = s;
else if(value < p->value)
p->left = s;
else
p->right = s;
return 1;
}
return 0;
}
static int index = 0;
void find_k_th(BSTree T, int k, int *value) {
if(T) {
find_k_th(T->left, k, value);
++index;
if(index == k) {
*value = T->value;
return;
}
find_k_th(T->right, k, value);
}
}
int get_value(BSTree T, int k) {
int k_value = -1;
if(k < 0 || k >= tree_size)
return k_value;
index = 0;
find_k_th(T, k, &k_value);
return k_value;
}
void in_traverse(BSTree T) {
if(T) {
in_traverse(T->left);
cout << T->value << " ";
in_traverse(T->right);
}
}
int main(int argc, char *argv[]) {
int a[] = {5, 9, 13, 4, 6, 7, 34, 12, 25, 16};
int len = sizeof(a) / sizeof(int);
int i;
BSTree T = NULL;
for(i = 0; i < len; i++) {
if(tree_insert(&T, a[i]))
tree_size++;
}
in_traverse(T);
cout << endl;
int k = 4;
cout << get_value(T, k) << endl;
cin.get();
return 0;
}
reverse the second string and use kmp search will be better. and also we can use suffix tree or suffix array, but they are too complicated. here is my program, and it will take O(n) time complexity(n: the length of first string) and O(m) space complexity(m: the length of second string):
#include<iostream>
#include<string>
using namespace std;
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void reverse(char *p_start, char *p_end) {
while(p_start < p_end) {
swap(p_start, p_end);
p_start++;
p_end--;
}
}
void get_next(char *p, int len, int *next) {
int j = -1;
int i = 0;
next[i] = -1;
while(i < len - 1) {
if(j == -1 || p[i] == p[j]) {
++i;
++j;
if(p[i] != p[j])
next[i] = j;
else
next[i] = next[j];
} else {
j = next[j];
}
}
}
char *kmp_search(char *s, int s_len, char *p, int p_len) {
if(NULL == s || NULL == p || 0 == s_len || 0 == p_len)
return NULL;
int *next = (int*)malloc(sizeof(int) * p_len);
memset(next, 0, sizeof(int) * p_len);
get_next(p, p_len, next);
int i = 0;
int j = 0;
while(i < s_len && j < p_len) {
if(j == -1 || s[i] == p[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if(next)
free(next);
if(j >= p_len)
return s + i - p_len;
else
return NULL;
}
int is_contain_permutation(char *s, char *d) {
if(NULL == s || NULL == d)
return 0;
int s_len = strlen(s);
int d_len = strlen(d);
char *temp = (char*)malloc(d_len + 1);
strcpy(temp, d);
reverse(temp, temp + d_len - 1);
char *ret = kmp_search(s, s_len, temp, d_len);
if(temp)
free(temp);
if(ret)
return 1;
else
return 0;
}
int main(int argc, char *argv[]) {
char s[] = "abcdefg";
char d[] = "ba";
is_contain_permutation(s, d);
cin.get();
return 0;
}
I can give you a O(n) solution and I will explain why I do like this later:
#include<stdio.h>
int find_dest_num(int *a, int len) {
int i;
int temp = a[0];
int count = 1;
for(i = 1; i < len; i++) {
if(temp == a[i]) {
count++;
} else {
count--;
if(count == 0) {
temp = a[i];
count = 1;
}
}
}
count = 0;
for(i = 0; i < len; i++) {
if(a[i] == temp)
count++;
}
if(count * 2 > len)
return temp;
else
return -1;
}
int main(int argc, char *argv[]) {
int a[] = {2, 2, 2, 3, 3, 3, 1, 3, 3};
int len = sizeof(a) / sizeof(int);
find_dest_num(a, len);
}
I think void pointer can be cast to any other type of pointers, like that if you want to implement a stack in c code to store any type of data,
struct stack_s{
int size;
void **table;
int top;
} if you use int* then you can only store int datas, but if you use void* you can store any type of datas.
then take a look at unsigned int, do you think if we balance the size of a vector or other thing will use negative, or a vector's size is negative, so it obviously tells us that unsigned int can represent the size.
mark...
- yingsun1228 February 05, 2013@Bin, it is also a very grateful idea. And can you put your codes here, and we can analysis your idea clearly.
- yingsun1228 January 29, 2013A very good solution.
- yingsun1228 January 28, 2013I'd like to change the wrong idea rooted deeply in your mind, I think you intended to use hashset, not hash map, and you think that if you use hash set, then the complexity will decreased, no, the implementation of hash set is including rb-tree, and the search time complexity of rb-tree is O(lgn), so the time complexity is also O(n*lgn). There is no algorithm of O(n) at all. And using hash set just can save your time and bring you convenience.
- yingsun1228 January 28, 2013I think the matrix can be split into levels, such as 1, 2, 3,
4, 5, 6,
7, 8, 9,
we can takes it as two levels: 1, 2, 3, 6, 9, 8, 7, 4 and 5 respetively. and print in level, here are my codes, there is no need extra space and time complexicity is O(n*n), or O(n).
#include<iostream>
using namespace std;
const int n = 5;
int a[n][n] = {1, 2, 3, 4, 5, 16, 17, 18, 19, 6, 15, 24, 25, 20, 7, 14, 23, 22, 21, 8, 13, 12, 11, 10, 9};
void spiral_traverse() {
int level;
int i;
for(level = 1; level <= n / 2; level++) {
for(i = level - 1; i < n - level; i++) {
cout << a[level - 1][i] << " ";
}
for(i = level - 1; i < n - level; i++) {
cout << a[i][n - level] << " ";
}
for(i = n - level; i >= level; i--) {
cout << a[n - level][i] << " ";
}
for(i = n - level; i >= level; i--) {
cout << a[i][level - 1] << " ";
}
}
if(n % 2 == 1) {
cout << a[n / 2][n / 2];
}
cout << endl;
}
void main() {
spiral_traverse();
getchar();
}
I have three methods, first, if we can use extra space we can use sprintf to convert int to string to judge whether this int is a palindrome. Second, we use / operator to reverse the int and judge whether the reversed number and the raw number are equal. Third, I will give you my program here. A very important point is that the second method maybe cause overflow.
#include<stdio.h>
#include<string.h>
int auxiliary(char *p_start, char *p_end) {
while(p_start < p_end) {
if(*p_start != *p_end) {
break;
}
p_start++;
p_end--;
}
if(p_start >= p_end) {
return 1;
} else {
return 0;
}
}
int is_palindrome1(int n) {
char s[10] = {'\0'};
sprintf(s, "%d", n);
int len = strlen(s);
char *p_start = s;
char *p_end = s + len - 1;
if(auxiliary(p_start, p_end)) {
return 1;
} else {
return 0;
}
}
int is_palindrome2(int n) {
int value = 0;
int temp = n;
while(temp) {
value = value * 10 + temp % 10;
temp /= 10;
}
if(value == n) {
return 1;
} else {
return 0;
}
}
int is_palindrome3(int n) {
int div = 1;
int temp = n;
int first, last;
while(temp >= 10) {
div *= 10;
temp /= 10;
}
while(n) {
first = n / div;
last = n % 10;
if(first != last) {
break;
}
n = (n % div) / 10;
div /= 100;
}
if(n == 0) {
return 1;
} else {
return 0;
}
}
void main() {
int n = 12344321;
if(is_palindrome3(n)) {
printf("yes\n");
} else {
printf("no\n");
}
getchar();
}
use sprintf to convert int to string, then reverse the string , and use sscanf to convert string to int. using duoble pointers to reverse.
- yingsun1228 January 25, 2013I do like this: making a map array, which record all the alphas and digits relations. Then open file, and process every word with length of the length of given number, ignore others which can save a lot of time. below is my codes, time complexity is O(N), if the length of word can be taken as O(1), space complexity is O(1).
#include<iostream>
#include<string>
using namespace std;
int map[26];
void init_map() {
int i;
int value = 2;
for(i = 0; i < 15; i += 3) {
map[i] = map[i + 1] = map[i + 2] = value;
value++;
}
map[15] = map[16] = map[17] = map[18] = value++;
map[19] = map[20] = map[21] = value++;
map[22] = map[23] = map[24] = map[25] = value;
}
bool process_word(char *word, char *number) {
while(*word) {
if(map[*word - 'a'] != (*number - '0')) {
return false;
}
word++;
number++;
}
return true;
}
void find_all_valid_words(char *file_path, char *number) {
char buffer[20];
int len_num = strlen(number);
FILE *input = fopen(file_path, "r");
init_map();
while(fscanf(input, "%s", buffer) != EOF) {
if(strlen(buffer) == len_num) {
if(process_word(buffer, number)) {
cout << buffer << endl;
}
}
}
}
void main() {
char number[] = "228";
char file_path[] = "words.txt";
find_all_valid_words(file_path, number);
getchar();
}
and here the test case:
bat cat act bus cut just take make bad pass typical
to decrease the space complexity.
- yingsun1228 January 22, 2013first, I think you should sort these two list in max(O(nlogn), O(mlogm)) time, then traverse two lists to check their common data and store them in a new array or list in O(m+n) time. so the time complexity is max(O(nlogn), O(mlogm)). later I will give my codes.
- yingsun1228 January 22, 2013@Hua, I agree your idea, it abvious a good choice to compare first two strings, and get their lcs, then use lcs to compare with next string. using dynamic programming, it really takes O(n) time complexity, but the space complexity is little more:O(n^2) .
- yingsun1228 January 22, 2013you are a genius。
- yingsun1228 January 21, 2013ternary search tree is a very goog choice.
- yingsun1228 January 21, 2013yes, you are right. And thanks, then I changed my code, this maybe work beterr.
#include<iostream>
#include<string>
using namespace std;
int is_contain(char *p_str, char *s_str) {
int repeat_count = 0;
int total_count = 0;
int count = 0;
int index = -1;
char first_letter;
int i = 0, j = 0;
int len_p = strlen(p_str);
int len_s = strlen(s_str);
first_letter = *s_str;
while(j < len_s) {
if(s_str[j] == first_letter) {
repeat_count++;
} else {
break;
}
j++;
}
j = 0;
while(j < len_s) {
if(s_str[j] == first_letter) {
total_count++;
}
j++;
}
while(i < len_p) {
if(p_str[i] == first_letter) {
count++;
if(count == (total_count - repeat_count)) {
index = i + 1;
break;
}
}
i++;
}
if(index == -1) {
return 0;
}
j = 0;
i = index;
while(i < len_p && j < len_s) {
if(p_str[i] != s_str[j]) {
return 0;
}
j++;
i = (i + 1) % len_p;
}
if(j == len_s) {
return 1;
} else {
return 0;
}
}
void main() {
char p_str[] = "password";
char s_str[] = "swordpas";
if(is_contain(p_str, s_str)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
getchar();
}
just as upstairs sayed, it works very well.
- yingsun1228 January 21, 2013can you paste your code here, thanks.
- yingsun1228 January 17, 2013ok, I know that, and I should add a new rule to my topic.
- yingsun1228 January 17, 2013if you turn it into c or c++, We will appreciate it very much.
- yingsun1228 January 17, 2013can you give us your codes? I did not quite understood what you mean.
- yingsun1228 January 17, 2013obviously not, because we want take all the strings to a circle, not only part of them.
- yingsun1228 January 17, 2013good idea, and I am very lazy, could you implement for us? so many people are eager to get a right solution.
- yingsun1228 January 17, 2013It is a very elegant idea, but if the array is not sorted, like this one:a[] = {9, 20, -2, 3, -45, 23, 5, 2,1}, you will get the wrong number. So, you should sort the given array first, then your idea will work better.
- yingsun1228 January 17, 2013that's nothing, and I am very grateful for you idea.
- yingsun1228 January 17, 2013thank you all the same.
- yingsun1228 January 17, 2013do you test it and what is the result: it works well?
- yingsun1228 January 16, 2013can you implement your idea for me? I am not quite understanding what you mean.
- yingsun1228 January 16, 2013thanks for your grateful idea, I am very grateful. I will implement your idea and let you know.
- yingsun1228 January 16, 2013how clever you are, I think these codes are better than me at upstairs. I am very grateful for your nice idea.
- yingsun1228 January 16, 2013I implement you idea by c++, only for using stack, and if it does not correspond to the form, you can use c implement a stack. here is the code:
#include<iostream>
#include<stack>
using namespace std;
typedef struct node{
int data;
struct node *next;
}LinkNode, *LinkList;
void create_list(LinkList *L, int *a, int n) {
int i = 0;
LinkNode *p = NULL;
LinkNode *temp = NULL;
while(i < n) {
p = (LinkNode*)malloc(sizeof(LinkNode));
p->data = a[i];
p->next = NULL;
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
i++;
}
}
int is_palindrome(LinkList head) {
int length = 0;
int mid = 0;
int i;
stack<LinkNode*> m_stack;
LinkNode *p = head;
LinkNode *temp = NULL;
int flag = 1;
while(p) {
length++;
p = p->next;
}
if(length %2 == 0) {
mid = length / 2;
} else {
mid = length / 2 + 1;
}
p = head;
i = 1;
while(i <= mid - 1) {
m_stack.push(p);
p = p->next;
i++;
}
if(length % 2 == 0) {
m_stack.push(p);
}
p = p->next;
while(!m_stack.empty() && p) {
temp = m_stack.top();
m_stack.pop();
if(temp->data != p->data) {
flag = 0;
break;
}
p = p->next;
}
return flag;
}
void main() {
int a[] = {1, 2, 3, 4, 5, 5, 4, 3, 2, 1};
int n = sizeof(a) / sizeof(int);
LinkList head = NULL;
create_list(&head, a, n);
if(is_palindrome(head)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
getchar();
}
this question has solutions now. and the time complexity is max(m*logm , n*logn). At first you should sort one of the array, then use a 'for' loop for the other array, using binary search, to every element, it will use logm or logn time. and the space complexity is o(1). And your question is the simple one, the other one is can you find all the common elements in two arrays.
- yingsun1228 January 16, 2013
and sorry for that there is a problem in your solution that traverse is not in the right
order, for root column it should output like 20, 3, 4, but yours is not, and I changed your code from inorder traverse to preorder traverse. here is the code
- yingsun1228 December 18, 2014