Saturday, March 21, 2015

Leetcode - Repeated DNA Sequences


Problem Link:

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.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

class Solution:
    # @param s, a string
    # @return a list of strings
    def findRepeatedDnaSequences(self, s):
        rs = []
        stringList = {}
        l = len(s)
        if(l <= 10):
            return rs
        k = l - 10
        while (k >= 0):
            if s[k:k+10] not in stringList:
                # stringList.append(s[k:k+10])
                stringList[s[k:k+10]] = 1

            elif s[k:k+10] not in rs:
                rs.append(s[k:k+10])
            k = k - 1
     
        return rs

My Lesson:
At the beginning, I tried to use stringList as an array.
     # stringList.append(s[k:k+10])
However, it will give me an error message: Time exceed limitation.
So I change array into a dictionary, which is based on HashMap. Then it will not give that error.
     stringList[s[k:k+10]] = 1


Leetcode - Find Peak Element

Problem Link --
Problem Description:
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findPeakElement(self, num):
        l = len(num)
        if(l == 1):
            return 0
        if(l == 0):
            return None
           
        if(num[0] > num[1]):
            return 0
        if(num[l-1] > num[l-2]):
            return (l-1)
           
        for i in range(1,l-1):
            if(num[i] > num[i+1] and (num[i] > num[i-1])):
                return i
       
        return None

Solution:
1. You have to notice the special case where the starting and ending nodes should be checked in a different way.

2. You must realize that  when the length of array is less than 2, the result should be 0 or none!



Thinking:
Every time you program on leetcode, it is better to run it until you are sure that everything goes well. Because in real interview setting, it is probably impossible for you to debug your program by running it. Usually, you will be asked to write your program in a white board.

Friday, March 20, 2015

Leetcode - Reverse Bits

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        rs = 0
        # rs = n%2
        # n = n >> 1
        for i in range(32):
            if (n % 2):
                rs = rs << 1
                rs = rs + 1

            else:  
                rs = rs << 1
            n = n >> 1
         
        return rs

Mistake I have made:
1.  It should move the step first and then add one.
                rs = rs << 1
                rs = rs + 1

2. rs has to be initialized before used
                rs = 0 

The cost for this method is very small!!

LeetCode - Number of 1 Bits (Python)

class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        rs = 0
        while(n > 0):
            if(n%2 == 1):
                rs = rs + 1
            elif ( n%2 == 0 ) and ( n/2 == 0 ):
                rs = rs + 1
            n = n/2
           
        return rs

Easy Mistake to make:

In the first practice, I didn't add that, so for example, when n is 2, it would never let rs add one. because the result of mode would be Zero. So in order to deal with the missing of one for the last digit 1, I add:

elif ( n%2 == 0 ) and ( n/2 == 0 ): 

It means after n = n/2, when n is 2, rs need add one anyway.