Endeavor steps of a young IT professional

31May/111

Bit Manipulation Code Snippets

The bit manipulation problems you see on interviews are usually trivial algorithmically. They are designed not to test your "strategic" thinking, but to focus on your "tactical" ability to work directly with bits. Unfortunately for me, and probably for many of my peers who grow up on Java, it is precisely the sort of low-level stuff that we lack.

Bit manipulation can be deep with a lot to learn, I wish to present a most basic toolbox in this article.

1. Swap 2 variables without using a temporary variable.

One of the classic silly interview questions that mostly test if you have heard about this problem before. One should point out that there is practically no need for this trick nowadays, this is because most modern compilers will automatically get rid of temp variables for you when you use the normal swapping with a temporary variable. In fact, using an XOR swap can be slower because it is not the expected by the optimizing compilers, and there are severe parallelism problems associated with it.

Another issue is that the XOR swap will cause the variables to be set to zeros when they are the same, so you have to make an extra check and it ended up not being too simple.

Here is the XOR swap:

void xorSwap (int *x, int *y)
{
if (x != y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}

2. Use a bitmap to represent boolean arrays

When you have an boolean array where each element is either true or false, a good space optimization is to use a bit array to represent you data and use bitmask to work with it. Not only will this allow you to shrink the required space to 1/8 of the original, you can also access your data faster by taking advantage of the CPU's ability to manipulate multiple bits at the same time. For example, you can count the number of true values in your bit mask 32 or 64 per CPU cycle. (Population count algorithms)

How do we quickly operate on individual bits on a value? For simplicity I will use a single byte "char" as the example to illustrate the basic idea of bit masking. Note though most integers are 4 bytes each.

int a = 0x0010100 //value= 20, boolean={false, false, false, true, false, true, false, false}

2.1 Checking a bit with the bitwise AND

To check whether the fifth boolean value is true is the same as checking wether the 5th bit is 0 or 1, we can do the following.

int bitmask5 = 0x00010000 // create a bit mask with the fifth bit set to 1,value in decimal = 16
int result = a & bitmask5 // using AND to check the 5th bit of our array,if it is 0,result will be 0,else it will be something else.
if (!result) // if your language treat 0 as false you can directly use it as a boolean, otherwise you can use if (result != 0)
do things if the bit is set, if the fifth boolean is true
else
do things if the bit is set, if the fifth boolean is false

2.2 Setting a bit to 1 with the bitwise OR

Setting the 4th boolean to 1 to represent a true value with the following code

int bitmask = 0x00001000 //make a bitmask with the 4th bit set to 1, others set to false, you can set multiple bit to true if you use a bit mask with multiple 1s
int a = a | bitmask //set the bits in the original bitmap to 1 with the bit mask.

2.3 Clearing a bit to 0

Clear the 3rd bit with the following

int bitmask = 0x00000100 //Make a bit mask with the bit you want to clear set to 1
int bitmask = ~bitmask // 0x11111011,using the bitwise not to reverse the mask(make sure you use the bitwise NOT(~) instead of the logical NOT(!))
int a = a & bitmask //using AND and the reversed mask to set the 3rd bit to zero and clear it

2.3 Inverting a bit

If you don't care what a bit is but only want to flip it, you can use an XOR operation

Flip the 3rd bit:

int bitmask = 0x00000100
int a = a ^ bitmask // 0x00010100 ^ 0x00000100 = 0x00010000 = 16

Flip the 2rd bit:

int bitmask = 0x00000010
int a = a ^ bitmask // 0x00010000 ^ 0x00000010 = 0x00010010 = 18

Making the bit masks, and other considerations

Always be careful about overflows and signed-ness of your value using bit manipulation. For example, bit shift operator ">>" will cause the bit to drop off in case of an overflow. Also, some language(C) requires you handle the signed integers in inverted notation yourself, while others (Java) will handle this for you.

You can create the bit mask by writing a method to generate them using the bit shift operator ">>", though it may be faster to save the values in memory because they wont take up a lot of space. Another way is to make them into constants, if you are dealing with 32 bit integers you will need 32 of those, if you are dealing with 64 bit integers, you need 64.

const int bitmask1 = 0x00000001
const int bitmask2 = 0x00000010
const int bitmask3 = 0x00000100
...
...
const int bitmask8 = 0x10000000

Lastly, a cheat sheet:

BIT OPERATIONS CHEAT SHEET
---------------------------------------------------------
SET NTH BIT TO 1 : value = value | bitmapN
SET NTH BIT TO 0 : value = value & ~bitmapN
INVERT NTH BIT : value = value ^ bitmapN
QUERY NTH BIT : boolean isset = (value & bitmapN != 0)
DIVIDE BY 2^n : value = value << n // careful about OVERFLOW
MULTIPLY BY 2^N : value = value >> n // careful about OVERFLOW
INVERT ALL BITS: value = ~value
LEAST SIGNIFICANT SET BIT : lsb = value & - value
---------------------------------------------------------

Filed under: Uncategorized 1 Comment
19May/110

Write a data structure to maintain median as they are generated

More interesting coding questions.

Write a data structure to find and maintain median as they are generated

Click here for a nicely formatted source code that you can actually run.

If that link is broken, you can find them below:

  public static Comparator<Integer> minCom, maxCom;
  public static PriorityQueue<Integer> minQ, maxQ;

  /**
   * Add a number to the data structure, this data structure will keep track
   * of the medium as elements are added Time complexity depends on the heap,
   * it is usually O(log n)
   *
   * @param num
   */

  public static void addNumber(int num) {
    minQ.add(num);

    // if one of the heap is too big, shift the new element over
    if(minQ.size() > maxQ.size() + 1) {
      maxQ.add(minQ.poll());
    }

  }

  /**
   * Find the median in O(1) by looking at the top of the min and max heap at
   * any time
   *
   * @return
   */

  public static double seeMedian() {
    if(minQ.size() == maxQ.size()) {
      return ((minQ.peek() + maxQ.peek()) / 2.0000);
    }
    return minQ.peek();
  }
public static void main(String[] args) {
    // build the comparators that will be used for determining priority,
    // this is not needed if you are writing your own heap
    minCom = new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
      }
    };

    maxCom = new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return -o1.compareTo(o2);
      }
    };

    // create two priority queues, these can be implemented with minimum and
    // maximum heaps yourself
    minQ = new PriorityQueue<Integer>(10, minCom);
    maxQ = new PriorityQueue<Integer>(10, maxCom);

    // example input and demonstration
    int[] input = new int[] { 4, 5, 6, 3, 7, 9, 10, 17, 21, 31, 22 };

    for (int i : input) {
      addNumber(i);
      System.out.println("median is: " + seeMedian());
    }

  }
