Author: Gopal Das

Data Scientist @ CrimsonLogic, Singapore BS in CSE from Khulna University ME in Internet Science & Engineering from Indian Institute of Science (IISc) Publications on Query Optimization in RDBMS in ACM SIGMOD, IEEE ICDE etc. Founding team member and VP Engineering of iTwin, a spinoff from A*STAR Software engineer/data scientist for 19 years Software, Database, ML Father of 3 (two @ NUS High and one is too little!) www.linkedin.com/in/dasgopal https://github.com/gopalcdas

Currency Arbitrage

11th 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|2 edges. Hence, Bellman-Ford ends up with O(|V||E|) = O(|V||V|2) = O(|V|3), 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, nth 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|2), 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

No luck here

No luck here

No luck here

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

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

No luck here

No luck here

No luck here

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|2), detect the presence of an arbitrage and output as specified.

Index

Sprint Completion Time

10th 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:

3

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:

2

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

9th 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 10th Nov 2017 and counting votes would commence on 13th 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

38th Friday Fun Session – 3rd 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:

  1. 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.
  2. 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.
  3. Output the top (if the same orange is not already outputted). We do it as it the max within the current window.
  4. 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

8th 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:

5

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:

4

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:

3

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:

  1. Bala Krishnan
  2. Tang Biao
  3. Vignesh Shankar
  4. Chia Wei Woo
  5. Mahadevan Hariharan
  6. Ramakrishnan Kalyanaraman
  7. William Lim
  8. Srila Das Bhattacharya
  9. Sravani Vanukuru
  10. Kristipi Valledor
  11. Jeffrey Quiatchon
  12. Jothi Kiruthika
  13. Sayed Neda Fatima
  14. Sreenivasulu Gotla
  15. Vishal Gupta
  16. French Jean Palma Jumawan
  17. Gopi Krishna Pasupuleti
  18. Htet Aung Nay
  19. Aquib Javed Momin
  20. Pravinkarthy Ravi
  21. Rishabh Mangal
  22. Sunil Koli
  23. Vikas Pai
  24. Sandip Dangat
  25. Hui Ling Chong
  26. Srinivasa Puchakayala Reddy
  27. Manikandan Chandran
  28. Sharon Wong
  29. Uma Maheswary Ganesan
  30. Ishwarya Sridharan
  31. Aristotle Tiru
  32. Balamurugan Chennarayaperumal
  33. Aarti Piskala Dhanabalan
  34. Karthik Kumar
  35. Sunil Khamkar
  36. Handy Toh Torres
  37. Daniel Vo
  38. Srinivasan Badri Prasad
  39. Parthasarathi Murugaiyan
  40. Hieu Nguyen Van
  41. Manikandan Panneerselvam
  42. Jayamaran Ayilu
  43. Muukta Kedar
  44. Gaurav Singh
  45. Vikas Kitawat
  46. Tanveer Shaikh
  47. Vishal Jain
  48. Dipti Saurabh Shindhe
  49. Samir Tank
  50. Bhushan Patil
  51. Munendra Tomar
  52. Prabakaran Boopathi
  53. Vikraman Sridharan
  54. Srikanth Rokkam
  55. Santhosh Kumar Janakiraman
  56. Christabel Merline
  57. Ankit Jain
  58. Neethila Arasi
  59. Hari Gopal Raman
  60. Sheryl Teo
  61. Jocelyn Pacson Maranan
  62. Kannan Palanisamy
  63. Chitra Muthu
  64. Chaitanya Joshi
  65. Billie Santiago
  66. Thandar Win
  67. Julius Pedroso
  68. Chinta Nagendra Babu
  69. Lourdu Michael Sam
  70. Gayan Gunarathne
  71. Amit Gupta
  72. Akshatha Davasam
  73. Parimi Chowdary
  74. Haribabu Gattipati
  75. Rajesh Mutyala
  76. Janani Vijayan
  77. Prashasti Shandilya
  78. Anju Singh
  79. Akash Mule
  80. Anclyn Demol Yballe
  81. Gopal Chandra Das

