Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Colorize Mac 'ls' output
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Peripheral (Boundary) of a complete tree
- First the root
- Then nodes on left edge
- Then leaf nodes
- Then nodes on right edge
- print root node
- print left nodes and leafs of left subtree in same order
- print leafs and right nodes of right subtree in same order
enum {LEFT, RIGHT, LEAF};
bool isleaf(struct node* tree)
{
return (!(tree->left || tree->right));
}
void rperipheral (struct node* root, int state)
{
if(root)
{
switch (state)
{
case LEFT:
printf("\t %d", root->data);
rperipheral(root->left, LEFT);
rperipheral(root->right, LEAF);
break;
case RIGHT:
rperipheral(root->left, LEAF);
rperipheral(root->right, RIGHT);
printf("\t %d", root->data);
break;
case LEAF:
if (isleaf(root))
printf("\t %d", root->data);
rperipheral(root->left, LEAF);
rperipheral(root->right, LEAF);
break;
}
}
}
void peripheral (struct node* root)
{
printf("%d",root->data);
rperipheral(root->left, LEFT);
rperipheral(root->right, RIGHT);
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Which loop is faster?
Question: A very basic programming puzzle is being asked in programming interviews since last few years. Which of the below two loops will run faster?
/* FIRST */
for(i=0;i<10;i++)
for(j=0;j<100;j++)
//do somthing
/* SECOND */
for(i=0;i<100;i++)
for(j=0;j<10;j++)
//do somthing
Answer: Firstly it seems, that since the code body (//do something) will run 1000 times in both the cases and so both loops should take equal time. But if we have a closer look how the loop statements are executing then we can certainly deduce that first loop is faster.
- The SECOND executes assignment operations ( j = 0 or i = 0) 101 times while FIRST executes only 11 times.
- The SECOND does 101 + 1100 comparisons (i < 100 or j < 10) while the FIRST does 11 + 1010 comparisons (i < 10 or j < 100).
- The SECOND executes 1100 increment operations (i++ or j++) while the FIRST executes 1010 increment operation.
main()
{
int i, j, k, l;
l = 0;
/* FIRST */
for(i=0, l++, k=0;i<10;i++, k++)
for(j=0, l++;j<100;j++, k++);
printf("First Loop: %d\t%d\n", k, l);
l= 0;
/* SECOND */
for(i=0, l++, k=0;i<100;i++, k++)
for(j=0,l++;j<10;j++, k++);
printf("Second Loop: %d\t%d\n", k, l);
}
Output of above code is as follows:
First Loop: 1010 11From the above output, we can clearly see that 2nd loops has more operations (assignment, increment). On a deeper analysis, comparison operations are also more in 2nd loop. So FIRST loop is clearly faster than SECOND.
Second Loop: 1100 101
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Diameter of a tree in O(n)
It can be shown that the diameter of a tree T is the largest of the following quantities:
- the diameter of T's left subtree
- the diameter of T's right subtree
- the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
int diameter(TreeNode t)
{
if (t == null)
return 0;
int leftD = diameter(t.left);
int rightD = diameter(t.right);
int rootD = height(t.left) + height(t.right) + 1;
return max(rootD, Math.max(leftD, rightD));
}
int diameter2(TreeNode t, int* height)
{
int lh = 0, rh = 0;
int leftD = 0, rightD = 0;
if(t == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}
leftD = diameter2(root->left, &lh);
rightD = diameter2(root->right,&rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;
return max(lh + rh + 1, leftD, rightD);
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Nth fibonacci number in O(logN)
A* [ F(1) F(0) ] = [ F(2) F(1) ]A* [ F(2) F(1) ] = [ F(3) F(2) ] = A^2 * [ F(1) F(0) ]A* [ F(3) F(2) ] = [ F(4) F(3) ] = A^3 * [ F(1) F(0) ]........A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ] = A^n * [ F(1) F(0) ]
Matrix findNthPower( Matrix M , power n ){if( n == 1 ) return M;Matrix R = findNthPower ( M , n/2 );R = RxR; // matrix multiplicationif( n%2 == 1 ) R = RxM; // matrix multiplicationreturn R;}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Speed up your code!!!
Many readers of this blog use to take part in online programming competitions and there are several problems, which are run-time bound. Usually when one gets a time-out error, one tries to revisit one’s logic. That’s the first thing to do but if you still are not making required progress you can try following tips:
C/C++:
Use printf, scanf over cin and cout: To get faster I/O operations. If you have enormous data to read, this will help you for sure.
Keep an eye on STL usage: STL is excellent for lessen your efforts and provide very smart inbuilt methods for many complex tasks but on the cost of time. An intelligent programmer can save time writing his/her own methods.
Note: This might cause you to take longer to solve a problem and STL beautify your code with fewer efforts. I personally love STL and everyone should use it in practice. But this can be a significant contributor in time-out frequently.
Ruby:
If you are using hash, avoid hash[“string”] it performs badly in terms of space and time. Use hash[:symbol] instead.
General:
- Avoid nested loops
- Check boundaries carefully
- Take care of program stack; not many folds/unfolds.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Cloud Storage: Amazon S3
As promised, I am back with another post on cloud computing. This time we will talk about storage in clouds and will try to find answers to following questions. Since I have worked on Amazon cloud storage called Simple Storage Service (Amazon S3), the figures and data in this post are true for Amazon S3 only but the concepts are true for any provider.
- What do we mean by Cloud Storage?
- What benefits does cloud storage provide?
- What disadvantages are there?
- Conclusion
- You did a very good job and make your business multifold. You would need new storage servers, more memory, and more money all at once. Cost arises suddenly so the infrastructure and maintenance cost.
- You goofed up and have to shutdown your business. What would you do with the entire infrastructure you built for starting? You feel like loosing money for all the hardware you earned during good days.
Solution both the cases is that in place of buying everything; rent it. Maintenance, infrastructure will automatically become lender’s problems; let the best guy do it for you against a nominal fee. Cloud storage is nothing but something which gives you space on demand. The best part is that cloud storage is elastic and you can use as much space as you want and just pay for the actual data. You need not worry about expanding or contracting your business.
Also you are not paying for extra hardware, you bought in optimistic anticipation or worrying about lesser hardware than required.
Benefits of cloud storage: In 4 words I will say its Bigger-Better-Faster-Cheaper…
Bigger coz there is no limit on data, pure elastic storage.
Better coz of redundancy, cloud-computing platforms provide. (up almost all the time). Focus on your core business Infrastructure becomes someone else's problem.
Faster coz it’s available on the fly and available on demand Provision via APIs not phone calls, fastest speeds is data I/O from clouds own computing infrastructure (EC2 in case of Amazon AWS)
Cheaper coz of no associated costs, Reduced need for capital, focus on OpEx not CapEx, Barrier to entry is much lower
Specific for Amazon S3:
- Storage is organized in buckets
- Like a namespace for the objects it contains
- Accessible via http://bucketname.s3.amazonaws.com
- It’s not file storage; it’s a key-value store
- Like a big hash table or dictionary
- Key-value pairs
- Accessible via http://bucketname.s3.amazonaws.com/keyname
- Implicit BitTorrent seeding for all keys
- 5GB limit for each key
- Official API to operate on buckets in different languages and for different platforms.
Also, you can specify access for individual keys; whether this particular data is public or private and other custom access.
You may choose what kind of reliability you want; more reliable more cost, less reliable less cost.
Disadvantages of cloud storage: Biggest disadvantage is if it’s down you are down.
Other problems is that bandwidth cost is very high; if you are having very large size public keys in S3 and someone gets holds of url of those keys; he may make you bankrupt by continuously fetching data. So you should be very careful about access specifier and key distribution. Whenever possible, hide your keys. Also you have to trust other with your critical data; it’s outside your firewall.
Specific to S3:
- Changing one byte means reinserting the entire object
- Renaming (re-keying) an object also means reinserting
- New beta API allows for object moves (copy) within a bucket
- Various bugs in third-party apps and S3 itself
- Inserting objects between 2 to 4 GB can be difficult
- Bandwidth can be a significant barrier
Conclusion: Cloud storage is a great entry point for new entrant in the industry with minimum possible CapEx and no worries about maintenance and infrastructure. If used wisely, it can prove a boon but in novice hands, it may be a curse as well.
PS: Points under different heading are true not only for storage but for cloud-computing in general (leave specific points aside).
This is not all, there has to be other measure like private, public, hybrid platforms; distribution of data. I will cover the same in upcoming posts.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
K-reverse a linklist
Code:
struct list* GetNthNode(int n, struct list* head) { if(!head) return head; struct list* Nth; int i; //Notice the loop body (empty) for (i=0, Nth=head; Nth && (i < nth="Nth-">next); if(i==n && Nth!=NULL) return Nth; return head->next; } bool isNnodes(struct list* head, int n) { int i; //Notice the loop body (empty) for (i=0 ; head && (i < head="head-">next); if(i == n) return true; return false; } void reverseN(struct list** list1, int n) { if (n==0 || n==1) return; struct list *cur, *tmp, *next; int i; cur = *list1; if(!isNnodes(*list1,n)) return; *list1 = GetNthNode(n-1,*list1); while(cur && isNnodes(cur, n)) { //take care on below step tmp = GetNthNode(n, GetNthNode(n-1, cur)); i=0; while(inext; cur->next=tmp; tmp = cur; cur = next; i++; } } }
PS: Later, I noticed that code can be much shorter than given above and I am leaving that exercise to the readers.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Find us on Facebook
I write about
- Algorithm (31)
- Amazon EC2 (3)
- Amazon Interview (9)
- Amazon S3 (5)
- Amazon SimpleDB (5)
- Amazon SQS (1)
- Architecture (3)
- Arrays/Strings (32)
- backtracking (1)
- Brain Teasers (8)
- C++ (3)
- Cloud Computing (14)
- Design Pattern (2)
- Dynamic programming (11)
- Facebook Interview (3)
- General (14)
- Git (2)
- Google Interview (6)
- Humour (1)
- Interviews (7)
- Link List (8)
- Mac (2)
- Mathematics (3)
- MIcrosoft Interview (4)
- Miscellany (1)
- python (3)
- queue (1)
- Ruby (9)
- tree (19)
- web development (1)