l******o
发帖数: 144 | 1 我了个去了，这些题还真是难啊
删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expr... 阅读全帖 |
|
d********w
发帖数: 363 | 2 删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expression tree设计，gr... 阅读全帖 |
|
l******o
发帖数: 144 | 3 我了个去了，这些题还真是难啊
删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expr... 阅读全帖 |
|
d********w
发帖数: 363 | 4 找到一个把中序转前序的题
http://www.justin.tv/problems/prefixer
当时还写过python版的
def parse(s, reduce):
for operator in ["+-", "*/"]:
depth = 0
for p in xrange(len(s) - 1, -1, -1):
if s[p] == ')': depth += 1
if s[p] == '(': depth -= 1
if not depth and s[p] in operator:
left = parse(s[:p], reduce)
right = parse(s[p+1:], reduce)
if reduce and left.isdigit() and right.isdigit():
return str(ev... 阅读全帖 |
|
e******x
发帖数: 184 | 5 def getCoke(min, max, m, n) :
if (n<0 or m>n) :
return False
for i in xrange(3) :
if (m<=min[i] and n>=max[i]) or getCoke(min, max, m-min[i], n-max[
i])
return True
return False
大概是这样。。求拍 |
|
p*****2
发帖数: 21240 | 6 来自主题: JobHunting版 - L 电面2 写了一个练练手
def reverse(s,i,j):
while i
t=s[i]
s[i]=s[j]
s[j]=t
i+=1
j-=1
s=list("Hello World")
reverse(s,0,len(s)-1)
start=-1
for i in xrange(len(s)):
if(s[i]==' '):
if(start!=-1):
reverse(s,start,i-1)
start=-1
else:
if(start==-1):
start=i
if start!=-1:
reverse(s,start,len(s)-1)
print "".join(s) |
|
p*****2
发帖数: 21240 | 7
第一题
def dfs(n,s,k,l):
if len(l)==k:
print l
if s==n:
return
for i in xrange(s,n):
l.append(i+1)
dfs(n,i+1,k,l);
del l[-1]
def comb(n,k):
l=[]
dfs(n,0,k,l) |
|
p*****2
发帖数: 21240 | 8 第二题
def dfs(arr,v,l):
ll=len(arr)
if(len(l)==ll):
print l
return
prev=-1
for i in xrange(ll):
if not v[i] and arr[i]!=prev:
v[i]=True
l.append(arr[i])
dfs(arr,v,l)
del l[-1]
v[i]=False
prev=arr[i]
arr=[1,1,2]
v=[False]*len(arr)
l=[]
dfs(arr,v,l) |
|
p*****2
发帖数: 21240 | 9 第二题
s=" tHis is 1 strinG. "
l=s.strip().split()
for i in xrange(len(l)):
ll=list(l[i])
ll[0]=ll[0].upper()
l[i]="".join(ll)
print "".join(l) |
|
p*****2
发帖数: 21240 | 10 def min(S,T):
d1={}
d2={}
for c in T:
if not d1.has_key(c):
d1[c]=0
d1[c]+=1
dq=deque()
count=len(d1)
ans=S
for i in xrange(len(S)):
c=S[i]
if d1.has_key(c):
dq.append(i)
if not d2.has_key(c):
d2[c]=0
d2[c]+=1
if d2[c]==d1[c]:
count-=1
if count==0:
while len(dq)>0 and d2[S[dq[0]]]>d1... 阅读全帖 |
|
j********e
发帖数: 1192 | 11 你想简单了，如果T是AAB，那么要求S对应的substring里包含两个A。
你的算法只适合T没有duplicate字符的情况。
而且memory usage是O(T.size()).
def min(S,T):
d1={}
d2={}
for c in T:
if not d1.has_key(c):
d1[c]=0
d1[c]+=1
dq=deque()
count=len(d1)
ans=S
for i in xrange(len(S)):
c=S[i]
if d1.has_key(c):
dq.append(i)
if not d2.has_key(c):
d2[c]=0
d2[c]+=1
if d2[c]==d1[c]:
cou... 阅读全帖 |
|
p*****2
发帖数: 21240 | 12 def dfs(l, start, list, sum):
if sum==0:
print list
return
if start==len(l) or sum<0:
return
prev=-1
for i in xrange(start,len(l)):
if l[i]!=prev:
list.append(l[i])
dfs(l,i+1,list,sum-l[i])
del list[-1]
prev=l[i]
l=[10,1,2,7,6,1,5]
k=8
l.sort()
list=[]
dfs(l,0,list,k) |
|
p*****2
发帖数: 21240 | 13 def dfs(l, start, list, sum):
if sum==0:
print list
return
if start==len(l) or sum<0:
return
prev=-1
for i in xrange(start,len(l)):
if l[i]!=prev:
list.append(l[i])
dfs(l,i+1,list,sum-l[i])
del list[-1]
prev=l[i]
l=[10,1,2,7,6,1,5]
k=8
l.sort()
list=[]
dfs(l,0,list,k) |
|
p*****2
发帖数: 21240 | 14 刚练了一个
from collections import deque
def Max(arr, k):
l=[]
dq=deque()
for i in xrange(len(arr)):
if len(dq) and dq[0]<=i-k:
dq.popleft()
while len(dq) and arr[dq[-1]]
dq.pop()
dq.append(i)
if i>=k-1:
l.append(arr[dq[0]])
return l
arr=[3, 4, 5, 7, 3, 5, 2, 9 ]
k=3
print Max(arr,k) |
|
p*****2
发帖数: 21240 | 15 第二题
def missing(s1,s2):
l1=list(s1)
l2=list(s2)
j=0
print "----------------------"
for i in xrange(len(l1)):
if j==len(l2) or l1[i]!=l2[j]:
print i
else:
j+=1
missing("abc","ab")
missing("abc","b")
missing("abc","ac")
missing("aab","ab") |
|
p*****2
发帖数: 21240 | 16 刚练了一个
from collections import deque
def Max(arr, k):
l=[]
dq=deque()
for i in xrange(len(arr)):
if len(dq) and dq[0]<=i-k:
dq.popleft()
while len(dq) and arr[dq[-1]]
dq.pop()
dq.append(i)
if i>=k-1:
l.append(arr[dq[0]])
return l
arr=[3, 4, 5, 7, 3, 5, 2, 9 ]
k=3
print Max(arr,k) |
|
p*****2
发帖数: 21240 | 17 第二题
def missing(s1,s2):
l1=list(s1)
l2=list(s2)
j=0
print "----------------------"
for i in xrange(len(l1)):
if j==len(l2) or l1[i]!=l2[j]:
print i
else:
j+=1
missing("abc","ab")
missing("abc","b")
missing("abc","ac")
missing("aab","ab") |
|
p*****2
发帖数: 21240 | 18 我写了一个练练
def count(str):
if not (str and len(str)):
return 0
l=len(str)
dp=[1]*2
if str[-1]=='0':
dp[1]=0
for i in xrange(2,l+1):
if str[-i]=='0':
dp[i%2]=0
else:
c=dp[(i+1)%2]
if str[l-i:l-i+2]<="26":
c+=dp[i%2]
dp[i%2]=c
return dp[l%2] |
|
p*****2
发帖数: 21240 | 19
我写了一个打印的练了练手。
def dfs(l,start,end):
if start>end:
return [[]]
else:
ret=[]
for i in xrange(start,end+1):
l1=dfs(l,start+1,i)
l2=dfs(l,i+1,end)
for x in l1:
x.append(l[start])
for y in l2:
tmp=[]
tmp.extend(x)
tmp.extend(y)
ret.append(tmp)
return ret |
|
d********g
发帖数: 10550 | 20 = 改为 ==
print结果应该为True
这题就是考reduce()、filter()、map()，然后lambda
先map一个y=x^2给xrange(10^6)，然后把list通过filter留下x为奇数的情况，再用
reduce全部加起来，应该等于直接sum一个步进为2的x^2 list（奇数x^2 list）
另外考这道题属于蛋疼 |
|
w**********o
发帖数: 140 | 21 2.
It's a variation of unbiased coin.
Python version
====================================
import random
def getProb(n):
for i in xrange(n):
if toss() == 0:
return 0
return 1
def toss():
return random.choice([0,1]) |
|
d******e
发帖数: 164 | 22 def break_words(line, sol, result):
if not line:
result.append(sol[:])
else:
for i in xrange(len(line)):
if in_dict(line[:i+1]):
sol.append(line[:i+1])
break_words(line[i+1:], sol, result)
sol.pop() |
|
t*********h
发帖数: 941 | 23 from collections import defaultdict
num1=2345678
num2=3429
def convert2int(lst):
return int(''.join(map(str,lst)))
def compare(num, result,l,digits):
n1=convert2int(str(num)[:l+1])
n2=convert2int(result[:l+1])
if l==(digits-1):
return n2>n1
return n2>=n1
def find_next(x1,num,result,digits,l):
if l==digits:
print 'found:'+''.join(map(str,result))
return
for i in xrange(10):
x=x1.copy()
if x[i]>0:
result[l]=i
x[i]-=1
if compare(num,result,l,digit... 阅读全帖 |
|
j********3
发帖数: 33 | 24 我来个python 版本的。
精确度考量： 当前版本精度为一秒。 如果要提高精度可以提高memory或者用queue
log所有的hit timestamp，然后压缩timestamp来减少memory。 tradeoff memory O(N)
instead of constant.
scalability：缩小维度，增加memory 使用 distrubuted array in python:
distarray。
edge case: in real world,应该不用考虑一秒内的request超出max integer，面试官
真的要问的话， 超出的话，可以溢出到下一个bucket
concurrency: 基本for loop in reset() 和 count++的地方都需要加锁了...
import time
N = 300
class Counter:
def __init__(self,lock):
self.last_index = 0
self.last_hit_time = 0
self.total... 阅读全帖 |
|
b*********s
发帖数: 115 | 25 其实很短就可以写完
def fac(low, n):
if n == 1:
return [[]]
res = []
for i in xrange(low, n + 1):
if n % i == 0:
head = [i]
res += [head + tail for tail in fac(i, n / i)]
return res
def solve(n):
res = fac(2, n)
# 上面算出来的res最后一个是[n], 在开头插入1变成[1, n]
res[-1].insert(0, 1)
print res
测试:
input: 12 output: [[2, 2, 3], [2, 6], [3, 4], [1, 12]]
input: 100 output: [[2, 2, 5, 5], [2, 2, 25], [2, 5, 10], [2, 50], [4, 5, 5]
, [4, 25], [5, 20], [10... 阅读全帖 |
|
p**o
发帖数: 3409 | 26 def mergesort_topdown (aList):
""" Top-down merge sort.
A total of logn splits;
in each split we merge n items.
So the complexity is O(n logn).
"""
_splitmerge (aList, 0, len(aList))
def _splitmerge (aList, i, j):
""" Recursively split runs into two halves
until run size == 1 (considered sorted), then
merge two halves and return back up the call chain.
"""
if j - i > 1:
m = (i + j) // 2
_splitmerge (aList, i, m)
... 阅读全帖 |
|
t********n
发帖数: 611 | 27 还是不够快的问题，自己机器上测试结果正确，用了BFS and DFS，不知道还能怎样改
进，请牛牛们指教！
Python code:
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
def buildPath(end, start, path= []):
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
for p in parents[end]:
... 阅读全帖 |
|
t********n
发帖数: 611 | 28 过了， 参考了某位高人的代码，每次找下级词汇前，把这一级从字典里删除，立刻快
了很多。
Code:
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
def buildPath(end, start, path= []):
# print
# print "path at beginning:", path
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
... 阅读全帖 |
|
i***h
发帖数: 19 | 29 我也用python寫的，一開始試過各種O(n^2)方法都不行，估計預期是要manacher之類O(
n)的算法；不過我後來用一些trick把它給過了，主要是對於長字串和短字段分別處理
class Solution:
# @return a string
def longestPalindrome(self, s):
if s is None or len(s) == 0:
return ''
def max_palindrome(left, right, min_length):
if right - left < min_length:
return ''
start = left
while left < right:
if s[left] != s[right]:
if right - left < min_length:
... 阅读全帖 |
|
x*******9
发帖数: 138 | 30 def get_next(needle):
l = len(needle)
nexts = [0 for i in xrange(l + 1)]
nexts[0] = -1
i, j = 0, -1
while i < l:
while j >= 0 and needle[i] != needle[j]:
j = nexts[j]
i += 1
j += 1
nexts[i] = j
return nexts
def get_prefix_match(S):
nexts = get_next(S)
print S
print nexts
for i, u in enumerate(nexts):
if u <= 0:
continue
v = u
print '>>', S[:u], "\t[0...%d]" % u, S[i - u: i], "\... 阅读全帖 |
|
n*n
发帖数: 157 | 31 我常用的 python 内建函数:
len
enumerate
print
sort
range/xrange
map
zip
format
open
close |
|
x*******9
发帖数: 138 | 32 import collections
dna = 'AAGATCCGTCAGTTTTCAAT'
dna_group = [dna[i: i + 2] for i in xrange(len(dna) - 1)]
c = collections.Counter(dna_group)
print sorted(c.most_common(), key=lambda x: x[0])
五行搞定嘛。。。 |
|
g******n
发帖数: 10 | 33 这题可以在循环内手动去重，也可以把 triplets 存到 hash set 里自动去重，函数返
回时再转回 list。前者代码略显啰嗦但时间复杂度最坏是 O(n^2)，后者代码更简洁但
时间复杂度更高，平均情况 O(n^2)，最坏情况 O(n^4)（例如共有 O(n^2) 个
triplets，全部被 hash 到同一个 bucket，每次插入都是 O(n^2)，所以总的时间复杂
度是 O(n^4)）。C++ 可以用 hash set 也可以先统一把 triplets 存到 vector<
vector> 里，然后 sort + unique + erase / resize 搞定。但是 C++ 这两种方
法都会超时，必须手动去重，Java 和 Python 用 hash set 都能过 OJ。
--------------------------------------------------------------------------
Java 版代码如下：
public class Solution {
public List>... 阅读全帖 |
|
e***i
发帖数: 231 | 34 抛个砖
1. 可以用递归或者循环
#!/bin/python
def _rec_all_prod(primes):
if len(primes) == 1:
return primes
sub_prod = _rec_all_prod(primes[1:])
new_prod = sub_prod[:]
new_prod.append(primes[0])
for prod in sub_prod:
new_prod.append(prod*primes[0])
return new_prod
def get_prod_one(primes):
return set(_rec_all_prod(primes))
def _loop_all_prod(primes):
new_prod = []
for x in xrange(2**len(primes)):
mask = "{0:b}".format(x)[::-1]
total = 1
for b, v in zip(mask, primes):
... 阅读全帖 |
|
c****z
发帖数: 42 | 35 来自主题: JobHunting版 - g 家面经 一个for loop就可以啦
def upsampling(arr, width, times):
new_width = width*times
new_height = len(arr)/width*times
ans = [None]*new_width*new_height
for i in xrange(len(ans)):
row, col = i/new_width/times, i%new_width/times
ori_index = row*width + col
ans[i] = arr[ori_index]
return ans |
|
c*****m
发帖数: 271 | 36 感觉蛮难的。１.2 是加强版的Regular Expression Matching么；３我之前也做过，不
过现在看到也没想起来；2我觉得可以用Trie啊，写了个如下，请拍
class Solution():
def matchString(self, pattern_list, search_list):
#build trie based on pattern_list
trie = {}
for one_str in pattern_list:
#add each string into the trie
node = trie
for char in one_str:
if char not in node:
node[char] = {}
node = node[char]
#suppose strings do not h... 阅读全帖 |
|
m*****n
发帖数: 2152 | 37 虽然算法垃圾一点，但是work的。
def test(data):
dataset = [[n, data.count(n)] for n in set(data)]
for i in xrange(2):
copydataset = copy.deepcopy(dataset)
print list(generator(copydataset))
print '\n'
def generator(dataset):
size = len(dataset)
while dataset:
index = int(random.random()*size)
dataset[index][1] -= 1
char = dataset[index][0]
if not dataset[index][1]:
dataset.pop(index)
size = size - 1
... 阅读全帖 |
|
发帖数: 1 | 38 def countSubstrings(self, s):
count = 0
for center in xrange(2*len(s) - 1):
i = center / 2
j = i + center % 2
while 0 <= i <= j < len(s) and s[i] == s[j]:
count += 1
i -= 1
j += 1
return count |
|
H**********5
发帖数: 2012 | 39 亲，是输出所有的对称subsequence，不是求count。求count这题都烂了我答案都背下
来了。
俩个不同的题难度不是一个数量级。
暴力解是不行滴，如何把指数级时间时间优化。
: def countSubstrings(self, s):
: count = 0
: for center in xrange(2*len(s) - 1):
: i = center / 2
: j = i center % 2
: while 0
: count = 1
: i -= 1
: j = 1
: return count
|
|
t*******r
发帖数: 22634 | 40 我用 gnuplot 画了你的第一张红线图。不过 gnuplot 只能上直角坐标系了，
对称美只能将就一下，懒人首先是省事！！！。。。gnuplot code 见下面，
图见附件：
set xrange [ 0 : 9 ] ; set yrange [ 0 : 5 ] ; set grid ;
plot 12-x linecolor -1 linewidth 3 ;
set style arrow 1 linecolor 1 linewidth 3 size 0.3, 10;
set arrow 1 from 0,0 to 0,5 as 1 ;
set arrow 2 from 0,5 to 5,0 as 1 ;
set arrow 3 from 5,0 to 5,5 as 1 ;
set arrow 4 from 5,5 to 9,1 as 1 ;
set arrow 5 from 9,1 to 0,1 as 1 ;
set arrow 6 from 0,1 to 1,0 as 1 ;
set arrow 7 from 1,0 to 1,5 as 1 ;
set arrow 8 fr... 阅读全帖 |
|
|
r****a
发帖数: 1350 | 42
for i in xrange(1,5):
list_of_exs.append(ex^i)
[ex^3] == filter(lambda x: x==true love, list_of_exs) |
|
S*A
发帖数: 7142 | 43
对啊，看 /usr/include/python2.7/object.h & sliceobject.h.
我做个实验也基本 confirm 这个理论。
x = [ slice(i,i+2) for i in xrange(1024*1024)]
It take about 1G in my machine.
每个 slice(i,i+2) 大概 90+ byte 左右。
你不要忘了 slice 指向的 3 个 int object 也分别要算在内存里的。
每个都有 PyObject header。
So no better than reading from file directly to array.array
Smaller memory usage size without struct unpack. That is
currently my working pure python solution.
It does have the advantage of delay evaluate the array.
Only read the page if it is n... 阅读全帖 |
|
w****i
发帖数: 964 | 44 if using hash table to compare existing ids, the speed should be ok
in python:
ids, group = {}, []
for seq in seqlist:
....n = len(group)
....g = [ids.get(id, n) for id in seq]
....groupid = min(g)
....if groupid == n: group.append([])
....for i in xrange(len(seq)):
........if g[i] == n:
............group[groupid].append(seq[i])
............ids[seq[i]] = groupid |
|
w****i
发帖数: 964 | 45 Try this,
group, hash = [], {}
for seq in seqlist:
....n = len(group)
....g = [hash.get(id, n) for id in seq]
....groupid = min(g)
....if groupid == n:
........group.append([])
....else:
........for dupid in list(set(g)):
............if dupid > groupid and dupid < n:
................for x in group[dupid]: hash[x] = groupid
................group[groupid] += group[dupid]
....for i in xrange(len(seq)):
........hash[seq[i]] = groupid
........if g[i] == n: group[groupid].append(seq[i])
it doesn't gi |
|
r****t
发帖数: 10904 | 46 letters = 'abcdef...xx'
combs = (c for n in xrange(len(letters)) for c in combinations(letters,n))
then you can iterate though 'combs' as you want. 这里直接用 python 的
itertools.combinations |
|
d*****u
发帖数: 17243 | 47 我刚开始看python
现在有一个字符串的list，现在想给其中每个元素（字符串）都添加相同的一段'abc'
，应该怎么实现最有效呢？
我现在用的是for loop
for i in xrange(len(strings)):
strings[i]='abc'+strings[i]
感觉应该有更好的办法 |
|
X****r
发帖数: 3557 | 48 def range10(n):
while n < 11:
yield n
n = n + 1
for n in range10(1):
print n
Note that range10(1) here is the same as xrange(1,11) , you could
just call that instead instead of writing your own. |
|
X****r
发帖数: 3557 | 49 和Perl相反，Python尽量少用符号，所以就是range(1,11)或者xrange(1,11)。前者生
成一个实际的list，后者相当于一个forward iterator。 |
|
x******a
发帖数: 6336 | 50 如果改成下面的loop就可以改变x的值了，请问怎么回事？谢谢 np是numpy
for i in xrange(len(x)):
x[i]=x[i]-np.mean(x[i]) |
|
