Separate the numbers challenge

Problem statement
A numeric string, s, is beautiful if it can be split into a sequence of two or more positive integers, 1_1, a_2, \dots, a_n, satisfying the following conditions:

  1. a_i - a_{i-1} = 1 for any 1 \textless i \le n (i.e., each element in the sequence is 1 more than the previous element).
  2. No a_i contains a leading zero. For example, we can split s=10203 into the sequence \left[1, 02, 03\right], but it is not beautiful because 02 and 03 have leading zeroes.
  3. The contents of the sequence cannot be rearranged. For example, we can split s=312 into the sequence \left[3, 1, 2\right], but it is not beautiful because it breaks our first constraint (i.e., 1 - 3 \ne 1).

The diagram below depicts some beautiful strings:

You must perform q queries, where each query consists of some string s. For each query, print whether or not the string is beautiful on a new line. If it’s beautiful, print YES x, where x is the first number of the increasing sequence (if there are multiple such values of x, choose the smallest); otherwise, print NO instead.

Input Format
The first line contains an integer denoting (the number of strings to evaluate).
Each of the subsequent lines contains some string for a query.

Constraints
1 \le q \le 10
1 \le |s| \le 32
Each character in s is a decimal digit from 0 to 9 (inclusive).

Output Format
For each query, print its answer on a new line (i.e., either YES x where x is the smallest first number of the increasing sequence, or NO).

Sample Input 0

Sample Output 0

Explanation 0
The first three numbers are beautiful (see the diagram above). The remaining numbers are not beautiful:

For s = 101103, all possible splits violate the first and/or second conditions.
For s = 010203, it starts with a zero so all possible splits violate the second condition.
For s = 13, the only possible split is \left[1,3\right], which violates the first condition.
For s = 1, there are no possible splits because s only has one digit.

Solution

 

An interesting game challenge

Problem statement
Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, A, of n distinct integers. The rules are as follows:

  • Bob always plays first and the two players move in alternating turns.
  • In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if A = \left[2,3,5,4,1\right], then it becomes A = \left[2,3\right] after the first move because we remove the maximum element (i.e., 5) and all elements to its right (i.e., 4 and 1).
  • The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play g games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print ANDY; if Bob wins, print BOB.

Input Format
The first line contains a single integer denoting g (the number of games). The 2\times g subsequent lines describe each game array over two lines:

  1. The first line contains a single integer, n, denoting the number of elements in A.
  2. The second line contains n distinct space-separated integers describing the respective values of a_0, a_1, \dots, a_{n-1} for array A.

Constraints
Array contains n distinct integers.
1 \le g \le 100
1 \le n \le 10^5
1 \le a_i \le 10^9
The sum of n over all games does not exceed 10^5.

Output Format
For each game, print the name of the winner on a new line (i.e., either BOB or ANDY).

Sample Input 0

Sample Output 0

Explanation 0
Andy and Bob play the following two games:

1.
Initially, the array looks like this:

In the first move, Bob removes 6 and all the elements to its right, resulting in A = \left[5,2\right]:

In the second move, Andy removes 5 and all the elements to its right, resulting in A = \left[\right]:

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print ANDY on a new line.

2.
In the first move, Bob removes 3 and all the elements to its right, resulting in A = \left[\right]. As there are no elements left in the array for Andy to make a move, Bob wins and we print BOB on a new line.

Solution

 

Yield To Maturity calculation using a Python script

When interested in buying bonds a term that often comes up is the definition of Yield To Maturity (YTM):

Yield to maturity (YTM) is the total return anticipated on a bond if the bond is held until the end of its lifetime. Yield to maturity is considered a long-term bond yield, but is expressed as an annual rate. In other words, it is the internal rate of return of an investment in a bond if the investor holds the bond until maturity and if all payments are made as scheduled. – Investopedia

Let us consider a bond with a par value of \$100 and a coupon rate of 3\% with the bond maturing in 29 years time. The current bond price is \$89. We are interested in the bond’s YTM.

Knowing that we get \$3 annual cashflow (coupon\ rate \times par\ value = 0.03 \times \$100 = \$3) we will have the following cashflow for the next 29 years. Notice in the last year we will receive an additional \$100 which is the bond’s principle:

