TIANYU'S HOMEPAGE
  • Home
  • Publications
  • Hobbies
  • BLOG
    • Planning & Control
    • Machine Learning
    • Game Theory
    • Python
    • Misc
  • Contact

Crack LeetCode

Technical interview questions can be pretty hard, at least when you are not prepared.
Let's get started!

6. ZigZag Conversion

3/4/2016

0 Comments

 
Sol 1 (C++): state machine 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

string convert(string s, int nRows) {
    if (nRows == 1) return s;
    vector < string > outs(nRows);
    bool flag = true; // idx going down
    int idx = 0;
    for (int i = 0; i < s.length(); i++) {
        outs[idx].push_back(s[i]);

        if (flag) {
            if (idx == nRows - 1) {
                flag = false;
                idx--;
            } else {
                idx++;
            }
        } else {
            if (idx == 0) {
                flag = true;
                idx++;
            } else {
                idx--;
            }
        }
    }

    string ans;
    for (int i = 0; i < nRows; i++)
        ans.append(outs[i]);

    return ans;
}
0 Comments

5. Longest Palindromic Substring

3/3/2016

0 Comments

 
Sol 1 (C++): scan & center growing, distinguish odd/even cases (e.g., 'a' & 'aa' can both be the center) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

string longestPalindrome(string s) {
    int maxLength = 1;
    int maxId0 = 0;
    int maxIdf = 0;
    
    for(int i=0; i<s.length(); i++) {
        
        int sideNum = 0;
        
        bool shouldContinue = true;
        while(shouldContinue) {
            int tmpId0 = i - sideNum; if( tmpId0 < 0 ) { shouldContinue = false; continue; }
            int tmpIdf = i + sideNum; if( tmpIdf >= s.length() ) { shouldContinue = false; continue; }
            if( s[tmpId0] != s[tmpIdf] ) { shouldContinue = false; continue;}
            
            int newLength = tmpIdf - tmpId0 + 1;
            if( newLength > maxLength ) {
                maxLength = newLength;
                maxId0 = tmpId0;
                maxIdf = tmpIdf;
            }
            sideNum++;
        }
    }
    
    for(int i=1; i<s.length(); i++) {
        if( s[i-1] != s[i] ) { continue; }
        
        int sideNum = 0;
        
        bool shouldContinue = true;
        while(shouldContinue) {
            int tmpId0 = i-1 - sideNum; if( tmpId0 < 0 ) { shouldContinue = false; continue; }
            int tmpIdf = i + sideNum; if( tmpIdf >= s.length() ) { shouldContinue = false; continue; }
            if( s[tmpId0] != s[tmpIdf] ) { shouldContinue = false; continue;}
            
            int newLength = tmpIdf - tmpId0 + 1;
            if( newLength > maxLength ) {
                maxLength = newLength;
                maxId0 = tmpId0;
                maxIdf = tmpIdf;
            }
            sideNum++;
        }
    }
    
    return s.substr(maxId0, maxIdf-maxId0+1);
}
Sol 2: DP
1. Define:
    dp[i][j]: s[i…j] is/is not palindrome
2. Initialize:
    all i>j: dp[i][j] = false
    all i=j: dp[i][j] = true
    all i+1=j: if s[i] == s[j], then dp[i][j] = true, else dp[i][j] = false
3. Update rule:
    if s[i]==s[j] && dp[i+1][j-1] == true, then dp[i][j] == true, else dp[i][j] == false

Sol 3: Manacher algorithm
http://www.cnblogs.com/TenosDoIt/p/3675788.html​
0 Comments

85. Maximal Rectangle

1/7/2016

0 Comments

 

Sol 1: use solution to Problem 84 ...

Skipped

Sol 2 (Python): naive dynamic programming (a nice double DP formulation, TLE though...)

Picture

dp[i][j][k][h, w]:
{i}: row id
[j]: col id
[k]: rectangle id
[h, w]: rectangle height/width 

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

