Beautiful quadruples challenge

Problem statement
We call an quadruple of positive integers, (W, X, Y, Z), beautiful if the following condition is true:

W \oplus X \oplus Y \oplus Z \ne 0

Note: \oplus is the bitwise XOR operator.

Given A, B, C and D, count the number of beautiful quadruples of the form (W, X, Y, Z) where the following constraints hold:

1 \le W \le A
1 \le X \le B
1 \le Y \le C
1 \le Z \le D

When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:
– They contain same integers.
– Number of times each integers occur in the quadruple is same.

For example (1, 1, 1, 2) and (1, 1, 2, 1) should be considered as same.

Input Format
A single line with four space-separated integers describing the respective values of A, B, C and D.

Constraints
1 \le A, B, C, D \le 3000

Output Format
Print the number of beautiful quadruples.

Sample Input

Sample Output

Explanation
There are 11 beautiful quadruples for this input:
(1,1,1,2)
(1,1,1,3)
(1,1,1,4)
(1,1,2,3)
(1,1,2,4)
(1,1,3,4)
(1,2,2,2)
(1,2,2,3)
(1,2,2,4)
(1,2,3,3)
(1,2,3,4)

Thus, we print 11 as our output.
Note that (1, 1, 1, 2) is same as (1, 1, 2, 1) .

Solution
Since the order of the integers in a quadruple does not matter we can sort our input values such that A \le B \le C \le D:

We will then solve it for the first half of the quadruple (a,b,c,d). For that we define the following arrays:
total = new int[3001]: total[B] holds the number of pairs \{ a,b\} such that a \le b with 1 \le a \le A and 1 \le b \le B:

count = new int[3000 + 1][4096 + 1]: count[B][x] holds the number of pairs \{a,b\} such that a \le b and a \oplus b = x with 1 \le a \le A and 1 \le b \le B:

Note here that the maximum XOR value achievable is 4096 since 1 \le A, B, C, D \le 3000 (12 bits).

We can now go ahead and use total and count to find our solution. Remember we sorted our A \le B \le C \le D so that we count our quadruples (a,b,c,d) such that a \le b \le c \le d.

For the second half of (a,b,c,d) we have \{c,d\} with 1 \le c \le C and 1 \le d \le D. Let c \oplus d = y. We know that a \oplus b \oplus c \oplus d = 0 if a \oplus b = y. We know that we have a total of total[c] pairs \{a,b\} with a \le b and 1 \le b \le c. We want to exclude the pairs that have a \oplus b = y. There are count[c][y] pairs \{a,b\} that combined with \{c,d\} result to 0. So from total[c] we have to exclude count[c][y] and do this for all possible c and d:
\sum_{c=1}^{C}\sum_{d=1}^{D}total[c]-count[c][c \oplus d]

The full code is listed below.

Full code

 

Sort hotel list challenge

Problem statement
Given a set of hotels and its guests reviews, sort the hotels based on a list of words specified by a user. The criteria to sort the hotels should be how many times the words specified by the user is mentioned in the hotel reviews.

Input
The first line contains a space-separated set of words which we want to find mentions in the hotel reviews.

The second line contains one integer M, which is the number of reviews.

This is followed by M+M lines, which alternates an hotel ID and a review belonging to that hotel.

Output
A list of hotel IDs sorted, in descending order, by how many mentions they have of the words specified in the input.

Notes
– The words to be find will always be singe words line ‘breakfast’ or ‘noise’. Never double words like ‘swimming pool’.
– Hotel ud is a 4-byte integer.
– Words match should be case-insensitive.
– Dots and commas should be ignored.
– If a word appears in a review twice, it should count twice.
– If two hotels have the same number of mentions, they should be sorted in the output based on their ID, smallest ID first.
– In case one or more test cases time out, consider revisiting the runtime complexity of your algorithms.

Sample input

Sample output

Explanation
Hotel 2 has 7 mentions of the words: ‘location’ and ‘citycenter’ are mentioned twice while ‘breakfast’, ‘price’ and ‘staff’ are mentioned once. Hotel 1 in the other hand has 6 mentions in total ‘location’ and ‘citycenter’ also twice and then ‘view’ and ‘metro’ once.

