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.
Some lesser known but useful Unix commands
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.
Print a Binary Tree in Zig Zag Level Order
Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter.
Example: zig-zag level order traversal of below tree will be
0 2 1 3 4 5 6 14 13 12 11 10 9 8 7
If we think logically then we will see that we need stack in place of queue. Now again a single stack won’t serve our purpose here, we need 2 stacks: stack1 for right to left and stack2 for left to right. For identifying, whether we need to put data in stack1 or stack2, we need a flag (left2right) to indicate direction (after a level finishes).
Initially, left2right is true and we push root node in stack1 and that’s our beginning point. Now since after root node, first level fished, we toggle left2right. Until stack1 is empty, we pop values from stack1 and push values based on left2right flag. Once stack1 finishes, we toggle left2right again and switch stack’s role.
For clarification, when left2right is true, push left node first in stack and then right node. Similarly left2right is false, push right node first in stack and then left node.
Code:
void ZigZagLevelOrder(tree *root) {
stack<tree*> stack1, stack2, *cur_level, *next_level, *temp;
bool left2right = true;
cur_level = &stack1;
next_level = &stack2;
// push root in stack
cur_level->push(root);
while (!cur_level->empty()) {
tree *node = cur_level->top();
cur_level->pop();
if (node) {
cout << node->data << " ";
if (left2right) {
next_level->push(node->left);
next_level->push(node->right);
} else {
next_level->push(node->right);
next_level->push(node->left);
}
}
if (cur_level->empty()) {
left2right = !left2right;
// swap stacks
temp = Cur_level;
cur_level = next_level;
next_level = temp;
}
}
}
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 largest sub-matrix with all 1s (not necessarily square)
In last post, we saw a dynamic programming approach to for finding maximum size square sub-matrix with all 1s. In this post, we will discuss how to find largest all 1s sub-matrix in a binary matrix. The resultant sub-matrix is not necessarily a square sub-matrix.
Example:
Largest all 1s sub-matrix is from (1,1) to (2,4).1 1 0 0 1 00 1 1 1 1 11 1 1 1 1 00 0 1 1 0 0
1 1 1 11 1 1 1
For above purpose, we need to generate an auxiliary matrix S[][] where each element represents the number of 1s above and including it, up until the first 0. S[][] for above matrix will be as shown below:
Now we can simple call our maximum rectangle in histogram on every row in S[][] and update the maximum area every time.1 1 0 0 1 00 2 1 1 2 11 3 2 2 3 00 0 3 3 0 0
Also we don’t need any extra space for saving S. We can update original matrix (A) to S and after calculation, we can convert S back to A.
Code: I am not writing the code for largestArea() function. One can find its definition in this post.
#define ROW 10
#define COL 10
int find_max_matrix(int A[ROW][COL])
{
int i, j;
int max, cur_max;
cur_max = 0;
//Calculate Auxilary matrix
for (i=1; i<ROW; i++)
for(j=0; j<COL; j++)
{
if(A[i][j] == 1)
A[i][j] = A[i-1][j] + 1;
}
//Calculate maximum area in S for each row
for (i=0; i<ROW; i++)
{
max = largestArea(A[i], COL);
if (max > cur_max)
cur_max = max;
}
//Regenerate Oriignal matrix
for (i=ROW-1; i>0; i--)
for(j=0; j<COL; j++)
{
if(A[i][j])
A[i][j] = A[i][j] - A[i-1][j];
}
return cur_max;
}
Complexity: Lets say that total number of rows and columns in A are m and n respectively and N = m*n
Complexity of calculating S = O(m*n) = O(N)
Complexity of LargestArea() for every row = O(n) since there are n elements in every row. Since we called LargestArea() m times so total complexity of calculating largest area = O(m*n) = O(N)
Complexity of converting S to A = O(m*n) = O(N)
So total time complexity = O(N)
Since we are not using any extra space, so space complexity is O(1).
Note: Above function only returns largest area, which can be very easily modified to get start and row indexes as well.
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.
Maximum size square sub-matrix with all 1s
Question: Given a matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s.
Example: Consider the below matrix.
The maximum square sub-matrix with all '1' bits is from (2,1) to (4,3)0 1 1 0 11 1 0 1 00 1 1 1 01 1 1 1 01 1 1 1 10 0 0 0 0
Answer: This is a classic Dynamic Programming problem. Lets calculate the maximum size square sub-matrix as we traverse the original matrix M[][]. We will use a auxiliary matrix S[][] of same size for memoization. S[i][j] represents size of the square sub-matrix with all 1s including M[i][j]. 'i' and 'j' will be the last row and column respectively in square sub-matrix.1 1 11 1 11 1 1
How to calculate S[i][j]:
We should note that if M[i][j] is '0' then S[i][j] will obviously be '0'. If M[i][j] is '1' then S[i][j] depends on earlier values.
If M[i][j] is '1' then it will contribute to the all 1s square sub-matrix ending at either M[i][j-1] or M[i-1][j] or M[i-1][j-1]. If we visualize the conditions then, we will see:
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
How did we arrive at above relationship?
Note if we include M[i][j] in earlier calculated sub-matrix then we are adding S[i][j] elements from ith row and jth columns. They all should be '1' if we wanna include M[i][j]. On visualizing with some examples, readers will analyze why, minimum of 3 neighbors is taken.
For the given M[][] in above example, constructed S[][] would be:
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.0 1 1 0 11 1 0 1 00 1 1 1 01 1 2 2 01 2 2 3 10 0 0 0 0
Code:
#define ROW 10
#define COL 10
void FindMaxSubSquare(bool M[ROW][COL], int &max_i, int &max_j, int &size)
{
int i,j;
int S[ROW][COL];
/* Set first column of S[][]*/
for(i = 0; i < ROW; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for(j = 0; j < COL; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for(i = 1; i < ROW; i++)
{
for(j = 1; j < COL; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum entry in S[][] */
size = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < ROW; i++)
{
for(j = 0; j < COL; j++)
{
if(size < S[i][j])
{
size = S[i][j];
max_i = i;
max_j = j;
}
}
}
return
}
Complexity:
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Note: Part of this post is taken from geeksforgeeks.
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.
Weekend Miscellany
Maths:
The Secret of the Fibonacci Sequence in Trees
C/C++:
The most stupid C bug ever
Computer Science:
The Busy Beaver Problem - good coders code, great reuse
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.
Divisibility by 7
How can you tell whether a number is divisible by 7? Almost everyone knows tricks to test divisibility by 2, 3, 5, or 9. Testing divisibility by 4, 6, 8, or 11 is a bit trickier. But not many people have ever seen a trick for testing divisibility by 7.
How to test: Remove the last digit from the number, double it, and subtract it from the first part of the number. Do this repeatedly until you get something you recognize as being divisible by 7 or not.
Example: Lets test for 826. Split 826 into 82 and 6. Subtract 12(6*2) from 82 to get 70. Since 70 is divisible by 7, so is 826.
Another Example: For 8632. Split 8632 into 863 and 2. Subtract 4(2*2) from 863 to get 859.
Now split 859 into 85 and 9. Subtract 18(9*2) from 85 to get 67, which isn’t divisible by 7. Hence, we conclude that 8632 isn’t divisible by 7.
Why does this work? Let b be the last digit of a number n and let a be the number we get when we split off b. That says n = 10a + b. Now n is divisible by 7 if and only if n – 21b is divisible by 7. But
n – 21b = 10a + b - 21b = 10(a – 2b)
Above is divisible by 7 if and only if a – 2b is divisible by 7.
Similarly, we can find divisibility by 13, 17, 19 etc.
Divisibility by 13: Add four times the last digit to the remaining leading truncated number to make it (n + 39b) = 10(a + 4b)
Divisibility by 17: Subtract five times the last digit from the remaining leading truncated number to make it (n - 51b) = 10(a - 5b)
Divisibility by 19: Add two times the last digit to the remaining leading truncated number to make it (n + 19b) = 10(a + 2b)
Test above divisibility yourselves with examples.
PS: Thanks John D. Cook for this trick.
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.
Change Headers Of S3 Object
Sometimes, we need to change header info for S3 objects. One solution is to download file locally and upload it again with new header information.
Using Amazon API COPY functionality, it is possible to change headers on an S3 object without downloading the entire object. We need to set x-amz-metadata-directive as REPLACE to copy a S3 key to the same location.
But if we do this using right_aws ruby gem, ACL information is not preserved. For preserving ACL information as well, we need to preserve ACL permission before changing headers and then apply ACL again after changing headers.
#!/usr/bin/env ruby
require 'rubygems'
require 'right_aws'
@s3 = RightAws::S3Interface.new('AWS_ACESS_KEY', 'AWS_SECRET_KEY', :logger => STDOUT)
#In this example, I'm changing the mime-type to image/png.
#You can change whatever header you want.
update_s3_object_headers(bucket, key, {'Content-Type' => 'image/png'})
def update_s3_object_headers(bucket, key, headers)
#Saving current ACL
acl_xml = @s3.get_acl(bucket, key)[:object]
# Performing a copy with directive REPLACE
@s3.copy(bucket, key, bucket, key, :replace, headers)
#Restore ACL
@s3.put_acl(bucket, key, acl_xml)
end
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.
Copy Files Between Separate AWS Accounts
Sometimes, we need to copy S3 data between separate AWS accounts. Though Amazon API provides COPY functionality but that is only for buckets under same account.
It seems that if we want to copy data between buckets in different accounts, only option is to download the file to local system and then upload it to destination bucket.
Since bucket names are unique across all S3, we can copy a public-read file to destination bucket (in different account) using COPY. I tested this and it works perfectly.
For copying a private file, we need to temporarily give public-read permission on the file and then COPY it to different AWS accounts. Don’t forget to change permissions for file in source and destination bucket once copy is done.
Also, we don't have to worry about bandwidth charges since COPY operation is internal to AWS. No download of the actual file required.
Code:
#!/usr/bin/env ruby
require 'rubygems'
require 'right_aws'
srcBkt = 'SourceTest'
srcKey = 'test.ppt'
destBky = 'DestTest'
destKey = 'test.ppt'
# Put credentials of destination account
s3 = RightAws::S3Interface.new('access_key', 'secret_key)
begin
#We can do a move operation as well if both the accounts are linked
s3.copy(srcBkt, srcKey, destBkt, destKey)
rescue Exception => e
puts e.inspect
end
Update: Please not that you will be able to COPY public content but can't MOVE (copy + delete) content across different accounts. If these accounts are linked with each other, you can MOVE as well.
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.
How To Add Facebook Comment Box To Blogger Blogs
Facebook comment box is one of the very useful tool for bloggers to increase engagement of readers. You may find many other blog posts teaching to add Facebook comment box to blogger blog. But still people are getting problem as I did. In this post, I will talk about how to integrate Facebook comment box to your blogger blog in very simple steps.
Step 1: Setup an application at Facebook developer page and enter your blog name, URL. Save the APP-ID for future reference.
Step2: Get your Facebook USER-ID. If you are using a custom username for your Facebook profile or page, you can get your profile Id from http://graph.facebook.com/<your username>. Here is the same page for Programming Interviews.
Step 3: Login to you Blogger dashboard and navigate to Layout > Edit HTML and check on Expand Widget Templates. Search for <head> and add following lines just after it:
To moderate comments across a site, all moderators must be added as admins of the app:
<meta property="fb:app_id" content="{YOUR_APP_ID}">
To receive notifications on every comment posted to the Comment Box, add:
<meta property="fb:admins" content="{YOUR_USER_ID}">
Change {YOUR_APP_ID} and {YOUR_USER_ID} with earlier saved values.
Step 4: Search for <data:post.body/> and add following lines just after it:
<!-- Facebook comment start -->
<b:if cond='data:blog.pageType == "item"'>
<script src='http://connect.facebook.net/en_US/all.js#xfbml=1'>
</script>
<fb:comments expr:href='data:post.url' num_posts='5' width='600'/>
</b:if>
<!-- Facebook comment end -->
Line 2 adds a check so that Facebook comment box doesn't appear on home page of your blog but only on the post pages. If you are familiar with blogger template you may want to add above code somewhere else. Please note to use expr:href in place of just href in line 5.
Step 5: You may or may not want to hide your blogger comment box. If you want to hide Blogger comment box, navigate to Settings > Comments and select hide and save settings.
PS: If you like this tutorial or have any question, please use below Facebook comment box to start conversation.
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 optimal number of jumps to reach last element
Question: Given an array, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps.
Example:
Given array A = {2,3,1,1,4}
Possible ways to reach the end (index list)
- 0,2,3,4 (jump 2 to index 2, and then jump 1 to index 3 and then jump 1 to index 4)
- 0,1,4 (jump 1 to index 1, and then jump 3 to index 4)
Answer: This problem is a classic example of Dynamic Programming. Though we can solve this by brute-force but complexity in that case will be horrendous. If you remember LIS problem or my first post on dynamic programming then we can solve this by using same process.
As soon as we traverse the array, we should find the minimum number of jumps for reaching that position (index) and update our result array. Once we reach at the end, we have the optimum solution at last index in result array.
How to find optimum number of jump for every position (index)?
For first index, optimum number of jumps will be zero. Please note that if value at first index is zero, we can’t jump to any element and return infinite.
For (N+1)th element, initialize result[N+1] as infinite. Then we should go through a loop from 0…N, and at every index (i), we should see if we are able to jump to (N+1) from there (i) or not. If possible then see if total number of jump (result[i] + 1) is less than result[N+1], then update result[N+1] else just continue to next index.
Code: I skipped algorithm but commented code properly.
//Define MAX 1 less so that adding 1 doesn't make it 0
#define MAX 0xFFFFFFFE;
unsigned int jump(int *array, int n)
{
unsigned int
*result = new unsigned int[n];
int i, j;
//Boundry conditions
if (n==0 || array[0] == 0)
return MAX;
result[0] = 0; //no need to jump at first element
for (i = 1; i < n; i++)
{
result[i] = MAX; //Initialization of result[i]
for (j = 0; j < i; j++)
{
//check if jump is possible from j to is
if (array[j] >= (i-j)) {
//check if better solution available
if ((result[j] + 1) < result[i])
result[i] = result[j] + 1; //updating result[i]
}
}
}
//return result[n-1]
unsigned int answer = result[n-1];
delete[] result;
return answer;
}
Above code will return optimum number of jumps only. If we want to have the jump indexes as well, we can very easily modify the code as per requirement.
Efficiency: Since we are running 2 loops here and iterating from 0 to I in every loop then total time takes will be 1 + 2 + 3 + 4 + … + (N-1).
So time efficiency O(n) = O(n*(n-1)/2) = O(n^2)
We also need O(n) space for result array.
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.
Matrix Madness - smallest non-negative number
Question: There is an N x N matrix with the property that each entry in the matrix is the smallest non-negative number, which does not appear either above the entry or to its left. Write a method to find the entry in a particular row and column.
For example, for N=8, we might have the matrix:
0 1 2 3 4 5 6 71 0 3 2 5 4 7 62 3 0 1 6 7 4 53 2 1 0 7 6 5 44 5 6 7 0 1 2 35 4 7 6 1 0 3 26 7 4 5 2 3 0 17 6 5 4 3 2 1 0
Answer: From the question statement, it is clear that the top left corner starts things off with 0 and the top row and the leftmost column are each completed with the positive integers 1,2,3,..., in order.
Secondly, if every time we fill another cell, we use the smallest non-negative integers that have not so far appeared in the same column and the same row, then it is impossible to get a repeated integer in either the same column or the same row. Square matrix of order n, in which every symbol occurs exactly once in each row and column of the array, is called latin square. So we can say that above matrix is a latin square in different setting.
Lets see if we can find some pattern in the sequence. If we write the matrix in binary number system an 8*8 matrix will look like below matrix:
If we took the highest power of 2 from these values, we can also write this matrix as
Now at every step for generating a square matrix of size 2n+1, we can expand the matrix by assuming that a corner square of size 2n (Mtl) has been filled. Copy it into adjacent squares Mtr, Mbr and Mbl and add 2n to every element of Mtr and Mbl. Final relationship will be like shown below:
Since we assumed that MN-1 (i.e. Mtl for MN) follows theis rule and entries of Mtr are formed by adding 2N-1 to Mtl. So Mtr is a latin square in itself. Also since elements from 0 to (2N-1 - 1) have already been used in Mtl, candidates for Mtr are only values greater than or equal to 2N-1. So we can say that Mtr adheres to the given rule. Similar argument can be given for Mbl.
For Mbr, we see that value for 0..(2N-1 -1) are not used in these row and column yet, We can use them and we used Mtl as it is. Hence we prove that MN the given conditions.
Now we can calculate value at any row and column in O(logN) time as on every step we can reduce the matrix size by half.
Can we do it in constant time?
Assume that rows and columns starting with 0 as in C/C++. Let M(m,n) denotes the number that appears in the (m, n) cell. Since we can denote any number with addition of power of 2, lets say
m = 2a + 2b + 2c + ... where a > b > c...
n = 2x + 2y + 2z + ... where x > y > z...
If a = x: then (m, n) lies in the Mbr square of the smallest square MN that contains (m, n). By dropping 2a from m and 2x from n, the point is moved into MN-1. So we don’t bother about ath and xth bit from m and n respectively.
If a < x: then (m, n) lies in the Mtr square of the smallest square MN that contains (m, n). As we saw earlier, we can move it into MN-1 by dropping 2a from m and add 2a to result. So we don’t bother about ath bit if it diffres.
If a > x: then (m, n) lies in the Mbl square of the smallest square MN that contains (m, n). As we saw earlier, we can move it into MN-1 by dropping 2x from n and add 2x to result. So we don’t bother about xth bit if it differs.
The process will continue while either m or n are not zero. Every time one of them has a binary bit which is 0 in the other, this bit is removed from the number but added to result. So we see that whenever any bit of m and n differs, we need to add it to result and just drop it if it’s same. In Boolean mathematics, XOR operator does the same. At the end of the day, m = n = 0 whereas result contains (m XOR n) of the original m and n. So finally
M(m,n) = m^n
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.
Convert binary tree in circular doubly linked list
Question: Take a binary tree and rearrange left and right pointers to make a circular doubly linked list.
You are supposed to play with pointers only. Assume left and right pointers of tree as previous and next pointers of doubly-linked list.
Answer: This is one of the most asked problems in programming interviews. Microsoft asks this question very frequently, I was asked the same when I rejected SDE-2 offer from Microsoft a few months ago. You can also find this problem at Stanford CS education library page as The Great Tree List Recursion Problem.
Below is original tree, which we have to convert in a circular doubly linked list.
And below is the original tree converted to circular doubly linked list with "next" and "previous" list arrows added.
Above drawing shows the all of the problem state -- the original tree is drawn with plain black lines and the desired next/previous pointers are added in as arrows. Notice that starting with the head pointer.
Looking at the last figure, you might have already started thinking about in-order traversal. If not then please notice that in final linked list (shown below), all the nodes left to a node were actually the nodes from left-sub-tree in original tree. Similarly, all the nodes right to a node were actually the nodes from right-sub-tree in original tree. This is similar to in-order traversal of tree:
- process left sub tree
- process current node
- process right sub tree.
As we traverse the tree in-order, we can modify a node’s left pointer to point to its predecessor. We also have to modify the predecessor’s right pointer to point to the current node to maintain the doubly linked list behavior.
In this manner, we will be creating a list but that won’t be circular. We can solve this problem by creating a circular doubly linked list at every step in place of creating only doubly linked list. For this, we need to update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automatically updated with the correct pointers.
Code:
struct node {
int data;
struct node* left;
struct node* right;
};
typedef struct node* Node;
//root: Current tree node
//prev: this pointer should have the address of in-order predecessor of root
//head: this denoted head of final link list
void treeToDoublyList(Node root, Node & prev, Node & head)
{
if (!root) return;
treeToDoublyList(root->left, prev, head);
// current node's left points to previous node
root->left = prev;
if (prev)
prev->right = root; // previous node's right points to current node
else
head = root; // if previous is NULL that current node is head
Node right = root->right; //Saving right node
//Now we need to make list created till now as circular
head->left = root;
root->right = head;
//For right-subtree/parent, current node is in-order predecessor
prev = root;
treeToDoublyList(right, prev, head);
}
//Wrapper function
Node treeToDoublyList(Node root)
{
Node prev = NULL;
Node head = NULL;
treeToDoublyList(root, prev, head);
return head;
}
Complexity: As this is nothing but in-order traversal with some extra steps at every node, we are traversing each node just once. Hence time complexity is O(n).
Credits: All the images are copied from Stanford CS library page.
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.
Truth or lie?
Question: There are 100 people in a room. A person always speaks either lie or truth. When asked:
1st person says => all are liars
2nd person says => at most 1 speaks truth
3rd person says => at most 2 speak truth
4th person says => at most 3 speak truth
.
.
.
.
100th person says => at most 99 speak truth
How many people speak only truth?
Answer: Lets assume that person 1 speaks truth then all including him should be liar. It means he doesn’t speak truth.
Before moving forward, we should make it clear what does “at most” mean? “at most N” means N or less.
Lets assume that 2nd person speaks truth then he is the only person who speaks truth coz at most 1 means 1 or less. But if this statement is true then statements by all others are also true. Coz if “at most 1 person speaks truth” is true then “at most N speak truth” is also true, where N >= 1. This contradicts his own statement, so person 2 is also a liar.
Now lets say that 3rd person is speaking truth. But then the statements of person 4-100 are also true, which contradicts his own statement. It means that person 3 is also a liar.
This process will continue since 50th person. So 1-50 people are liars.
51st person says “at most 50 speak truth”. Lets say he is speaking truth. “at most 50” means any number from 0-50. It means that statements like “at most 51 speak truth” and “at most 70 speak truth” are also true. It means that people from 51 to 100 are speaking truth.
Hence, 50 people speak truth.
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.
Count Number of Blobs
Question: You are given a 2D array like below:
x o o o o xx x x o o xo o x o x oo o x o o o
A blob is defined as 1 or more adjacent (8 adjacent) Xs. Find the number of blobs in the most efficient manner.
Example: Below 2D array has 2 blobs. One blob consists of cells which have red 'x' and another consists of cells which have blue 'x'.
Extension: This question is also asked as to count the number of islands in an ocean where ocean is represented as a grid. Cells, having a part of any island, are marked as 'x' otherwise 'o'.
An efficient solution will be to mark all the cells in a single blob as used and increase the count by 1 for every blob. For this we need a data structure, which we can use to find cells in a single blob. This can be achieved by using a queue as described below.
While traversing the array in row/column major order, as soon as you encounter an unused 'x' cell, push it in queue. Also increment the count by 1 and mark this cell as used. Now pop front element from queue and check for its 8 neighbors, if they contain 'x' and not used, put them in queue. Repeat this process until queue is empty.
Using above method, you will be able to mark all cells of a blob as used. Now traverse array further and repeat the same process if you encounter any unused 'x' cell.
Algorithm:
count = 0
while row < total rows
while column < total columns
if cell[row][column] is unused
put in queue
increase count by 1
while queue is not empty
tmp = front element of queue
pop from queue
push unused 'x' neighbors of tmp in queue
end while
end if
end while
end while
return count
Code:
I have used MSB of every cell to use as a flag for used and unused cell. You can always use a different method.
#define MAX 100
#define USED 0x80
struct point
{
int x,y;
};
void push_in_queue(int x, int y, queue<struct point> *q, char mat[MAX][MAX], int nrow, int ncol)
{
if(x < 0 || x >= nrow || y < 0 || y >= ncol)
return;
struct point pnt;
if (mat[x][y] == 'X' && !(USED & mat[x][y]))
{
mat[x][y] = USED | mat[x][y];
pnt.x = x;
pnt.y = y;
q->push(pnt);
}
}
int count_blob(char mat[MAX][MAX], int nrow, int ncol)
{
queue<struct point> que;
int cnt = 0;
int x, y;
point pnt, tmp;
if (nrow == 0 && ncol == 0)
return 0;
for(x = 0; x < nrow; x++)
{
for(y = 0; y < ncol; y++)
{
if (USED & mat[x][y])
continue;
if (mat[x][y] == 'X')
{
cnt += 1;
mat[x][y] = USED | mat[x][y];
pnt.x = x;
pnt.y = y;
que.push(pnt);
while( !que.empty() )
{
tmp = que.front();
que.pop();
push_in_queue(tmp.x - 1, tmp.y, &que, mat, nrow, ncol);
push_in_queue(tmp.x - 1, tmp.y - 1, &que, mat, nrow, ncol);
push_in_queue(tmp.x - 1, tmp.y + 1, &que, mat, nrow, ncol);
push_in_queue(tmp.x + 1, tmp.y, &que, mat, nrow, ncol);
push_in_queue(tmp.x + 1, tmp.y - 1, &que, mat, nrow, ncol);
push_in_queue(tmp.x + 1, tmp.y + 1, &que, mat, nrow, ncol);
push_in_queue(tmp.x, tmp.y - 1, &que, mat, nrow, ncol);
push_in_queue(tmp.x, tmp.y + 1, &que, mat, nrow, ncol);
}
}
}
}
return cnt;
}
Complexity: Since every element of the matrix is processed at the most twice, once while putting in queue and once while normal 2D array traversal, time complexity is O(n) where n is total number of cells. You may argue that we are checking a few element more than 2 times while pushing in the queue, in that case also complexity will be O(n).
Space complexity: Extra space is occupied by queue. Please notice that queue size will never be more than 'n'. You can also deduce that queue size will always be much lesser than 'n' in worst case as well. So space complexity is of order 'n' = O(n).
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.
Detect where the loop starts in a singly link list
In last post, we found how to detect if there is a loop in singly link list or not. Now we will see how to detect where the loop starts.In above figure, we see that loop starts at node (a) after length x and loop length is z. So the total length of link list is (x+z). Also as we saw in last post that slow and fast iterator will meet at some node (b).
Please note if we move a pointer (one node per iteration) from (b) and keep count of nodes until we visit (b) again, we will be able to calculate z.
After finding z, start an iterator itr1 form head and move it z nodes from head at (c). Take another iterator itr2 and start it from head. Now if you move itr1 and itr2 in parallel one node at a time, they will meet first at start of the loop (a).
Explanation is based on following invariance:
"In a circle if we start from some point and move the distance equal to circumference along circle periphery, we will be at the same point again."
Both the iterators are meeting at (a) coz itr1 is z nodes ahead from itr2. Once itr1 is at (a), itr2 is z nodes behind (a). After z iterations, itr2 will reach (a) and itr1 also reaches (a) because of above invariant.
This solution has been suggested by Saket in comments to last post. Great solution Saket!
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 Loop in a Singly Linked List
Question: Usually a singly link list always ends in null pointer. What if there is no null pointer; what if you are stuck in an infinite loop? If you have a singly link list head pointer, detect if there is a loop in the list or not.
Example:
The loop may start at the very beginning of the link list as well (like a circular singly link list.)
Answer: If you have ever watched a race in Olympics athletics event, you should be aware of the circular tracks. Lets take the example of 100m race; it takes place on a section of circular ground and has the dead end. So that a perfect example of a legitimate link list (have a null pointer at the end.)
A 1000m race also takes place on a circular track but athletes have to make multiple rounds of the same track (we can say this track as a loop in the list.) What if there is no finish line, an athlete has to run forever (because of no null pointer in the end.) Now if athlete X runs faster than athlete Y, X is bound to leave Y behind at some point. In the process, there will be a time when X and Y are at same place.
Similarly, if we traverse the link list using a slow iterator and a fast iterator, both the iterators will be at same node at some time if there is a loop. If there isn’t any loop, fast iterator will reach the end (null pointer) first. Detecting a loop is then just detecting that the fast iterator has lapped the slow iterator or not.
Code: I have written the following code assuming slow iterator moves one node at once and fast iterator moves 2 nodes at once.
bool hasLoop(list *head)
{
list *slow, *fast;
slow = fast = head;
while (slow && fast )
{
slow = slow->next;
fast = fast->next;
if (fast)
fast = fast->next;
else
return false; //dead end
if (slow == fast) //loop detected
return true;
}
return false;
}
Efficiency: Since both the iterators are traversing through the list at most twice in this case, so complexity is O(2*n) = O(n).
Further thoughts: Readers should find the optimal speed of fast iterator? Is there an effect on efficiency if we move fast iterator at a speed of 3 nodes per iteration in place of 2?
We have detected if there is a loop or not. Next task is to find where the loop starts. Give it a thought before I write a post for that.
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.
Fit 1*2 dominos in 2*N strip
Question: In how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?
Answer: Please notice that we can put tiles either vertically or horizontally. For putting vertical tiles, we need a gap of at least 2 X 2. For putting horizontal tiles, we need a gap of 2 X 1. Number of arrangements will be the same as the arrangements, we can make with gaps of 1 and 2 (order dependent). In this manner, this problem reduces to find the number of ways to partition N using the numbers 1 and 2 with order considered relevant.
For example: 11 = 1 + 2 + 2+ 1 +2 + 2 + 1
If we have to find such arrangements for 12, we can either place a 1 in the end or can add 2 in the arrangements possible with 10.
Similarly, Lets say we have Xn possible arrangements for N. Then for (N+1), we can either place just 1 in the end. Or we can find possible arrangements for (N-1) and put a 2 in the end.
Lets verify above theory for our original problem:
In how many ways, we can fill a 2 X 1, strip:
- 1 -> only one vertical tile.
In how many ways, we can fill a 2 X 2, strip:
- 2 -> Either 2 horizontal or 2 vertical tiles.
In how many ways, we can fill a 2 X 3, strip:
- 3 -> either put a vertical tile in 2 solutions possible for 2 X 2 strip or put 2 horizontal tiles in only solution possible for 2 X 1 strip. (2 + 1 = 3)
Similarly in how many ways, we can fill a 2 X N, strip:
- Either put a vertical tile in solutions possible for 2 X (N-1) strip or put 2 horizontal tiles in solution possible for 2 X (N-2) strip. (Xn-1 + Xn-2).
That’s how, we verified that our final solution:
Xn = Xn-1 + Xn-2
Above recurrence relation is nothing but Fibonacci Series with X1 = 1 and X2 = 2.
I am confident that all the readers can write a optimized code for fibonacci series very easily. Try writing a working code with memoization.
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 if given pattern is present in given grid
Question: You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.
Example: Find “microsoft” in below matrix.
We can see the read color character, which form “Microsoft” in above 2D array.
Answer: I was asked this question in a Microsoft interview almost a year ago. A reader asked me to post the solution for this.
Manually finding the solution of this problem is relatively intuitive, we just need to describe an algorithm for it. Ironically, describing the algorithm is not the easy part.
How do we do it manually? First we match the first element; if it matched we matched the 2nd element in the 8 neighbors of first match; do this process recursively; when last character of input pattern matches, return true.
During above process, you take care not to use any cell in 2D array twice. For this purpose, you mark every visited cell with some sign. If your pattern matching fails at some place, you start matching from the beginning (of pattern) in remaining cells. While returning, you unmark visited cells.
Lets convert above intuitive method in algorithm. Since we are doing similar checks every time for pattern matching, a recursive solution is what we need here.
In recursive solution, we need to check if the substring passed is matched in the given matrix or not. The condition is not to use the already used cell. For finding already used cell, we need to have another 2D array to the function (or we can use an unused bit in input array itself.) Also, we need the current position of input matrix, from where we need to start. Since we need to pass a lot more information than actually given, we should be having a wrapper function to initialize that extra information to be passed.
Algorithm:
If you are past the last character in pattern Return true If you got an used cell again Return falseIf you got past the 2D matrix Return false If searching for first element and cell doesn’t match findmatch with next cell in row-first order (or column first order) otherwise if character matches mark this cell as used res = findmatch with next position of pattern in 8 neighbors mark this cell as unused Return res Otherwise Return false
#define MAX 100 //level: index till which pattern is matched //x, y: current position in 2D array bool findmatch(char mat[MAX][MAX], char *pat, int x, int y, int nrow, int ncol, int level) { if (level == strlen(pat)) //pattern matched return true; if (x<0 || y<0 || x>=nrow || y>=ncol) return false; if (mat[x][y] == pat[level]) { // printf("{%d, %d}\n",x,y); bool res; //marking this cell as used char temp = mat[x][y]; mat[x][y] = '#'; //finding subpattern in 8 neighbours res = findmatch(mat, pat, x-1, y, nrow, ncol, level+1) || findmatch(mat, pat, x+1, y, nrow, ncol, level+1) || findmatch(mat, pat, x, y-1, nrow, ncol, level+1) || findmatch(mat, pat, x, y+1, nrow, ncol, level+1) || findmatch(mat, pat, x+1, y+1, nrow, ncol, level+1) || findmatch(mat, pat, x+1, y-1, nrow, ncol, level+1) || findmatch(mat, pat, x-1, y+1, nrow, ncol, level+1) || findmatch(mat, pat, x-1, y-1, nrow, ncol, level+1); //marking this cell as unused mat[x][y] = temp; return res; } else return false; } bool findmatch_wrapper(char mat[MAX][MAX], char *pat, int nrow, int ncol) { // if total characters in matrix is less then pattern lenghth if (strlen(pat) > nrow*ncol) return false; for (int i=0; i<nrow; i++) for (int j=0; j<ncol; j++){ if (mat[i][j] == pat[0]) if(findmatch(mat, pat, i, j, nrow, ncol, 0)) return true; } return false; }
Please note the use of OR operator while calculating res. This confirms me that I don’t evaluate next condition as soon as one of the conditions evaluates to true.
Complexity:
Best case complexity is obviously O(1), if pattern is NULL.
Worst case: What will be worst case for this problem. The matrix (lets say N*N) is filled with ‘A’ in all the cells and pattern is “AAAA…….AAAAB” of length N^2. Then it will match with every cell, search in 8 neighbors recursively and fails at last element every time.
I'm leaving it to readers to find the complexity of this approach.
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 Merge node in 2 link lists
Answer: We should have one fact in mind that merging node is found by comparing the address (not value) of the nodes. Since we have 2 different lists, one way is to have 2 for loops and compare addresses of all the possible nodes. This solution is O(mn) where 'm' and 'n' are lengths of given lists.
If length of 2 lists are of equal length, we can traverse both the lists one node at a time and find the common node. But since lengths may not be same, we first find a node in bigger list, from where we have length same as that of smaller list. For this, first we need to find the length of both the lists, then move ahead the difference in bigger list and then match nodes in parallel.
Algorithm:
- Find length (len1) of first link list.
- Find length (len2) of second link list.
- find diff = abs(len1 – len2)
- Traverse the bigger list from the first node till 'diff' nodes. Now we have two lists, which have equal no of nodes.
- Traverse both the lists in parallel till we come across a common node.
Code:
struct node* findMergeNode(struct node* list1, struct node* list2)
{
int len1, len2, diff;
struct node* head1 = list1;
struct node* head2 = list2;
len1 = getlength(head1);
len2 = getlength(head2);
diff = len1 - len2;
if (len1 < len2)
{
head1 = list2;
head2 = list1;
diff = len2 - len1;
}
for(int i = 0; i < diff; i++)
head1 = head1->next;
while(head1 != NULL && head2 != NULL)
{
if(head1 == head2)
return head1->data;
head1= head1->next;
head2= head2->next;
}
return NULL;
}
Complexity: Complexity of above solution is O(m+n).
PPS: Try extending this solution to N lists, where N > 2.
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.
Global git ignore rules
# git ls-files --others --exclude-from=.git/info/exclude# Lines that start with '#' are comments.*.[oa]*.pyc
git config --global core.excludesfile ~/.gitignore_global
# Compiled source ####################*.com*.class*.dll*.exe*.o*.so*.lo*.Plo*.Po*.la*.pc*Makefile
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.
Check if identical BSTs from given number streams
Question: You are given 2 number streams. You need to find whether they will create the same BST or not.
Example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True
Array1:10 5 20 15 30
Array2:10 15 30 20 5
Result: False (see corresponding trees below)
Answer:
Method of building a BST from an incoming stream is like below:
- Make first element as root.
- If current element is smaller then root -> insert in left subtree.
- If current element is greater then root -> insert in right subtree.
- If current element is equal to root -> skip (or as pre-decided)
- While inserting in left and right subtree, follow above steps recursively.
So in above question, we have to check top-down if all the subtrees are identical or not. For that, we should follow below steps:
- Check if stream is finished if yes -> return false
- Check if both the stream has same number of elements, if not -> return false
- Check if root is same, if not -> return false
- leftsubtree arrays = constructed from smaller elements than root
- rightsubtree arrays = constructed from greater elements than root
- if leftsubtree == rightsubtree -> return true
- For finding result in step 6, follow above steps recursively
Code: While writing code, I am skipping the element equal to root.
Ruby:
def checkidenticaltree(a, b)
return false if a.length != b.length
return false if a[0] != b[0]
return true if a.length <= 1
a_left = a.select {|v| v < a[0]}
a_right = a.select {|v| v > a[0]}
b_left = b.select {|v| v < b[0]}
b_right = b.select {|v| v > b[0]}
return checkidenticaltree(a_right, b_right) && checkidenticaltree(a_left, b_left)
end
Python:
def checkidenticaltree(a, b):
if len(a) != len(b):
return False
if a[0] != b[0]:
return False
if len(a) <= 1:
return True
a_left = []
a_right = []
for x in a:
if x < a[0]:
a_left.append(x)
elif x > a[0]:
a_right.append(x)
b_left = []
b_right = []
for x in b:
if x < b[0]:
b_left.append(x)
elif x > b[0]:
b_right.append(x)
return checkidenticaltree(a_right, b_right) and checkidenticaltree(a_left, b_left)
PS: This is not a very efficient approach as we have to segment stream on each recursion. It will be great, if we can find some bottom-up approach. Any suggestions?
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.
GIT: Combine Local Git Commits into One with git-svn
On running "git svn dcommit", git creates a separate commit in SVN for every local commit, one made since last syncing with SVN. Here is a way to combine all recent local commits into single commit for SVN.
If you have multiple commits piled up on your local system, you just need to run following commands:
git reset <hash tag of commit till which u need to combine>
git commit -am "your message"
Above commands will create one clubbed commit of all the commit till the hash tag used. Please Make sure to you add any new files using "git add <file>". "git commit -am " does not add new files by itself.
I have answered this question on stackoverflow. You can find more answers by expert users here.
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.
Reconstruct tree from pre-order traversal
Question: A tree has a special property where leaves are represented with ‘L’ and non-leaf with ‘N’. Each node has either 0 or 2 children. If given preorder traversal of this tree, construct the tree.
Example:
Given Pre Order string => NLNLL
In normal scenario, it’s not possible to detect where left subtree ends and right subtree starts using only pre-order traversal. But here, we are given a special property. Since every node has either 2 children or no child, we can surely say that if a node exists then its sibling also exists. So every time we are computing a subtree, we need to compute its sibling subtree as well.
Secondly, whenever we get ‘L’ in the input string, that is a leaf so we can stop for a particular subtree at that point. So after this ‘L’ node (left child of its parent ‘L’), it’s sibling starts. If ‘L’ node is right child of its parent, then we need to go up in the hierarchy to find next subtree to compute.
Keeping above invariant in mind, we can easily determine, when a subtree ends and next start. It means that we can give any start node to our method and it can easily complete the subtree it generates w/o going outside its nodes.
We just need to take care, that we are passing correct start nodes to different subtrees.
Code:
tree* newnode(char c)
{
tree *node = new(tree);
node->val = c;
node->left = node->right = NULL;
return node;
}
tree* construct_tree(char* A, int *i)
{
//Boundary Condition
if (A == NULL){
return NULL;
}
tree *node = newnode(A[*i]);
//On reaching leaf node, return
if (A[*i] == 'L'){
return node;
}
//Populate left sub tree
*i = *i + 1;
node->left = construct_tree(A, i);
//Populate right sub tree
*i = *i + 1;
node->right = construct_tree(A, i);
return node;
}
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.
Right_aws: Weird expires behavior in s3_interface#get_link
At Slideshare, we use Amazon Web Services offerings and our main usage are of EC2, SQS and S3. We host almost all of our content at S3 because of scalability and reliability, it provides. For interacting with S3 via ruby, we use right_aws gem from Rightscale.
For finding a link for a private S3 object, we use get_link() method in right_aws. By default, get_link() returns a link, which remains valid for 24 hours. This is because default expiry time is set to 24 hours.
DEFAULT_EXPIRES_AFTER = 1 * 24 * 60 * 60 # One day's worth of seconds
I found out that the expires parameter passed to get_link() in s3_interface is limited to 1 year in seconds. For longer expires, it is required to pass (Time.now.utc + expires) in get_link() because of the following check:
expires ||= DEFAULT_EXPIRES_AFTER
expires = Time.now.utc + expires if expires.is_a?(Fixnum) && (expires < ONE_YEAR_IN_SECONDS)
expires = expires.to_i
When we call get_link(), it call generate_link() in turn and above code snippet is copied from generate_link(). You can see the function definition here.
Since finally, we recalculate the 'expires' in generate_link(), I fail to see the necessity of such a limitation.
I am writing this post so that one takes care while generating link using right_aws gem.
Example:
For 30 days expire (< one year), I'll use:
link = @s3_helper.get_link(bucket, key, expires = 30 * 24 * 60 * 60)
For 366 days (> one year) expire, I’ll use:
link = @s3_helper.get_link(bucket, key, expires = Time.now.utc + 366 * 24 * 60 * 60)
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.
Get maximum sum from coins in a line
Question: There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
Answer: If we assume that n is even then there is simple strategy to ensure that you win. Find the sum of coins at even and odd positions say X and Y respectively. Now if X>Y, pick coins only at even positions else pick coins only at odd positions.
How to ensure that you pick coins only at even or odd positions:
Assume that n = 6 and value are {3, 2, 2, 3, 1, 2}. Then sum at even positions is 7 (2 +3 +2) and at odd positions is 6 (3 +2 +1). So you will always pick the coins at even positions to ensure wining. How to achieve it:
Is above strategy optimal:
Above strategy ensure you winning but doesn’t ensure that you are drawing the maximum amount of money. For previous example {3, 2, 2, 3, 1, 2}, you drew a sum of 7, but you could have drawn a sum of 8. Lets see how:
Pick the first coin (3) instead. The opponent is left with two possible choices, the left coin (2) and the right coin (2), both valued at 2. No matter, which coin the opponent chose, you can always take the other coin (2) next and the configuration of the coins becomes: {2, 3, 1}. Now, the coin in the middle (3) would be yours to keep for sure. Therefore, you win the game by a total amount of 3 + 2 + 3 = 8, which proves that the previous non-losing strategy is not necessarily optimal.
Since your opponent is as smart as you, so we need to take all the possible combinations in consideration before our move. Calculating all those moves will include repetitive calculations so this is the place where we can use Dynamic Programming to show its magic.
Say coins are in stored in array A and C(i, j) is the maximum sum possible when remaining coins are from i to j. Lets discuss the case when there are remaining coins from i to j (positions) and it’s your turn to pick the coin. Now there are 2 possibilities:
- You pick coin A(i)
- You pick coin A(j)
Therefore, the maximum amount you can get when you choose Ai is:
C1 = Ai + min { C(i+2, j), C(i+1, j-1) }
Case 2 - If you pick coin Aj :
Similar to case 1, the maximum amount you can get when you choose Aj is:
ThereforeC2 = Aj + min { C(i+1, j-1), C(i, j-2) }
C(i, j) = max { C1, C2 }
= max { Ai + min { C(i+2, j), C(i+1, j-1) },
Aj + min { C(i+1, j-1), C(i, j-2) } }
Now we have the recursive function in hand and the above recurrence relation could be implemented in few lines of code. But if we follow simple recursion, its complexity is exponential. The reason is that each recursive call branches into a total of four separate recursive calls, and it could be n levels deep from the very first call).
To reduce the time complexity, we need to store the intermediate values in a table and use them, when required. Memoization provides an efficient way by avoiding re-computations using intermediate results stored in a table.
If you notice, we do not need to build complete matrix but only need to build right (upper) triangular matrix. Also notice that C[i, i] (diagonal elements) will always be equal to A[i]. Below is the code which runs in O(n^2) time and takes O(n^2) space.
#define MAX 100
int maxMoney(int A[], int N) {
int C[MAX][MAX] = {0};
int x, y, z; //x = C[m+2][n], y = C[m+1][n-1], z = C[m][n-2]
for (int i = 0; i < N; i++) {
for (int m = 0, n = i; n < N; m++, n++) {
//calculate x, y, z
x = (m+2 < N) ? C[m+2][n] : 0;
y = (m+1 < N && n-1 >= 0) ? C[m+1][n-1] : 0;
z = (n-1 > 0) ? C[m][n-2] : 0;
C[m][n] = max(A[m] + min(x,y),
A[n] + min(y,z));
//For Debugging
cout << x << ", " << y << ", " << z << endl;
cout << m << ", " << n << ", " << C[m][n] << endl;
}
}
return C[0][N-1];
}
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.
Ambiguity in Base64 encoding between ruby and python
I had to convert ttf fonts in Base64 encoding and save them in CSS while doing some more complex stuff. I wrote a python script for it using inbuild base64 library, which worked pretty fine.
I did the same in ruby (with inbuild Base64 library) and my code ran without any error. So far so good! But when I saw the results in browser, I was surprised to see that it replaced the actual glyphs with random glyphs. Since python script output was doing good job, I was surprised, what I did wrong.
When I run the base64 encoding on a shorter string, I noticed the difference in results.
Ruby Run:
irb(main):010:0* require 'base64'
=> false
irb(main):011:0> str="Akash is testing Base64 Encoding between python and ruby"
=> "Akash Agrawal is testing Base64 Encoding between python and ruby"
irb(main):012:0> Base64.encode64(str)
=> "QWthc2ggaXMgdGVzdGluZyBCYXNlNjQgRW5jb2RpbmcgYmV0
d2VlbiBweXRo\nb24gYW5kIHJ1Ynk=\n"
Python Run:
>>> import base64
>>> str="Akash is testing Base64 Encoding between python and ruby"
>>> base64.b64encode(str)
'QWthc2ggaXMgdGVzdGluZyBCYXNlNjQgRW5jb2RpbmcgYmV0
d2VlbiBweXRob24gYW5kIHJ1Ynk='
Please notice that the results in both the languages are same, except ruby appended a line feed ('\n') after every 60 characters.
Surprisingly, on decoding ruby gives same result with both the versions (with and without '\n').
I checked RFC standards and there it was written that
Implementations MUST NOT not add line feeds to base encoded data unless the specification referring to this document explicitly directs base encoders to add line feeds after a specific number of characters.
Though ruby seems to be following some other standards but browsers are complying without '\n' result. TO achieve the same in ruby, one can do the following:
irb(main):018:0> Base64.encode64(str).gsub("\n", '')
PS: In ruby-1.9.2 you have Base64.strict_encode64 which doesn't add that '\n' (newline) at the end.
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.
How to get public IP for Amazon EC2 instances
If you run "ifconfig –a" on an amazon ec2 instance (linux), it will give you the internal IP address, which is not accessible from outside world. Here is a way to get the public and private IP address for an amazon EC2 instance.
To obtain the IP addresses, issue the following HTTP queries from within the instance:
To obtain the internal IP address:
curl http://169.254.169.254/latest/meta-data/local-ipv4
To obtain the public IP address:
curl http://169.254.169.254/latest/meta-data/public-ipv4
Alternatively, you can obtain the public and private DNS name/IP of an EC2 instance from AWS console (or from any service provider like RightScale.)
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.
Writing faster ruby code: Avoid Temporary Objects
We have learnt a tip for writing faster ruby code and profiling ruby in last past. Today we will see a few more tips to write faster ruby code.
Tip #2: Avoid Temporary Objects:
Consider following ruby code, how can we make it fast?
#!/usr/bin/env ruby
require 'benchmark'
a = ""
1_000_00.times { a += "." }
Which means that every time we are doing this operation, we are creating a temporary objects with value (a + “.”) and then assigning it back to a. The creation of this temporary variable is actually costing us most of the time and space. If we can avoid the use of this temporary variable, we can make things faster. Consider the following:
#!/usr/bin/env ruby
require 'benchmark'
a = ""
1_000_00.times { a << "." }
Rehearsal ---------------------------------------
+= 2.740000 0.460000 3.200000 ( 3.250396)
<< 0.040000 0.000000 0.040000 ( 0.037068)
------------------------------ total: 3.240000sec
user system total real
+= 2.760000 0.510000 3.270000 ( 3.352737)
<< 0.040000 0.000000 0.040000 ( 0.036535)
Tip #3: Use Destructive functions:
Consider following functions calls, can we make it faster?
“akashagrawal”.gsub
“akashagrawal”.sub
“akash” + “agrawal”
[1, 2].collect
[1, 2].compact
[1, 2].uniq
[1 , [2, 3]].flatten
[1] + [2]
Each and every line in above code creates a temporary object and then assigning the same to that object. If we use the corresponding destructive version of above (given below), we can save a lot of time.
“akashagrawal”.gsub!
“akashagrawal”.sub!
“akash” << “agrawal”
[1, 2].collect!
[1, 2].compact!
[1, 2].uniq!
[1 , [2, 3]].flatten!
[1].concat[2]
I am leaving the exercise of benchmarking the usage of destructive vs non-destructive function to readers.
PS: Don’t overuse destructive functions, as “Premature optimization is the root of all evil.”
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.
Writing faster ruby code: Tip #1
Developers usually feel that ruby is a slow language in terms of time efficiency. This is true but if you use some tricks, your ruby code can run faster. I am giving you some tips (with example) to optimize your ruby code and you can see the results in practice.
How to profile: To know, where to make changes in your code to run faster, you need to profile your code. You can use inbuild “benchmark” library or Ruby-Prof for this purpose. Though there are many other tools, but I found these 2 very suitable and easy to use. Ruby-Prof gives you output in multiple formats so that you can analyze it easily.
Tip #1 :- Printing
Consider following ruby code, how can we make it fast?
require 'benchmark'
n = 50_000
for i in 1..n do
$stderr.print i, "and"
$stderr.puts i
end
Above code has a couple of problems, which are making in run slow:
- We are using 2 distinct functions calls (puts and print).
- We are using ‘puts’, which includes the overhead of adding a ‘\n’ to every line that doesn't already have one.
require 'benchmark'
n = 50_000
Benchmark.bmbm(15) do |r|
r.report("original version 2 calls") do
for i in 1..n do
$stderr.print i, "and"
$stderr.puts i
end
end
r.report("single puts call") do
for i in 1..n do
$stderr.puts "#{i} and #{i}"
end
end
r.report("single print call") do
for i in 1..n do
$stderr.print "#{i} and #{i}\n"
end
end
end
When I run this script, I found following results from benchmarking:
Above results clearly show an improvement of reducing function calls and of using 'print' over 'puts'.akash$ ruby puts_print.rb 2> /dev/null
Rehearsal ------------------------------------------------------------
original version 2 calls 0.370000 0.260000 0.630000 ( 0.639098)
single puts call 0.250000 0.140000 0.390000 ( 0.397769)
single print call 0.170000 0.070000 0.240000 ( 0.256804)
--------------------------------------------------- total: 1.260000sec
user system total real
original version 2 calls 0.380000 0.270000 0.650000 ( 0.658632)
single puts call 0.240000 0.140000 0.380000 ( 0.390004)
single print call 0.170000 0.070000 0.240000 ( 0.250661)
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)