Let us assume that we want to value these future cashflows and determine how much they are worth today. What we need to do, is to present value all of these future cashflows back to today and add up those present values pv_i. This sum would be the price of the bond.

A present value is the amount of money pv one would need to invest today in order to have c amount of money in n years if he is earning r% (annual)interest on his investment:

  pv = \frac{c}{(1 + r)^n}

For example, if Bob wants to have \$100 one year from now at a rate of 5\%, he needs to invest \$95.24 today (\frac{100}{(1 + 0.05)} = 95.24).

Back to our bond’s present value of future cashflows the resulting formula would look as follows:
  bond\ price = \frac{future\ cashflow\ 1}{(1 + ytm)^1} + \frac{future\ cashflow\ 2}{(1 + ytm)^2} + \frac{future\ cashflow\ 3}{(1 + ytm)^3} + \dots + \frac{future\ cashflow\ 29}{(1 + ytm)^{29}}

with ytm being the yield to maturity we are looking for.

For our particular bond the formula will look like this:
  bond\ price = \frac{3}{(1 + ytm)^1} + \frac{3}{(1 + ytm)^2} + \frac{3}{(1 + ytm)^3} + \dots + \frac{3 + 100}{(1 + ytm)^{29}}

So how can we go about finding ytm? Well, above we have learned that sum of present values of all future cash flows is our bond price. Since we already know the today’s bond price which is \$89, the formula becomes like this:
  \frac{3}{(1 + ytm)^1} + \frac{3}{(1 + ytm)^2} + \frac{3}{(1 + ytm)^3} + \dots + \frac{3 + 100}{(1 + ytm)^{29}} = 89

All we need to do now is to solve the above equation for ytm so that it holds true. We will do this through trial-and-error.

Solving the equation by hand requires an understanding of the relationship between a bond’s price and its yield, as well as of the different types of bond pricings. Bonds can be priced at a discount, at par and at a premium. When the bond is priced at par, the bond’s interest rate is equal to its coupon rate. A bond priced above par (called a premium bond) has a coupon rate higher than the interest rate, and a bond priced below par (called a discount bond) has a coupon rate lower than the interest rate. So if an investor were calculating YTM on a bond priced below par, he or she would solve the equation by plugging in various annual interest rates that were higher than the coupon rate until finding a bond price close to the price of the bond in question (quote from: Investopedia).

You can verify this quickly with a simple example. Assume a bond with current price b and a par value of 100 that matures in 1 year. The coupon rate is c and interest rate is ytm:

  b = \frac{100 + c \times 100}{(1 + ytm)}
==>
  b \times (1 + ytm) = 100 + c \times 100 = 100 \times (1 + c)
==>
  \frac{b}{100} = \frac{(1 + c)}{(1 + ytm)}

If \frac{b}{100} \textless 1 then (1 + ytm) \textgreater (1 + c). Similarly for the other cases.

Back to our bond. We had the following equation:
  \frac{3}{(1 + ytm)^1} + \frac{3}{(1 + ytm)^2} + \frac{3}{(1 + ytm)^3} + \dots + \frac{3 + 100}{(1 + ytm)^{29}} = 89

Now we must solve for the interest rate ytm which is where things start to get difficult. Yet, we do not have to start simply guessing random numbers if we stop for a moment to consider the relationship between bond price and yield. As was mentioned above, when a bond is priced at a discount from par, its interest rate will be greater than the coupon rate. In this example, the par value of the bond is \$100, but it is priced below the par value at \$89, meaning that the bond is priced at a discount. As such, the annual interest rate we are seeking must necessarily be greater than the coupon rate of 3\%.

With this information we can now calculate and test a number of bond prices by plugging various annual interest rates that are higher than 3\% into the formula above. Using a few different interest rates above 3\%, one would come up with the following bond prices:

I have used 0.00001 increments and as we can see with an interest rate of 3.62\% we can approximate our current price of \$89 quite good enough. So 3.62\% would be our Yield To Maturity.

Full code

References
Yield To Maturity (YTM) – Investopedia

 

Gena playing Hanoi challenge

