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 code and idea, but it will turn out to be wrong when a and b like this:a[] = {1, 3, 6}; b[] = {2, 5, 6};
- yingsun1228 January 16, 2013yes, thanks for your explanations, and i will try your idea.
- yingsun1228 January 16, 2013I am sorry for that when I first look at this question, I was very confused and thought it was funny, if you use windows of 32bits, then you always get 'error', because function 'rand()' only can generate number in range of 0-65535, and even two numbers generated bu rand() to be plused, the result will always be positive not negative.But if you use machines of 16bits. then the answer will changed.
- yingsun1228 January 16, 2013#include<stdio.h>
#include<string.h>
int is_rotation(char *s1, int len_1, char *s2, int len_2) {
int i, j;
int flag = 0;
i = 0;
while(i < len_1) {
if(s1[i] == s2[0]) {
break;
}
i++;
}
if(i >= len_1) { // not find the first character of s2 in s1
return 0;
}
j = 0;
while(i < len_1 && j < len_2) {
if(s1[i] != s2[j]) {
flag = 0;
break;
}
i = (i + 1) % len_1;
j++;
}
if(j == len_2) {
flag = 1;
}
return flag;
}
void main() {
char s1[] = "password";
char s2[] = "asswordp";
if(is_rotation(s1, strlen(s1), s2, strlen(s2))) {
printf("yes\n");
} else {
printf("no\n");
}
getchar();
}
a very nice solution, but it takes a lot of space, I can give you a O(1) space and linear time solution.
- yingsun1228 January 16, 2013#include<stdio.h>
#include<string.h>
char first_non_repeat(char *s) {
char *p = s;
char temp;
int count = 0;
char result;
while(*p) {
temp = *p;
count = 0;
while(*p == temp) {
p++;
count++;
}
if(count == 1) {
result = temp;
break;
}
}
if(count == 1) {
return temp;
} else {
return '\0';
}
}
void main() {
char s[] = "aabbbccccddeffffgg";
char result = first_non_repeat(s);
if(result) {
printf("%c\n", result);
} else {
printf("no.\n");
}
getchar();
}
I also think you make it wrong, saying as upstairs, your code will not always get the right answer. I have a suggestion than you can take another array order to record which one is turn up first. for example: order[26].
- yingsun1228 January 16, 2013thank you, you get the main idea and the right resolution, but the time of this solution is a little long. And sorry for that I have not got the best anwser yet and we both waiting for other people's idea. Thank you.
- yingsun1228 January 16, 2013no, you did not get the idea, sorry for my bad english, I mean the counts of conbination of ai+bj is k, not only one. k-th means the count is k.
- yingsun1228 January 16, 2013I change the expression, could help me to get this question.
- yingsun1228 January 16, 2013I use two queue to do this work. And it works well, because I take level traversal, so the time using is O(n).
#include<iostream>
#include<queue>
using namespace std;
typedef struct node{
int data;
struct node *left, *right;
}BTNode, *Tree;
#define NIL 0
int a[] = {1, 2, 4, 0, 0, 5, 0, 0, 3, 6, 0, 0, 7, 0, 0};
static int i = 0;
void pre_order_create(Tree &T) {
int num = a[i++];
if(num == NIL) {
T = NULL;
} else {
T = (BTNode*)malloc(sizeof(BTNode));
T->data = num;
pre_order_create(T->left);
pre_order_create(T->right);
}
}
calculate_diff(Tree T, int *odd_sum, int *even_sum) {
queue<BTNode*> *m_queue1 = new queue<BTNode*>();
queue<BTNode*> *m_queue2 = new queue<BTNode*>();
queue<BTNode*> *temp_queue;
BTNode *temp;
int level = 1;
int *sum;
m_queue1->push(T);
while(!m_queue1->empty()) {
if(level % 2 == 1) {
sum = odd_sum;
} else {
sum = even_sum;
}
while(m_queue1->size() > 0) {
temp = m_queue1->front();
(*sum) += temp->data;
if(temp->left) {
m_queue2->push(temp->left);
}
if(temp->right) {
m_queue2->push(temp->right);
}
m_queue1->pop();
}
level++;
temp_queue = m_queue1;
m_queue1 = m_queue2;
m_queue2 = temp_queue;
}
}
void main() {
Tree T = NULL;
pre_order_create(T);
int odd_sum = 0;
int even_sum = 0;
calculate_diff(T, &odd_sum, &even_sum);
cout << "odd_sum=" << odd_sum << ",even_sum=" << even_sum << endl;
getchar();
}
I can explain how this sentence works. u can take b and t as tuple, in this "select count(*) from book as t where t.price>b.price" we can get how many books's price is higher than t, including itself, then we will choose the book that there are less than five books' price higher than it. This is how this sentence works. I think it is b or t confused you, you can take it as a variable, and its value comes from sql table.
- yingsun1228 January 15, 2013Hi, the brother upstairs, I can help you resolve these cases:first, if all zero, return 1 as the missing minimum positive; second if all the numbers are negative, also return 1 as the missing minimum positive, third, if all the numbers are like this, in my opinion this topic will missing its raw intent and I think you have no need to consider this case.
- yingsun1228 January 15, 2013I write a simple program use c and the algorithm is from up comments
#include<stdio.h>
#include<string.h>
void remove_duplicate(char *str) {// assume all characters are little
char *p_slow = str;
char *p_fast = str;
int flag = 0;
int value;
int bits;
while(*p_fast) {
value = 1;
bits = *p_fast - 'a';
value = (value << bits);
if((flag & value) == value) {
p_fast++;
} else {
*p_slow++ = *p_fast++;
flag |= value;
}
}
*p_slow = '\0';
}
void main() {
char str[] = "abcddbcdefghijm";
remove_duplicate(str);
printf("%s\n", str);
getchar();
}
I should thank you give us so wonderful solution。
- yingsun1228 January 14, 2013I think I get a in-place sort algorithm, is anyone can help me check this methods, if it does not work well, please tell me, with my thanks.
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}LinkNode, *LinkList;
void create_list(int *a, int n, LinkList *L) {
int i;
LinkNode *temp, *p;
for(i = 0; i < n; i++) {
p = (LinkNode*)malloc(sizeof(LinkNode));
p->data = a[i];
p->next = NULL;
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
}
}
void resort_list(LinkList *L) {
LinkNode *p_second_start = NULL;
LinkNode *q = *L;
LinkNode *p = q->next;
LinkNode *temp = NULL;
int _is_fisrt = 0;
while(p != NULL && q->data <= p->data) {
q = p;
p = p->next;
}
if(p == NULL) {
return ;
}
p_second_start = p;
q->next = NULL; // turn a list to two list
p = *L;
*L = NULL;
q = p_second_start;
while(p != NULL && q != NULL) {
if(p->data <= q->data) {
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
p = p ->next;
} else {
if(*L == NULL) {
*L = q;
} else {
temp->next = q;
}
temp = q;
q = q->next;
}
}
if(p != NULL) {
temp->next = p;
}
if(q != NULL) {
temp->next = q;
}
}
void print_list(LinkList L) {
LinkNode *p = L;
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void main() {
LinkList L = NULL;
int a[] = {1, 5, 7, 9, 11, 2, 4, 6};
int n = sizeof(a) / sizeof(int);
create_list(a, n, &L);
print_list(L);
resort_list(&L);
print_list(L);
getchar();
}
yes, I do like this:
- yingsun1228 January 16, 2013#include<stdio.h>
#include<string.h>
int is_rotation(char *s1, int len_1, char *s2, int len_2) {
int i, j;
int flag = 0;
i = 0;
while(i < len_1) {
if(s1[i] == s2[0]) {
break;
}
i++;
}
if(i >= len_1) { // not find the first character of s2 in s1
return 0;
}
j = 0;
while(i < len_1 && j < len_2) {
if(s1[i] != s2[j]) {
flag = 0;
break;
}
i = (i + 1) % len_1;
j++;
}
if(j == len_2) {
flag = 1;
}
return flag;
}
void main() {
char s1[] = "password";
char s2[] = "asswordp";
if(is_rotation(s1, strlen(s1), s2, strlen(s2))) {
printf("yes\n");
} else {
printf("no\n");
}
}