Jin Lee

Retro on 2012

Words

• Vegas
• Car crash
• Bay to breakers
• AngularJs
• Sonata
• Jay
• Sundance
• Acquisition

Events

• Started 2012 in Vegas with awesome fireworks
• Got involved in a car accident that almost killed myself
• Didn’t beat my previous record but continued my commitment for Bay to breakers
• AngularJs is awesome and I started to love writing javascript
• Walked into a Hyundai dealer and bought a Sonata out of impulse
• Jay was born
• A core product summit at Sundance was fun and productive
• Permira acquisition has been finalized and we’re all rich now

C# property syntax in JavaScript

I just learned that you can define properties in JavaScript like in c# in ECMAScript5 standard.

How interesting?

function Person() {
        
        var _firstName;
        
        Object.defineProperty(this, "firstName", {
            get: function () {
                return _firstName;
            },
            set: function (value) {
                _firstName = value;
            }
        });                                                              
   }

Get to know your employees

One of my managers back in Sydney used to ask me this question at every review I had with him.
“Do you have skills that I don’t know about but you want to use at work?”. It wasn’t exact wording but it went something like that.

Basically, he wanted to get to know me better. It was as simply as that. I could say “yes” or “no”. It was my choice and he would ask the same question again at the next review.

I remember my school teachers managing 60 wild kids in a class. Is it too hard for a manger to try to get to know his less than 30 people a little better?.

Multiple assignment in Python

Scratching the surface

I just started learning Python and this is the first thing that caught my eyes probably because I haven’t seen this type of syntax in any of the languages I learned in the past. That is the multiple assignment syntax.

x = 1
y = 2

x, y = y, x

print x
# >>> 2
print y
# >>> 1

What it basically does is to swap the values of x and y variables. At first, I was like ‘what the hell is this for?’. Then after I thought about how I achieve the same thing in c#, I realized this is pretty handy. The point is that these multiple assignment are supposedly happening simultaneously.

int x = 1;
int y = 2;

// To swap the two values in c#, you need a third variable
int temp = x;
x = y;
y = temp;

In c#, there is no such thing as simultaneous multiple assignment syntax, so you need a third variable that holds the value of the either one of the two variables

Do you ever use BitVector32 in c#?

What does the BitVector32 class do?

BitVector32 is a wrapper (or you can call it abstraction) around c#’s bit operations. For example, the following two statements return the same result:

• 1 « 1
• BitVector32.CreateMask(1)

Let’s say there is an integer array containing some duplicate numbers. We want to find all duplicates. Of course, You can simply use the GroupBy function in Linq but let’s pretend we don’t have Linq.

The first option is brute force approach where each element will be compared against every element in the given array:

foreach(int i in list) 
{
    foreach(int j in list)
    {
        if (i == j) 
        {
            // print this or store it in the result list
        }
    }
}

Since the brute force approach will result in N square running time, which is pretty inefficient, we can think of utilizing HashSet which will provide a constant lookup time or O(1)

HashSet hashSet = new HashSet();

foreach(int i in list)
{    
    if (hashSet.Contains(i))
    {
        // print the duplicate or add it to the result list
    }
    else
    {
        hashSet.Add(i);
    }
}

This approach will result in the linear running time or O(n). However, it requires extra memory of n * 4 bytes (assuming we’re talking about the 32 bit integer)

The third approach is similar to using a hashset except it requires less memory by using a boolean array

bool[] masks = new bool[maxNumber];

for (int i = 0; i < list.length; i++) 
{
    if (masks[list[i]])
    {
        // print or add to the result list
    }
    else
    {
        masks[list[i]] = true;
    }
}

it uses an boolean array instead of an HashSet. It has the same run time which is O(n) but requires 1/4th amount of the memory since the bool type takes up 1 byte (8bits) while integer takes up 4 bytes (32 bits)

Finally, we can solve this problem using the BitVector32 class or the native bit shifting operations.

int check = 0;
for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i];
    if (check & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        check = check | mask;
    }
}

It will also result in a linear run time with only 32 bits of memory in total. So the memory usage is n/32. Of course, this is not going to work if the max value in the array is greater than 32. We can use 64 bit unsigned integer to increase the number of slots in the mask but it still has a very short limit. In that case, if you create an array of BitVectory32 and you can shift the bit to the BitVector32 object in the next index of the array. For instance, the code will go something like below

BitVector32[] bitVectorArray = new BitVector32[list.Length / 32];
bitVectorArray[list[i] / 32] = 1 << list[i] % 32;

This way, you don’t have to be limited to the 32 bit size limit. You can grow the size of the big mask indefinitely as long as the memory capacity allows. So, put everything together:

BitVector32[] bitVectorArray = new BitVector32[maxNumber / 32];

for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i] % 32;

    if (bitVectorArray[list[i] / 32][list[i] % 32] & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        bitVectorArray[list[i] / 32] = bitVectorArray[list[i] / 32] | mask;
    }
}

Conclusion

I haven’t had a chance to use BitVector64 class anywhere else other than in this blog as well as bit shifting tricks in general. Well, but this class drew my attention. Who knows this dot will connect to some other dots some day some time