Problem statement
The Tower of Hanoi is a famous game consisting of 3 rods and a number of discs of incrementally different diameters. The puzzle starts with the discs neatly stacked on one rod, ordered by ascending size with the smallest disc at the top. The game’s objective is to move the entire stack to another rod, obeying the following rules:

  1. Only one disc can be moved at a time.
  2. Each move consists of taking the topmost disc from a stack and moving it to the top of another stack.
  3. No disc may be placed on top of a smaller disc.

Gena has a modified version of the Tower of Hanoi. His Hanoi has 4 rods and N discs ordered by ascending size. He made a few moves (following the rules above), but stopped and lost his place. He wants to restore the tower to its original state by making valid moves. Given the state of Gena’s Hanoi, help him calculate the minimum number of moves needed to restore the tower to its original state.

Note: Gena’s rods are numbered from 1 to 4. All discs are initially located on rod 1.

Input Format
The first line contains a single integer, N, denoting the number of discs.
The second line contains N space-separated integers, where the i^{th} integer is the index of the rod where the disk with diameter i is located.

Constraints
1 \le N \le 10

Output Format
Print the minimum number of moves Gena must make to restore the tower to its initial, ordered state on the first rod.

Sample Input

Sample Output

Explanation
3 moves are enough to build the tower. Here is one possible solution:

Solution
We will use BFS to solve this challenge. We will use a helper array minForTower with minForTower[i] holding the size of the smallest disc located at tower i. The validMovesFromState() method will compute and return a Set<Integer[]> of all valid directly subsequent moves that can be made from a given tower-disc allocation. We will store visited states in an array int[] visited = new int[(int) Math.pow(4, n)] using a key. The array length is 4^N since we can have a maximum of 4^N possible tower-disc allocations/states. Each state has an integer key. For example, given a state \left[1, 4, 1\right], a key is an integer representing that allocation. Bits 2i and 2i+1 of the key represent the tower (Tower 0 = 00_b, Tower 1 = 01_b, Tower 2 = 10_b, Tower 3 = 11_b). For \left[1, 4, 1\right] the key is 12 = 001100_b.

We then do a BFS putting the states in a queue along with the depth of the given state. The depth or number of steps it took us to get to that state is stored at index 0 of the state array. Each time we reach our goal state we check we update our minimum if necessary.

The full code is listed below.

Full code

 

The power sum challenge

Find the number of ways that a given integer, X, can be expressed as the sum of the N^{th} power of unique, natural numbers.

Input Format
The first line contains an integer X.
The second line contains an integer N.

Constraints
1 \le X \le 1000
2 \le N \le 10

Output Format
Output a single integer, the answer to the problem explained above.

Sample Input 0

Sample Output 0

Explanation 0
If X = 10 and N=2, we need to find the number of ways that 10 can be represented as the sum of squares of unique numbers.

10 = 1^2 + 3^2

This is the only way in which 10 can be expressed as the sum of unique squares.

Sample Input 1

Sample Output 1

Explanation 1
100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2

Sample Input 2

Sample Output 2

Solution

 

Minimum loss challenge

Problem statement
Lauren has a chart of distinct projected prices for a house over the next n years, where the price of the house in the i^{th} year is p_i. She wants to purchase and resell the house at a minimal loss according to the following rules:

The house cannot be sold at a price greater than or equal to the price it was purchased at (i.e., it must be resold at a loss). The house cannot be resold within the same year it was purchased. Find and print the minimum amount of money Lauren must lose if she buys the house and resells it within the next years.

Note: It’s guaranteed that a valid answer exists.

Input Format
The first line contains an integer, n, denoting the number of years of house data. The second line contains space-separated long integers describing the respective values of p_1, p_2,\dots, p_n.

Constraints
2\le n \le 2 \times 10^5 1 \le p_i \le 10^{16} All the prices are distinct. It’s guaranteed that a valid answer exists.

Output Format
Print a single integer denoting the minimum amount of money Lauren must lose if she buys and resells the house within the next n years.

Sample Input 0

Sample Output 0

Explanation 0
Lauren buys the house in year 1 at price p_1 = 5 and sells it in year 3 at p_3 = 3 for a minimal loss of 5 - 3 = 2.

Sample Input 1

Sample Output 1

Explanation 1
Lauren buys the house in year 2 at price p_2 = 7 and sells it in year 5 at p_5 = 5 for a minimal loss of 7 - 5 = 2.

