JLTi Code Jam – Sharing Experiences

Currency Arbitrage with Decreasing Rate

12^th JLTi Code Jam – Feb 2018

Here we extend the Currency Arbitrage problem that expected us to re-compute the best path cost matrix when a new currency arrived along with some rates from and/or to the existing currencies. We came up with a solution at O(n²) cost.

If we look at the currency exchange issues, we realize that new currencies are not arriving every day. Rather, rates among the existing currencies are the ones which are changing every now and then. So it’s equally, if not more, important to find a solution as to how to address the rate changes and compute the cost matrix.

Rate between two currencies can either increase or decrease. Here we will focus only on rate decrease.

Given that we have an existing best path cost matrix, when a rate between two currencies decreases what shall we do? Well, just like Currency Arbitrage problem, we have two options: i) re-compute the cost matrix from the scratch, using Floyd-Warshall, at a cost O(V³) and ii) update the already computed cost matrix using some partial computations. This problem expects a solution using the second option.

Input:

1 USD = 1.380 SGD

1 SGD = 3.080 MYR

1 MYR = 15.120 INR

1 INR = 0.012 GBP

1 GBP = 1.30 USD

I CAD = 0.57 GBP

1 GBP = 1.29 USD

Explanation: We have 7 inputs here. Each time an input is given, we need to present an output and hence, we have 7 lines of output. We already know how to incrementally add a new currency. The first 4 do not result in any arbitrage; we output “No luck here”. For 5^th, we have an arbitrage and we output the same. For 6^th, we continue to have the same arbitrage and we again output the same.

At 7^th input, we see the existing rate from GBP to USD, which was 1.30 last time, has changed to 1.29 now. With this new rate in effect, the arbitrage disappears now. Output should be “No luck here”.

Since we are dealing with only decreasing rate, in input, between two currencies, rate will only decrease. For example, an input like 1 GBP = 1.31 USD will never appear.

When multiple arbitrages exist, printing any one will do.

Output:

No luck here

USD -> SGD -> MYR -> INR -> GBP -> USD

No luck here

Task: For each line of input, for each new vertex, incrementally adjust/add shortest paths at a cost (time) of O(|V|²), detect the presence of an arbitrage and output as specified. Use existing solution for this.

If input contains a rate that decreases since last time, accommodate that change in the best path cost matrix using some partial computations, instead of computing the whole matrix from the scratch.

Index

Solution – Currency Arbitrage

49^th Friday Fun Session – 2^nd Feb 2018

Negative Cycle can be identified by looking at the diagonals of the dist[][] matrix generated by Floyd-Warshall algorithm. After all, diagonal dist[2][2] value is smaller than 0 means, a path starting from 2 and ending at 2 results in a negative cycle – an arbitrage exists.

However, we are asked to incrementally compute the same, at cost of O(n²) for each new vertex.

Floyd-Warshall algorithm takes O(n³) time to compute All-Pairs Shortest Path (APSP), where n is the number of vertices. However, given that it already computed APSP for n nodes, when (n+1)^th node arrives, it can reuse the existing result and extend APSP to accommodate the new node incrementally at a cost of O(n²).

This is the solution for JLTI Code Jam – Jan 2018.

Converting Rates

If USD to SGD rate is r₁ and SGD to GBP rate is r₂, to get the rate from USD to GBP, we multiply the two rates and get the new rate that is r₁*r₂. Our target is to maximize rate, that is maximizing r₁*r₂.

In paths algorithm, we talk about minimizing path cost (sum). Hence maximizing multiplication of rates (r₁*r₂) would translate into minimizing 1/(r₁*r₂) => log (1/(r₁*r₂)) => log (r₁*r₂)^-1 => – log r₁ – log r₂ => (–log r₁) + (–log r₂) => sum of (–log r₁) and (–log r₂). Rate r₁ should be converted into – log r₁ and that is what we need to use in this algorithm as edge weight.

While giving output, say the best rate from the solution, the rate as used in the dist[][] matrix should be multiplied by -1 first and then raised to the b^th power, where b is the base (say one of 2, 10 etc.) of the log as used earlier.

Visualizing Floyd-Warshall

We have seen the DP algorithm that Floyd-Warshall deploys to compute APSP. Let us visualize to some extent as to how it is done for 4 vertices.

What Cells Are Used to Optimize

The computation will be done using k = 1 to 4, in the following order – starting with cell 1-1, 1-2, . . . . .2-1, 2-2, …….3-1, ……. 4-3, 4-4.

At first, using k = 1.

Let us see how the paths are improving using the following two examples.

dist[2][3] = min (dist[2][3], dist[2][1] + dist[1][3])