Problems in JLTi Code Jam

JLTi Code Jam Problems

Year 2018

Mar (13th) – Currency Arbitrage with Increasing Rate

Feb (12th) – Currency Arbitrage with Decreasing Rate

Jan (11th) – Currency Arbitrage

Year 2017

Dec (10th) – Sprint Completion Time

Nov (9th) – RC Election Result

Oct (8th) – Choosing Oranges

Sep (7th) – Team Lunch

Aug (6th) – FaaS

Jul (5th) – Scoring Weight Loss

Jun (4th) – Manipulating Money Exchange

May (3rd) – Making Money at Stock Exchange

Apr (2nd) – Company Tour to Noland

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

Index

Other Posts

Topics in Friday Fun Session

Friday Fun Session Topics

Year 2019

Jul

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

Jun

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

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

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

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

May

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

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

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

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

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

Apr

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

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

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

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

Mar

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

21st Mar 2019 (95th) – Permutation

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

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

Feb

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

21st Feb 2019 – Missed, On Leave

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

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

Jan

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

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

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

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

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

Year 2018

Dec

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

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

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

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

Nov

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

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

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

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

Oct

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

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

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

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

3rd Oct 2018 (72nd) – Gradient Descent

Sep

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

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

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

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

Aug

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

22nd Aug 2018 – Missed, Public Holiday

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

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

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

Jul

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

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

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

4th Jul 2018 (60th) – DFS

Jun

27th Jun 2018 (59th) – BFS

20th Jun 2018 – Cancelled

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

6th Jun 2018 – Missed, On Leave

May

30th May 2018 – Missed, On Leave

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

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

11th May 2018 – Cancelled

4th May 2018 – Cancelled

Apr

27th Apr 2018 – Cancelled

20th Apr 2018 – Cancelled

13rd Apr 2018 – Cancelled

6th Apr 2018 – Cancelled

Mar

30th Mar 2018 – Missed, Public Holiday

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

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

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

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

Feb

23rd Feb 2018 (51st) – Merkle Tree

16th Feb 2018 – Missed, Chinese New Year

9th Feb 2018 (50th) – RSA

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

 Jan

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

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

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

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

Year 2017

Dec

29th Dec 2017 – Missed, On Leave

22nd Dec 2017 – Missed, On Leave

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

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

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

Nov

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

17th Nov 2017 (40th) – Hamiltonian Path

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

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

Oct

27th Oct 2017 – Missed, On Leave

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

13th Oct 2017 – Missed, JLT D&D

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

Sep

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

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

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

8th Sep 2017 – Missed, JLT Family Day

1st Sep 2017 – Missed, Hari Raya

Aug

25th Aug 2017 (32nd) – Multithreaded Programming

18th Aug 2017 (31st) – Knapsack Problem

11th Aug 2017 (30th) – Vertex Coloring

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

Jul

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

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

14th Jul 2017 (26th) – Rete Algorithm

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

Jun

30th Jun 2017 (24th) –  Rules Engine

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

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

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

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

May

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

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

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

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

Apr

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

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

14th Apr 2017 – Missed, Good Friday

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

Mar

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

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

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

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

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

Feb

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

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

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

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

Jan

27th Jan 2017 – Missed, Chinese New Year Eve

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

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

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

Other Posts

Problems in JLTi Code Jam

Transactions in Nested SP

34th Friday Fun Session (Part 2) – 22nd Sep 2017

When one (MS SQL Server) Stored Procedure (SP), say, A calls another SP, say, B inside it; we call the SPs are nested. It is not always the case that A calls B. B can be called directly as well. Now if they are required to execute within transaction, in both the cases – when executed individually or nested, we face some interesting situations. Here we discuss how to manage transactions for those cases, when scope is limited within a database.

Requirements