Filed under: Uncategorized No Comments
19May/110

Given an array of numbers, find if 3 of them adds up to a number n

I have been brushing up my algorithm skills when I come across this cool question online.

Give array of numbers, find out if 3 of them add up to 0

Click here for a nicely formatted source code that you can actually run.

If that link is broken, you can find them below:

  /**
   * Given a sum S and a sorted list L, find all subset of L with size 3 and
   * sum = S The idea of this solution is to rephrase the question to be
   * "find A, B, C such that A + B = (SUM - C)" O(n) Time complexity O(n^2),
   * space complexity O(1) This algorithm is in-place, some constant factor
   * improvements can be done if we are allowed to modify the list
   *
   * @param sumS
   * @param listL
   */

  public static void findThreeSum(int sumS, int[] listL) {

    // then traverse L, for each element i in L, find all size 2 subset of
    // list - i with sum S' = (S - i)
    for (int indexC = 0; indexC < listL.length; indexC++) {
      int sumWithoutC = (sumS - listL[indexC]);

      // if list[i] is greater than n already, then all subsequent
      // elements will not be part of the solution
      if(sumWithoutC <= 0)
        break;

      // find the two number that adds up to (n - i) in, pretend that C is
      // not in the list anymore because we are using it , O(n)
      findTwoSum(sumWithoutC, indexC, listL);
    }
  }
/**
   * Given a sum S and a sorted list L, find all subset of L with a size 2 and
   * sum = S This takes advantage that the list is sorted to find all possible
   * combination in one traversal Time complexity O(n), space complexity O(1)
   * The ignoreElement is used to "eliminate" an element being used in the
   * 3sum algorithm without modifying the list.
   *
   * @param sumS
   * @param ignoreElement
   * @param listL
   */

  public static void findTwoSum(int sumS, int ignoreElement, int[] listL) {
    int indexA = 0; // one pointer at the beginning, the smallest element
    int indexB = listL.length - 1; // another pointer at the end, the
                    // largest element
    int ignoreIndex = ignoreElement; // remember which element to ignore

    // while the pointer didn't meet yet
    while (indexB > indexA) {
      if(listL[indexA] + listL[indexB] > sumS || indexB == ignoreIndex) {
        // if the sum is too big, decrement the pointer B to try a
        // smaller element
        indexB--;
      } else if(listL[indexA] + listL[indexB] < sumS || indexA == ignoreIndex) {
        // if the sum is too small, increment the pointer A to try a
        // larger element
        indexA++;
      } else if(listL[indexA] + listL[indexB] == sumS) {
        // point out a solution and move the pointers to try the
        // remaining elements
        System.out.println("SUM OF " + listL[ignoreElement] + ", " + listL[indexA] + ", " + listL[indexB]);
        indexB--;
        indexA++;
      }
    }
  }