Solution/Full code

 

Delta encoding challenge

Problem statement
Given a list of numbers, e.g.:

Output a delta encoding for the sequence. In a delta encoding, the first element is reproduced as is. Each subsequent element is represented as the numeric difference from the element before it. E.g. for the sequence above, the delta encoding would be:

However, if a difference value does not fit in a single signed byte, i.e. -127 \le x \le 127, then, instead of the difference, we would like to use an escape token, printing it.

This will denote that the value following the escape token is a full four-byte difference value, rather than a one-byte different value.

For this exercise, we’ll declare -128 as the escape token.

Following the same example above, the final result would be:

Solution

 

Sum of 2 numbers in an array

Problem statement
Identify whether there exists a pair of numbers in an array such that their sum is equal to N.

Input
The first line contains one integer N, which is the sum we are trying to find. The second line contains one integer M, which is the length of the array. This is followed by M lines each containing one element of the array.

Output
Output 1 if there exists a pair of numbers in the array such that their sum equals N. If such a pair does not exist, output 0.

Sample Input

Sample Output

Solution

 

Polygons challenge

Problem statement
Identify whether four sides (given by four integers) can form a square, a rectangle, or neither.

Input
You will receive an list of strings, each containing four space-separated integers, which represent the length of the sides of a polygon. The input lines will follow the ‘A B C D’ order as in the following representation:

Output
A single line which contains 3 space-separated integers; representing the number of squares, number of rectangles, and number of other polygons with 4 sides. Note that squares shouldn’t be counted as rectangles. Invalid polygons should also be counted as ‘other polygons’.

Constraints
The four integers representing the sides will be such that: -2000 \le x \le 2000 (Where x represents the integer)

Sample Input

Sample Output

Solution

 

Binary Search Tree to sorted doubly-linked list

Problem statement
Given the root of a Binary Search Tree (BST), convert the BST to a sorted doubly linked list in-place. BST is formed only on left and right pointers. prev and next pointers are unassigned initially. Initialise prev and next pointers of Node for creating a doubly-linked list. BST and doubly-linked list should co-exist in the same structure. The abstract structure of Node is given as follows:

Sample input
Binary Search Tree (BST) to sorted doubly-linked list

Sample output
Binary Search Tree (BST) to sorted doubly-linked list

Solution
We will solve this problem using in-order tree traversal. The way in-order tree traversal works, is as follows: the left subtree is visited first, then the root and later the right sub-tree.

Obviously if a BST is traversed in-order, the output will produce sorted values in an ascending order.

Since we want a doubly-linked list as our result we will need to keep track of the first element in the list, head. We also need to keep track of the previously visited element, prev, so that we can set it as the current node’s previous node.

Initially, both head and prev are set to null. We then traverse the left subtree all the way down. When there is no more left subtree left to traverse we know we have reached the smallest element. This element is going to be our head (first element in the list). We set the current node’s previous link to point to prev (Note: for head previous will point to null). We also set the prev (if prev is not equal to null) node’s next to point to the current node. Then, before we continue with the right subtree we set prev to the current node. We then recursively call the in-order function for the right subtree.

The full code is listed below.

Full code

 

The maximum continuous and non-continuous subarray challenge

Problem statement
Given an array A=\left[a_1, a_2, \dots, a_N\right] of N elements, find the maximum possible sum of a
1. Contiguous subarray
2. Non-contiguous (not necessarily contiguous) subarray.

Empty subarrays/subsequences should not be considered.

Input Format

First line of the input has an integer T. T cases follow.
Each test case begins with an integer N. In the next line,N integers follow representing the elements of array A.

Constraints
1 \le T \le 10
1 \le N \le 10^5
-10^4 \le a_i \le 10^4

The subarray and subsequences you consider should have at least one element.

Output Format
Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).

Sample Input

Sample Output

Explanation
In the first case:
The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).

In the second case:
\left[2, -1, 2, 3, 4\right] –> This forms the contiguous sub-array with the maximum sum.
For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.

Solution for contiguous subarray
We first need to initialise our current sum and max variable with some value. For that we can use sum = max = a[0].