We usually face two kinds of requirements.

  1. Full Commit: either all in both parent (A) and child (B) have to be executed or all should fail.
  2. Partial Commit: if one or more calls to child fail, let them fail. But persist/commit the changes done by parent and the successful calls to child.

Nesting does not need to be limited within two levels (parent and child) as stated here. For example, B can further call another SP C, or A can call any of B or C and so on. The requirements can vary in some other ways as well. However, if we solve the above two cases, the same mechanism/logic can be used/extended to handle all other situations.

Note that, we are also considering the situation that the child, B can be directly called, and in that situation, we are making sure that it is executing within its own transaction.

Full commit

The way we have written the SPs A and B as shown below, A is calling B 6 times. However B fails on the last call. A is inserting data into a table called OuterTable and B is doing the same for InnerTable.

In all or nothing case, we want to make sure, when we execute A, if any call to B fails, no data should be inserted in any of the tables; all should fail. It is obvious that if all the calls pass, then all data changed by them should persist.

It is also required that if B is executed directly, everything happening inside it must happen within a transaction.

Code for SP A:

CREATE Procedure [A]
AS
BEGIN
  BEGIN TRANSACTION;

  BEGIN TRY
    DECLARE @Success AS INT
    DECLARE @Counter AS INT

    SET @Success = 0
    SET @Counter = 0

    INSERT INTO [OuterTable] ([Name]) VALUES(@Counter)

    WHILE < 6
    BEGIN
      EXEC @Success = [B] @Counter;

      IF @Success = 0
        THROW 50001, 'B Failed! Rollback all!', 1

      SET @Counter = @Counter + 1;
    END

    IF @@TRANCOUNT > 0
      COMMIT TRANSACTION;
  END TRY

  BEGIN CATCH
    SET @Success = 0

    IF @@TRANCOUNT > 0
      ROLLBACK TRANSACTION;
  END CATCH;

  RETURN @Success
END

Code for SP B:

CREATE Procedure [B] (@CallCounter INT)
AS
BEGIN
  BEGIN TRANSACTION;

  BEGIN TRY
    DECLARE @Success AS INT
    SET @Success = 0

    IF @CallCounter = 5
      THROW 50001, 'Last call cannot be executed! Rollback all!', 1

    INSERT INTO [InnerTable] ([Name]) VALUES(@Counter)

    SET @Success = 1

    IF @@TRANCOUNT > 0
      COMMIT TRANSACTION;
  END TRY

  BEGIN CATCH
    SET @Success = 0

    IF @@TRANCOUNT > 0
      ROLLBACK TRANSACTION;
  END CATCH;

  RETURN @Success
END

When A gets called it starts a transaction. It then calls B, that succeeds 5 times, and subsequently fails on the last one.

@@TRANCOUNT is important

When B starts, it begins a transaction, unconditionally. Each time A calls B, @@TRANCOUNT gets incremented by 1 and reaches 2. Each time B succeeds, it executes a commit, thus reducing @@TRANCOUNT Back to 1, corresponding to the transaction started by A.

However, the last call to B fails. It then throws an exception, that gets the execution flow jump into the catch block, where it checks @@TRANCOUNT, that is now 2. It then rollbacks the transaction. A rollback discards all transactions in the nested call and resets @@TRANCOUNT. Before commit or rollback, it is a safe practice to make sure that it is still under a transaction, by checking @@TRANCOUNT value that should be greater than 0.

At this situation, B returns 0 to indicate failure (usual practice is to use 0 for indicating success though). A gets to know that B has failed. A throws exception, and ends up in catch block, where it checks @@TRANCOUNT, that is already 0. No further rollback is called and at the end 0 is returned from A to mean that it has failed.

Everything that A and B have done so far are all rolled back. After all, no matter how many transactions are started, a single rollback can discard all. At the end, no data changes happen to either of the tables, where they inserted data.

If B executes directly, depending on the parameter, data would persist or it would fail. However, all inside it would happen within a transaction.

