vivekh
BAN USERThe best time complexity we could get is O(m) where m is the no of 1's in the digit.
Idea:
start from the rightmost bit
while(N) {
if(N&1 == 0){
run a variant of binary search to reach to the left end of zeros.
and keep a count of the number of zeros
}
N = N>>1
}
after the loop return the max value
@- sbgobbur : the divided and conquer technique that you are using is nlog(n) and not log n.Even before you recurse you are traversing the entire array O(n), to calculate left crossing and right crossing.
Recurrence for your algo is T(n) = n + 2(T(n/2)) = nlog(n)
Can be done using an Augmented AVL tree.
1. create an AVL tree with an additional field as count;
2. Treat numbers in an array as stream of intergers
3. start creating the AVL tree , and keep on updating the count field for each node.
4. Once the array is complete, do a traversal of tree and print nodes whose count > N/3
To solve this , we need an augmented data structure. where at each node(r) of BST, we maintain the number of nodes in the subtree rooted at r.(refer
page 340 CLRS). Now given a range first we try to reach to a node(n) such that x<=n<y. ie node lies between the given range. this can be done recursively.
Total nodes lying in the range = nodes > x on the left subtree rooted at n + nodes < y on the right subtree rooted at y + 1 ( the root node, n)
(part 1) (part2)
to calculate part1:
1. start from node n
2. if x < n, go left other wise go right
3. while travering the BST if you find a node greater than x the keep a running count of node->right->size +1
4. continue this procedure till the search terminates.
to calculate part2:
everything remains same, except step 3
3. while travering the BST if you find a node less than x the keep a running count of node->left->size +1
Finally total = part1 + part2 + 1
Comments/Issues ?
One more way
626 void print_wildcard(char *S, char *res, int i, int n) {
627
628 if(i>n){
629 /*res[i] = S[i];*/
630 printf("%s\n", res);
631 return;
632 }
633
634 if(S[i]!='?'){
635 res[i] = S[i];
636 print_wildcard(S, res, i+1, n);
637
638 }else {
639 S[i] = '0';
640 res[i] = S[i];
641 print_wildcard(S, res, i+1, n);
642 S[i] = '1';
643 res[i] = S[i];
644 print_wildcard(S, res, i+1, n);
645 S[i] = '?'; //move the string back to the origial character
646 }
647
}
- vivekh September 11, 2015594 void print_i18n(char *S, int i, int j, int n) {
595
596 int k=0;
597
598 while(k<=i){
599 printf("%c", S[k]);
600 k++;
601 }
602 printf("%d", j-(i+1));
603 while(j<=n){
604 printf("%c", S[j]);
605 j++;
606 }
607 printf("\n");
608 }
609
610 void i18n(char *S, int i, int j, int n) {
611
612 if(j-i == 1)
613 return;
614
615 print_i18n(S, i, j, n);
616
617 i18n(S, i+1, j, n);
618 i18n(S, i, j-1, n);
619
}
call this function like this : i18n(S, 0, n-1, n-1);
where n is length of the string
*algorithm :
262 *1. Let A be the the orginal max-heap array
263 *2. Initially queue is empty and rank = 0
264 *3. Insert root(max element of A) in queue
265 *4. while(Queue!= empty){
266 *
267 * //add queue currents node's left and right child to the queue
268 * enqueue(leftchild);
269 * enqueue(rightchild);
270 * //heapify the queue
271 * heapify(Queue);
272 *
273 * //delete node from queue (deletion is done from front and insertion from tail, like BFS)
274 * dequeue(Queue);
275 *
276 * rank++;
277 *
278 * if(rank == ith order statsictic)
279 * return the dequeued element
280 *
281 *}
282 *
283 *complexity : since to find Kth largest we atleast need to dequeue K element , and for each element , we need to heapify the
284 *queue which take log(n) time , n-> no of elements in the queue at a given time,
285 * so total time = Klog(n)
thoughts/critiques?
- vivekh September 07, 20151. parse each string in a given set and sort them
2. Insert each string into a trie
3. count the total number of paths in the trie, this will be the number of unique sets
eg i/p = { abc, cab, dac, beed, deb, few, acd }
sorted o/p = {abc, abc, adc, bdee, bde, efw, adc}
after inserting in trie we get following unique paths( root to leaf)
{ abc, adc, bdeem bde, efw}
return the count of unique paths
1. sort the kids by weight
2. take 2 pointers high and low pointing to first and last kid in the sorted array
3. while ( low < high) {
if(A[high] > 150 || A[low]+ a[high] > 150)
high --; count++;
else if (A[low] + A[high] < = 150)
high--; low++; count++;
}
return count;
complexity = O(nlogn)
33 /*
34 * logic : calculate the differene between count of odd and even count set bits
35 * if it is multiple of 3 , then the number is a multiple of 3. function return 1 or 0
36 */
37 int checkMultipleOf3(int n){
38
39 int even_c = 0, odd_c = 0;
40
41 if(n<0)
42 n = -n;
43 if (n == 0)
44 return 1;
45 if(n == 1)
46 return 0;
47
48 while(n > 0){
49
50 if(n&1)
51 odd_c++;
52 n = n>>1;
53 if(n&1)
54 even_c++;
55
56 n = n>>1;
57 }
58 return(abs(odd_c - even_c));
/*
* Algorithm:
*For the first two elements add smaller one to the maxHeap on the left, and bigger one to the minHeap on the right. Then process stream data one by one,
*
*Step 1: Add next item to one of the heaps
*
* if next item is smaller than maxHeap root add it to maxHeap,
* else add it to minHeap
*
* Step 2: Balance the heaps (after this step heaps will be either balanced or
* one of them will contain 1 more item)
*
* if number of elements in one of the heaps is greater than the other by
* more than 1, remove the root element from the one containing more elements and
* add to the other one
*
* Then at any given time you can calculate median like this:
* If the heaps contain equal elements;
* median = (root of maxHeap + root of minHeap)/2
* Else
* median = root of the heap with more elements
*/
Nice idea using the state logic . Here is my implementation
446 void num_problem_util(char A[][6], int i, int c, int n, char *path, int k, int l) {
447 int j;
448
449 if(k==n) {
450 //we print only at the leaves
451 printf("%s ", path);
452 return;;
453 }
454
455 for(j=0;j<c;j++) {
456 if(A[i][j] != 'x') {
457 path[l] = A[i][j];
458 num_problem_util(A, A[i][j]-'0', c, n, path, k+1, l+1);
459 }
460 }
461 }
462 void number_problem() {
463 //maintain the state information, ie for each digit we store the number of permissible next digits
464 char state[][6] = { {'4', '5', '6', '7', '8', '9'}, // digit 0
465 {'5', '6', '7', '8', '9', 'x'}, // digit 1
466 {'6', '7', '8', '9', 'x', 'x'},
467 {'7', '8', '9', 'x', 'x', 'x'},
468 {'0', '8', '9', 'x', 'x', 'x'},
469 {'0', '1', '9', 'x', 'x', 'x'},
470 {'0', '1', '2', 'x', 'x', 'x'},
471 {'0', '1', '2', '3', 'x', 'x'},
472 {'0', '1', '2', '3', '4', 'x'},
473 {'0', '1', '2', '3', '4', '5'} }; // digit 9
474
475 /*
476 * now we create a path array array to store all the valid combination of the arrays
477 * the length of the array will be 6 ( max number of column in state array)
478 */
479
480 char *path = (char*)malloc(sizeof(char)*6);
481 int n;
482 printf("Enter length of digits\n");
483 scanf("%d", &n);
484
485 num_problem_util(state, 1, 6, n, path, 0, 0);
486 }
The idea is :
1. start with root
2. if the number is less than root value , go left otherwise go right
3. recursively continue step 2 till you reach the leaf node,
4. Now as the recursion stack pops, at each node check if the abs(difference between the node value and the number is minumum value) is less than the previous value.
5. If you find the abs value calculated in step 4 to be less , then return the node pointer.
Below is the simple code :
1480 int MOD(int x, int y) {
1481 return (x-y)>0?(x-y):(0-(x-y));
1482 }
1483 TREE* closest(TREE* node, int n, int *close) {
1484
1485 TREE* temp;
1486
1487 if(!node)
1488 return NULL;
1489
1490
1491 if(node->value > n)
1492 temp = closest(node->left, n, close);
1493 else if(node->value <= n)
1494 temp = closest(node->right, n, close);
1495
1496 // if the difference between the node value and passed val is less than previously stored value, then update it
1497 if(MOD(node->value, n) < *close) {
1498 *close = MOD(node->value, n);
1499 temp = node;
1500 }
1501 return temp;
1502
}
- vivekh August 28, 2015One way could be to store the path lengths from source to dest in in a min heap. now whenever you remove the an egde , you check if the edge belongs to the shortest path(O)1) time). If yes then delete the egde, swap the shortest path with the path stored at the end of heap array, and heapify the array(excluding the swapped array). continue this process till you find a the shortest path which is not a part of removed edge.
This can work for the cases when edge is added back. Just figure out the path sums which were part of that edge , increase the size of heap array by 1 and heapify again to get the shortest path
192 1. put chars in a link list ( can use doubly link list)
193 2. p1 = start of list
194 3. p2 = p1->next;
195 4. while (all elements in list become same) {
196
197 while(p2!=NUL){
198 if(p1=>value != p2->value){
199 p2 = p2->next;
200 p2->value = replace with 3rd char
201 del(p2);
202
203 } else {
204 p2 = p2->next;
205 p1 = p1->next;
206 }
207 }
208 }
209
210 5. after the loop ends all chars will be same. get the lenth of link list
211 6. Reverse the orginal link list
212 8. run step 4 on reversed link list
213 9. get the length on the list obtained in step 8
214 10 return the min len of step 5 and 9
the idea is to create a trie of Trie(or Ternary tree) of L.
Now start with index i = 0 of S.
1. search for 4 letters(or whatever the length of words) at a time in the trie. if you dont find a match, then increment i by 1 and continue searching
2. if u find a match increment i by 4 , and mark the entry as 'M' (match).
3. stop parsing the string when you get MMMM(4 matches ) , return the index of the first M
complexity = O(len(S)*log(len(word)))
Comments/corrections are invited.
This can be done through dynamic programming effieciently.
We maintain an extra array to store the the no of intervals for i th index where
0<i<n;
Lets call this array as T
base case :
T[0] = 0
recurrence :
T[i] = T[i-1] + cnt
where cnt is calculated by the below logic
while (i>0){
1.search till the start of orginal array, from index i
2. whenever we find 0s == 1s, we increment the cnt
i--;
}
repeat this process for all i
Your logic wont work. According to ur logic,
A1 B1 A1 can be printed, as after printing B1 you are doing signal(X).
if Thread 1 is scheduled just after this, A1 can again be printed.
To maintain the order, you need to use 4 mutuxes
m_A1 = 1, m_A2 = 0, m_B1 = 0, m_B2 = 0;
thread1() {
wait(m_A1);
print A1
signal(m_B1)
wait(m_A2)
print A2
signal(m_B2)
}
thread2{
wait(m_B1)
print B1
signal(m_A2)
wait(m_B2)
print B2
signal(m_A1)
}
66 //thread prototypes
67 void* thread0(void *data) {
68
69 int i = 0;
70 while(i<10) {
71 sem_wait(&mutex[0]);
72 printf("0");
73 sem_post(&mutex[1]);
74 i++;
75 }
76 return NULL;
77
78 }
79
80 void* thread1(void *data) {
81 int i = 0;
82 while(i<10) {
83 sem_wait(&mutex[1]);
84 printf("1");
85 sem_post(&mutex[2]);
86 i++;
87 }
88 return NULL;
89 }
91 void* thread2(void *data) {
92
93 int i = 0;
94 while(i<10) {
95 sem_wait(&mutex[2]);
96 printf("2");
97 sem_post(&mutex[0]);
98 i++;
99 }
100 return NULL;
101 }
111 void sync_threads() {
112
113 //init the mutex variables
114 init_mutex();
115
116 //create thread ids
117 pthread_t tid[THREADS];
118
119 pthread_create(&tid[0], NULL, thread0, NULL);
120 pthread_create(&tid[1], NULL, thread1, NULL);
121 pthread_create(&tid[2], NULL, thread2, NULL);
122
123 pthread_join(tid[0], NULL);
124 pthread_join(tid[1], NULL);
125 pthread_join(tid[2], NULL);
126
127 sem_destroy(&mutex[0]);
128 sem_destroy(&mutex[1]);
129 sem_destroy(&mutex[2]);
130 }
131
int main() {
sync_threads();
}
- vivekh August 10, 2015273 LIST* delete_all_occurences_recursive(LIST* node, int value) {
274
275 LIST* temp;
276
277
278 if(node && node->next == NULL)
279 return node;
280 if(!node)
281 return NULL;
282
283 temp = delete_all_occurences_recursive(node->next, value);
284 if(temp->value == value){
285 node->next = temp->next;
286 free(temp);
287 }
288 return node;
289
290
}
- vivekh August 08, 20151. run a loop to read each word in the sentence
2. Sort the word and add into the Trie, ( Augment the trie data structure at leaf, with a count variable)
3. After adding the working increment this count variable ;
4. Keep on reading the words and adding in Trie. If you find the count variable as 1 then it means this word is an anagram
Its a modification of Knapsack problem, where,
1250 = total capcity of knasack
Item 1 :
w = 1300 , v = 10500
Item 2 :
w = somevalue , v = some value
now have to select subset of items whose total weight is less than the capacity and have min value. ( in Knapsack we select items having max value)
{{
49 double sqroot(double low, double high, double num) {
50
51 double mid;
52 double sqrt;
53 if(high < 0)
54 return -1;
55
56 mid = (low+high)/2;
57
58 if((mid*mid < num) && (high-low > EPS))
59 sqrt = sqroot(mid, high, num);
60 else if((mid*mid > num) && (high-low) > EPS)
61 sqrt = sqroot(low, mid, num);
62 else
63 sqrt = mid;
64
65 return sqrt;
66 }
call sqroot(0, num, num)
}}
/*funtion to print all the nodes of a tree at a given level */
print_at_level ( TREE* node, int lvl, int level ) {
if(node == NULL)
return;
if(level == lvl )
printf("%d ",node->value);
print_at_level(node->right,lvl+1,level);
print_at_level(node->left,lvl+1,level);
}
/*Sorting of linklist using bubble sort */
void sort_list ( LIST *head) {
int count=0,tmp,i;
LIST *node;
node=head;
/*count the number of elements*/
while (node!=NULL){
count++;
node=node->next;
}
/*do a bubble sort */
for ( i=1;i<count;i++){
node = head;
while(node->next!=NULL){
if(node->value > node->next->value)
{
tmp = node->value;
node->value = node->next->value;
node->next->value = tmp;
}
node = node->next;
}
}
}
Sort the arrays and merging logic it using 2 pointers.If the elements are equal print it.
308 /*function to print the intersectio of two arrays
309 len1= len of a,len2= len of b */
310
311 void intersection(int *a, int*b, int len1, int len2) {
312 /*sort the arrays*/
313 sort_array(a,0,len1);
314 sort_array(b,0,len2);
315
316 while (len1>=0 && len2>=0){
317
318 if(a[len1] > b[len2])
319 len1--;
320 else if (a[len1] < b[len2])
321 len2--;
322 else{
323 printf("%d ",a[len1]);
324 len1--;
325 len2--;
326
327 }
328
329 }
Simple and clean solution. Cross checked it works.
void intersection(int *a, int*b, int len1, int len2) {
312 /*sort the arrays*/
313 sort_array(a,0,len1);
314 sort_array(b,0,len2);
315
316 while (len1>=0 && len2>=0){
317
318 if(a[len1] > b[len2])
319 len1--;
320 else if (a[len1] < b[len2])
321 len2--;
322 else{
323 printf("%d ",a[len1]);
324 len1--;
325 len2--;
326
327 }
328
329 }
330 }
The solution can be optimised for space by having only 27 char array , instead of 256. here is the compiled and tested code
/* this function initializes the hash table */
void init_hash( char *remove, char *p){
int i;
memset(p,'0',26);
p[26] = '\0';
while(*remove){
p[*remove - 97] = *remove;
remove++;
}
}
/* this function checks if hash search is successful or not */
int is_hash(char c, char* p){
if(p[c-97] == c)
return 1;
else
return 0;
}
/*this functions remove all the characters in remove string from
* the source string
* eg : source : aabbcc
* remove : ab
* output : cc */
void strRemove(char *source , char *remove){
char *p = source;
char s[27];
int i;
init_hash(remove,s);
for( i=0;i<strlen(p);i++){
if(is_hash(p[i],s))
p[i]=' ';
else
printf("%c",p[i]);
}
printf("\n");
}
now from main
char source[] = "amazon development centre";
char remove[] ="aenr";
strRemove(source,remove);
Can be easily solved in O(n) time using Augmented RB tree, where each node apart from storing left , right, and color, will also store size of node( no of nodes on left subtree + no of nodes on right subtree + 1(node itself). Check out the chapter on Augmented data structures in CLRS
- vivekh September 21, 2015