e*****u
发帖数: 67 | 1 自己不是CS專業，只學過一門數據結構，會一些Python.
明天on-site面試一個engineer工作。 臨時抱佛腳。
如果明天當場要寫code，估計只能有Python硬着頭皮寫-
請教諸位大俠， 下面這幾道題用Python怎麼寫-
1) Describe recursive mergesort and its runtime. Write an iterative
version in Python.
2) Given an array of numbers, replace each number with the product of
all the numbers in the array except the number itself *without* using
division.
3) Write a program to find depth of binary search tree without using
recursion.
4) Efficiently implement 3 stacks in a single array.
5) Given an array of integers which is circularly sorted, how do you
find a given integer.
6) Find the maximum rectangle (in terms of area) under a histogram in
linear time.
7) Most phones now have full keyboards. Before there there three letters
mapped to a number button. Describe how you would go about implementing
spelling and word suggestions as people type.
8) How would you determine if someone has won a game of tic-tac-toe on a
board of any size?
9) Create a cache with fast look up that only stores the N most recently
accessed items.
10) How to design a search engine? If each document contains a set of
keywords, and is associated with a numeric attribute, how to build
indices?
11) Given two files that has list of words (one per line), write a
program to show the intersection.
12) What kind of data structure would you use to index annagrams of
words? e.g. if there exists the word “top” in the database, the query
for “pot” should list that.
------------
多謝各位。 明天面試回來，一定來回報一下！ | e*****u
发帖数: 67 | 2 不曉得對不對-
>2) Given an array of numbers, replace each number with the product of
>all the numbers in the array except the number itself *without* using
>division.
import copy
ls = [1,2,3]
new_ls = []
for item in ls:
prod = 1
lsx = copy.copy(ls)
lsx.remove(item)
print ls, lsx
for z in lsx:
prod*=z
new_ls.append(prod)
print new_ls | s*********b
发帖数: 815 | 3 这是隐性的DP问题啊。products[i] = products_below[i] * products_above[i]。所
以关键是怎么搭建products_below[i]和products_above[i]。这俩都有线性递归的关系
：prouducts_below[i] = products_below[i-1]*ints[i-1], 而products_above[i] =
products_above[i+1] * ints[i+1]。线性递归最安逸了。您老练临时存储都不用。直
接算了记下来就行：
def product(ints):
products = [0]*len(ints)
# products_below[i]
p = 1
for i in xrange(len(ints)):
products[i] = p
p *= ints[i]
# products_above[i]
p = 1
for i in xrange(len(ints)-1, -1, -1):
products[i] *= p
p *= ints[i]
return products
时间O(n)。空间：O(1) （不算结果占用的空间的话）。
【在 e*****u 的大作中提到】
: 不曉得對不對-
: >2) Given an array of numbers, replace each number with the product of
: >all the numbers in the array except the number itself *without* using
: >division.
: import copy
: ls = [1,2,3]
: new_ls = []
: for item in ls:
: prod = 1
: lsx = copy.copy(ls)
| l****6
发帖数: 1180 | 4 请问面试前是怎么知道这些题目的啊？
【在 e*****u 的大作中提到】
: 自己不是CS專業，只學過一門數據結構，會一些Python.
: 明天on-site面試一個engineer工作。 臨時抱佛腳。
: 如果明天當場要寫code，估計只能有Python硬着頭皮寫-
: 請教諸位大俠， 下面這幾道題用Python怎麼寫-
: 1) Describe recursive mergesort and its runtime. Write an iterative
: version in Python.
: 2) Given an array of numbers, replace each number with the product of
: all the numbers in the array except the number itself *without* using
: division.
: 3) Write a program to find depth of binary search tree without using
| e*****u
发帖数: 67 | 5 thanks so much for your reply. 記下了。已收入錦囊之中。
可否再幫忙看下第 11 題 -
'''11) Given two files that has list of words (one per line), write a
program to show the intersection.
'''
ls_1 = ['this is begining', 'this is middle' , 'that is end']
ls_2 = ['first notice', 'this is middle' , 'case is closed']
interx = []
for item in ls_1:
for element in ls_2:
if item == element:
interx.append(item)
print interx
#好像我的以上solution 是 O(N^2). | e*****u
发帖数: 67 | 6 #11題正確答案如下 （這個solution也是O(N^2)嗎？為什麽比我的code要好呢？）
def LCS(X, Y):
m = len(X)
n = len(Y)
# An (m+1) times (n+1) matrix
C = [[0] * (n+1) for i in range(m+1)]
print C
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
C[i][j] = C[i-1][j-1] + 1
else:
C[i][j] = max(C[i][j-1], C[i-1][j])
print C
return C
def backTrack(C, X, Y, i, j):
if i == 0 or j == 0:
return ""
elif X[i-1] == Y[j-1]:
return backTrack(C, X, Y, i-1, j-1) + X[i-1]
else:
if C[i][j-1] > C[i-1][j]:
return backTrack(C, X, Y, i, j-1)
else:
return backTrack(C, X, Y, i-1, j)
X = ['A','A','T','C']
Y = ['A','G','F','T']
m = len(X)
n = len(Y)
C = LCS(X, Y)
print "All LCSs: %s" % backTrack(C, X, Y, m, n) | s*********b
发帖数: 815 | 7 您老没搞错吧？求交集跟LCS都那儿跟那儿啊？这个用shell就搞定了：comm -12 <(
sort file1) <(sort file2)。如果用python也简单：
from sets import Set
def intersect(words, another_words):
return Set(words) & Set(another_words)
【在 e*****u 的大作中提到】
: #11題正確答案如下 （這個solution也是O(N^2)嗎？為什麽比我的code要好呢？）
: def LCS(X, Y):
: m = len(X)
: n = len(Y)
: # An (m+1) times (n+1) matrix
: C = [[0] * (n+1) for i in range(m+1)]
: print C
: for i in range(1, m+1):
: for j in range(1, n+1):
: if X[i-1] == Y[j-1]:
|
|
