code review: Hackerrank kindergarten adventures

March 19, 2017

Problem statement

Code review is posted here.

C# code - still work on more test cases on API testing, Modify and Query.

Introduction

Julia starts to learn binary index tree and segment tree through hackerrank university codesprint #2 in November 2016, she tried a few times but failed each time. She knew that she is better to work on the algorithm "kintergarden adventure" and learn from the algorithm.

She also did post the question on segment tree algorithm on code review to ask help on Dec. 10, 2016, and then the question "kintergarden adventure" was closed. Through the incident, Julia knew that she was afraid to learn by herself.

Julia is very comfortable at data analysis, so in order to figure out the algorithm, Julia chose to have some test case study, put together some data, and then taught herself what to look for through those tables.

Test case study

For example, there are 20000 students in the circle, and the first student only need to 0 minute to finish drawing, so that if the teacher starts from any students from ID = 1 to 20000, the first student can complete the drawing. SegmentTree class Modify API has to take the task to mark those 20000 nodes as value 1, it is not scalable for 3 seconds time limit, so that we can use up to logN intervals to cover the range of [1, 20000].

To make it simple, we assume that the range's width is 1024 instead of 20000, and see how many steps we need to mark in tree[]. Not up to 1024, but in the level of logN = log1024 = 10.


Here is the SegmentTree class Modify API: To understand the test case, in order to modify 1024 nodes as 1, we only do it in less and equal to 10 times, here is the two images to explain the detail.

The two variables of left and right are iterated from beginning to end 10 times, each iteration two variables's values are recorded in the table.

Let us get our hands dirty on this test case, RunTestcaseModify3() line 12, tree.Modify(0,1024,1). We look into the function call.

First row of table, left = 20001, right = 21024, since Modify API is called and function arguments: start = 0, count = 1024, value = 1,
read Modify API code line 5 and line 6, left is calculated as 20001 and right is calculated as 21024.

and more detail is here:

Action items

Review code review Hackerrank Modular Range Queries
Read the tutorial of segment tree.
Learn binary index tree from topcoder

Inspiration

This is the first time Julia started to use Microsoft Excel to do some test case analysis to help her understand the segment tree algorithm design.

All it takes is for her to have some patience. She read those two tables built by Microsoft Excel, and then she asks herself what is missing, what problems she can tell from those data. After a few times search, she comes out ideas to move forward her study.