and dist[3][4] = min (dist[3][4], dist[3][1] + dist[1][4])

We see that for k = 1, all paths are optimized using paths from 1^st (k^th) row and 1^st (k^th) column.

K^th Row and Column do not Change

What about paths on k^th row and k^th column?

dist[1][2] = min(dist[1][2], dist[1][1] + dist[1][2]) – well, there is no point in updating dist[1][2] by adding something more to it.

So we see, at a certain k^th iteration, k^th row and k^th column used to update the rest of the paths while they themselves are not changed.

At k = 1

At k = 2

At k = 3

At k = 4

Consider Only 3X3 Matrix Was Computed

Now assume that we did not consider that we had 4 vertices. Rather we considered that we had 3 vertices and completed APSP computations for all paths in the 3X3 matrix. We ignored the 4^th row and column altogether.

So we have APSP computed for the following matrix using k = 1, 2 and 3.

Add 4^th Vertex

Let’s say, 4^th vertex arrives now. First, we can compare the computations used for the above 3X3 matrix with the same for the 4X4 matrix as shown earlier and find out what all computations need to be done now to extend this 3X3 matrix to 4X4 matrix to accommodate the new 4^th vertex.

We will find that at first we have to optimize the 4^th row and column using k = 1, 2 and 3. Let us do that.

Note that at this point, 4^th row and column are not used to optimize paths for the older 3X3 matrix. So now that we have the 4^th row and column optimized using k = 1, 2 and 3, we have to optimize that 3X3 matrix using k = 4.

This way, we don’t miss out any computation had we considered all the 4 vertices at one go. And thus we are done with optimizing all the paths in the 4X4 matrix.

Code

dist[][] //APSP matrix, already computed for n-1 vertices

p[][] //predecessor matrix, already computed for n-1 vertices


dist[n][] = ∞

dist[][n] = ∞

dist[n][n] = 0


for each edge (i, n)

  dist[i][n] = weight(i, n)

  p[i][n] = n


for each edge (n, i)

  dist[n][i] = weight(n, i)

  p[n][i] = i


for k = 1 to n-1

  for i = 1 to n-1

    if dist[i][n] > dist[i][k] + dist[k][n]

      dist[i][n] = dist[i][k] + dist[k][n]

      p[i][n] = p[i][k]

  for j = 1 to n

    if dist[n][j] > dist[n][k] + dist[k][j]

      dist[n][j] = dist[n][k] + dist[k][j]

      p[n][j] = p[n][k]


for i = 1 to n-1

    for j = 1 to n-1

      if dist[i][j] > dist[i][n] + dist[n][j]

        dist[i][j] = dist[i][n] + dist[n][j]

        p[i][j] = p[i][n]

Complexity

The complexity for this incremental building for a new vertex is clearly O(n²). That makes sense. After all, for n vertices the cost is O(n³) that is the cost of Floyd-Warshall, had all n vertices were considered at one go.

But this incremental building makes a huge difference. For example, consider that we have 1000 vertices for which we have already computed APSP using 1 billion computations. Now that 1001^st vertex arrives, we can accommodate the new vertex with a cost of 1 million (approx.) computations instead of doing 1 billion+ computations again from the scratch – something that can be infeasible for many applications.

Printing Arbitrage Path

We can find the first negative cycle by looking (for a negative value) at the diagonals of the dist[][] matrix, if exists and then print the associated path. For path reconstruction, we can follow the steps as described here.

GitHub: Code will be updated in a week

Index

Currency Arbitrage

11^th JLTi Code Jam – Jan 2018

Here we revisit Manipulating Money Exchange problem where we tried to find currency arbitrage using Bellman-Ford at a time complexity of O(|V||E|).

In general, this kind of graph can be dense. Suppose, there are 4 currencies: USD, SGD, GBP and INR. Usually, a rate is given from each currency to all other currencies, resulting in |V|² edges. Hence, Bellman-Ford ends up with O(|V||E|) = O(|V||V|²) = O(|V|³), that is quite expensive. Specially, when you consider the fact that apart from the few hundred fiat currencies, there are 1000+ cryptocurrencies out there.

Also we should not forget that currency exchange rate is not a factor of solely the currency itself, rather it is tied with an exchange. For example, suppose, Moneycorp exchange has a USD to SGD rate 1.4 while for HiFX it is 1.396 for the same. So we see, USD appearing twice in the graph – once as part of Moneycorp and again as part of HiFX.

However, computing shortest paths, a prerequisite for finding arbitrage, is something quite expensive. In this problem, we need to incrementally compute shortest paths when a new vertex, n^th one arrives, assuming we have pre-computed results for (n-1) vertices that we can re-use.