Partial Commit

In this case, we want to persist the changes made by 5 successful calls to B, along with what A has done. The only thing that should get discarded is the failed 6th call to B.

Code for SP A:

CREATE Procedure [A]
AS
BEGIN
  BEGIN TRANSACTION;

  BEGIN TRY
    DECLARE @Success AS INT
    DECLARE @Counter AS INT

    SET @Success = 0
    SET @Counter = 0

    INSERT INTO [OuterTable] ([Name]) VALUES(@Counter)

    WHILE < 6
    BEGIN
      EXEC @Success = [B] @Counter;

      IF @Success = 0
        PRINT 'I know B Failed! But I am just ignoring that!', 1

      IF @Success = 2
        THROW 50001, 'Something terribly wrong! Rollback all!', 1

      SET @Counter = @Counter + 1;
    END

    IF @@TRANCOUNT > 0
      COMMIT TRANSACTION;
  END TRY

  BEGIN CATCH
    SET @Success = 0

    IF @@TRANCOUNT > 0
      ROLLBACK TRANSACTION;
  END CATCH;

  RETURN @Success
END

Code for SP B:

CREATE Procedure [B] (@CallCounter INT)
AS
BEGIN
  DECLARE @ProcedureSave NVARCHAR(MAX)
  DECLARE @TranCounter INT;

  SET @ProcedureSave = 'B-' + CONVERT(CHAR(23), GETDATE(), 121)
  SET @TranCounter = @@TRANCOUNT;

  IF @TranCounter > 0
    SAVE TRANSACTION @ProcedureSave;
  ELSE
    BEGIN TRANSACTION;

  BEGIN TRY
    DECLARE @Success AS INT
    SET @Success = 0

    IF @CallCounter = 5
      THROW 50001, 'Last call cannot be executed! Rollback all!', 1

    INSERT INTO [InnerTable] ([Name]) VALUES(@Counter)

    SET @Success = 1

    IF @TranCounter = 0 AND @@TRANCOUNT > 0
      COMMIT TRANSACTION;
  END TRY

  BEGIN CATCH
    SET @Success = 0

    IF @TranCounter = 0
      ROLLBACK TRANSACTION;
    ELSE
      IF XACT_STATE() <> -1
        ROLLBACK TRANSACTION @ProcedureSave;
      ELSE
        SET @Success = 2
  END CATCH;

  RETURN @Success
END

Savepoint

B starts a transaction, only if it is already not inside one. Meaning, if it is directly called then it starts a transaction of its own. However, if it is called by A, it does not do so. In that case, it creates a savepoint. A savepoint name is created in a way so that for each instance of the SP’s execution, it remains unique. A savepoint is a point where it can come back by executing a partial rollback. In such a situation, all changes between the savepoint and the place where partial rollback is called get discarded.

That is precisely what happens, when B fails and an exception is thrown. In catch block, it checks whether it started the transaction on its own. If that is the case, it simply calls a (full) rollback. However, if it was called by A, that also means it created a savepoint; it would simply execute a partial rollback using the savepoint. A partial rollback only discards the changes done by B itself.

XACT_STATE() is a safe choice

However, prior to executing the partial rollback it should check whether it is safe to do so. If XACT_STATE() returns -1, that means something went wrong, something that should happen rarely. In this situation, a partial rollback is no longer possible – only a full rollback can be done. Special failure code 2 is returned by B to indicate such a colossal failure.

A remains mostly the same. The only thing that gets changed is when it knows B has failed. Earlier, it would have thrown an exception. But this time, if the returned failure code is 0, it simply ignores that B has failed. If the returned failure code is 2, it knows that B fails to execute partial rollback  – something really bad – A executes a (full) rollback.

In the above case, we see that the outer table gets one new row, and the inner table gets 5 new rows; notwithstanding the fact that 6th call to B fails.

When B is called directly – not from A – it manages its own transaction; savepoint is never used.

Index