Sample Input & Output 3
minimum-loss-input
minimum-loss-output

Solution
Naive approach
The naive approach is to iterate over each price p_i and compare it with all the subsequent prices, storing any new found minimum loss based on the two rules stated in the problem statement. This obviously has a running time of \mathcal{O}(n^2).

Binary Search Tree (BST) approach
We can construct a BST from the prices array. The construction has a running time of \mathcal{O}(nlogn). We then go through all the nodes. Starting at node x we traverse up (go to its parent) the BST as long as the current node is not a left child of its parent (or no parent is available). If the current node is a left child then we return the value of its parent. This value is the smallest value that is greater than the value of the original/starting node x. Searching the BST for every node has a total worst case running time of \mathcal{O}(nlogn).

Full code

 

Migrating WordPress site from a legacy hosting provider to AWS

Up until now my blog (lucaslouca.com) was hosted on a traditional/old fashioned hosting provider, Their service provided a fixed 10GB of hosting storage together with FTP access and a cPanel.

So here are the reasons why I switched over to AWS:
– Less expensive
– More flexible due to the fact that you can launch unlimited virtual servers, database instances, configure firewalls, load balancers, etc
– More security: my database isn’t publicly available anymore and sits in a VPC, better user management
– Literally thousands of services from CloudWatch to Lambda

Overall using AWS you have more control over your web applications.

So lets get started with the migration process!

We are going to do the following:
• Setup an EC2 instance using a Basic 64-bit Amazon Linux AMI
• Setup a S3 bucket
• Setup a MySQL RDS Instance
• Migrate old MariaDB database to new AWS DB Instance
• Install Apache Web Server, MySql, PHP, Git and Python on EC2 instance
• Install WordPress on EC2 instance
• Issue a Let’s Encrypt certificate
• Configure Apache Web Server on EC2 for HTTPS

Create an S3 bucket
We will first create an S3 bucket that we can use to store any database dumps and files so we can access them through our new EC2 instance.

To create a new instance, access the AWS Management Console and click the S3 tab. Create a new bucket and give it a name. Mine is named lucaslouca.com-wordpress.

Create an EC2 instance
To create a new instance, access the AWS Management Console and click the EC2 tab:

  • Choose an AMI in the classic instance wizard: I chose the Basic 64-bit Amazon Linux AMI.
  • Instance details: Select the Instance Type you want to use. I chose t2.micro.
  • Create a new key pair. Enter a name for your key pair (i.e. lucasloucacom) and download your key pair (i.e. lucasloucacom.pem).
  • Make sure you create a new security group, give it a name (e.g. lucaslouca.com-security-group) and add inbound rules for SSH, HTTP and HTTPS that allow traffic from all sources.
  • Launch your instance.

Note:For security purposes you can edit the inbound rule for SSH to allow traffic only from your IP address.

Map IP Address and Domain Name
Your EC2 instance has an IP address as well as a DNS name. However, the default IP address is assigned dynamically and might change. You will keep the IP address as long as the instance is running and across reboots, but if you are forced to stop/start or anything like that you will lose it. If you have a domain name pointing to your instance, that is a bad thing. Thats why we need to associate an IP address to our instance and then map your domain name to that IP address.

To associate an IP address to your instance:
In the AWS Management Console, click Elastic IPs (left navigation bar). Click Allocate New Address, and confirm by clicking the Yes, Allocate button.
Select the newly allocated IP address and select Actions -> Associate address in the popup menu. Select the EC2 instance and click Yes, Associate

Note down the new Public DNS (e.g. ec2-35-158-16-195.eu-central-1.compute.amazonaws.com) of our EC2 instance. We will need it later.

Then, go to Route 53-> Hosted zones-> Create Hosted Zone. Amazon will list you four NS servers:

Note them down and login to your domain registrar. Under the DNS Manager delete the NS entries and any A records pointing to your web server. In my domain registrar I have deleted the NS and A entries and edited the names servers for my domain lucaslouca.com to point to the Route 53 provided name servers instead of my hosting providers defaults.

