t****9
发帖数: 1100 | 1 就是普通的def排放系统嘛，现在的柴油机都用这个，要消耗尿素，也就是def.，但是
这东西不是必须的，没有发动机也工作，只是不能发动，没关的发动机照样工作，只是
排放会不达标罢了。 |
|
|
|
e******d
发帖数: 14 | 4 对找EMBEDDED SOFTWARE的可能有些帮助。做这种题，其实就是一个学习的过程。
1. Consider the following declarations:
typedef struct
{
int a;
int b;
int c;
} ABC;
typedef struct
{
int d;
int e;
int f;
ABC *abc;
} DEF;
Given the above declarations, fill in the body of the following two
functions given below:
// The create function should use a single call to malloc to allocate memory
// for structure DEF and its |
|
C****u
发帖数: 18 | 5 1 def count(s,i):
2 o = i
3 c = s[i]
4 while (i < len(s) and c == s[i]):
5 i += 1
6 return (c,i - o)
7
8 def foo(s):
9 res = ''
10 pos = 0
11 while(pos < len(s)):
12 (ch,cnt) = count(s, pos)
13 res += str(cnt)
14 res += ch
15 pos += cnt
16 return res
17
18 s = '1'
19 print s
20 for i in range(10):
21 s = foo(s)
22 print s
运行结果：
python seq.py
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
111312211331121 |
|
s*********t
发帖数: 1663 | 6 手算
我写了一个
def printCombo(instr):
dic = ("","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ")
s = []
n = 1
for i in instr:
s.append(dic[i][0])
n *= len(dic[i])
for i in range(n):
print ''.join(s)
for j in range(len(s)-1,-1,-1):
s[j] = chr( ord(s[j])+1 )
if dic[ instr[j] ].find(s[j])==-1:
s[j] = dic[ instr[j] ][0]
else:
break
instr = [2, 3, 4, 5]
print |
|
c******f
发帖数: 2144 | 7 最短公共超序列问题(Shortest common supersquence):给一些字符串 比如 abc ,bcd
,def
然后可以判断是否有长度为 x 的字符串是这些字符串的父串，换句话说是否有一个长
度为x 的字符串能包含着三个字符串，比如abcdef就能，如果x为6 我们就能找到长度
为6的字符串包含了abc, bcd, def
再给一个例子，如果有这些字符串 abc, bcd, efg， x还是为 6，是否有长度为6的字
符串能包含这3个字符串么？没有！最短的是abcdefg 也就是说这三个字符串的最短公
共超序列长度为7
我现在不需要求最短公共超序列，但是我想证明这个问题是NP hard的，我想用TSP旅行
商问题 或者汉密尔顿路的问题reduce到这个问题上来证明这个最短公共超序列也是
nphard的，因为如果我们能把任何一个nphard的问题reduce到最短公共超序列问题上来
，就能证明最短公共超序列问题也是nphard的了。换句话说，我不明白怎么能给一个旅
行商问题或者汉密尔顿路径的问题，根据这些问题建立出一个最短公共超序列问题，然
后如果最短公共超序列问题可以解 |
|
V*******g
发帖数: 678 | 8 来自主题: JobHunting版 - 看看这道题 (1)
char *input = "abc def";
reversestring(input);
(2)
char input[] = "abc def";
reversestring(input);
(1)和(2) 有什么区别？ (1)编译报错，为什么？ |
|
t****a
发帖数: 1212 | 9 some python like code here:
def get_subtree(tree, values):
newtree = copy(tree)
filter_tree(newtree, values)
def filter_tree(tree, values):
if len(values)==0:
return NULL
elif tree.value in values:
values.remove(tree.value)
tree.left = filter_tree(tree.left, values)
tree.right = filter_tree(tree.right, values)
return tree |
|
f****g
发帖数: 313 | 10 We have two schedules S1&S2:
S1 = { , , ... }
S2 = { , , ... }
Assumptions:
1. S1&S2 are sorted by the starting time.
2. There are no conflicts in S1 and S2 itself.
Problem:
We try to find all the conflicts between these two schedules.
the basic idea is to merge sort to find the conflicts. the running time is
O(n).
My code in python: (code is kind of messy)
def merge(a,b):
i, j = 0, 0
unconflict = []
conflict = []
while( i < len(a... 阅读全帖 |
|
o****u
发帖数: 714 | 11 python code
a = 1
b = 1
def f(a,b,i):
if i == 10:
return
a = a + b
print a
f(b,a,i+1)
print a
print b
f(a,b,1)
def f2(a,b,i):
if i == 10:
return
a = a + b
f2(b, a, i+1)
print a
print ' '
f2(a,b,1)
print a
print b
2)
30 |
|
h*********n
发帖数: 11319 | 12 8,9 怎么错了啊？b的排序不是这么拍
的么？
import copy
def select(array, start, depth):
if depth==0:
print array
else:
for i in range(start, len(array)):
arrayCopy = copy.deepcopy(array)
del arrayCopy[i]
select(arrayCopy, i, depth-1)
def select2(array, string, start, depth):
if depth==0:
print string
else:
for i in range(start, len(array)):
string.append(array[i])
select2(array, string, i+1, depth-1)
del string[len(string)-1... 阅读全帖 |
|
i*****f
发帖数: 578 | 13 括号那题.基本思路是一个stack，遇到（就push，）就pop，如果stack空了，就不能继
续append ）。一共给N个（和N个），用完就不能再用。
递归来做.
'''List all legal combination of N pairs of parentheses.'''
def F(B, A0, A1):
if A0>0:
for res in F(B+[1], A0-1, A1):
yield [0]+res
if A1>0 and len(B):
for res in F(B[:-1], A0, A1-1):
yield [1]+res
if A0==A1==0: yield []
#### tests #####
def print_as_parentheses(a):
for b in a:
if b == 0: print '(',
else: print ')',
print
N = 4
for x in F... 阅读全帖 |
|
j*******r
发帖数: 52 | 14 1 def my_cmp(x,y):
2 if str(x)[0]>str(y)[0]:
3 return -1
4 elif str(x)[0]==str(y)[0]:
5 return 0
6 return 1
7
8 def BiggestNum(L):
9 L.sort(my_cmp)
10 print L
11 return reduce(lambda x,y: str(x)+str(y), L)
貌似比较数字最大位上的值就可以了？ |
|
i*****f
发帖数: 578 | 15 题目看错了。。。以为是最大化node个数。。。
这里是新的解，借鉴了wwwar3的解，而且应该可以handle树不complete的情况。牛牛们
看看还有什么为题没有？（测试及测试结果在最后面）
'''
Tree node is a 3-tuple (value, left child, right child)
'''
D = {}
def MaxPathSum(N):
'''
Find the path from N to a leaf that maximize the sum from N to the leaf.
Returns [leaf, sum]
'''
assert N!=None
if D.has_key(N): return D[N]
if not N[1] and not N[2]: return [N, N[0]]
r = [None, float('-inf')]
if N[1]:
r = MaxPathSum(N[1])
if N[2]:
r =... 阅读全帖 |
|
s*********b
发帖数: 815 | 16 Facebook说了必须用in-place的解法么？这种问题用函数编程最简单了：
(define (transpose matrix)
(apply map (cons list matrix)))
(define (rotate-90 matrix)
(map reverse (transpose matrix)))
测试一下：
> (rotate-90 '((1 2 3) (4 5 6) (7 8 9) (a b c)))
((a 7 4 1) (b 8 5 2) (c 9 6 3))
换成Python一类的语言也简单：
def rotate90(matrix):
m = zip(*matrix)
return [tuple(reversed(row)) for row in m]
测试一下：
>>> rotate90([[1, 2, 3], [4, 5, 6], [7, 8, 9], ['a', 'b', 'c']])
[('a', 7, 4, 1), ('b', 8, 5, 2), ('c', 9, 6, 3)]
Ruby类似(假设空矩阵的形式是... 阅读全帖 |
|
r****t
发帖数: 10904 | 17 his desire, def of "no problem" == compile time error.
your def of "no problem" == compile success. |
|
n******n
发帖数: 49 | 18 我对题意的理解是：
比如
the list of words with the same size: abc, def, ghi
the big string: xxxdefghiabcxxxxxx
应该返回3，因为defghiabc是一个(abc, def, ghi)的permutation, 它在big string中
起始index是3. |
|
n******n
发帖数: 49 | 19 我对题意的理解是：
比如
the list of words with the same size: abc, def, ghi
the big string: xxxdefghiabcxxxxxx
应该返回3，因为defghiabc是一个(abc, def, ghi)的permutation, 它在big string中
起始index是3. |
|
t****t
发帖数: 6806 | 20 if the two constructors of B can be distinguished, then D's two
instantiations can be distinguished.
suppose you have
B::B(const char*, int);
B::B(int, const char*);
B::B(double, float);
and template:
template
D::D(T1 t1, T2 t2) : B(t1, t2) {}
you can write
B b1("abc", 1), b2(2, "def"), b3(1.234, 5.678f);
D d1("ABC", 3), d2(4, "DEF"), d3(10.987, 6.543f);
clear enough?
as for your other question, if you have a 100 parameter constructor, you do
have to write 100 paramete... 阅读全帖 |
|
n*s
发帖数: 752 | 21 4. string transpose
import sys
def transpose(input,i):
mystr = list(input)
mystr[i],mystr[i+1] = mystr[i+1],mystr[i]
return ''.join(mystr)
def str_transpose():
print 'input two strings, separated by blank:'
a, b = sys.stdin.readline().split()
size = len(a)
if size != len(b) or sorted(a) != sorted(b):
return 'no way!'
next = [b]
parent = {b:None}
idx = size -1
notFound = True
while notFound:
newstr = []
for x in next:
... 阅读全帖 |
|
n*s
发帖数: 752 | 22 4. string transpose
import sys
def transpose(input,i):
mystr = list(input)
mystr[i],mystr[i+1] = mystr[i+1],mystr[i]
return ''.join(mystr)
def str_transpose():
print 'input two strings, separated by blank:'
a, b = sys.stdin.readline().split()
size = len(a)
if size != len(b) or sorted(a) != sorted(b):
return 'no way!'
next = [b]
parent = {b:None}
idx = size -1
notFound = True
while notFound:
newstr = []
for x in next:
... 阅读全帖 |
|
w******p
发帖数: 166 | 23 import sys;
def pfact(mult, fact, prefix):
for f in reversed(range(2, fact+1)):
d, m = divmod(mult, f)
if not m:
if d == 1: print "%s %d" % (prefix, f)
else: pfact(d, f, "%s %d *" % (prefix, f))
def prtFact(orig):
pfact(orig, orig, '')
prtFact(int(sys.argv[1])) |
|
S**I
发帖数: 15689 | 24 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 01:52:31 2011, 美东) 提到:
Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
nodes in the path from root to Y - sum of nodes in the common path from root
to first common ancestor of the Nodes X and Y
☆─────────────────────────────────────☆
SecretVest (Secret Vest) 于 (Tue Jun 21 04:01:30 2011, 美东) 提到:
not hard if someone is used... 阅读全帖 |
|
r*******n
发帖数: 266 | 25 return (maxDep(r) - minDep(r)) > 1
def maxDep(r):
if r == None: return 0
else:
return 1 + max(maxDep(r.left),maxDep(r.right))
def minDep(r):... |
|
x*******5
发帖数: 152 | 26 谢谢指正，修正两个bug，原始程序中只考虑了vector s[j]-s[i]，也就是位于i和j之
间的subarray，person同学给出的test case 是[0，i]之间的subarray，程序修正如下
def Subvector_Zero(v):
"find the subvector whose sum is close to zero"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(1,len(v)):
minv=min(minv,abs(s[i]-s[i-1]))
for c in s:
minv=min(minv,abs(c))
return minv
返回值是离0的最近距离
test case
v=[11,-30,-... 阅读全帖 |
|
p*****2
发帖数: 21240 | 27 翻转链表练习
class Node:
def __init__(self, val):
self.val=val
next=None
def reverse(head):
newhead=None
while(head!=None):
p=head
head=head.next
p.next=newhead
newhead=p
return newhead |
|
p*****2
发帖数: 21240 | 28 翻转链表练习
class Node:
def __init__(self, val):
self.val=val
next=None
def reverse(head):
newhead=None
while(head!=None):
p=head
head=head.next
p.next=newhead
newhead=p
return newhead |
|
p*****2
发帖数: 21240 | 29 最后一题是反着clone BT吧？
将一个bt，mirror一下返回一个新的数，要求不改变原来的树。我跟他说
，我不想做了，头一天坐了6个小时的飞机，他就送我下楼。
class Node:
def __init__(self,val):
self.val=val;
left=None;
right=None;
def clone(root):
if root==None:
return None;
Copy=Node(root.val)
Copy.left=clone(root.right)
Copy.right=clone(root.left)
return Copy |
|
p*****2
发帖数: 21240 | 30
第一题
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 | 31 第二题
def next(s):
ch=s[0]
c=1
ans=""
for i in xrange(1,len(s)):
if(s[i]==ch):
c+=1
else:
ans+=str(c)+ch
ch=s[i]
c=1
ans+=str(c)+ch
return ans
def get(n):
s="1"
for i in xrange(1,n):
s=next(s)
return s |
|
p*****2
发帖数: 21240 | 32 我写了一个
def merge(node1, node2):
if node1==None or node2==None:
return node1 if node2==None else node2
node1.right=merge(node2,node1.right)
return node1
def delete(root, node):
if root==None:
return None
elif root==node:
return merge(node.left,node.right)
else:
root.left=delete(root.left,node)
root.right=delete(root.right,node)
return root |
|
p*****2
发帖数: 21240 | 33 我写了一个
def merge(node1, node2):
if node1==None or node2==None:
return node1 if node2==None else node2
node1.right=merge(node2,node1.right)
return node1
def delete(root, node):
if root==None:
return None
elif root==node:
return merge(node.left,node.right)
else:
root.left=delete(root.left,node)
root.right=delete(root.right,node)
return root |
|
p*****2
发帖数: 21240 | 34 第一题
def Max(l):
dp=[1]*len(l)
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
dp[i]=dp[i-1]+1
return max(dp)
l=[3, 4, 4, 4, 2, 2, 3, 4]
print Max(l)
O(1) space的
def Max(l):
m=1
c=1
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
c+=1
m=max(m,c)
else:
c=1
return m |
|
p*****2
发帖数: 21240 | 35 第一题
def Max(l):
dp=[1]*len(l)
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
dp[i]=dp[i-1]+1
return max(dp)
l=[3, 4, 4, 4, 2, 2, 3, 4]
print Max(l)
O(1) space的
def Max(l):
m=1
c=1
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
c+=1
m=max(m,c)
else:
c=1
return m |
|
l****p
发帖数: 397 | 36 我觉得这题主要是考怎么构建树，至于树建起来了，怎么展现比较漂亮那是另一回事了
。这年头很少人会考用ASCII字符在控制台上打图形吧。顺便贴上我的实现：
class TreeNode
attr_accessor :value
attr_accessor :left
attr_accessor :right
def initialize value
@value = value
end
end
def get_trees preorder, head=0, tail=preorder.size
return [nil] if tail <= head
trees = []
for right_root in (head+1..tail)
left_trees = get_trees preorder, head+1, right_root
right_trees = get_trees preorder, right_root, tail
left_trees.each do |lt|
right_tree... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 37 贴个python版的
def expressable0(numList, target, curr, index):
N = len(numList)
if(index == N):
return curr == target
if(expressable0(numList, target, curr + numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr - numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr * numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr // numList[index], index + 1)):
... 阅读全帖 |
|
Z*****Z
发帖数: 723 | 38 贴个python版的
def expressable0(numList, target, curr, index):
N = len(numList)
if(index == N):
return curr == target
if(expressable0(numList, target, curr + numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr - numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr * numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr // numList[index], index + 1)):
... 阅读全帖 |
|
g****y
发帖数: 240 | 39 insertion sort? 不过要N^2的复杂度
def reverse(alist, i, j):
if i >= j:
return alist
return alist[:i] + alist[i: j + 1][::-1] + alist[j + 1:]
def sort(alist):
for i in range(1, len(alist)):
for j in range(i - 1, -1, -1):
if alist[j + 1] < alist[j]:
alist = reverse(alist, j, j + 1)
else:
break
return alist |
|
t****a
发帖数: 1212 | 40 谢谢提示。据此写clojure code如下，调试成功
(use 'incanter.core)
(defn subseqzero? [a]
(let [ac (cumulative-sum (cons 0 a))
acf (frequencies ac)]
(some #(> % 1) (vals acf))))
(def a [1 -3 4 1 -2 9])
(subseqzero? a) ; true
(def a [1 -3 4 3 -2 9])
(subseqzero? a) ; nil |
|
q****x
发帖数: 7404 | 41 这个yield到底有啥好处？这里的例子怎么省内存了？readlines不还是要读入整个文件
吗？
http://stackoverflow.com/questions/7883962/where-to-use-yield-i
我的理解：
def func_0(input_list):
return [f(i) for i in input_list]
def func_1(input_list):
for i in input_list:
yield f(i)
这两个区别在于，func_0把所有的f(i)算好，返回。func_1创建一个对象，包含input_
list，函数f，迭代子iter。遍历这个对象时，动态计算f(i)。这样看上去只是lazy
evaluation，并没有省内存啊。 |
|
g****y
发帖数: 240 | 42 第二题，只需要把第一个string中的数字map到第二个string的order就好了。
def reorder(str, order_str):
d = {c:i for i, c in enumerate(order_str)}
str = [c for c in str]
def get_key(c):
if c in d:
return d[c]
else:
return len(d)
str.sort(key=get_key)
return "".join(str) |
|
a**c
发帖数: 52 | 43 今天面了F家，现在来说说面经。
首先说了说做过的两个project，然后出了两道题让选择其中的一道
1. Anagram Buckets
Anagram = abc, cba, cab
Input: [abc, def, xyz, fde, fed, cab]
Output: [[abc, cab], [def, fde, fed], [xyz]]
2. RWLocks
xcgh, xadd, ...（题没有打完就选了第一题）
果断选择了第一道，写完code之后后被检查出一个小bug，没写i++,于是补上。
然后问有啥问题，我问了master和phd进公司后有啥区别么，答没区别，完全看干活水
平。
我觉得这题略简单啊，面过F家第一面的同学进来说说吧，能进入下一轮么？ |
|
s*********l
发帖数: 103 | 44 # The most beautiful substring
def f(s):
if len(s) <= 1:
return s
s1, s2 = split(s)
return ''.join(s1 + [c for c in f(s2)])
def split(s):
arr = [c for c in s]
last_seen = {}
max_v = 0
max_ind = -1
for i, c in enumerate(arr):
if c > max_v:
max_v = c
max_ind = i
last_seen[c] = i
i = max_ind - 1
s1 = [max_v]
while (i >= 0):
if last_seen[arr[i]] == i or arr[i] > s1[0]:
if arr[i] in s1:
... 阅读全帖 |
|
s*********l
发帖数: 103 | 45 # The most beautiful substring
def f(s):
if len(s) <= 1:
return s
s1, s2 = split(s)
return ''.join(s1 + [c for c in f(s2)])
def split(s):
arr = [c for c in s]
last_seen = {}
max_v = 0
max_ind = -1
for i, c in enumerate(arr):
if c > max_v:
max_v = c
max_ind = i
last_seen[c] = i
i = max_ind - 1
s1 = [max_v]
while (i >= 0):
if last_seen[arr[i]] == i or arr[i] > s1[0]:
if arr[i] in s1:
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 46 终于写完了，大牛们见笑了。
require 'set'
$dict=Set.new ['fox','fog','dog']
def indict?(word)
$dict.include? word
end
def transfer(first,last)
queue=[first]
hash={first=>0}
until queue.empty?
word=queue.shift
step=hash[word]
(0...word.length).each do |i|
curr=word[i]
('a'..'z').each do |c|
word[i]=c
if(word==last)
return step+1
elsif indict?(word) && !hash[word]
hash[word]=step+1
queue<<(String::new word)
end
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 47 我也写了一个练练。
mat=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
def helper(mat, i, j)
while i=0
print "#{mat[i][j]} "
i+=1
j-=1
end
puts
end
def print_mat(mat)
(0...mat[0].length).each {|k| helper(mat,0,k)}
(1...mat.length).each {|k| helper(mat,k,mat[0].length-1)}
end
print_mat(mat) |
|
p*****2
发帖数: 21240 | 48 def dfs(arr, start, buf)
p buf if buf.length>0
(start...arr.length).each do |i|
buf<
dfs(arr,i+1,buf)
buf.pop
end
end
def subset(arr)
buf=[]
dfs(arr,0,buf)
end
subset([1,2,3]) |
|
l*******b
发帖数: 2586 | 49 试一下scala写的第一个程序。。。
val list = Array[Int](1,3,4,5,7,9)
def powerSet(l: Array[Int]) = {
def select(i: Int, n:Int) =
for(j <- 0 to n if((i & (1 << j)) != 0)) yield l(j)
val n = l.length - 1
val p = (1 << (n+1)) - 1
val power = for(i <- 0 to p) yield select(i,n).mkString(" ")
power.mkString("\n")
} |
|
p*****2
发帖数: 21240 | 50 require 'set'
$dict=Set.new ['check','out','checkout']
def indict?(word)
$dict.include? word
end
def min_words(str)
n=str.length
dp=[-1]*(n+1)
dp[n]=0
(n-1).downto(0).each do |i|
min=-1
(1..n-i).each do |j|
if indict?(str[i,j]) && dp[i+j]>=0 && (min==-1 || dp[i+j]+1
min=dp[i+j]+1
end
end
dp[i]=min
end
dp[0]
end
p min_words('checkout') |
|