def maximalRectangle(matrix):
    """
    :type matrix: List[List[str]]
    :rtype: int
    """
    M = len(matrix)
    if M == 0:
        return 0
    N = len(matrix[0])
    if N == 0:
        return 0

    dp = [[[[0,0]] for i in range(0,N)] for j in range(0,M)]

    maxArea = 0

    if matrix[0][0] == '1':
        dp[0][0][0][0] = 1
        dp[0][0][0][1] = 1
    for j in range(1,N):
        if matrix[0][j] == '1':
            dp[0][j][0][0] = 1
            dp[0][j][0][1] = dp[0][j-1][0][1] + 1
        maxArea = max(maxArea, dp[0][j][0][0] * dp[0][j][0][1])

    for i in range(1,M):
        if matrix[i][0] == '1':
            dp[i][0][0][0] = dp[i-1][0][0][0] + 1
            dp[i][0][0][1] = 1
        maxArea = max(maxArea, dp[i][0][0][0] * dp[i][0][0][0])

    for i in range(1,M):
        for j in range(1,N):

            if matrix[i][j] == '1':
                for p in range( len(dp[i][j-1]) ):
                    for q in range( len(dp[i-1][j]) ):
                        region1 = [0, 0]
                        region1[0] = max(1, min(dp[i][j-1][p][0], dp[i-1][j][q][0] + 1))
                        region1[1] = max(1, dp[i][j-1][p][1] + 1)
                        # Check if there is element in dp[i][j] whose h & w are both smaller than region1, then delete that element
                        # Check if there is element in dp[i][j] whose h & w are both greater than region1, then do not insert this element
                        cnt = 0
                        isInsert = True
                        while cnt < len(dp[i][j]):
                            if dp[i][j][cnt][0] <= region1[0] and dp[i][j][cnt][1] <= region1[1]:
                                del dp[i][j][cnt]
                                cnt-=1
                            elif dp[i][j][cnt][0] > region1[0] and dp[i][j][cnt][1] > region1[1]:
                                isInsert = False
                            cnt+=1
                        if isInsert:
                            dp[i][j].append( region1 )

                        region2 = [0, 0]
                        region2[0] = max(1, dp[i-1][j][q][0] + 1)
                        region2[1] = max(1, min(dp[i][j-1][p][1] + 1, dp[i-1][j][q][1]))
                        # Check if there is element in dp[i][j] whose h & w are both smaller than region1, then delete that element
                        cnt = 0
                        isInsert = True
                        while cnt < len(dp[i][j]):
                            if dp[i][j][cnt][0] <= region2[0] and dp[i][j][cnt][1] <= region2[1]:
                                del dp[i][j][cnt]
                                cnt-=1
                            elif dp[i][j][cnt][0] > region2[0] and dp[i][j][cnt][1] > region2[1]:
                                isInsert = False
                            cnt+=1
                        # Check if there is element in dp[i][j] whose h & w are both greater than region1, then do not insert this element
                        if isInsert:
                            dp[i][j].append( region2 )

            for k in range(len(dp[i][j])):
                maxArea = max(maxArea, dp[i][j][k][0] * dp[i][j][k][1])
    return maxArea


matrix = [['0', '1', '1', '0'],
          ['1', '1', '1', '1'],
          ['0', '1', '1', '1'],
          ['1', '1', '1', '1']]
print(maximalRectangle(matrix))
0 Comments

221. Maximal Square

1/6/2016

0 Comments

 

Sol 1 (Python): dynamic programming

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

def maximalSquare(self, matrix):
    """
    :type matrix: List[List[str]]
    :rtype: int
    """
    M = len(matrix)
    if M == 0:
        return 0
    N = len(matrix[0])
    if N == 0:
        return 0

    # http://stackoverflow.com/questions/2397141/how-to-initialize-a-two-dimensional-array-in-python
    dp = [[0 for i in range(0,N)] for j in range(0,M)]
    maxlength = 0

    i = 0
    for j in range(0,N):
        if matrix[i][j] == '1':
            dp[i][j] = 1
        else:
            dp[i][j] = 0
        maxlength = max(maxlength, dp[i][j])

    j = 0
    for i in range(0,M):
        if matrix[i][j] == '1':
            dp[i][j] = 1
        else:
            dp[i][j] = 0
        maxlength = max(maxlength, dp[i][j])

    for i in range(1,M):
        for j in range(1,N):
            if matrix[i][j] == '1':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            else:
                dp[i][j] = 0
            maxlength = max(maxlength, dp[i][j])

    return maxlength*maxlength
0 Comments

53. Maximum Subarray

1/6/2016

0 Comments

 

Sol 1 (python): dynamic programming
The key idea is really simple. Define dp[i] as the cumulative sum of the greatest subarray that INCLUDEs the ith number, nums[i]. Then only two options exist for every incoming nums[i]:
1. either appended to the greatest subarray that includes the (i-1)th number ==> the cumulative sum will be dp[i]=dp[i-1]+nums[i], or
2. start the subarray from itself ==> dp[i]=nums[i]
We always choose the option that yields the greater dp[i] value: dp[i]=max(dp[i-1]+nums[i], nums[i])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) == 0:
        return 0

    maxSum = float('-inf')

    dp = 0
    for i in range(0, len(nums)):
        dp = max(dp+nums[i], nums[i])
        maxSum = max(dp, maxSum)

    return maxSum
0 Comments

4. Median of Two Sorted Arrays

1/3/2016

0 Comments

 

Sol 1 (python): merge two sorted array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