Back in the AWS console go to Route 53-> Hosted zones and select your newly created zone. Click on Create Record Set to setup some A records. Leave Alias to No and paste the elastic IP address of your EC2 instance into the value field. This will create a new A record pointing the domain name lucaslouca.com to the IP 35.158.16.195. You can repeat this for any subdomains also. For example you can click on Create Record Set again and under Name enter www, Alias set to Yes and from the Alias Target target you can select the previously created record (e.g. lucaslouca.com). That way www.lucaslouca.com will also point to the same IP as lucaslouca.com.

Install Updates, Apache Web Server, MySql, PHP, etc
Once the instance is up and running go ahead and ssh to your EC2 instance:

In order to install the required tools and updates run the following commands:

Create a DB instance
Next, we are going to need a MySQL database for our blog.

To create a new instance, access the AWS Management Console and click the Database -> RDS tab. Then click Launch a DB Instance and select MySQL.

Then specify a username, password and database name and make sure Publicly Accessible is set to NO. Make sure you also create a new security group.

Once the instance is created, select it and under Configuration Details click on the security group (e.g. rds-launch-wizard-3). Edit the inbound rules for that group and set the Source for the MYSQL/Aurora type to the security group you created earlier for your EC2 instance (e.g. lucaslouca.com-security-group). This will allow only traffic in that comes from the security group lucaslouca.com-security-group. In other words only traffic that comes from our EC2 web server is allowed in.

Once created note down the endpoint address (e.g. lucaslouca-com-wordpress-db.shsfahjkiahd.eu-central-1.rds.amazonaws.com:3306). You are going to need it later.

Install WordPress
Back in your EC2 shell:

Finaly, adjust wp-config.php to your database settings (i.e. username, passowrd, database name, host) that you created earlier.

By now you should be able to access your newly installed WordPress blog via http://ec2-35-158-16-195.eu-central-1.compute.amazonaws.com.

Export database from old blog
If your hosting server is as crapy as mine and your only option is to use phpMyAdmin then go ahead and login into your phpMyAdmin site. Then, select your blog database from the left side-bar and then go to Export. Select the Custom - display all possible options option and make sure you check the Add DROP TABLE / VIEW / PROCEDURE / FUNCTION setting. This will drop (delete) the table if it exists and recreate it in the database you are importing it to. For Format select SQL. and click Go.

Once you have your OLD_DB.sql go ahead and upload it to your S3 Bucket.

Backup wp-content from old blog
You also want to migrate any existing themes, plugins etc to your new AWS hosted blog. For that you need to migrate the contents of wp-content from your old blog into your newly installed wordpress blog. So for that you need to connect to your old hosting provider via FTP, navigate to your blog directory and download the entire wp-content directory. Archive it using:

Then go ahead and upload wp-content.tar to your S3 Bucket.

Create a new AMI access role for your EC2 instance
We need to be able to access our S3 bucket through our EC2 instance, so we can download our backed-up database and wp-content files. For that you need to login into your AWS console and navigate to your EC2 instance.

Select your EC2 instance and under Actions select Instance Settings -> Attach/Replace IAM role. From there you can select an existing role or create a new one by clicking Create new IAM role. Alternatively you can create a new role by from Services -> Security, Identity & Compliance -> IAM -> Roles -> Create new role.

So go ahead and create a new role providing it the policy AmazonS3FullAccess and attach the new role to your EC2 instance.

Access S3 from EC2
OK, once you have attached an IAM role with AmazonS3FullAccess policy to your EC2 instance you can go ahead and ssh to your EC2 instance:

Once you are logged in create a directory to sync our S3 bucket into:

Then try and sync the S3 bucket using:

In order to get the correct region type:

Then configure your aws client tot use it as the default region:

Verify your configuration using:

And then go ahead and try and sync your S3 bucket again:

Your files are now accessible under lucaslouca.com-wordpress/

Import old database into AWS hosted database
Go ahead and ssh to your EC2 instance:

And import your old database into your AWS RDS database:

Linking to new URL and defining new domain
Next you need to update any existing old URLs in your db to your new AWS URL. For that I temporary made my DB Instance Publicly Accessible and edited the security group’s inbound rules to allow any source (i.e. 0.0.0.0/0). That way I could access my db through a nice GUI SQL client (I used Sequel Pro) and run the following SQL:

Of course you could again ssh into your EC2 and use the mysql command.

Note: Once you are done do not forget to disable Publicly Accessible and remove the added inbound rules from the security group.