Next, we are going to iterate over our array (starting from index 1) and have a look at the current elements. If the current element a[i] is greater than sum + a[i], then we might as well try a new sum starting from element a[i] and discard the current sum. This is because adding sum to a[i] only decreases a[i], we might be better off starting a new sum with just a[i].

If the current element a[i] is not greater than sum + a[i], that is a[i] becomes greater by adding the current sum, then it doesn’t make sense to try starting a new sum from just a[i] and we might be better off carrying the current sum with us.

Above I have used the term might. This is due to the fact that we need to check if we have a new maximum sum every time we update sum.

The full code for the continuous part is listed below:

The running time of this algorithm is \mathcal{O}(n)

Solution for non-contiguous subarray
For the non-contiguous subarray version of this problem we are going to sort our array first in ascending order. Then we can iterate over our array from right to left and keep adding elements to our current sum, sum, until we have iterated over all elements or reached a point where adding an element to sum only decreases it.

For example the input \left[2, -1, 2, 3, 4, -5\right] will become \left[-5, -1, 2, 2, 3, 4\right] after sorting. Then starting with sum = 4 we continue updating sum. Next, sum becomes sum = 4 + 3 = 7. Then it becomes sum = 7 + 2 = 9. Continuing, sum becomes sum = 9 + 2 = 11. We then reach the element a[1] = -1 which would decrease sum (11 - 1 < 11), so we stop since all elements that would follow -1, would be smaller than -1 and will also just decrease sum.

The full code for the non-continuous part is listed below:

The running time of this algorithm is \mathcal{O}(nlogn)

The full code for both version is listed below.

Full code

 

Deploy a Node.js app to OpenShift from a private GitHub repository

Assuming you have an OpenShift account go ahead and login. Otherwise create an account first.

Next, login to OpenShift’s web console, create a new Node.js application by clicking on Add Application… and then selecting Node.js 0.10.

Fill out the fields such as Public URL (e.g. testnode) and leave the rest with their default value and click on Create Application.

Once your application is created you will receive a repository URL to a newly created Git repository hosted on OpenShift similar to:

Install the OpenShift client tools:

Once installed, run the rhc setup command to configure the client tools. The setup wizard generates a new pair of SSH keys in the default .ssh folder of your home directory. The setup requires your OpenShift username and password.

Next clone your GitHub repository:

Add a new remote called openshift and merge your Github repository into your Openshift repository:

The git push openshift HEAD starts a new Jenkins build and deploys your Node.js application. Once it is done, you can access your Node.js application at https://testnode-lukesnode.rhcloud.com.

You can also go ahead and clone your OpenShift repository if you want to:

This includes an .openshift directory which contains various OpenShift metadata and configuration that are important for deployment.

(Optional) Setting up environment variables
It is often the case that your web application requires some sort of configuration for certain functionalities such as an email contact form. This configuration may include parameters such as username and password for the mail server. This configuration is usually done using a sensitive.config.js file which you include in your Node.js application using:

Since you want to avoid hardcoding usernames and passwords in source code files you can parse these to your application though environment variables. So at the end of the day your sensitive.config.js configuration file may look as follows:

and your repository stays clean from sensitive information. The process.env property returns an object containing the user environment. process.env is followed by the name of the variable you wish to access such as MAIL_USERNAME and MAIL_PASSWORD in our case. See more under process.env documentation.

Now, we need to setup these environment variables in OpenShift. So go ahead, fire up your Terminal and enter:

What is left to do is restart you Node.js application through the OpenShift web console.

