class Solution:
def twoSum(self, nums, target):
my_dict = {item:index for index,item in enumerate(nums)} # Create dict with item:index key-pair.
if target % 2 == 0 and nums.count(target/2) == 2: # Edge case: two identical elements with target/2 value?
return [i for i,val in enumerate(nums) if val==target/2] # return list of indexes. See reference
else:
for index, item in enumerate(nums): # for all elements in the list, O(n) RT
seek_number = target-nums[index] # Get the seek number
if seek_number != target/2 and seek_number in my_dict: # avoid the edge case
return [index, my_dict[seek_number]]
break
# reference: https://stackoverflow.com/questions/6294179/how-to-find-all-occurrences-of-an-element-in-a-list
Given a 32-bit signed integer, reverse digits of an integer. Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
class Solution:
def reverse(self, x):
string_x = str(x)
result = ''
if string_x[0] == '-': # edge case: negative number
result += string_x[0] # add the negative sign in front
end_num = len(string_x)-1 # do not include the first characger
else:
end_num = len(string_x)
for i in range(0, end_num):
result += string_x[len(string_x)-i-1] # add the character to result int
if abs(int(result)) < 2**31: # edge case: check whether interger exceeds 32-bit limit
return int(result)
else:
return 0
class Solution:
def isPalindrome(self, x):
if x < 0: # edge case: false for all negative number
return False
else:
x = str(x) # cast it into string
for i in range(0, len(x)//2): # loop from 0 to the mid-point
if x[i] != x[len(x)-i-1]:
return False
return True
`
class Solution:
def longestCommonPrefix(self, strs):
if strs == []: # edge case: empty list?
return ""
shortest_length = min(len(x) for x in strs) # length of the shortest string
for i in range(0, shortest_length): # loop through
char_list = [x[i] for x in strs] # character list for all strings at position i
if char_list.count(char_list[0]) < len(strs): # the sum of the count is less than total number
return strs[0][:i] # return upon the current length
return strs[0][:shortest_length] # edge case: all of them are the same, return the shortest one
class Solution:
def longestCommonPrefix(self, strs):
if not strs:
return ""
shortest = min(strs,key=len)
for i, ch in enumerate(shortest):
for other in strs:
if other[i] != ch:
return shortest[:i]
return shortest
20. Valid Parentheses(20min)
Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
class Solution:
def isValid(self, s):
stack = []
if s == '': # edge case: empty string
return True
else:
for i in range(0, len(s)):
if s[i] == '(' or s[i] == '{' or s[i] == '[': # append to stack for left parentheses
stack.append(s[i])
else:
if stack == []: # edge case: empty stack when coming in a right parentheses
return False
elif s[i] == ')':
if stack.pop() != '(':
return False
elif s[i] == ']':
if stack.pop() != '[':
return False
elif s[i] == '}':
if stack.pop() != '{':
return False
if stack == []: # if stack is empty
return True
else:
return False
Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
class Solution:
def removeDuplicates(self, nums):
start = 0 # lower limit
end = len(nums) - 1 # upper limit
if start >= end: # edge case: empty list or list with 1 element
return end+1
else:
while start < end: # go over the unique part of the list
if nums[start+1] == nums[start]:
temp = nums.pop(start+1) # pop up the replicated element
nums.append(temp) # append to the end
end-=1 # decrease the lower limit to avoid it
else:
start+=1
return end+1
Given an array and a value, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
class Solution:
def strStr(self, haystack, needle):
if len(needle) == 0 or haystack == needle: # edge case: empty or identical needle
return 0
elif len(needle) > len(haystack): # edge case: if needle is longer than haystack
return -1
else:
for i in range (0, len(haystack)-len(needle)+1): # total h-n+1 positions
sub_haystack = haystack[i:i+len(needle)]
if sub_haystack == needle:
return i
return -1
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) < 1: # edge case: empty list
return 0
elif nums[0] >= target: # edge case: smaller than the first element
return 0
elif nums[len(nums)-1] < target: # edge case: larger than the last element
return len(nums)
elif nums[len(nums)-1] == target: # edge case same as the last element
return len(nums)-1
else:
start = 0
end = len(nums) - 1
mid = (end + start) // 2
while start != mid and mid != end: # could be changed to start != end
if target == nums[mid]:
return mid
elif target < nums[mid]:
end = mid
mid = (end + start) // 2
else:
start = mid
mid = (end + start) // 2
return start+1
class Solution:
def maxSubArray(self, nums):
if len(nums) < 1: # edge case: empty list
return float("-inf")
else:
results = [nums[0]] # initiate results
for i in range(1, len(nums)): # loop through 1 to the end
results.append(max(results[i-1]+nums[i], nums[i])) # append the max between the continued subarray or start a new one
return max(results) # return the max result
class Solution:
def lengthOfLastWord(self, s):
length = 0
s = s.strip() # delete whitespaces before and after
for i in range(0, len(s)):
if s[len(s)-i-1] != ' ': # whether the character is whitespace or not
length+=1
else:
return length
return length
class Solution:
def plusOne(self, digits):
number = 0
for i in range(0, len(digits)):
number += (digits[len(digits)-i-1]) * (10**i) # transform each digits into integer
number += 1
return [int(x) for x in str(number)] # return list of digits
附录：网上的code
.py
1 2 3
class Solution:
67. Add Binary (30min)
问题
我的解法清晰明了：两个helper function负责转换binary和integer，然后直接调用helper function就可以了，需要注意log function的domain是positive real number，要考虑到edge case.
class Solution:
def addBinary(self, a, b):
import math
def binary2Int(b):
number = 0
for i in range(0, len(b)):
number += int(b[len(b)-i-1]) * (2**i) # same logic as 66
return number
def int2Binary(num):
binary = ""
digits = math.floor(math.log2(num)) + 1 # number of digits
for i in range(0, digits): # for each digits
if num >= 2**(digits-i-1): # if the num is larger than the current digits
num -= 2**(digits-i-1)
binary += "1"
else:
binary += "0"
return binary
numA = binary2Int(a)
numB = binary2Int(b)
if numA == 0 and numB == 0:
return "0"
else:
return int2Binary(numA+numB)
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
start = 0
end = x
if x <= 1: # edge case: x = 0
return x
else:
while(start <= end): # when start is not end
mid = (start + end) // 2 # calculate mid
if mid * mid > x: # if x < mid^2: decrease end
end = mid-1
else:
if (mid+1) * (mid+1) > x: x is between mid^2 and (mid+1)^2
return mid
else: x < (mid+1)^2: increase start
start = mid+1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head: # edge case: empty ListNode
return []
else:
results = ListNode(head.val) # construct a new ListNode
prev = results # setup pointer
while head.next: # while there is a pointer to the next
if head.next.val != head.val:
prev.next = head.next # let the pointer point the the item
prev = prev.next # move the pointer to the next
head = head.next # move the list to the next in any cases
prev.next = None # After finishing, close up the pointer
return results
class Solution:
def merge(self, nums1, m, nums2, n):
while m > 0 and n > 0:
if nums1[m-1] >= nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSameTree(self, p, q):
def tree2List(t):
if not t: # edge case: empty node
return None
else:
result = [] # string result
stack = [t] # stack
while stack: # if not finished
node = stack.pop(0) # pop the first element: FIFO
result.append(node.val) # append the value to the stack
if not (node.left or node.right): # if empty node
print("None")
else:
if node.left: # if there exists left node: add to stack
stack.append(node.left)
else: # add indicator to result
result.append("Left")
if node.right:
stack.append(node.right)
else:
result.append("Right")
return result
return tree2List(p) == tree2List(q)
class Solution:
def isSameTree(self, p, q):
if p is None and q is None: # if both p and q are empty nodes
return True
elif p is None or q is None: # if one of them are empty but not the others
return False
if p.val != q.val: # if value is not equal
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) # use recursion to return the results from left node and from right node. Wonderful!
class Solution:
def isSymmetric(self, root):
def isMirror(leftT, rightT):
if leftT == None and rightT == None: # two empty tree
return True
elif leftT == None or rightT == None: # either tree is empty
return False
else: # the value of current node, left of leftT vs. right of rightT, right of leftT vs. left of rightT
return leftT.val == rightT.val and isMirror(leftT.left, rightT.right) and isMirror(leftT.right, rightT.left)
return isMirror(root, root)
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = [] # Initialize empty stack
self.min = [] # Initialize empty min stack
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.stack.append(x) # append x to stack
if self.min == []: # edge case: empty min stack
self.min.append(x)
elif x < self.min[-1]: # if x is smaller than the min value
self.min.append(x)
else:
self.min.append(self.min[-1]) # keep the current min value
def pop(self):
"""
:rtype: void
"""
self.min.pop() # pop the value in min stack to release
return self.stack.pop() # return the value
def top(self):
"""
:rtype: int
"""
return self.stack[-1] # get the last item
def getMin(self):
"""
:rtype: int
"""
if self.min is None: # edge case: empty stack
return None
else:
return self.min[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
class Solution:
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows < 1: # edge case: 0 stage
return []
elif numRows == 1: # edge case: 1 stage
return [[1]]
elif numRows == 2: # edge case: 2 stages
return [[1],[1,1]]
else:
results = [[1],[1,1]] # initialize 2 stages
for i in range(2, numRows): # for loop for stages 2 to numRows
temp = [1] # initialize current floor
for j in range(1, i): # complete value in between
temp.append(results[i-1][j-1]+results[i-1][j]) # append the value
temp.append(1) # append the last element
results.append(temp) # append the finished floor to the stage
return results
class Solution:
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.lower() # lower all letter
if not s: # edge case: empty string
return True
else:
i = 0 # start index
j = len(s)-1 # end index
while(i < j): # while not finished
if not s[i].isalnum(): # edge case: char i is not a valid input
i+=1
elif not s[j].isalnum(): # edge case： char j is not a valid input
j-=1
elif s[j] != s[i]: # if two chars are not the same:
return False
else: # if two chars are the same
i+=1
j-=1
return True
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dict_int = {} # empty dict
for i in range(0, len(nums)): # loop through all elements
if nums[i] not in dict_int: # if not seen before: add it
dict_int.update({nums[i]: 1})
else: # remove seen item
del dict_int[nums[i]]
for key in dict_int:
return key
附录：网上的code
Concept
If we take XOR of zero and some bit, it will return that bit
a \oplus 0 = aa⊕0=a
If we take XOR of two same bits, it will return 0
a \oplus a = 0a⊕a=0
a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = ba⊕b⊕a=(a⊕a)⊕b=0⊕b=b
So we can XOR all bits together to find the unique number.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head == None or head.next == None: # edge case: empty list or only 1 node in it
return False
else:
slow = head # slow pointer
fast = head.next # fast pointer
while slow != fast: # if not equal
if fast == None or fast.next == None: # if fast pointer reaches the end
return False
slow = slow.next # move slow pointer 1 step forward
fast = fast.next.next # move fast pointer 2 steps forward
return True
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
start = 0 # front pointer
end = len(numbers)-1 # end pointer
while start < end: # if start is less than end
if numbers[start]+numbers[end] > target: # sum is greater than target: move back end pointer
end-=1
elif numbers[start]+numbers[end] < target: # sum is smaller than target: move forward front pointer
start+=1
else:
return [start+1, end+1]
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
totalNum = len(nums) # length of the nums
numDict = {} # initialize dict
for i in nums:
if i not in numDict: # element that is not in the dict
numDict.update({i: 1})
else:
numDict[i] += 1
if numDict[i] > math.floor(totalNum/2): # check if it is the majoirity element
return i
class Solution:
def majorityElement(self, nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 5: # edge case: no zero
return 0
elif n == 5: # edge case: one zero
return 1
else:
numOfZero = 0
num = int(math.floor(math.log(n,5))) # max number of power of 5
for i in range(1, num+1):
numOfZero += n // 5**i # add the corresponding number of 5
return(numOfZero)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if not head: # edge case: empty list
return []
else:
headPointer = head # set up pointer
while headPointer.val == val: # while the first element need to be deleted
if headPointer.next == None: # edge case: only 1 element exists
return []
else:
head = headPointer.next # update the head to the next
headPointer = head # update the pointer
while headPointer != None: # while the pointer is not None
if headPointer.next == None: # if the pointer is end: return the head
return head
elif headPointer.next.val == val: # if the value of the next need to be deleted
headPointer.next = headPointer.next.next # update the pointer to be the second next one
else:
headPointer = headPointer.next # update the pointer to the next element
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: # edge case: empty list
return 0
else:
results = [0] # add a 0 in front
results.append(nums[0]) # add the first household
nums.insert(0,0) # insert 0 in front
for i in range(2,len(nums)): # for the second household and then:
results.append(max(results[i-1], nums[i] + results[i-2]))
return results.pop()
附录：网上的code
.py
1 2
202. Happy Number (20min)
问题
这道题在思路上很简单，如果用dict记录下每次的数字的话很轻松就能写出来了。但是如果想达到in-place的话则需要仿照之前写过的detect linked list cycle的方法。
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
numList = [] # number list
while n not in numList: # if is not visited
numList.append(n) # append the current number
sum = 0
for i in str(n): # calculate the sum of squared of each digit
sum += int(i)**2
n = sum
if numList.pop() == 1: # if the last one is 1, return True
return True
else:
return False
附录：网上的code
.py
1 2
Zhifu Xiao
Master Student at Columbia University studying Data Science. Love to become a full-stack data scientist!
Get the big picture, determine scope, define success, find resources Big picture: know daily SQL queries, how to use them, what are the tricks and how to optimize them. Scope: 80% most freqent SQL usage. Success: Finish the online quiz on Hackerrank on SQL. Resources: SQL in 10 Minutes, Sams Teach Yourself (4th Edition) by Ben Forta
Get started Database vs. Table vs. Column: Container vs. structured file for some specific character vs.
As a graduating student in Data Science without much experience in that field, I want to write something for people with similiar background on how to review data science and get ready for interview. Here is my methodology adapted from the book Soft Skills: The Software Developer’s Life Manual.
Before we started, it is very important to know yourself in the data science field: what is your current stage, what kind of applicant you want to be, and what is your strength and weakness?
I started this blog last September, and I haven’t used it until this January. I began to write some articles this April regularly, so I was not entirely familiar with blogging, and it seems that no so many people know and visit this blog. Earlier today, when I tried to click on the tags under the article, I found that there is a bug corresponding it that it uses two backslashes instead of one.
In my recent project, there is a need to create some visualization for the relationship between bank accounts. One bank account could serve as an intermediate account to receive money from its child account, and transfer the surplus to its head account. I want to find out the relationship between accounts and do some further analysis, so I searched online to find some visualization tools for network analysis, and here are some tools I try.
1 Abstract
2 Introduction
3 Preliminary Analysis of Data Quality
3.1 Missing Patterns Analysis
3.2 Outlier Analysis
4 Executive Summary
5 Main Analysis
5.1 Analysis on Speaking Languages
5.2 Analysis on Ethnicity
5.3 Analysis on Body Type
6 Summary, Limitation and Further Direction
Reference
1 Abstract
This exploratory data analysis firstly provides a preliminary analysis of the data quality of the Yahoo Dating dataset. An executive summary is followed to explain the most important findings in this study.
I received my Nintendo Labo 01: variety kit this afternoon, and I immediately went through it. There are three parts: Make, Play and Discover. You need to fold and formulate different items, like RC car, fishing rod, and piano. Each piece will take you a while to finish it. Larger and more complicated piece will take longer time: the toy-con piano will take up to 210 minutes to complete that, so you need to prepare for that.