WordPress pretty permalinks on Amazon EC2 Linux instance
You will need to edit /etc/httpd/conf/httpd.conf and change AllowOverride None to AllowOverride All. So it should look like so:

Note: AllowOverride None appears two times in /etc/httpd/conf/httpd.conf and you need to change it in all cases.

Then, navigate to /var/www/html/blog and create an .htaccess file that looks like so:

Also create a .htaccess file under /var/www/html/ to route lucaslouca.com/ to lucaslouca.com/blog

This will transparently redirect all requests to /blog/{requested_resource}. If you have other subfolders that need to be excluded from this redirect you can just an .htaccess file in those directories saying:

For example, I wanted to leave https://lucaslouca.com/bargain and it’s content alone completely so I have just added such an .htaccess file under /var/www/html/bargain.

Finally, you then need to restart apache:

You should be able to view your old posts etc under the new host http://ec2-35-158-16-195.eu-central-1.compute.amazonaws.com.

Updated WordPress site URLs
In the previous section we updated out database entries to point to our ec2-35-158-16-195.eu-central-1.compute.amazonaws.com domain. That way we could continue working until the NS and A records are updated. We can run the sql script again to point to our domain name (http://lucaslouca.comNote: http and not https).

You may need to temporary make your DB Instance Publicly Accessible and edit the security group’s inbound rules to allow any source (i.e. 0.0.0.0/0). That way you can access your db through a nice GUI SQL client (I used Sequel Pro) and run the following SQL:

Enable HTTPS
We already enabled any HTTPS traffic in our lucaslouca.com-security-group. We now need to configure our Apache server to also listen on port 443 in order for us to be able to access our blog via HTTPS. For that we first need to obtain a CA-signed certificate. We will use Let’s Encrypt for our CA.

Add the following to your /etc/httpd/conf/httpd.conf:

Install python and git on your EC2:

Get the letsencrypt client:

Create a config file that will be used for new certificates and renewals. It contains the private key size and your email address.

Important: Before you run letsencrypt temporary disable /var/www/html/.htaccess:

Run letsencrypt:

Note: If you are trying to letsencrypt your AWS domain (e.g. ec2-35-158-16-195.eu-central-1.compute.amazonaws.com) and you are getting an error its because amazonaws.com happens to be on the blacklist of Let’s Encrypt.

Enable /var/www/html/.htaccess and clean up:

The certificates are located at /etc/letsencrypt/live/ and the last thing is to update your webserver’s configuration. So edit your /etc/httpd/conf.d/ssl.conf file:

Restart apache:

Try and access https://lucaslouca.com. It should work!

Finally, add the renew command in a crontab. Refresing your webserver command should also be here.

Updated WordPress site URLs
In the previous section we updated out database entries to point to our http://lucaslouca.com domain. Now that we got HTTPS up and running we can update our WordPress site URLs to point to HTTPS.

You may need to temporary make your DB Instance Publicly Accessible and edit the security group’s inbound rules to allow any source (i.e. 0.0.0.0/0). That way you can access your db through a nice GUI SQL client and run the following SQL:

Note: Once you are done do not forget to disable Publicly Accessible for your db instance and remove the added inbound rules from the security group.

Give Apache apache access to the folders
An issue still exists when you try to update/install plugins etc. The issue is that apache does not have access to the folders. The default permission is given to the ec2-user in the AMI.

Run this in your EC2 shell and you should be good to go:

Thats it guys!!

 

Word in string challenge

Problem statement
We say that a string, s, contains the word hackerrank if a subsequence of the characters in s spell the word hackerrank. For example, haacckkerrannkk does contain hackerrank, but haacckkerannk does not (the characters all appear in the same order, but it’s missing a second r).

More formally, let p_0, p_1, \dots, p_9 be the respective indices of h, a, c, k, e, r, r, a, n, k in string s. If p_0 \textless p_1, \textless p_2 \dots \textless p_9 is true, then s contains hackerrank.

You must answer q queries, where each query i consists of a string, s_i. For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Input Format
The first line contains an integer denoting q (the number of queries).
Each line i of the q subsequent lines contains a single string denoting s_i.

Output Format
For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Sample Input 0

Sample Output 0

Solution

 

Recursive Digit Sum challenge

Problem statement
We define super digit of an integer x using the following rules:

  • If x has only 1 digit, then its super digit is x.
  • Otherwise, the super digit of x is equal to the super digit of the digit-sum of x. Here, digit-sum of a number is defined as the sum of its digits.

For example, super digit of 9875 will be calculated as:

You are given two numbers n and k. You have to calculate the super digit of P.

P is created when number n is concatenated k times. That is, if n = 123 and k = 3, then P=123123123.

Input Format
The first line contains two space separated integers, n and k.

Constraints
1 \le n \textless 10^{100000}
1 \le k \le 10^{5}

Output Format
Output the super digit of P, where P is created as described above.

Sample Input 0

Sample Output 0

Explanation 0
Here n=148 and k=3, so P=148148148.

Sample Input 1
recursive-digit-sum-input-1

Sample Output 1
recursive-digit-sum-output-1

Solution

 

Random video chat website using WebRTC

Seing as how many people are interested in my video-conference-webrtc project, I have decided to develop a random video chat website using WebRTC. The project is called rtcrandom and is hosted on GitHub. A live demo is also available at test.tengmo.chat.

Pitch

RTCRandom is an online (video)chat website that allows users to socialize with others without the need to register. The service       randomly pairs users in one-on-one chat sessions where they chat anonymously using the names “You” and “Stranger”.

For the project I have used GitHub for my online project hosting service using Git, issue tracking, collaboration and wikis. Node.js and JavaScript are the main programming languages used for development. For continuous integration I am using Jenkins with OpenShift as my hosting service. The wiki is available here.

I not going into great detail explaining the code. I will rather give you a brief overview on how rtcrandom works and leave the pleasure of examining the code to you.

Back-End
For the back-end Node.js is used with Express as the web application framework. I used winston for logging and EJS as the templating language for the views.

Front-End
For the front-end simple HTML with JavaScript (jQuery, socket.io) and CSS is used. In order to add WebRTC support for browsers like Safari (which does not support WebRTC yet) I have used the Temasys WebRTC adapter. If you do not wish to use such an adapter see release v0.1-alpha.

Main components
On the back-end the main component is server.js and on the front-end the magic happens in public/js/room.js, which is loaded by the views/room.ejs view.

How does the matching work
When a client first loads the page a bidirectional event-based communication is created between the client’s browser and the back-end using socket.io. I call this the default communication channel. The default communication channel is used by the client to let the server know, that the client wants to find a new chat partner etc. It also allows the server to inform a client about a new chat partner etc.

So once a client wants to find a new (or initial) communication partner he triggers a next event through the default communication channel, letting the server know about its ID and that he wants a new chat partner. The ID is a random hash that is generated once on client-side. The server then puts the client’s request into a queue and checks if the queue has at least two requests (note: no client is put twice in the queue). If at least two requests are in the queue (one from a different client and one from our current client), the two clients are polled from the queue. The server then generates a random room name (a random six digit alphanumeric string) and sends it to the two clients via the default communication channel.

Once each client receives the new room name, they send a message to the server via the default channel that they want to join the room. The client whose message arrives first at the server creates and joins the room and the second client simply joins the new room. The peer that simply joins the new room gets notified by the server that it just joined, so that it can broadcast the message to the default channel saying that it is a new participant that joined the room and wants to receive a WebRTC offer to open up a peer-to-peer WebRTC communication with the other client in the room (the one that created the room). The room creator then receives the new participant message in the default channel and creates an offer for the joining peer. This offer will be send via a private communication channel which both clients open using the room name as namespace. The room creator then sends the offer through this channel, which the other peer receives and responds to with an answer. Further WebRTC related communication messages to build the WebRTC peer-to-peer connection between the two clients are also exchanged through the private channel. Once a peer-to-peer connection is establish the video stream and chat messages are exchanged directly between the two clients (no server required).

Note: when a peer disconnects from one peer (e.g. because it wants to chat with a different person) the disconnect event is not immediately received by the other peer, due to WebRTC delays. This is why the disconnecting peer also sends a disconnect notification message to the other peer via the private channel, so that it can update its view. The notification is send using the private channel because it tends to be faster than waiting for the WebRTC notifications.

The source code is available here. A live demo is available at test.tengmo.chat.