(Optional) Skip OpenShift Git repository
You can also configure OpenShift to use only your GitHub repository for deployment by enabling Jenkins. In you web console select your Node.js application and click on Enable Jenkins. This will provide you with a Jenkins URL (e.g. https://jenkins-lukesnode.rhcloud.com/) along with a username and password. Open up you Jenkins URL and login using the provided username and password.

Taking a look at the build project’s configuration you can see that OpenShift already filled in the shell command to be executed on build:

If your repository is a private repository OpenShift will not be able to download the source code as it will not have the credentials to authenticate itself against the git repository.

To configure Jenkins to use GitHub we need to install some plugins. First, download the following Jenkins plugins:
github-api
plain-credentials
token-macro
credentials
structs
workflow-step-api
workflow-scm-step
scm-api
git-client
git
github

In Jenkins, go to Manage Jenkins then Manage Plugins and then Advanced. Then under Upload Plugin click Choose File and upload the .hpi file to install the plugin. Do this for all the plugins in the given order:
1. github-api
2. plain-credentials
3. token-macro
4. structs
5. workflow-step-api
6. workflow-scm-step
7. scm-api
8. credentials
9. git-client
10. github
11. git

Next, go to Jenkins -> Credentials -> System -> Global credentials and click Add Credentials. Choose Kind: Username with password and Scope: Global. Enter your GitHub credentials and click OK to save.

Next, go to Jenkins -> Credentials and click on Add Domain. Enter api.github.com and click OK to save.

Next, go to Jenkins -> Credentials -> System -> api.github.com and click Add Credentials. Then open GitHub in a new tab and generate a new Personal Access Token. Select the scopes repo and admin:repo_hook and click Generate token.

Back in Jenkins, select Kind: Secret text and paste your access token in the Secret field. Give your credentials a Description (e.g. GitHub access token) and hit OK to save.

Then go to Manage Jenkins -> Configure System and in the GitHub section and a new GitHub server and make sure the API URL is set to https://api.github.com. Select GitHub access token in the Credentials drop down and click Test connection. Everything should work ok. Click Save.

We want GitHub to notify your Jenkins instance whenever you push commits to the repo. We’ll use Webhooks for this. Go to your GitHub repository settings (e.g. https://github.com/lucaslouca/foobubble/settings) and click on Webhooks. Then click Add webhook. Under Payload URL enter https://jenkins-lukesnode.rhcloud.com/github-webhook/ and choose the Content type application/x-www-form-urlencoded. Finally, click Add webhook.

Back to Jenkins, navigate to your Jenkins build project’s configuration page. Find the checkbox GitHub project and check it. For Project url enter your GitHub repository URL (e.g. https://github.com/lucaslouca/foobubble).

In the Source Code Management choose Git and again enter your GitHub repository URL (e.g. https://github.com/lucaslouca/foobubble). For Branches to build set it to */master. For Credentials choose the username/password credentials you made earlier from the dropdown.

Scroll down to the Build Triggers section and check Build when a change is pushed to GitHub and click Save to save the changes.

Now when you push to your GitHub repository Jenkins will be notified via the Webhook and will start a new build. It will use the GitHub repository URL you specified under Source Code Management.

Thats it! Happy continuous delivery!

The Node.js application used in this tutorial is live at foobubble.com.

 

The inquiring manager challenge

You are responsible for auditing all customer orders. Each order has a price, P_i, and a timestamp, T_i, denoting the minute when it was received.

At any given time, your manager can ask you for the maximum price of any order placed within the last 60 minutes. For example, if your manager stops in at minute 83, you must know the maximum price of any order received between minutes 24 and 83. Observe that you must also account for orders received in the same minute as your manager arrived.

You are given a list of N events, where each event represents either a received order or an inquiry. For each inquiry from your manager, print the maximum price for any order placed within the last 60 minutes on a new line.

Input Format
The first line contains a single integer, N, denoting the number of events. Each of the N subsequent lines describes either of the following types of events:
1 P T – An order with price P was placed at time T.
2 T – Your manager stopped in at time T to inquire about the maximum order price for the last 60 minutes.
All the events are given in non-decreasing order with respect to T, so for i \textless j, we have T_i \le T_j.

If there are multiple events of different types occurring at the same time, the received orders will be listed before manager inquiries.

Constraints
1 \le N \le 10^6
0 \le P_i,T_i \le 10^{18}

Output Format
For each event of type 2, print a number denoting the maximum price for any order placed within the previous 60 minutes on a new line. If no orders were placed during that interval, print -1.

Assume there will be at least one event of type 2.

Sample Input

Sample Output

Explanation
The largest order price in time range \left[0,40\right] is 150.
The largest order price in time range \left[0,59\right] is still 150.
The largest order price in time range \left[1,60\right] is 143.
The largest order price in time range \left[2,61\right] is 159.
The largest order price in time range \left[61,120\right] is still 159.
There were no orders placed in time range \left[62,121\right], so we print -1 for this inquiry.

Solution
We will solve this using a Map time2price, with time2price[t] holding the maximum price at exactly time t. While we read our input we check if it is an order or inquiry. If we have an order we check if we already have a price for the current time t (as multiple orders can be made at the same time). If we already have a price we choose the maximum between the existing and the new price. If we do not have a price for t, we insert it into our map.

Since we don’t want our map to grow unnecessarily, we remove entries that we don’t consider relevant anymore every time we read a new price. Those entries are prices with a timestamp \textless t - 60. That way our map will hold a maximum of 60 entries at any given time.

Now, if we get an inquiry, we just need to search our map for the maximum price and print it.

Full code

 

Bike racers challenge

Problem statement
There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers want to participate in the HackerRace competition, but unfortunately only K bikers can be accommodated in the race. Jack is organizing the HackerRace and wants to start the race as soon as possible. He can instruct any biker to move towards any bike in the city. In order to minimize the time to start the race, Jack instructs the bikers in such a way that the first K bikes are acquired in the minimum time.

Every biker moves with a unit speed and one bike can be acquired by only one biker. A biker can proceed in any direction. Consider distance between bikes and bikers as Euclidean distance.

Jack would like to know the square of required time to start the race as soon as possible.

Input Format
The first line contains three integers, N, M, and K, separated by a single space. The followingN lines will contain N pairs of integers denoting the co-ordinates of N bikers. Each pair of integers is separated by a single space. The next M lines will similarly denote the co-ordinates of the M bikes.

Constraints
1 \le N \le 250
1 \le M \le 250
1 \le K \le min(N,M)
0 \le x_i, y_i \le 10^7

Output Format
A single line containing the square of required time.

Sample Input

Sample Output

Explanation
There’s need for two bikers for the race. The first biker (0,1) will be able to reach the first bike (100,1) in 100 time units. The second biker (0,2) will be able to reach the second bike (200,2) in 200 time units. This is the most optimal solution and will take 200 time units. So output will be 200^2 = 40000.

Solution
We will solve this problem using bipartite matching. We will construct a bipartite graph where we connect bikers with bikes iff the biker is within \le t distance from the biker. We will then add a source and target node similar to the students and dorms problem to our bipartite graph. That is, source node will have outgoing edges to all the bikers while target node will have incoming edges from all the bikes in the bipartite graph. Similar to the students and dorms problem, all edges have a capacity of 1.

Once we have our bipartite graph, we can solve the maximum flow problem using the Ford-Fulkerson algorithm. We keep solving the maximum flow problem for all possible t until maximum flow is \ge k and t is minimum. Once we have a minimum t for a maximum flow \ge k we print t \times t as our answer.

Since the resulting distance needs to be squared and 0 \le x_i, y_i \le 10^7 we know that our return value t \times t must be 0 \le t \times t \le 100000000000000. We also know that when maximum flow is \ge k for some T, it will also be \ge k for some T'\textgreater T. This will enable us to perform a binary search in the interval 0\dots 100000000000000 until we find a t \times t for which the graph connecting bikers and bikes with distance \le t, has maximum flow \ge k and t minimum.

Node: Since the Euclidean distance is defined as \sqrt{(x_1-x_2)\times(x_1-x_2) + (y_1-y_2)\times(y_1-y_2)} we can omit the square root since we are comparing with t \times t. That is because the relation \sqrt{(x_1-x_2)\times(x_1-x_2) + (y_1-y_2)\times(y_1-y_2)} \times \sqrt{(x_1-x_2)\times(x_1-x_2) + (y_1-y_2)\times(y_1-y_2)} \le t \times t is the same as (x_1-x_2)\times(x_1-x_2) + (y_1-y_2)\times(y_1-y_2) \le t \times t.

Also, because creating a BigInteger is expensive to do every time we compute a distance for each maximum flow calculation, we pre-compute the distances and store them in a BigInteger[][].

The full code is available below.

Full code