**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.
skip to main |
skip to sidebar
##
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

**Question:** Write a program to find the anti-clock-wise peripheral (boundary) of a complete tree.

**Answer:** For a complete tree peripheral (boundary) is defined as

**Algorithm:****Code:**

**PS:** Above solution can be extended to incomplete trees as well with small modifications. But one must be clear to define the boundary in case of incomplete tree.

**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?

**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.

Output of above code is as follows:

**FIRST loop is clearly faster than SECOND**.

**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)

**Definition:** The *diameter* of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

**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)

**Question:** Find Nth fibonacci number in O(logN) time complexity.

**Answer:** We all know the Fibonacci recurrence as F(n+1) = F(n) + F(n-1) but we can represent this in the form a matrix as shown below:

In this manner, by using the magic of DP, we can get the Nth fibonacci number in O(logN).

**PS:** This question was asked me in Amazon Interview and I could not replied it that time. I got this answer here and sharing the same.

**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!!!

**PS:** Above is a small list of speed checkup; I urge everyone to contribute through comments to the post.

**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

**What is Cloud Storage:** Suppose you started a small startup with a few gigabytes of data to store and you setup your system accordingly. At a later stage are two possibilities:

**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

**Algorithm:**

Code:

**PS:** Later, I noticed that code can be much shorter than given above and I am leaving that exercise to the readers.

**Important:** As said many times; it's always better to design a generalized algorithm rather than designing one for a specific case. Since this problem is solving that swap nodes problem, it's beter to design this kind of algorithm so that if in near future some needs arise, you can reuse the code.

**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.
## I write about

Since I have switched to Mac, I was wondering how to colorize the 'ls' output for it. I really like having color output when I use the ls command. This enables me to quick scan filetypes in a jiffy. In unix you can do this by giving '-color' option with ls but unfortunately that doesn't work with Mac. Apple has chnaged this option from '-color' to '-G'. So next time you want to see the colored ls output on your mac terminal, simple append below line in your .profile.

alias ls="ls -G"

You can also choose what color (foreground/background and bold/normal) you want for your specific file type. For this you need to set LSCOLORS variable as your choice. I use following LSCOLORS in my .profile:

export LSCOLORS=dxfxcxdxbxegedabagacad

You can craete your own LSCOLORS very easily here.

under:
Mac

- First the root
- Then nodes on left edge
- Then leaf nodes
- Then nodes on right edge

For the above tree, peripheral will be

0 1 3 7 8 9 10 11 12 13 14 6 2

- 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);

}

Time complexity of the above solution is O(n) as every node is traversed just once.

under:
tree

**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

- 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.

Points 1 and 2 can be verified from following code. It clearly shows the number of assignment and increment operations.

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

Second Loop: 1100 101

The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

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*)

A pseudo program based on above algorithm is shown below:

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));

}

The problem with above algorithm is that this is not an O(n) algorithm but O(n^2). And the main culprit here is the height function. As height function is itself a linear function and is called for every node so this make the whole algorithm an O(n^2) affair.

This problem can be solved if we calculate the height with diameter itself and don't call height recursively for each node again and again. Pseudo code for the same is shown below:

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);

}

Look at the matrix A = [ [ 1 1 ] [ 1 0 ] ] . Multiplying A with [ F(n) F(n-1) ] gives us [ F(n+1) F(n) ] , so we say that

A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ]

start with [ F(1) F(0) ] , multiplying it with A gives us [ F(2) F(1) ]; again multiplying [ F(2) F(1) ] with A gives us [ F(3) F(2) ] and so on...

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) ]

So all that is left is finding the nth power of the matrix A. Well, this can be computed in O(log n) time, by recursive doubling. The idea is, to find A^n , we can do R = A^(n/2) * A^(n/2) and if n is odd, we need do multiply with an A at the end. The following pseudo code shows the same.

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;}

under:
Algorithm,
Amazon Interview

Posted by Akash Agrawal

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.

under:
General

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.

under:
Amazon S3,
Cloud Computing

Posted by Akash Agrawal

Question: k-reverse of linklist where k>0. This means that you should reverse block of k nodes in a list.

Example:

i/p: 1 2 3 4 5 6 7 8 9 10

o/p:

For k=2: 2 1 4 3 6 5 8 7 10 9

For k=3: 3 2 1 6 5 4 9 8 7 10

For k=4: 4 3 2 1 8 7 6 5 9 10

This is nothing but an extension of swapping nodes in a linklist. But in my opinion, it's a slightly easier problem than that. One can also use this solution for swapping nodes in a list.

1) check if remaining list has k nodes.

if yes get the pointer of (k+1)th node.

else return.

2) reverse first k nodes.

3) set next of last node (after reversal) to (k+1)th node.

4) move to (k+1)th node.

5) Go to step 1.

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++; } } }

under:
Link List

- 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)