N568
BAN USER- 0of 0 votes
AnswersImagine that you are developing a text editor. What is the best data structure to implement the buffer of text?
- N568
Then imagine that you have to paste 3000chars into your buffer. How does your structure handles that?| Report Duplicate | Flag | PURGE
Qualcomm Software Engineer / Developer Data Structures - 0of 0 votes
AnswersImagine that you have an histogram stored in an array. Now imagine that you can pour water on top of your histogram. Describe an algorithm that computes the amount of water that remains trapped among the columns of the graph. Clearly on the edges the water would fall off. Use the language or the pseudocode you prefer.
- N568| Report Duplicate | Flag | PURGE
Qualcomm Software Engineer / Developer Algorithm
The function checkes wether y is a power of 2.
here is the output:
y: foo(y)
0: 1
1: 1
2: 1
3: 0
4: 1
5: 0
6: 0
7: 0
8: 1
9: 0
10: 0
11: 0
12: 0
13: 0
14: 0
15: 0
16: 1
17: 0
18: 0
19: 0
20: 0
21: 0
22: 0
23: 0
24: 0
25: 0
26: 0
27: 0
28: 0
29: 0
30: 0
31: 0
32: 1
typedef struct list_t{
int x;
struct list_t* next;
} list_t;
// add two lists and return a list
list_t* add(list_t* A, list_t *B){
int s;
list_t* least=NULL; //pointer to the sum list least impotant digit
list_t* most=NULL; //pointer to the sum list most impotant digit
list_t* tmp=NULL;
// while there are 2 digits, add them
while( A != NULL && B != NULL){
s = A->x + B->x;
// initialize sum list
tmp = malloc(sizeof(list_t));
if(least == NULL){
least = most = tmp;
}
// add either 1 or 2 digits
if(s<9){
tmp->x = s;
tmp->next = NULL;
most->next=tmp;
most=tmp;
}
else{
tmp->x = s -10;
tmp->next = malloc(sizeof(list_t));
tmp->next->x = 1;
tmp->next->next=NULL;
most->next=tmp;
most=tmp->next;
}
A=A->next;
B=B->next;
}
while( A != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
A = A->next;
most = most->next;
}
while( B != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
B = B->next;
most = most->next;
}
return least;
}
So we have 2 lists A and B and we need to sum them.
Question 1. The results is again a list?
->: let's assume yes, a SUM list
Question 2. How numbers are organized? starting from the most significant ? or least significant?
-> if from most significant on, the problem is hard, so we can just reverse the list and then sum. Reversing a list is a O(n) problem and the sum is also an O(n) so the total op is O(n).
So assuming A, B lists starting from the least significant digit and the sum returns S list also from the least sig. digit the problem is:
typedef struct list_t{
int x;
struct list_t* next;
} list_t;
// add two lists and return a list
list_t* add(list_t* A, list_t *B){
int s;
list_t* least=NULL; //pointer to the sum list least impotant digit
list_t* most=NULL; //pointer to the sum list most impotant digit
list_t* tmp=NULL;
// while there are 2 digits, add them
while( A != NULL && B != NULL){
s = A->x + B->x;
// initialize sum list
tmp = malloc(sizeof(list_t));
if(least == NULL){
least = most = tmp;
}
// add either 1 or 2 digits
if(s<9){
tmp->x = s;
tmp->next = NULL;
most->next=tmp;
most=tmp;
}
else{
tmp->x = s -10;
tmp->next = malloc(sizeof(list_t));
tmp->next->x = 1;
tmp->next->next=NULL;
most->next=tmp;
most=tmp->next;
}
A=A->next;
B=B->next;
}
while( A != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
A = A->next;
most = most->next;
}
while( B != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
B = B->next;
most = most->next;
}
return least;
}
char* c = *a ?.....
- N568 August 09, 2012checks whether the value pointed by a is >0 not if a is NULL.
if you have
char x = "A";
char *a = &x;
then "char* c = *a ?....." depends on the value of x