To be more specific, suppose, at this moment, we have 12344 vertices and we already know whether there is an arbitrage, after computing the necessary shortest paths. And then, a new currency, JioCoin arrives with some new rates (from JioCoin to some existing currencies, say, JioCoin to INR and from some existing currencies to JioCoin, say, SGD to JioCoin). Now we have 12345 vertices. Computing shortest paths for a dense graph with 12345 vertices would take a very long time (try running 3 nested for loops, each looping 12345 times), doing billions of computations.

At this moment, would it be not wise to use the existing results for 12344 vertices? And then incrementally adjust the new shortest paths and compute some new ones? That is precisely, this problem is all about. We need to incrementally, adjust/add shortest paths once a new vertex arrives. And this is to be done at a time complexity of O(|V|²), something that is comfortably manageable. After this, we have to now say, whether an arbitrage exists.

Input:

1 USD = 1.380 SGD

1 SGD = 3.080 MYR

1 MYR = 15.120 INR

1 INR = 0.012 GBP

1 GBP = 1.30 USD

I CAD = 0.57 GBP

Explanation: Whenever a rate arrives, starting from the first, for each new vertex, we need to incrementally adjust/add shortest paths, find whether an arbitrage exists or not and output the same. We have 6 inputs here. Each time an input comes, we need to output and hence, we have 6 lines of output. The first 4 did not result in any arbitrage, we output “No luck here”. From 5th we have an arbitrage and we output the same.

Once an arbitrage is found, it is going to last. Note that, there might exist more than one arbitrage. Printing any one will do.

An important thing: rate between a certain currency pair will not appear twice in the input. Meaning once, GBP to USD rate arrives at line 5, a new rate between the two won’t arrive again.

Output:

No luck here

USD -> SGD -> MYR -> INR -> GBP -> USD

Input:

1 USD = 1.38295 SGD

1 SGD = 3.08614 MYR

1 MYR = 15.0996 INR

1 INR = 0.0119755 GBP

1 GBP = 1.295 USD

Output:

No luck here

Task: For each line of input, for each new vertex, incrementally adjust/add shortest paths at a cost (time) of O(|V|²), detect the presence of an arbitrage and output as specified.

Index

Sprint Completion Time

10^th JLTi Code Jam – Dec 2017

At the start of a sprint we are given a list of deliverables. The first thing in our mind is whether the team can deliver it in time. Thus estimating time to complete a sprint is something very important.

The first thing we do is, split the deliverables into a number of tasks, and estimate the time required to complete each of them. A task takes 3 days to complete means it takes 3 days for one person to complete; it cannot be split further to get 3 persons doing it on a single day.

While some tasks can be completed independently, others might be dependent tasks – meaning we cannot start them unless the prerequisite tasks are completed first. For example, work on a report cannot start until we are done with the database design/creation. Testing or deployment cannot be done unless we develop the solution. Suppose, completing task 1, and task 2 takes 4, and 6 days respectively and task 2 is dependent on task 1 – in other words – task 1 is a prerequisite for task 2. In this case, completing task 2 would take 10 days.

Finally, we don’t have an infinite number of people available. And for simplicity, assume each person is capable of doing any of the tasks.

Input:

4 3 2 1 4 6

1 2 4

2 3 4

4 3

5 6

6 3

Output: 12

Explanation:

The first line says the team has 3 persons. Second line lists the number of days required to complete each of the tasks. Here we have 6 numbers. It says we have 6 tasks – task 1 takes 4 days to complete, task 2 takes 3 days to complete and so on. The last, task 6, takes 6 days.

The subsequent lines list the dependent tasks. 1 2 4 means task 1 depends on tasks 2 and 4. 6 3 means task 3 is a prerequisite for task 6. No line starts with 3 means task 3 does not depend on any other task.

Task 3 can be completed in 2 days by one person. These first 2 days the other two persons have to sit idle as all other tasks are dependent tasks. After 2 days, task 2, 4 or 6 – all of which were dependent on task 3 can start. Each of the 3 persons can start any of them. Once task 6 is done task 5 can start. Similarly, when task 2 is done task 1 can start. We will see completing all of them takes 12 days.

Input:

4 3 6 2

1 2

2 3

3 1

Output: Infeasible

Explanation: We have 2 persons to complete 4 tasks – completing them take 4, 3, 6 and 2 days respectively. However, we see that task 1 is dependent on task 2, task 2 is dependent on task 3 and task 3 is dependent back on task 1. While we can finish task 4 easily, we cannot start any of the first 3 tasks. They are dependent on each other and thus creating a dependency cycle.

Task: Manually calculating the minimum time required to complete the tasks is time consuming and prone to error, especially when we need to estimate this very often. Why not write a small program that can do it for us?

