输入"rft567.908kih000000hh890jug678gtff567"这样包含字母和数字的字符串，找到出线次数最多的数字，print "567 shows two time"
s = "rft567.908kih000000hh890jug678gtff567f678"
s += ' ' #special case to deal with last number
pre, i = 0, 0
lis = []
import collections
mp = collections.defaultdict(int)
while i < len(s):
if s[i] != '-' and not s[i].isdigit():
if i!=pre:
mp[s[pre:i]] += 1
i += 1
pre = i
else:
i += 1
cumax = 0
res = []
for v, w in mp.items():
if w > cumax:
tmp = []
cumax = w
tmp.append(v)
res = tmp
elif w == cumax:
res.append(v)
print res
test justification
class Solution(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
res, cur, num_of_letter = [], [], 0
for w in words:
if len(cur) + len(w) + num_of_letter > maxWidth:
for i in xrange(maxWidth - num_of_letter):
cur[i%(len(cur)-1 or 1)] += ' '
res.append(''.join(cur))
cur, num_of_letter = [], 0
cur += [w]
num_of_letter += len(w)
return res + [' '.join(cur).ljust(maxWidth)]
edit distance
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
len1 = len(word1)
len2 = len(word2)
f = [[0 for i in xrange(len2+1)] for j in xrange(len1+1)]
for i in xrange(len1+1):
f[i][0] = i
for j in xrange(len2+1):
f[0][j] = j
for i in xrange(1, len1+1):
for j in xrange(1, len2+1):
if word1[i-1] == word2[j-1]:
f[i][j] = f[i-1][j-1]
else:
f[i][j] = min(f[i-1][j-1], f[i][j-1], f[i-1][j]) + 1
return f[-1][-1]
Largest Rectangle in Histogram
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
heights.append(0)
stack = [-1]
result = 0
for i in range(len(heights)):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
result = max(result, h * w)
stack.append(i)
heights.pop()
return result
第一道题是coding，把一个字符串转化成浮点数， e.g. "123.456" -> 123.456 e.g. "+.34" -> 0.34 e.g. "-1.234" -> -1.234 输入不保证是valid，如果不valid，throw exception即可
double convert(string s){
double ans = 0;
int i=0, n=s.size();
while(i<n && s[i]!='.' && s[i]!='e') ans= ans*10+s[i]-'0', i++;
if(i>=n) return ans;
if(s[i]=='.'){
i++;
double w = 0.1;
while(i<n && s[i]!='e') ans+=w*(s[i]-'0'), w/=10, i++;;
}
if(i>=n) return ans;
i++;
int exp=0;
bool flag=0;//0 means +, 1 means -
if(i<n && s[i]=='+') i++;
else if(i< n && s[i]=='-') i++, flag=1;
while(i<n) exp=exp*10+s[i]-'0', i++;
if(!flag) ans = ans * pow(10, exp);
else ans = ans/ pow(10, exp);
return ans;
}
第二道题大致是个设计题，系统向后台写record，统计过去24小时的records中内出现次数前五的词。 follow up是如果我在写日志的时候，为了减少每条日志的大小，不写timestamp，怎么获得同样的答案，可以有误差。
- find max number of points in one line + 系统设计（设计一个topic ranking 系统）
- design calendar class 有 day year month 实现 add (days) return calendar、、
- 有向有环图中 找source 到 target 的距离为n的可能性
wordbreak 2 (follow up : NLP problems)
2 integer differnce, distance
c = x ^ y
count = 0
while c!= 0:
c &= (c-1)
count += 1
return count
- sort colors
def sortColors(self, A):
# write your code here
if A == []:
return
p0, p2 = 0, len(A)-1
i = 0
while i <= p2:
if A[i] == 2:
A[i], A[p2] = A[p2], A[i]
p2 -= 1
elif A[i] == 0:
A[i], A[p0] = A[p0], A[i]
p0 += 1
i += 1
else:
i += 1
- database design
- java basics
LC 65 Valid Number
state = [{},
{'blank':1, 'sign':2, 'digit':3, '.':4},
{'digit':3, '.':4},
{'digit':3, '.':5, 'e':6, 'blank':9},
{'digit':5},
{'digit':5, 'e':6, 'blank':9},
{'sign':7, 'digit':8},
{'digit':8},
{'digit':8, 'blank':9},
{'blank':9}
]
currState = 1
for c in s:
if c >= '0' and c<= '9':
c = 'digit'
if c ==' ':
c = 'blank'
if c == '+' or c == '-':
c = 'sign'
if c not in state[currState].keys():
return False
currState = state[currState][c]
print c, currState
if currState not in [3, 5, 8, 9]:
return False
return True
LC 85 Maximal Rectangle
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
height = [0] * (n + 1)
ans = 0
for row in matrix:
for i in xrange(n):
height[i] = height[i] + 1 if row[i] == '1' else 0
stack = [-1]
for i in xrange(n+1):
while height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - stack[-1] - 1
ans = max(ans, h*w)
stack.append(i)
return ans
max rectangle 输出其坐标 Next permutation
class Solution:
# @param num : a list of integer
# @return : a list of integer
def nextPermutation(self, num):
# write your code here
partition = -1
for i in xrange(len(num)-2, -1, -1):
if num[i] < num[i+1]:
partition = i
break
if partition == -1:
num.reverse()
return num
for i in xrange(len(num)-1, partition, -1):
if num[i] > num[partition]:
num[i], num[partition] = num[partition], num[i]
break
num[partition+1:] = num[partition+1:][::-1]
return num
Word break I, II
def wordBreak(self, s, dict):
# write your code here
dp = [False for i in xrange(len(s)+1)]
dp[0] = True
for i in xrange(1, len(s)+1):
for w in dict:
if dp[i-len(w)] and s[i-len(w):i] == w:
dp[i] = True
return dp[len(s)]
class Solution:
# @param {string} s a string
# @param {set[str]} wordDict a set of words
def check(self, s, wordDict):
dp = [False for i in xrange(len(s)+1)]
dp[0] = True
for i in xrange(1, len(s)+1):
for k in xrange(0, i):
if dp[k] and s[k:i] in wordDict:
dp[i] = True
return dp[len(s)]
def dfs(self, s, wordDict, stringlist, res):
if self.check(s, wordDict):
if len(s) == 0: res.append(stringlist[1:])
for i in xrange(1, len(s)+1):
if s[:i] in wordDict:
self.dfs(s[i:], wordDict, stringlist + ' ' + s[:i], res)
def wordBreak(self, s, wordDict):
# Write your code here
res = []
self.dfs(s, wordDict, '', res)
return res
- two sum
- three sum 上来第一题是判断两个矩形是否相交 http://www.aichengxu.com/suanfa/24601035.htm
reservoir sampling, leetcode这个tag下面有类型题目
def __init__(self, nums):
self.nums = nums
def pick(self, target):
res = None
count = 0
for i, x in enumerate(self.nums):
if x == target:
count += 1
chance = random.randint(1, count)
if chance == count:
res = i
return res
贡献题库。面食馆引渡人。输入hashtable{"a"=>50, "b"=>25, "c"=25}, 要求每次call这个function，print概率按照输入hashtable里面概率. 所以有50%的概率print a, 25% b, 25% c。理解题意花了好久。
- two sum, 电面用 hashset，onstie 又考了一遍用两种方法做
分解质因数
shift array (shifts an array by N number of steps. E.g. [0,1,2,3,4] shiftArray(arr, 3) -> [2,3,4,0,1])
- search in rotated array
- valid BST. 我刚说完思路面试官就说我知道是对的你不用写代码了⊙▽⊙
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
import sys
return self.isBST(root, -sys.maxint, sys.maxint)
def isBST(self, root, curMin, curMax):
if root is None:
return True
if root.val <= curMin or root.val >= curMax:
return False
return self.isBST(root.left, curMin, root.val) and self.isBST(root.right, root.val, curMax)
- database design + SQL
- fib, 非要让我不用 temp 和不能多用两个数……
edit distance，本来想背dp答案的，结果没等我开口给我简化了并让我用 recursion 写
Calculate the distance of bits between two integers. For example: 1 -> 01; 2 -> 10; dist = 2;
c = x ^ y
count = 0
while c!= 0:
c &= (c-1)
count += 1
return count
sqrt
Fibonacci, recursive + non recursive; 然后都问了下时间空间复杂度。 上面试题： 1. Given a nm size 2D array with integers from 1 to nm - 1 in it. Integers are not sorted. The last position of the matrix stays a movable block. For each time, you can swap the movable block with any adjacent number. And eventually you will have the integers sorted and the movable block returned to its starting position. Think about an approach to print the path. (You can assume it always have at least a solution)
longest increasing subsequence.
def longestIncreasingSubsequence(self, nums):
# write your code here
if not nums:
return 0
length = len(nums)
max = 1
dp = [1 for i in xrange(length)]
for i in xrange(1, length):
for j in xrange(i):
if nums[i] > nums[j] and dp[i]<dp[j]+1:
dp[i] = dp[j]+1
if dp[i] > max:
max = dp[i]
return max
nlogn
tails = [0] * len(nums)
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = (i+j)/2
if tails[m] < x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i+1, size)
return size
- Remove any number containing 9 like 9, 19, 29, ... 91, 92, ... 99, 109... . 1point3acres.com/bbs Write a function that returns the nth number. E.g. newNumber(1) = 1 newNumber(8) = 8, newNumber(9) = 10, 最后给了hint把数变成9-based
- kSum.... expect better runtime than backtracking... Consider 3sum's backtracking complexity is worse than n^2, which use's two sum's two pointer approach.
- Design Excel. Implement int get(string cell) void put(string cell, string expr). expr can be "A1= B1+1". 这题的关键在于，要解决各个cell的dependence问题. 比如说call put(B1, "3")之后，同时也要update A1的值。会牵扯到topo sort的问题。总之这题是design题，就看你有没有意识到这种dependence。
- Design Intagram
- Android lock pattern from leetcode.
class Solution(object):
def numberOfPatterns(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
skip = [[0 for i in xrange(10)] for j in xrange(10)]
skip[1][3] = skip[3][1] = 2
skip[1][7] = skip[7][1] = 4
skip[7][9] = skip[9][7] = 8
skip[3][9] = skip[9][3] = 6
skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = skip[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = 5
vis = [False for i in xrange(10)]
res = 0
for i in xrange(m, n+1):
res += self.dfs(skip, vis, 1, i-1) * 4
res += self.dfs(skip, vis, 2, i-1) * 4
res += self.dfs(skip, vis, 5, i-1)
return res
def dfs(self, skip, vis, cur, rem):
if rem < 0:
return
if rem == 0:
return 1
vis[cur] = True
res = 0
for i in xrange(1, 10):
if not vis[i] and (skip[cur][i] == 0 or vis[skip[cur][i]]):
res += self.dfs(skip, vis, i, rem-1)
vis[cur] = False
return res
LC304
def __init__(self, matrix):
"""
:type matrix: List[List[int]]
"""
if matrix is None or not matrix:
return
n, m = len(matrix), len(matrix[0])
self.sums = [[0 for j in xrange(m+1)] for i in xrange(n+1)]
for i in xrange(1, n+1):
for j in xrange(1, m+1):
self.sums[i][j] = matrix[i-1][j-1] + self.sums[i][j-1] + self.sums[i-1][j] - self.sums[i-1][j-1]
def sumRegion(self, row1, col1, row2, col2):
"""
:type row1: int
:type col1: int
:type row2: int
:type col2: int
:rtype: int
"""
row1, col1, row2, col2 = row1+1, col1+1, row2+1, col2+1
return self.sums[row2][col2] - self.sums[row2][col1-1] - self.sums[row1-1][col2] + self.sums[row1-1][col1-1]
第一题经典题，一堆不同面值的硬币，一个target，找到最少硬币数，求和等于target。（用dp做，2个for loop就行了）
dp = [amount+1 for i in xrange(amount+1)]
dp[0] = 0
for i in xrange(1, amount+1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i-c]+1)
return dp[-1] if dp[-1] != amount+1 else -1
第二题，给一个序列的定义 n（奇数）：3n＋1 n（偶数）：n/2. visit 1point3acres.com for more. 每个数都能到1，比如：5->16->8->4->2->1, 长度为5。 找到1-1000中序列最长为多少。 houzz给的链接里，用recursive写会爆栈，iterative的话可以用for loop，每次循环把路径存在stack中，每个数对应的序列长度保存在map中。
int helper(unordered_map<int, int>& map, int target){
int count = 0;
while(target != 1){
if(map.find(target) != map.end())
return count + map[target];
if(target % 2)
target = 3 * target + 1;
else{
target /= 2;.
}.
count++;
}
return count;
}
int main(){
int Max = 0;
unordered_map<int, int> map;
for(int i = 1; i <= 1000; i++){
Max = max(Max, helper(map, i));
}
cout << Max << endl;
}
- 完全背包， 刚开始理解成了01背包，后来发现他想要完全背包， 反正两种都写了. From 1point 3acres bbs
- 水题， implement queue using stack
给一串string，里面有数字, return 最大的top k 个数字，比如k = 3： input = “dfsfs980sdf123poier110poipoikkj-10” output = [980, 123, 110]. m
第一题是检查一个graph是不是bipartite的，bfs解完了，接下来问时间复杂度，可不可以优化。
class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)] \
for row in range(V)]
def isBipartite(self, src):
colorArr = [-1] * self.V
# Assign first color to source
colorArr[src] = 1
# Create a queue (FIFO) of vertex numbers and
# enqueue source vertex for BFS traversal
queue = []
queue.append(src)
# Run while there are vertices in queue
# (Similar to BFS)
while queue:
u = queue.pop()
// Return false if there is a self-loop
if self.graph[u][u] == 1:
return False;
for v in range(self.V):
# An edge from u to v exists and destination
# v is not colored
if self.graph[u][v] == 1 and colorArr[v] == -1:
# Assign alternate color to this
# adjacent v of u
colorArr[v] = 1 - colorArr[u]
queue.append(v)
# An edge from u to v exists and destination
# v is colored with same color as u
elif self.graph[u][v] == 1 and colorArr[v] == colorArr[u]:
return False
return True
# Driver program to test above function
g = Graph(4)
g.graph = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
print "Yes" if g.isBipartite(0) else "No"
第二题问一个unfair coin，怎么disign一个process可以返回同样几率的0和1.
So the two cases appear with equal probability. The idea is to return consider only the above two cases, return 0 in one case, return 1 in other case. For other cases [(0, 0) and (1, 1)], recur until you end up in any of the above two cases.
The below program depicts how we can use foo() to return 0 and 1 with equal probability.
#include <stdio.h>
int foo() // given method that returns 0 with 60% probability and 1 with 40%
{
// some code here
}
// returns both 0 and 1 with 50% probability
int my_fun()
{
int val1 = foo();
int val2 = foo();
if (val1 == 0 && val2 == 1)
return 0; // Will reach here with 0.24 probability
if (val1 == 1 && val2 == 0)
return 1; // // Will reach here with 0.24 probability
return my_fun(); // will reach here with (1 - 0.24 - 0.24) probability
}
int main()
{
printf ("%d ", my_fun());
return 0;
}
LC 上面 walls and gates 很像
def wallsAndGates(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: void Do not return anything, modify rooms in-place instead.
"""
if not rooms:
return
for i in xrange(len(rooms)):
for j in xrange(len(rooms[0])):
if rooms[i][j] == 0:
queue = collections.deque([])
queue.append((i+1, j, 1))
queue.append((i-1, j, 1))
queue.append((i, j+1, 1))
queue.append((i, j-1, 1))
visited = set()
while queue:
x, y, val = queue.popleft()
if x < 0 or x > len(rooms)-1 or y < 0 or y > len(rooms[0])-1 or rooms[x][y] in [-1, 0] or (x,y) in visited:
continue
visited.add((x,y))
rooms[x][y] = min(rooms[x][y], val)
queue.append((x+1, y, val+1))
queue.append((x-1, y, val+1))
queue.append((x, y+1, val+1))
queue.append((x, y-1, val+1))
find median of two sorted array
l = len(nums1) + len(nums2)
if l % 2 == 1:
return self.getkth(nums1, nums2, l/2+1)
else:
return 0.5*(self.getkth(nums1, nums2, l/2)+self.getkth(nums1, nums2,l/2+1))
def getkth(self, A, B, k):
lena, lenb = len(A), len(B)
if lena > lenb: return self.getkth(B, A, k)
if lena == 0: return B[k-1]
if k == 1: return min(A[0], B[0])
pa = min(k/2, lena)
pb = k - pa
if A[pa-1] < B[pb-1]:
return self.getkth(A[pa:], B, pb)
else:
return self.getkth(A, B[pb:], pa)
- merge k sorted arrays
def mainMergeK(*lists):
# implemented by k-way partition
k = len(lists)
if k > 1:
mid = int(k / 2)
B = mainMergeK(*lists[0: mid])
C = mainMergeK(*lists[mid:])
A = merge(B, C)
print B, ' + ', C, ' = ', A
return A
return lists[0]
def merge(B, C):
A = []
p = len(B)
q = len(C)
i = 0
j = 0
while i < p and j < q:
if B[i] <= C[j]:
A.append(B[i])
i += 1
else:
A.append(C[j])
j += 1
if i == p:
for c in C[j:]:
A.append(c)
else:
for b in B[i:]:
A.append(b)
return A
import heapq
class Solution:
# @param {int[][]} arrays k sorted integer arrays
# @return {int[]} a sorted array
def mergekSortedArrays(self, arrays):
result = []
heap = []
for index, array in enumerate(arrays):
if len(array) == 0:
continue
heapq.heappush(heap, (array[0], index, 0))
while len(heap):
val, x, y = heap[0]
heapq.heappop(heap)
result.append(val)
if y + 1 < len(arrays[x]):
heapq.heappush(heap, (arrays[x][y + 1], x, y + 1))
return result
- group anagrams, 2. prime factors. given a number return the prime factor multiplication. eg. 90 = 2 3 3 * 5. def primeFactors(n):
# Print the number of two's that divide n
while n % 2 == 0:
print 2,
n = n / 2
# n must be odd at this point
# so a skip of 2 ( i = i + 2) can be used
for i in range(3,int(math.sqrt(n))+1,2):
# while i divides n , print i ad divide n
while n % i== 0:
print i,
n = n / i
# Condition if n is a prime
# number greater than 2
if n > 2:
print n
input 一个日期，即年月日，要求返回加上n天以后得到的日期 最后出了一个道题给一个Calendar class（有三个field，year，month，day）和一个数N，实现一个函数，返回N天之后的calendar，譬如说输入是{2017， 3，20}和12， 那么返回的是{2017，4， 1}.
def isleap(y):
if y % 4 == 0 and y % 100 != 0 or y % 400 == 0:
return True
return False
def offsetDays(d, m, y):
offset = d
month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 31, 31]
for i in xrange(m):
offset += month[i]
if isleap(y) and m > 2:
offset += 1
return offset
def revoffsetDays(offset, y):
month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 31, 31]
if isleap(y):
month[2] = 29
for i in xrange(1, 12):
if offset < month[i]:
break
offset -= month[i]
return offset, i
def addDays(d, m, y, x):
offset = offsetDays(d, m, y)
remdays = 366 - offset if isleap(y) else 365 - offset
print offset, remdays
offset2, y2 = 0, 0
if x <= remdays:
offset2 = x + offset
print offset2
y2 = y
else:
x -= remdays
print "x is ",x
y2 = y + 1
y2days = 366 if isleap(y2) else 365
while x > y2days:
x -= y2days
y2 += 1
y2days = 366 if isleap(y2) else 365
offset2 = x
d2, m2 = 0, 0
d2, m2 = revoffsetDays(offset2, y2)
print d2, m2, y2
d = 14
m = 3
y = 2015
x = 166
addDays(d, m, y, x)
distributed key value store，然后是写代码merge n sorted array
第一题是Given a DAG, a source, a target, and number n, 找出从source到target的长度为n的路径的个数。第二题是given a undirectd and acyclic graph, 一个source和一个target，找出source到target的最长path。
斐波那契数列，recursive & iterative各写一遍
- find max number of points in one line + 系统设计（设计一个topic ranking 系统）
- design calendar class 有 day year month 实现 add (days) return calendar、、
- 有向有环图中 找source 到 target 的距离为n的可能性. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
- wordbreak 2 (follow up : NLP problems) 2 Design tiny url three sum，我说先挑一个数字然后再用2sum，他说不错，还能不能更快，要我写个nlogn的写法，