COMPUTER ENGINEERING DIARIES

Lets say we want to have sum of two integers. But we are not allowed to use + and - operators. Below is a way to do that: public class Solution {     public static int getSum(int a, int b) {         if (a > 0 && b > 0) {             return positiveSum(a, b);         }         if (a < 0 && b < 0) {             return negate(positiveSum(Math.abs(a), Math.abs(b)));         }         if (a > 0 && b < 0) {             return minus(a, Math.abs(b));         } else {             return minus(b, Math.abs(a));         }     }     private static int minus(int a, int b) {         boolean[] result = new boolean[32];         boolean carry = false;         for (int i = 0; i < 32; ++i) {             boolean ba = ((a & (1 << i))) != 0;             boolean bb = (b & (1 << i)) != 0;             result[i] = ba ^ bb;             if (carry) {                 result[i] = !result[i];             }             if (ba == true) {                

Problem description from LeetCode: Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. Input: [1,2,1,3,2,5]  Output: [3,5] Solution: If we apply XOR to all the elements, the result is the XOR of the lonely integers. The next step is finding the two integers that produce the XOR result.  To do that, we can use this trick: The set bits of A XOR B  gives us which bits are different in A and B After finding the last different set bit, we can dissect the numbers from the input.  Source Code: class Solution {         public static int[] singleNumber(int[] nums) {         int xor = 0;         for (int num : nums) {             xor ^= num;         }         int lastSetBit = lastSetBit(xor);         int set1 = 0; int set2 = 0;         for (int i = 0; i < nums.length; ++i) {             if ((nums[i] & lastSetBit) == 0) {

Problem description from LeetCode: All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. Example: Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC", "CCCCCAAAAA"] Solution: The idea is that we can use 2 bits to store a letter.  We use a map to count occurences of 10 letter sequences. When we get a new letter, we shift 2 bits to the left and then append the new letter. After appending 11th character, we must remove the first char on the left. To remove it, since we store 10 letters in 20 bits, our bit mask is: 0xFFFFF Source Code: public class RepeatedDNA {     public static List findRepeatedDnaSequences(String string) {         if (strin

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules: For 1-byte character, the first bit is a 0, followed by its unicode code. For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10. Given an array of integers representing the data, lets calculate whether it is a valid utf-8 encoding. Example: data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.  Return false.  The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character. The next byte is a continuation byte which starts with 10 and that's correct. But the second continuation byte does not start with 10, so it is invalid. Source Code: public static void main(String[] args) {         // should be true         System.out.println(validUtf8(new int[]{228, 189, 160, 229, 165, 189, 13, 10}));         //should be false      

Finding nth bit of an integer: If you want to get the nth bit of a number, use this mask: 1 << n So if you left shift 1 n times, you get the mask. Below is the expression to find the nth bit: number & (1 << n)  Setting the nth bit to 1: number | (1 << n) Clearing the nth bit (setting it to zero): We want to apply & operator with 0 to the nth bit. The mask we need is: ~(1 << n) So the expression to clear the nth bit is: number & ~(1 << n) Flipping the nth bit: We want to apply XOR with 1. Below is the expression: number ^ (1 << n) Finding if a bit in a position is set: One way to do that is to right shift the number n times. Than the nth bit is the first bit. The following expression is the answer: (number >> n) & 1 Finding number of 1 bits in unsigned integer Loop through the bits and check. (Look at hammingWeight() method code below) Finding Hamming Distance The Hamming dista

Synchronization is the coordination of two or more tasks to get the desired results. Control synchronization: One task depends on the end of another task, the second task can't start before the first has finished. Data access synchronization: Tasks have access to a shared variable and only one of the tasks can access the variable at any given time. Critical section:   A piece of code that can be only executed by a task at any given time because of its access to a shared resource. Synchronization helps us to avoid concurrency problems but this comes at a cost. So if our algorithm will not be more efficient because of heavy synchronization, then a serial program may perform better. We can use a semaphore  to control the access to a resource. A mutex (short for mutual exclusion) is a special kind of semaphore that can take only two values (resource is free and resource is busy), and only the process that sets the mutex to busy can release it. Monitor??? Tasks can use