Index

RC Election Result

9^th JLTi Code Jam – Nov 2017

Whole JLT is buzzing with Recreational Committee (RC) aka Fun Ministry election 2018. It is more palpable in JLTi where a fierce competition is taking place between two candidates representing Millennial Party and Traditional Party. In this two-party system, Millennial Party is claiming that they know the magic as to how people can be entertained while the Traditional Party cannot stop laughing at them saying they are just inexperienced kids incapable of running the massive Fun Ministry.

This time, voting mechanism has changed. Instead of one person one vote that was how it worked till last year, one person’s vote weight would now equal to the number of years he/she is working at JLT. For example, I am working here for 4 years and hence my vote would count as 4. If somebody is working for just 1 year, his/her vote weight would be 1. For obvious reason, Millennial Party is unhappy about this new legislation that was recently passed by the incumbent Traditional Party. They call it unfair. But law is law.

Voting stopped on 10^th Nov 2017 and counting votes would commence on 13^th Nov 2017 followed by the announcement of result on the same day.

Being a member of the existing RC, my concern is little different. I am worried about a tie, and if that happens, what would be the next course of action.

Hence, I am checking the possibility of a tie. Manually doing so is quite problematic, if not impossible, for several hundred employees that we have in Singapore. Being the only software engineer in the existing RC, I am tasked to write a program that would take vote weight of each of the voters as input and output whether a tie is possible.

Input:

20 10 4 6

Output: Possible

Explanation: Vote weight 20 and 10 – sounds familiar? Anyway, we see that if the first voter votes for one candidate and the rests for another – a tie is inevitable.

Input:

8 7 2 5 16

Output: Not Possible

Explanation: As you see the total vote weight for the above 5 voters is 38. For a tie to happen each candidate should get a vote count of 19. However, we can see, no way a vote count of 19 is possible here.

Input:

5, 6, 7, 3

Output: Not Possible

Explanation: We see, the total vote weight for the above 4 voters is 21. An odd number cannot be divided by two.

Task: Given a list of vote weight, one for each voter, we need to find whether a tie is possible. We are assuming that all voters in the input would vote for sure.

Index

Solution – Choosing Oranges

38^th Friday Fun Session – 3^rd Nov 2017

Given a set of goodness scores of oranges and a window length, we need to find the highest scoring oranges within the window as we move it from left to the end.

This is the solution for JLTI Code Jam – Oct 2017.

Using priority queue

Suppose we have n scores and the window length is m. We can simply move the window from left to to right and take (consecutive) m scores within the window and each time compute the max of them, and output it, if it is already not outputted. Finding max from m scores would take O(m) and as we do it n times (n-m+1 times, to be precise), the complexity would be O(mn). However, it was expected that the complexity would be better than this.

Alternatively, we can use a max-heap, where we push each score as we encounter it. At the same time, we retrieve the top of the max-heap and if all is fine – output it. By if all is fine, we mean to say, we need to make sure that the orange has not been already outputted and that it belongs to the current window. At the same time, if the top item is out-dated, we can pop it, meaning take it out of the heap. Note that, max-heap is a data structure that retains the max element at the top.

Let us walk through an example

Let us take the first example as mentioned here. For the scores 1 3 5 7 3 5 9 1 2 5 with window size 5, let us walk through the process.

At first, we push the first 4 items (4 is one less than the window size 5). The max-heap would look like: 1 3 5 7 where 7 is the top element.

Then for each of the remaining items, we do the following:

If the (new) item is greater than or equal to the top item in the max-heap, pop it (out) and push the new item into it. Output the new item (if the same orange is not already outputted). We do it because the new item is the max in the present window. And the existing top one is of no further use. We can now move to the next item.
Keep on popping the top as long it is not one belonging to the current window. We do it, as we are interested to find the max within the window, not the out-dated ones those are no longer inside the window.
Output the top (if the same orange is not already outputted). We do it as it the max within the current window.
If the top item is the oldest (left-most/first/earliest/starting one) in the current window, pop it. We do it because this item is going to go out of the window as the next item gets in.

Score 3:

3 is not >= 7 (top in heap)

Existing top (7) is within the current window. Output it.

Push 3; max-heap looks like: 1 3 3 5 7

Score 5:

5 is not >= 7 (top in heap)

Existing top (7) is within the current window (3 5 7 3 5). But this orange is already outputted (we can use index of the item to track it, meaning instead of just pushing the score, retain the index along with it). No output this time.

Push 5; max-heap looks like: 1 3 3 5 5 7

Score 9:

9 >= 7 (top in heap)

Pop 7, push 9, output 9.

New max-heap: 1 3 3 5 5 9

