## 8thJLTi 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

## 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
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
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

## 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

## 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