Segment trees

December 10th, 2020 17:58

Recently I read about a data structure which I found to be the most interesting data structure from the point of view of generic problem solving. As the title of this post indicates, this data structure is segment tree.

A segment tree is as the name says a tree, whose each leaf can be made to indicate corresponding data items in an array, and each non leaf node can be a processed value. This processed value can be things such as minimum of leaf nodes, their sum, their GCD, LCM etc.

What the segment tree allows is to allow something like finding the sum of all values between index i and j in an array A[N] in O(logN) time. We can find the sum between these i and j indices in O(1) time if we use a prefix sum array, but then updating even 1 value in the original array would need recalculation of the entire prefix sum, which would be O(N). Using segment tree, we can do both the updates and query in O(logN) time, which is great.

Also, the implementation of segment tree is fairly simple and straight forward.

There are lots of interesting applications of it. For details, I suggest you look up this write up on segment tree


Cryptic Ruby

April 27th, 2021 00:08

Ruby is on the most expressive programming languages out there. This can make code fun because you can write code in the manner in which it makes the most sense to you. But this also means, that if you are not familiar with some syntax, you can encounter code which almost looks cryptic to you.
In this post, we would see some such syntax which is not as commonly seen in other languages.

Last Parameter Hash

A hash can be passed on to a function. That in itself is not confusing. When the hash is the last parameter, then the curly braces {} around the hash are optional.
def welcome(name, options)
  if options.empty?
   pronoun = "MR"
   age = 18
    pronoun = options.fetch("pronoun")
    age = options.fetch("age")
  puts "#{pronoun} #{name} #{age}"

The above welcome function can be called in the following ways, all of which are correct-

welcome("neeraj", {age: 18, pronoun: "him"})
welcome("neeraj", age: 18, pronoun: "him")

Since the hash is the last parameter, the {} have become optional for the last parameter. This is used extensively in Rails and elsewhere.

What if some hash keys were always needed?

def welcome(name:, place:)
  "hello #{name}, #{place}"
welcome(name:'neeraj', place: 'world')

The method definition above means that the welcome method should be passed a hash as parameter and that hash should have keys :name, and :place and no other keys should be present.

The above welcome method is defined and is called with a proper hash. The above call will work, because the hash passed has both :name and :place as keys. If any of the keys were missing in the hash, the method would throw an error. Also, you can not pass on any hash which has any extra keys other than the ones defined in the method definition. This would lead to safer code.

Splat operator

is the splat operator and ** is the double splat operator. Both of these have different meaning in different places.

def welcome(*students)
  # the splat operator here combines the incoming params into an array
  p students.class # Array

welcome("first", "second", "third")
The above is a simple usage of splat in method parameter.

rest = ["fourth", "fifth"]

Below we use the splat in calling of the method and not in the method definition. Here, it takes an array and converts it into comma separated values, similar to how  we pass on arguments to normal ruby methods.

In the following line, the splat operator in essence splits the rest array. Now the whole of params are received by the function, where the splat operator ensures that all of them are combined into the array students. So in essence, the splat operator used twice here, once in a the calling code and once in parameter list -> it combines all of the params into once array. A rather cryptic way to join an array!
welcome("first", "second", "third", *rest) 

Interesting links-