Score 1:

1 is not >= 9 (top in heap)

Existing top (9) is within the current window. But this orange is already outputted. No output this time.

Push 1; max-heap looks like: 1 1 3 3 5 5 9

Score 2:

2 is not >= 9 (top in heap)

Existing top (9) is within the current window. But this orange is already outputted. No output this time.

Push 2; max-heap looks like: 1 1 2 3 3 5 5 9

Score 5:

Existing top (9) is within the current window. But this orange is already outputted. No output this time.

Push 5; max-heap looks like: 1 1 2 3 3 5 5 5 9

No item left. We are done!

Finally, output is 7, 9.

Complexity

If we closely observe, we see that the size of the max-heap would be always around m. Because, if the new item is greater or equal we are popping the top – hence the max-heap size is not increasing. If new item is smaller, we are pushing it and the size of the max-heap is increasing – true; but then soon the top would be out-dated and then we would pop that. So the max-heap size remains around m. Pushing (in) or popping (out) an item would cost log m, and since we would do it n times – the complexity would be O(n log m). Please note that getting the top of the max-heap costs O(1).

GitHub: Choosing Oranges

Index

Choosing Oranges

8^th JLTi Code Jam – Oct 2017

Orange is one of my favourite fruits that I buy for our Friday Fun Session participants. How would you choose the good ones from hundreds of them; especially, on the way to office, when you stop by the supermarket, in the morning rush hour?

To speed up the selection while at the same time choosing the good – firm, smooth and heavier compare to its size – I have devised a selection process. I would go from left to right, scoring each of the oranges, in a scale from 0 to 9, 9 being the best; and once a row is done, I go to the next row and so on. As I go and score, I would also choose the best one among each consecutive, say 5 oranges.

How that would look like?

Input:

1 3 5 7 3 5 9 1 2 5

Output: 7, 9

Explanation:

The first line says: choose the best among consecutive 5. The second line shows the score for each of the 10 oranges. The first 5 are: 1, 3, 5, 7, and 3; best among them is 7. We choose 7. The next 5 are: 3, 5, 7, 3, and 5; best among them 7 – already chosen. Move on to the next 5: 5, 7, 3, 5, and 9; best among them 9, pick that. Move to the next 5: 7, 3, 5, 9, and 1; best among them is 9, already chosen. Next 5 are: 3, 5, 9, 1, and 2; once again the best among them 9 is already chosen. Final 5 are: 5, 9, 1, 2, and 5; same as before. We cannot move further as we don’t have 5 oranges after this point.

We end up with two oranges: 7 and 9. I am not doing a bad job of selecting the best oranges for you, am I?

Input:

1, 3, 5

Output: None

The first line says: choose the best among 4. However, the second line shows only 3 oranges. Obviously we cannot choose any.

Input:

1 2 4 9

Output: 4, 9

Choose 4 from 1, 2 and 4. And then choose 9 from the next consecutive 3: 2, 4 and 9. And we are done!

Task: If we have a total of n oranges and we got to choose the best from each consecutive m, I am looking for a solution having better than O(mn) time complexity.

Index

Graced by Your Presence

Friday Fun Session Participants

Those of us who participate(d) our weekly learning and discussion session:

Bala Krishnan
Tang Biao
Vignesh Shankar
Chia Wei Woo
Mahadevan Hariharan
Ramakrishnan Kalyanaraman
William Lim
Srila Das Bhattacharya
Sravani Vanukuru
Kristipi Valledor
Jeffrey Quiatchon
Jothi Kiruthika
Sayed Neda Fatima
Sreenivasulu Gotla
Vishal Gupta
French Jean Palma Jumawan
Gopi Krishna Pasupuleti
Htet Aung Nay
Aquib Javed Momin
Pravinkarthy Ravi
Rishabh Mangal
Sunil Koli
Vikas Pai
Sandip Dangat
Hui Ling Chong
Srinivasa Puchakayala Reddy
Manikandan Chandran
Sharon Wong
Uma Maheswary Ganesan
Ishwarya Sridharan
Aristotle Tiru
Balamurugan Chennarayaperumal
Aarti Piskala Dhanabalan
Karthik Kumar
Sunil Khamkar
Handy Toh Torres
Daniel Vo
Srinivasan Badri Prasad
Parthasarathi Murugaiyan
Hieu Nguyen Van
Manikandan Panneerselvam
Jayamaran Ayilu
Muukta Kedar
Gaurav Singh
Vikas Kitawat
Tanveer Shaikh
Vishal Jain
Dipti Saurabh Shindhe
Samir Tank
Bhushan Patil
Munendra Tomar
Prabakaran Boopathi
Vikraman Sridharan
Srikanth Rokkam
Santhosh Kumar Janakiraman
Christabel Merline
Ankit Jain
Neethila Arasi
Hari Gopal Raman
Sheryl Teo
Jocelyn Pacson Maranan
Kannan Palanisamy
Chitra Muthu
Chaitanya Joshi
Billie Santiago
Thandar Win
Julius Pedroso
Chinta Nagendra Babu
Lourdu Michael Sam
Gayan Gunarathne
Amit Gupta
Akshatha Davasam
Parimi Chowdary
Haribabu Gattipati
Rajesh Mutyala
Janani Vijayan
Prashasti Shandilya
Anju Singh
Akash Mule
Anclyn Demol Yballe
Gopal Chandra Das