30Aug/100

Improving office productivity….at home

My Kashoo Home OfficeHow to increase home office productivity

Like many knowledge workers today, I telecommute. I also take advantage of flex-time. And because of this, my productivity is optimized. By avoiding the commute, valuable hours are added to both my working life and my personal life. By opting to rest after lunch and doing some work after dinner, I no longer feel compelled to stare at the monitor to create the illusion of productivity in lieu of real productivity. The benefits are immense both for the company and for the employee, but for these benefits to be realized, this “freedom” must be enjoyed correctly. As a newly-minted engineering graduate when I joined Kashoo to build the best accounting software, I felt thrilled but also anxious at the opportunity of working from home without the immediate supervision and physical presence of my coworkers. It is challenging indeed, but I have developed my arsenal of tools for staying fresh and productive in my Kashoo home office. I hope that, by sharing the things that I have learned, I can bring something new to your own quest for telecommuting productivity. Oh yes, before I forget, we are hiring for a Customer Service Professional. Check out the Kashoo Kareer page.

The correct mindset

To be successful in your home office endeavor, the correct mindset is essential. A telecommuter should recognize that the company is taking a risk by giving its employees the freedom of telecommuting. If you are one of the lucky telecommuters, it is up to you to prove that the decision was a wise one, or it will be short-lived as the company realizes its mistake and “fixes” it. The mindset of mutual respect goes hand-in-hand with a mindset of mutual benefit. The telecommuting arrangement is a win-win one that can result in the best gains for both parties but it is also an unstable one, in the sense that if you decide to go for personal gain by exploiting it, the company ends up with a bigger loss than if they had kept you in the office. Thus, an essential ingredient for preventing your telecommuting arrangement from ending prematurely is to share the new-found benefits and become a more productive member of the team than you are in the office.

Segment your life

A common problem with working out of a home office is finding yourself thinking about work during “off hours” and about your chores and personal life when you are supposed to be working. Having to contend with both aspects of your life all the time can quickly spiral out of control. It can also very demoralizing because despite being busy doing “things” all day and night, nothing much gets achieved. This is why a key component of telecommuting productivity is the separation of work and personal life, ensuring that at any moment, you are consciously aware of your work/off-work status, making it easier to focus and easier to relax.

Establish a before work / after work routine

The separation of work and personal life can be assisted by establishing pre-work ritual. The idea of a pre-work ritual comes from the commute. Though I do not enjoy the commute, I find it very useful to walk out of the door and have an hour or so of “cushion” time separating my personal thoughts and company thoughts. During the morning commute, I would typically think about the upcoming day of work; in the afternoon I reflect on the day of work and tie up the loose ends of the day. The commute itself becomes a clear boundary between the working hours and leisure time and serves as a perfect on-off switch. To maintain the same sort of clarity in my home office without the rush hour drive, I maintain a proper morning grooming regimen even though nobody will be seeing me. I take a short walk around the block before and after work for my own “change of status”. If you are having trouble preventing your work and life from spilling into each other, especially in the morning or late afternoon, it is a good idea to find twenty minutes, or so, to develop a routine that works for you. You will want something that is neither too fun, nor requires a lot of effort or thinking, but something that is also actively engaging to your mind and body. A refreshing shower or a short exercise session fit the bill. The key to success of this method is to force yourself to commit to the routine so it becomes a natural part of your daily life.

Separate the work area from the living area

In addition to separating your schedule with before and after work routines, physically separating the home office from the rest of your home has the same benefit of acting as a cue to aid your switch between work mode and personal mode. If you have the space to pull it off, it is a good idea to put your office in a separate room and give it the same respect that you give your old office. This means keeping it clean and uncluttered and free from objects from your household that you wouldn’t bring to the office. It is a great idea to have a computer that you use only for work and take the after work browsing or games session to another computer in your family room. This will not only act as a barrier for the urge to start watching YouTube or play a quick game when you are supposed be doing some work, but it also prevents you from reading emails or glancing at the piles of drafts, documents or code littered on the desktop of your computer and being reminded of work when you genuinely want and need to have some fun. As with the routine advice, it is imperative to force yourself to get out of your office when you make the conscious decision to finish with the work day.

Invest in the work environment

Another part of physically managing your workspace is improving the home office and making it comfortable. Though your home office is attached to your home and it may seem like a good idea to just use an old table and chairs for your office, it is important to invest to make your home office comfortable. It does not seem that much like of a stretch when you realize that one-third of your life could be spent in the dimly-lit office, in front of a desk that is too low with cramped legroom, on a chair that doesn’t adjust. Businesses invest in boring looking but surprisingly expensive office furniture because, despite your suspicions to contrary, they are concerned for your health….or at least your productivity. Even if the performance benefit is not enough to make the investment worthwhile, you may qualify for tax deductions for the home office costs. Tax deductions aside, you are in some ways already reimbursed by the amount of time and money saved by not having to go to the other side of the town.