def findMedianSortedArrays(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: float
    """
    m = len(nums1)
    n = len(nums2)

    idx1 = 0
    idx2 = 0
    idxm = 0

    isEven = (m+n)%2 == 0

    currM = 0
    prevM = 0

    while idx1 < m or idx2 < n:
        if idx1 == m:
            prevM = currM
            currM = nums2[idx2]
            idx2 = idx2+1
            idxm = idxm+1
        elif idx2 == n:
            prevM = currM
            currM = nums1[idx1]
            idx1 = idx1+1
            idxm = idxm+1
        else:
            if nums1[idx1] <= nums2[idx2]:
                prevM = currM
                currM = nums1[idx1]
                idx1 = idx1+1
                idxm = idxm+1
            else:
                prevM = currM
                currM = nums2[idx2]
                idx2 = idx2+1
                idxm = idxm+1

        if isEven and (int)((m+n)/2) == idxm-1:
            return (prevM + currM) / 2.0
        elif not isEven and (int)((m+n)/2) == idxm-1:
            return currM

Sol 2: find kth smallest number --> binary search

The following blog provided a very good analysis: http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
0 Comments

3. Longest Substring Without Repeating Characters

12/29/2015

0 Comments

 

Sol 1 (C++): hash table (set) + two pointers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int lengthOfLongestSubstring(string s) {
    if(s.length() == 0) return 0;

    int idx0 = 0;
    int idxf = 1;

    int maxLength = 1;

    unordered_set<char> set;
    set.insert(s[idx0]);

    while(idxf<s.length()) {
        if( set.find(s[idxf]) != set.end() ) {
            idxf--;
            set.erase(s[idx0]);
            idx0++;
        }
        else {
            set.insert(s[idxf]);
            maxLength = max(maxLength, idxf-idx0+1);
        }
       
        idxf++;
    }

    return maxLength;
}

Sol 2 (Python): hash table (map) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    strLength = len(s)
    tmp = []
    charMap = dict(tmp)

    idx0 = 0
    idxf = 0

    maxLength = 0

    while idxf < strLength:
        charCurr = s[idxf]
        if charCurr in charMap:
            # remove the characters from idx0 to idxStop
            idxStop = charMap[charCurr]
            for id in range(idx0, idxStop+1):
                if s[id] in charMap:
                    del charMap[s[id]]
            charMap[charCurr] = idxf
            idx0 = idxStop + 1
        else:
            charMap[charCurr] = idxf
            maxLength = max( maxLength, idxf-idx0+1 )
        idxf+=1

    return maxLength
Copyright © [Tianyu Gu] [2016]. All rights reserved.
0 Comments

2.  Add Two Numbers

12/29/2015

0 Comments

 

Sol 1 (C++): math, linked list, carry

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
    ListNode* ansRoot = NULL;
    ListNode* ansCurr = NULL;
       
    bool firstTime = true;
    int carry = 0;
       
    while( l1 != NULL || l2 != NULL || carry != 0 )
    {
        int val1 = (l1!=NULL) ? l1->val : 0;
        int val2 = (l2!=NULL) ? l2->val : 0;   
        ListNode* newNode = NULL;
           
        int tmpVal = val1 + val2 + carry;
        if( tmpVal > 9 )
        {
            carry = 1;
            newNode = new ListNode(tmpVal - 10);
        }
        else
        {
            carry = 0;
            newNode = new ListNode(tmpVal);
        }
           
        if(firstTime)
        {
            firstTime = false;
            ansRoot = newNode;
            ansCurr = ansRoot;
        }
        else
        {
            ansCurr->next = newNode;
            ansCurr = ansCurr->next;
        }
           
        l1 = (l1!=NULL) ? l1->next : l1;
        l2 = (l2!=NULL) ? l2->next : l2;
    }
       
    return ansRoot;
}
Copyright © [Tianyu Gu] [2016]. All rights reserved.
0 Comments

1. Two sum

12/29/2015

0 Comments

 

Sol 1 (Python): sort + two pointers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """

    numIdxPairs = []
    for idx in range(0, len(nums)):
        numIdxPairs.append( (nums[idx], idx) )

    def getKey(item):
        return item[0]
    numIdxPairs.sort( key=getKey )

    idx0 = 0
    idxf = len(nums)-1

    ans = []
    while idx0 != idxf:
        if numIdxPairs[idx0][0] + numIdxPairs[idxf][0] == target:
            ans = [numIdxPairs[idx0][1]+1, numIdxPairs[idxf][1]+1]
            ans.sort()
            break
        elif numIdxPairs[idx0][0] + numIdxPairs[idxf][0] < target:
            idx0 = idx0 + 1
        else:
            idxf = idxf - 1

    return ans

Sol 2 (C++): hash table

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

vector<int> twoSum(vector<int> &numbers, int target) 
{
    std::map<int, int> map;
    for(int i=0; i<numbers.size(); i++) {
        map.insert(std::make_pair(numbers[i],i) );
    }
   
    for(int i=0; i<numbers.size(); i++) {
        std::map<int,int>::iterator iter = map.find(target-numbers[i]);
        if( iter != map.end() && i != iter->second ) {
            vector<int> answer;
            if( i<iter->second ) {
                answer.push_back( i + 1 );
                answer.push_back( iter->second + 1 );
            } 
            else {
                answer.push_back( iter->second + 1 );
                answer.push_back( i + 1 );
            }               
            return answer;
        }
    }
}
Copyright © [Tianyu Gu] [2016]. All rights reserved.
0 Comments
  • Home
  • Publications
  • Hobbies
  • BLOG
    • Planning & Control
    • Machine Learning
    • Game Theory
    • Python
    • Misc
  • Contact