Problems in JLTi Code Jam

JLTi Code Jam Problems

Year 2018

Mar (13^th) – Currency Arbitrage with Increasing Rate

Feb (12^th) – Currency Arbitrage with Decreasing Rate

Jan (11^th) – Currency Arbitrage

Year 2017

Dec (10^th) – Sprint Completion Time

Nov (9^th) – RC Election Result

Oct (8^th) – Choosing Oranges

Sep (7^th) – Team Lunch

Aug (6^th) – FaaS

Jul (5^th) – Scoring Weight Loss

Jun (4^th) – Manipulating Money Exchange

May (3^rd) – Making Money at Stock Exchange

Apr (2^nd) – Company Tour to Noland

Mar (1^st) – No Two Team Member Next to Each Other

Index

Topics in Friday Fun Session

Friday Fun Session Topics

Year 2019

Jul

4^th Jul 2019 (110^th) – Detecting the Start Node of a Loop in a Singly Linked List, if Exists

Jun

27^th Jun 2019 (109^th) – Building the Highest Stack of Cuboids of Varrying Length, Height, and Width Without Rotating in Non-Increasing Order From Bottom to Top

20^th Jun 2019 (108^th) – Detecting Poison in 1 Out of 2ⁿ bottles Using n Strips That Changes Color Only When Poison is Poured On it

13^th Jun 2019 (107^th) – Searching in a Sorted and Rotated Array

6^th Jun 2019 (106^th) – Delete a Node from BST

May

30^th May 2019 (105^th) – Retrieving a Random Item from BST

23^rd May 2019 (104^th) – Optimizing SQL Queries Using Join Hints

16^th May 2019 (103^rd) – Largest Rectangular Area in a Histogram at O(n)

9^th May 2019 (102^nd) – Efficient Construction of Hierarchical Dropdown for UI

2^nd May 2019 (101^st) – Hierarchical and Recursive Queries in T-SQL

Apr

25^th Apr 2019 (100^th) – Segment Tree (Query and Update)

18^th Apr 2019 (99^th) – Segment Tree (Building)

11^th Apr 2019 (98^th) – Maximum Rectangular Area in Histogram (Divide and Conquer)

4^th Apr 2019 (97^th) – Trapping Rain Water

Mar

28^th Mar 2019 (96^th) – Dutch National Flag Problem

21^st Mar 2019 (95^th) – Permutation

14^th Mar 2019 (94^th) – Post-order sequence to binary tree, check if BST

7^th Mar 2019 (93^rd) – Pre-order sequence to binary tree, check if BST

Feb

28^th Feb 2019 (92^nd) – Task Dependencies, Build Execution Order, if Any (using DFS)

21^st Feb 2019 – Missed, On Leave

14^th Feb 2019 (91^st) – Build BST in an Efficient Way to Count Height of Each Node (Contd.)

7^th Feb 2019 (90^th) – Build BST in an Efficient Way to Count Height of Each Node (Contd.)

Jan

31^st Jan 2019 (89^th) – Build BST in an Efficient Way to Count Height of Each Node (Contd.)

25^th Jan 2019 (88^th) – Build BST in an Efficient Way to Count Height of Each Node

17^th Jan 2019 (87^th) – Common First Ancestor of Two Nodes in a Binary Tree with All Unique Values

10^th Jan 2019 (86^th) – Check if a Binary Tree is Balanced

3^rd Jan 2019 (85^th) – Number of Paths with a Certain Sum in a Binary Tree (Top-down)

Year 2018

Dec

27^th Dec 2018 (84^th) – Number of Subsequences Making a Certain Sum In an Array

20^th Dec 2018 (83^rd) – Number of Paths with a Certain Sum in a Binary Tree (Bottom-up)

13^th Dec 2018 (82^nd) – Binary Tree to Doubly Linked List

5^th Dec 2018 (81^st) – Given a BST, Find All Input Sets That Can Build it

Nov