Check out the great company I am working for at Kashoo Online Accounting Kashoo Online Accounting

15Feb/100

Passing the Microsoft 70-536 TS: .NET Framework – Application Development Foundation

This is the exam all MCPs have to take first, its mostly to test your familiarity with a .NET language of your choice, C#, VB, VC++ and emphasis strongly features of .NET framework.

After the 70-536, I still need to take the 70-562 (ASP.NET) to claim the MCTS certificate, and finally pass the 70-564(ASP.NET/Web) to claim the MCPD certificate.
The exam is not that difficult, but it is incredibly broad and very API intensive, this means that memorization will play a large role in success.
I am sharing my study plan with those of you who are thinking of taking the exam.

Time Commitment: 36 Hours

Money Commitment: $125 Exam + $55 Self-Paced Training Kit

Prerequisite:

  1. You understand the basics of programming and computer science at a level comparable to a upper-level CS student.
  2. You have some experience with Java and have done some labs with C# and Visual Studio 2008, so you understand the similarity and difference between those two.
    (I recommend reading through Programming C# to learn the language, or you have a some experience with one of the .NET languages.
  3. You have a lot of time for at least 3 days.

Day 1:

1. Read through MCTS Self-Paced Training Kit (Exam 70-536): Second Edition from cover to cover. Get an understanding of what is involved in the exam and the concepts/ideas/vocabs presented in the book. Do read the code examples but don't try to memorize them yet. (About 8 Hours)
2. Re-read particularly difficult Chapters like Access Control or Event Handling, these have a lot of new concepts and are heavily emphasized on the exams. (About 4 Hours)

Day 2:

1. Work through the guided exercises and code examples of the book on your computer, this time pay attention to how are things implemented and why are they implemented that way. All the code examples of the book are important because you will be shown codes similar to them at the exams.

  • Focus on recognizing what is correct, you don't have to write any code in the exam.
  • Pay specific attention to the codes on Delegates and Events, Security and Assembly info, these involves heavy use of the .NET APIs and information that are specific to Windows.
  • Don't bother with the chapter end questions and the practice test on the CD-ROM, they are useless.

(About 8 Hours)

2. Now you are ready for problem sets, the test kits from many test prep companies are useful. I gathered about 350 questions and started with a printed pdf with 200 questions as problem sets.

  • You don't need to simulate the test condition now so just work and look at answer as you go. Try to at least eliminate some wrong answers or give arguments to both side if you can't choose. Anytime you look at answer before you take the question, you have wasted a valuable question.
  • Regardless of whether you get a question right or wrong, use the explanations to fully understand why are the wrong answers wrong and right answers right.

(About 4 Hours)

Day 3:

1. Read up on book sections that you seem to be weak on, this time, DO pay attention to the particulars of implementation, the order of arguments, which methods/fields are valid for which classes etc. If you have trouble memorizing a code, try actually implementing it at your computer.(2 Hours)

2. Take a practice exam in exam conditions, ideally you use your simulation exam for this. Resist the urge to peek or rush through the questions. If you score higher than 90, you are quite ready for the actual thing. (1 Hour)

3. At this point you really have a choice, or a mixture of:

  • Reading up chapters that you are weak in, DO implement the code.
  • Go back to the problem set you did yesterday and work through them, eliminate a question once you fully understand it and understand the question. Before your exam, you MUST memorize all of these problems because they will show up on the actual exam.
  • Take more practice exams in exam condition to test your progress, do this sparingly as there isn't a lot of problems available.
  • Go to MSDN sections suggested by the practice exam questions you have trouble with, the MSDN contains a lot of detailed information thats not covered by the book, but this may spend a lot of time if you just wish to pass.

(9 hours or more as needed.)

Day 4:

Before the exam, you must have the following done, in order of importance:

  1. Read all sections of the book at least once. (Of course)
  2. Memorized all practice questions and practice test, this means you will consistently get 100% on all of the questions you have and know why is each question right or wrong. (This is incredibly important!)
  3. Worked through all of the code examples of the book at least once.
    With this plan and a lot of intensive studying (36 hour over three days) , your should be able to pass your 70-356 exam and become one step closer to being a MCPD. Good luck!
14Feb/100

Hello World!

As a recently graduated computer science student from the University of British Columbia. I am currently working as a software engineer at a local start up in Vancouver, BC.

Striving to excel, I spend my days learning as much as I can so I can become a skilled and contributing member of the IT industry.

The purpose of this blog is to write down things I come across in this long learning process, things worth sharing with you.

Tagged as: No Comments