28^th Nov 2018 (80^th) – Number of ways a BST can be built with n distinct keys

21^st Nov 2018 (79^th) – Merge Two Lists in All Possible Ways Preserving Relative Order of Elements Within Each List

14^th Nov 2018 (78^th) – Two-way/Bidirectional Search BFS

7^th Nov 2018 (77^th) – Detecting Cycle in a Directed Graph

Oct

31^st Oct 2018 (76^th) – Drawing with HTML5 <canvas> and JavaScript, Rotation of Axes, Arrow Drawing

24^th Oct 2018 (75^th) – CA, ICA, Chain of Trust

17^th Oct 2018 (74^th) – How does SSL/TLS work

10^th Oct 2018 (73^rd) – Self-signed SAN Certificate for localhost Using OpenSSL

3^rd Oct 2018 (72^nd) – Gradient Descent

Sep

26^th Sep 2018 (71^th) – Simple Linear Regression Using Gradient Descent

19^th Sep 2018 (70^th) – Simple Linear Regression Using Linear Least Squares

12^th Sep 2018 (69^th) – Multiple Linear Regression Demo Using R

5^th Sep 2018 (68^th) – Cycle Detection Using Union by Rank and Path Compression in an Undirected Graph

Aug

29^th Aug 2018 (67^th) – Union by Rank and Path Compression

22^nd Aug 2018 – Missed, Public Holiday

15^th Aug 2018 (66^th) – Stable Roommates Problem (continued)

8^st Aug 2018 (65^th) – Stable Roommates Problem (continued)

1^st Aug 2018 (64^th) – Stable Roommates Problem

Jul

25^th Jul 2018 (63^rd) – 2-d Array Printing in Spiral order

18^th Jul 2018 (62^nd) – Stable Marriage Problem (continued)

11^th Jul 2018 (61^st) – Stable Marriage Problem

4^th Jul 2018 (60^th) – DFS

Jun

27^th Jun 2018 (59^th) – BFS

20^th Jun 2018 – Cancelled

13^th Jun 2018 (58^th) – Ford-Fulkerson Method (Max-flow)

6^th Jun 2018 – Missed, On Leave

May

30^th May 2018 – Missed, On Leave

23^rd May 2018 (57^th) – Karger’s Algorithm (Minimum cut)

16^th May 2018 (56^th) – Solution – Currency Arbitrage with Increasing Rate

11^th May 2018 – Cancelled

4^th May 2018 – Cancelled

Apr

27^th Apr 2018 – Cancelled

20^th Apr 2018 – Cancelled

13^rd Apr 2018 – Cancelled

6^th Apr 2018 – Cancelled

Mar

30^th Mar 2018 – Missed, Public Holiday

23^rd Mar 2018 (55^th) – Bitcoin – Simple Payment Verification (SPV)

16^th Mar 2018 (54^th) – Cryptographic Hash Function – Properties

9^th Mar 2018 (53^rd) – Collation in MS SQL Server

2^nd Mar 2018 (52^nd) – Solution – Currency Arbitrage with Decreasing Rate

Feb

23^rd Feb 2018 (51^st) – Merkle Tree

16^th Feb 2018 – Missed, Chinese New Year

9^th Feb 2018 (50^th) – RSA

2^nd Feb 2018 (49^th) – Solution – Currency Arbitrage

Jan

26^th Jan 2018 (48^th) – Overview of Bitcoin and Blockchain

19^th Jan 2018 (47^th) – Johnson’s Algorithm

12^th Jan 2018 (46^th) – Dijkstra’s Problem with Negative Edge

5^th Jan 2018 (45^th) – Solution – Sprint Completion Time

Year 2017

Dec

29^th Dec 2017 – Missed, On Leave

22^nd Dec 2017 – Missed, On Leave

15^th Dec 2017 (44^th) – Rod Cutting Problem

8^th Dec 2017 (43^rd) – Task Scheduling – Unlimited Server

1^st Dec 2017 (42^nd) – Solution – RC Election Result

Nov

24^th Nov 2017 (41^st) – Traveling Salesman Problem (Brute force and Bellman–Held–Karp)

17^th Nov 2017 (40^th) – Hamiltonian Path

10^th Nov 2017 (39^th) – Coin Exchange – Min Number of Coins

3^rd Nov 2017 (38^th) – Solution – Choosing Oranges

Oct

27^th Oct 2017 – Missed, On Leave

20^th Oct 2017 (37^th) – Coin Exchange – Number of Ways

13^th Oct 2017 – Missed, JLT D&D

6^th Oct 2017 (36^th) – Solution – Team Lunch

Sep

29^th Sep 2017 (35^th) – Floyd-Warshall Algorithm

22^nd Sep 2017 (34^th) – Executing SP Using EF; Transaction in Nested SP

15^th Sep 2017 (33^rd) – Solution – FaaS; Pseudo-polynomial Complexity

8^th Sep 2017 – Missed, JLT Family Day

1^st Sep 2017 – Missed, Hari Raya

Aug

25^th Aug 2017 (32^nd) – Multithreaded Programming

18^th Aug 2017 (31^st) – Knapsack Problem

11^th Aug 2017 (30^th) – Vertex Coloring

4^th Aug 2017 (29^th) – Solution – Scoring Weight Loss

Jul

28^th Jul 2017 (28^th) – Minimum Spanning Tree – Kruskal and Prim

21^st Jul 2017 (27^th) – Pseudorandom Number Generator

14^th Jul 2017 (26^th) – Rete Algorithm

7^th Jul 2017 (25^th) – Solution – Manipulating Money Exchange

Jun

30^th Jun 2017 (24^th) – Rules Engine

23^rd Jun 2017 (23^rd) – Inducting Classification Tree

16^th Jun 2017 (22^nd) – Incision into Isolation Level; Interpreting IIS Internals; Synchronizing Web System

9^th Jun 2017 (21^st) – Maximum Subarray Problem

2^nd Jun 2017 (20^th) – Solution – Making Money at Stock Market

May

26^th May 2017 (19^th) – Understanding Correlation Coefficient; k-NN Using R

19^th May 2017 (18^th) – k-d Tree and Nearest Neighbour Search

12^th May 2017 (17^th) – Bellman Ford Algorithm

5^th May 2017 (16^th) – Solution – Company Tour 2017 to Noland

Apr

28^th Apr 2017 (15^th) – Models in Machine Learning; k-Nearest Neighbors (k-NN)

21^st Apr 2017 (14^th) – Edit/Levenshtein Distance

14^th Apr 2017 – Missed, Good Friday

7^th Apr 2017 (13^th) – Solution – No Two Team Member Next to Each Other

Mar

31^st Mar 2017 (12^th) – N-queens

24^th Mar 2017 (11^th) – Longest Common Subsequence (LCS)

17^th Mar 2017 (10^th) – Dijkstra’s Algorithm

10^th Mar 2017 (9^th) – Infix, Prefix (Polish), Postfix (Reverse Polish)

3^rd Mar 2017 (8^th) – Order 2-D Array in all Directions & Find all Triplets with Sum Zero in an Array

Feb

24^th Feb 2017 (7^th) – Trailing Zeros in a Factorial

17^th Feb 2017 (6^th) – Is this Tree a BST?

10^th Feb 2017 (5^th) – Given a Number, Find the Smallest Next Palindrome

3^rd Feb 2017 (4^th) – Merge n Sorted Lists, Each Having m Numbers, Into a Sorted List

Jan

27^th Jan 2017 – Missed, Chinese New Year Eve

20^th Jan 2017 (3^rd) – Shortest Exit from Maze

13^rd Jan 2017 (2^nd) – Finding Fibonacci – Exponential vs. Linear

6^th Jan 2017 (1^st) – Gmail API with OAuth 2.0

12th JLTi Code Jam – Feb 2018

49th Friday Fun Session – 2nd Feb 2018

Converting Rates

Visualizing Floyd-Warshall

What Cells Are Used to Optimize

Kth Row and Column do not Change

Consider Only 3X3 Matrix Was Computed

Add 4th Vertex

Code

Complexity

Printing Arbitrage Path

11th JLTi Code Jam – Jan 2018

10th JLTi Code Jam – Dec 2017

9th JLTi Code Jam – Nov 2017

38th Friday Fun Session – 3rd Nov 2017

Using priority queue

Let us walk through an example

Complexity

8th JLTi Code Jam – Oct 2017

Friday Fun Session Participants

JLTi Code Jam Problems

Year 2018

Year 2017

Friday Fun Session Topics

Year 2019

Jul

Jun

May

Apr

Mar

Feb

Jan

Year 2018

Dec

Nov

Oct

Sep

Aug

Jul

Jun

May

Apr

Mar

Feb

Jan

Year 2017

Dec

Nov

Oct

Sep

Aug

Jul

Jun

May

Apr

Mar

Feb

Jan

12^th JLTi Code Jam – Feb 2018

49^th Friday Fun Session – 2^nd Feb 2018

K^th Row and Column do not Change

Add 4^th Vertex

11^th JLTi Code Jam – Jan 2018

10^th JLTi Code Jam – Dec 2017

9^th JLTi Code Jam – Nov 2017

38^th Friday Fun Session – 3^rd Nov 2017

8^th JLTi Code Jam – Oct 2017