l*******b
发帖数: 2586 | 1 写成state machine得有7种状态，5种字符，还不能handle + -空格。。。
val table = Array(Array(0,0,0,0,0), // 0 false
Array(0,2,0,0,7), // 1 numbers eof
Array(0,2,3,5,7), // 2 numbers e . eof
Array(0,4,0,0,0), // 3 numbers
Array(0,4,0,5,7), // 4 numbers e eof
Array(0,6,0,0,0), // 5 numbers
Array(0,6,0,0,7), // 6 numbers eof
Array(7,7,7,7,7)) // 7 true
def isNumber(s: String) = {
def isNumber_helper(index: Int, stat: Int) :Boolean = {
val t... 阅读全帖 |
|
l*******b
发帖数: 2586 | 2 写成state machine得有7种状态，5种字符，还不能handle + -空格。。。
val table = Array(Array(0,0,0,0,0), // 0 false
Array(0,2,0,0,7), // 1 numbers eof
Array(0,2,3,5,7), // 2 numbers e . eof
Array(0,4,0,0,0), // 3 numbers
Array(0,4,0,5,7), // 4 numbers e eof
Array(0,6,0,0,0), // 5 numbers
Array(0,6,0,0,7), // 6 numbers eof
Array(7,7,7,7,7)) // 7 true
def isNumber(s: String) = {
def isNumber_helper(index: Int, stat: Int) :Boolean = {
val t... 阅读全帖 |
|
p*****2
发帖数: 21240 | 3 也许我理解错了。我简单写了一个，看看有没有问题。
def check(left:TreeNode, right:TreeNode)={
def dfs(left:TreeNode, right:TreeNode):Boolean={
if(left==null || right==null) return left==right
if(map1.contains(left) || map2.contains(right)) return map1.
contains(left) && map1(left)==right && map2.contains(right) && map2(right)==
left
map1(left)=right
map2(right)=left
return left.value==right.value && dfs(left.left,right.left) &&
dfs(left.right,right.r... 阅读全帖 |
|
w**********o
发帖数: 140 | 4 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]) |
|
w**********2
发帖数: 20 | 5 Reduce 的输出肯定是(i,j) -> 下一次的值。Map的输出目的就是，想办法能把reduce
计算(i,j)下一时刻的值需要用到的数据group到一起。 假设map的输入是(i, j) ->当
前值，计算(i,j) 下一时刻的值需要用到它的八邻点，反推他的八邻点下一时刻的值也
需要用到(i,j)当前值。 所以 map的输出就是 (i-1, j) -> (i,j)当前值，(i+1,j) ->
(i,j)当前值，...输出8个键值对。对reduce来说就好办了，需要的数据都gourp好了。
def map(partMat):
for k, v in partMat:
i, j = k
emit((i-1, j-1), v)
emit((i, j-1), v)
emit((i+1, j-1), v)
emit((i-1, j), v)
emit((i+, j), v)
emit((i-1, j+1), v)
emit((i, j+1), v)
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 6 class MyIterator[T](it:Iterator[T]){
private[this] var curr:T=_
private[this] var has=false
def peek():T={
if(has) return curr
if(it.hasNext){has=true; curr=it.next; curr} else null.asInstanceOf[
T]
}
def pop():T={
if(has) has=false; return curr
if(it.hasNext) it.next else null.asInstanceOf[T]
}
} |
|
p*****2
发帖数: 21240 | 7 class MyIterator(v:Vector[Vector[Int]]){
private[this] val vector1=v.iterator
private[this] var vector2:Iterator[Int]=null
def hasNext():Boolean={
if(vector2!=null && vector2.hasNext) return true
vector2=null
while(vector1.hasNext && (vector2==null || !vector2.hasNext))
{
val next=vector1.next
if(next!=null) vector2=next.iterator
}
vector2!=null && vector2.hasNext
}
def next():Int={
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 8 我写了一个练练
def findPosition(arr:Array[Int], target:Int):Int={
def bsearch(start:Int, end:Int):Int={
if(start==end) return end
val mid=start+(end-start)/2
arr(mid)-target match{
case x if x<=0 =>bsearch(mid+1,end)
case _ => bsearch(start,mid)
}
}
bsearch(0,arr.size)
} |
|
p*****2
发帖数: 21240 | 9 我贴一下我的
val n=S.length
val s_counts=new Array[Int](26)
val t_counts=new Array[Int](26)
0 until n foreach{i=>
s_counts(S(i)-'A')+=1
t_counts(T(i)-'A')+=1
}
var count=0
for(i<-0 until n if s_counts(S(i)-'A')-t_counts(S(i)-'A')>0)
process(i)
out.println(count)
out.println(S.mkString)
out.close
def process(i:Int){
val next=find
val c=S(i)
if(t_counts(c-'A')==0 || next
S(i)=n... 阅读全帖 |
|
p*****2
发帖数: 21240 | 10 val arr=Array(1,2)
val n=arr.length
var target=5
println(calPos(n,null)(target))
def calPos(i:Int, dp:Array[Int]):Array[Int]=i match{
case `n` => val ar=new Array[Int](target+1);ar(0)=1;calPos(i-1,ar)
case -1=>dp
case _ => val ar=calAmount(i,dp); calPos(i-1,ar)
}
def calAmount(i:Int,dp:Array[Int]):Array[Int]={
val ar=new Array[Int](target+1)
for(j<-0 to target)
if(j阅读全帖 |
|
p*****2
发帖数: 21240 | 11 def distinct(arr:Array[Int]):Int={
dfs(arr, 0, arr.length-1, math.max(arr.head.abs, arr.last.abs), 1)
}
def dfs(arr:Array[Int], i:Int, j:Int, curr:Int, count:Int):Int=arr match{
case null => 0
case _ if arr.length==0 =>0
case _ if i>j => count
case _ if arr(i).abs==curr => dfs(arr, i+1, j, curr, count)
case _ if arr(j).abs==curr => dfs(arr, i, j-1, curr, count)
case _ => dfs(arr, i, j, math.max(arr(i).abs, arr(j).abs), count... 阅读全帖 |
|
p*****2
发帖数: 21240 | 12 def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(i<-0 until operators.length) operators(i) match{
case '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -... 阅读全帖 |
|
p*****2
发帖数: 21240 | 13 def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(i<-0 until operators.length) operators(i) match{
case '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -... 阅读全帖 |
|
p*****2
发帖数: 21240 | 14 来自主题: JobHunting版 - G 家面经 第一题练了练。没有测试。
class QTreeNode (var color:Int){
val children=new Array[QTreeNode](4)
}
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}
def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.ch... 阅读全帖 |
|
p*****2
发帖数: 21240 | 15 来自主题: JobHunting版 - G 家面经
加了一句，检查这个条件。你觉得够了吗？
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}
def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.children(i)=intersection(left.children
(i), right.children(i))
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 16 来自主题: JobHunting版 - G 家面经 第一题练了练。没有测试。
class QTreeNode (var color:Int){
val children=new Array[QTreeNode](4)
}
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}
def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.ch... 阅读全帖 |
|
p*****2
发帖数: 21240 | 17 来自主题: JobHunting版 - G 家面经
加了一句，检查这个条件。你觉得够了吗？
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}
def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.children(i)=intersection(left.children
(i), right.children(i))
... 阅读全帖 |
|
s******s
发帖数: 63 | 18 根据楼上的某个版本写的 大概1秒可以run ~1，000，000 长度的输入
import sys
def prime_factors(n):
pf={}
prime = 2
while n>=prime:
if n%prime == 0:
pf[prime] = 1
n = n/prime
while n%prime==0:
n = n/prime
pf[prime] = pf[prime]+1
prime = prime + 1
return pf
def main(s):
n = len(s)
sl = set(s)
if n <= 1 or n==len(sl):
return 1
pf = prime_factors(n)
print(pf)
multiplier = 1
for factor in pf:
while pf[factor]>0:
divide = 1
for i in range(f... 阅读全帖 |
|
p*****2
发帖数: 21240 | 19 第一题
def solve(mat:Array[Array[Int]]):Unit={
val n=mat.length
val m=mat(0).length
val v=Array.ofDim[Boolean](n,m)
def check(i:Int, j:Int):Unit={
val isOK=(x:Int,y:Int)=>{
x>=0 && x=0 && y
}
var fill=true
if(isOK(i,j)){
val set=collection.mutable.Set[Int]()
val queue=collection.mutable.Queue[Int]()
queue+=i... 阅读全帖 |
|
p*****2
发帖数: 21240 | 20 我写了一个。看看有没有问题？
import collection.mutable.{Map, Queue}
object test2 extends App {
val Array(n,k)=readLine.split(" ").map(_.toInt)
val start=readLine.split(" ").map(_.toInt-1).mkString(" ") //pegs and
discs start from 0
val end=readLine.split(" ").map(_.toInt-1).mkString(" ")
val queue=new Queue[String]()
val map=Map[String,String]()
var distance=0
var count=1
queue+=end
map(end)=null
while(count>0){
distance+=1
while(count>0){
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 21 我写了一个。看看有没有问题？
import collection.mutable.{Map, Queue}
object test2 extends App {
val Array(n,k)=readLine.split(" ").map(_.toInt)
val start=readLine.split(" ").map(_.toInt-1).mkString(" ") //pegs and
discs start from 0
val end=readLine.split(" ").map(_.toInt-1).mkString(" ")
val queue=new Queue[String]()
val map=Map[String,String]()
var distance=0
var count=1
queue+=end
map(end)=null
while(count>0){
distance+=1
while(count>0){
... 阅读全帖 |
|
S*******w
发帖数: 24236 | 22 第一题python解法：
def getK(numList, b):
numList.sort()
print numList
sumNumList = sum(numList)
if (sumNumList<=b):
print "Does not exist such K!"
return -1
currentSum = 0
n = len(numList)
for m in range(0, n):
if (b-currentSum)>0 and (b-currentSum)%(n-m)==0:
K = (b-currentSum )//(n-m)
if K < numList[m]:
return K
currentSum += numList[m]
print "Does not exist such K!"
return -1
def main():
... 阅读全帖 |
|
f********d
发帖数: 51 | 23 and the reason why scala throws error is because of the way it treats def
and val
you can do:
class A {def a="a"}
class B extends A { override val a="b"}
if you go with javap, you will get:
public class B extends A{
public java.lang.String a();
public B()
}
at byte code level, val is indeed converted to a method. in other word,
scala doesn't treat the field as real field but methods.
methods obviously need to follow method resolution which is override.
technically, scala is really following jvm ... 阅读全帖 |
|
g***9
发帖数: 159 | 24 发个python的第一题试试：
def AllBracketsMatchedImpl(line, counter):
if len(line) == 0:
if counter == 0:
return True
else:
return False
#if
c = line[0]
if c == '(':
counter += 1
elif c == ')':
if counter == 0:
return False
counter -= 1
#if
return AllBracketsMatchedImpl(line[1:], counter)
def AllBracketsMatched(line):
counter = 0
return AllBracketsMatchedImpl(line, counter)
##line ... 阅读全帖 |
|
B**********2
发帖数: 923 | 25 首先感谢microleo，给我推荐
电话两轮，一个聊天，一个简单的电面。
Coding Test 一轮，题目为Spread Sheet，大家可以自行Google
得到Positive Feedback
5月8号 On site
分别两个工程师两个项目经理
鉴于每个人多聊了一会我以前的Project，所以每个人问1到3个问题不等。
----------------- 割割割割割割割割 -----------------------------
Q: Spread Sheet 如果太大，不能整个Load进内存来处理。但是可以有多个
机器按照一定的信息读本机文件。假设Spread Sheet每个连通片的计算量
一个机器能够处理
A: Virtually的建立无向连通图，用DFS获得连通片，每个连通片交给一个主机来计算
----------------- 割割割割割割割割 -----------------------------
Q: 给一个森林和已知两个节点，求最近公共祖先，如果没有，返回NULL
A: 我说啥语言没有什么区别，先上伪码，MIT Press Algorithm ... 阅读全帖 |
|
w********g
发帖数: 106 | 26 按行倒序输出文件。例如一个文件如下：
abc
123
def
那么输出：
def
123
abc
我说先给个naive的方法一会再改进，建个vector，把每一行写到这个vector
里，然后倒序输出这个vector。他问有什么缺点，我说处理不了大文件，他就叫我改进
。他给了我三个函数：
void seek(int location)：文件指针指向第location个字符，如果seek(-1)那么文件
指针指向end of file。
int tell()：返回文件指针当前指向哪个字符
string read(bytes)：每次读bytes个字符，返回这些字符组成的string，然后文件指
针向后移动一个字符。比如本来文件指针指向第10个字符，那么read(1)就返回第10个
字符组成的字符串，并且文件指针指向第11个字符。
他让我用这三个函数写倒序输出。写着写着我就逻辑混乱了。其实这题很简单，没有算
法很严，就是考察思路是不是严谨。但是我确实写写就乱了。。。我感觉其实面试时考
察这么繁琐的题目是最难的。 |
|
g****o
发帖数: 547 | 27 这题是不是常考的一道智力题？
2、 用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然
后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单
词本身又被转回来了。
可以在o(n)时间内原地实现
具体来说
abc
123
def
先将整篇文章的所有字符逆序
fed
321
cba
然后用同样的办法将每个单词内部的字符逆序
def
123
abc
就完成了
vector |
|
c*******h
发帖数: 22 | 28 来自主题: JobHunting版 - 问个面试题 想出来一个用hashtable + bfs的方法，用python写了一下。
from sets import Set
def create_pool(pool,maps,keys):
pool += keys
[ create_pool(pool, maps, maps[key]) for key in keys if maps.has_key(key
) ]
return pool
def findminimalpair(pairs):
keys = list(Set([item[0] for item in pairs ]))
maps = dict((key,[]) for key in keys)
for item in pairs:
maps[item[0]].append(item[1])
result = []
for key in keys:
values = maps[key]
pool = create_pool([],maps,[key])
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 29 (def dict #{"i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream",
"icecream",
"man", "go", "mango"})
(def input "ilikesamsung")
(defn dfs [str, start, curr, list]
(if (= curr (count str))
(when (= start (count str))
(println (reverse list)))
(let [next (inc curr) sub (subs str start next)]
(when (contains? dict sub)
(dfs input next next (cons sub list)))
(dfs input start next list))
))
(dfs input 0 0 ()) |
|
p*****2
发帖数: 21240 | 30
第二题
(def a '(5 6 6 8))
(def b '(4 4 6 6 8))
(defn f [a, b, c]
(let [aa (first a) bb (first b)]
(if (and aa bb)
(cond
(< aa bb) (f (rest a) b c)
(> aa bb) (f a (rest b) c)
:default (f (rest a) b (cons aa c)))
c)))
(println (reverse (f a b ()) )) |
|
p*****2
发帖数: 21240 | 31 def pow(x:Int, y:Int)= {
def f(x:Int, y:Int, s:Double):Double= y match{
case some if some<0 => 1.0/f(x, -y, s)
case 0=> s
case some if some%2==0 => f(x*x, y/2, s)
case _ => f(x, y-1, s*x)
}
f(x,y,1.0)
} |
|
b*******e
发帖数: 123 | 32 例如，
def memo Fibo(n):
if(n<3):
return 1;
else:
return Fibo(n-1) + Fibo(n-2);
因为有memo keyword, compiler 会自动加个dictionary(int,int),compiler 出来的
psedo-code 是
di = {}
def Fibox(n):
if n in di:
return di[n];
else:
di[n] = Fibo(n)
return di[n]
当然这个是简单例子，如果有很多input parameter的话，好像会简洁些。 |
|
r*******n
发帖数: 3020 | 33 难道用map reduce?
def map_function(array):
for i, each in enumerate(array):
EmitKeyValue((i,each), 1) // use index and array[index] as key
// to make duplicate elements unique
def reduce_function(key, iterator v):
if sum(v)==4:
EmitKeyValue(key) //this is the key in 4 arrays.
way |
|
b*********s
发帖数: 115 | 34 def solution(n):
cache = {}
def helper(target, minVal, allowedZero):
if (target, minVal) in cache:
return cache[(target, minVal)]
if minVal > target:
return []
elif minVal == target:
return [[minVal]]
else:
res = []
for i in range(minVal, target):
tail = helper(target - i, i, True)
for solution in tail:
solution.append(i)
res += t... 阅读全帖 |
|
z***e
发帖数: 58 | 35 估计是跪了
简历题， 网站架构方面。
第一道题 nondetermistic testing 怎么测试， 这个题卡住了 不知道怎么回答。
第二题： 有序数组中查找第一个出现的数，数组里面可能有重复。 做完之后写test
case，如何设计test case， 考虑哪方面， 感觉还行。
第三题： 就是这个题把我整跪了，
def inc:
while True:
v = v + 1 //---A
set(s) // ---B
def disp:
while True:
wait(s) //---C
print v //----D
求输出序列的可能情况 v 是shared value 初始为0
s是binary semophore 初始为0。set(s) 置s为1，wait(s) unset s 并且blocking。
第一问 0 是否能输出， 回答 不能，因为会blocking ， OK。
第二问， 后面的情况，会输出什么样的递增数字， 我一想执行序列可能为 ABABCD，
这样的话 有些number 就m... 阅读全帖 |
|
b*********s
发帖数: 115 | 36 其实很短就可以写完
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... 阅读全帖 |
|
b*********s
发帖数: 115 | 37 谢面经!
RF 第一题答的不对
比如说 num = 42319, k = 4, 按你的删法会得到2, 但最小应该是1
应该是扫描前k个digit，找到最小的一个，假设为第i个，那么就把前i- 1个digit删掉
，然后对从第i+1个digit开始到字符串末尾的substring递归，新的递归里面k要减掉i
- 1
下面是python实现：
def solve(s, k):
return deleteDigit(s, 0, len(s), k)
def deleteDigit(s, start, end, k):
if end - start <= k or k <= 0:
return ''
minDigit = 10
minPosition = -1
for i in range(start, start + k + 1):
d = ord(s[i]) - ord('0')
if 0 <= d <= 9:
if d < minDigit:
... 阅读全帖 |
|
m*****n
发帖数: 204 | 38 I wrote a java solution in another thread using iterator-ized (tail)
recursion:
http://www.mitbbs.com/article0/JobHunting/32585567_0.html
It is equivalent to the following python code:
def iterate(list):
for obj in list:
if isinstance(obj, int):
yield obj
else:
for sub_obj in iterate(obj):
yield sub_obj
def main():
list = [ 1, 2, [], 3, [ 4, 5 ], 6 ]
for i in iterate(list):
print i
print 'Done' |
|
r*****n
发帖数: 35 | 39 来自主题: JobHunting版 - f家店面题 A method combine DP and greedy
object RiverJump {
def main(args: Array[String]) {
//val a = Array(1,1,1,0,1,1,0,0)
val a = Array(1,1,1,0,1,1,1,1, 0, 0)
val m = jump(a, 0, 1)
println(s"""$m""")
}
val set = new mutable.HashSet[(Int, Int)]()
def jump(r: Array[Int], start: Int, speed: Int): (Int, Boolean) = {
var ret: (Int, Boolean) = (Int.MaxValue, false)
if (start >= r.length) {
ret = (0, true)
} else if (set.contains(start, speed) || r(start) == 0) {
... 阅读全帖 |
|
A*****o
发帖数: 284 | 40 Bless !
第一题第二问写了个用集合的方法O(nlogk), 不知道LZ是怎么做的?
def has_dup_k(arr, k):
if not arr or k <= 0:
return False
n = len(arr)
s = set([])
for i in xrange(0, k):
x = arr[i]
if x in s:
return True
s.add(x)
#for
for i in xrange(k, n):
x = arr[i]
if x in s:
return True
s.remove(arr[i-k])
s.add(x)
return False
def test():
arr = [1, 2, 3, 1, 3, 2, 9, 0, 1]
k = 2
print has_dup_k(arr, k)... 阅读全帖 |
|
z***e
发帖数: 5393 | 41 来这里吐槽国内招人的郁闷：
老子真心没有想刁难哪个啊，但是招程序不就是以"talk is cheap, show me the code
"为原则么，尼玛为毛中国至少成都这边的各种所谓满大街都是的程序员一听说要写白
板，一听说“单链表"(linked list)这种东西就像见鬼了一样啊！！！
数了一下，本周面了两个川大的，两个电子科大的，两个西南大学（原西南师范大学）
，两个西南交大，两个成都理工大学的在读硕士。。。面的题目就是俗得不能再俗的
reverse linked list。。。然后这些人的表情才叫精彩，只有一个西南交大毕业工作
了一年左右的还能用正确的数据结构然后人工在那里模拟如何reverse，起码还可以动
手，虽然最后也没完成。其它的，基本上在那里呆看半天，写一个 while (next->next
){ ， 然后。。。就没有然后了，就给我说哎呀很久没弄这些了记不得了（尼玛老子找
的都是毕业不到一年的你给我说你记不得了）。。。
好，记不得linked list，或者你说你不是computer science毕业的，好，我理解（我
理解个屁啊，你来应聘software en... 阅读全帖 |
|
p**o
发帖数: 3409 | 42 The idiomatic way:
In [1]: s = 'the sky is blue'
In [2]: ' '.join(reversed(s.split()))
Out[2]: 'blue is sky the'
Follow-up: OK, looks simple, but `s.split()` creates auxiliary space.
Can you do it in-place, i.e., with O(1) space?
为了迎合这样的变态要求，我们被迫要写下面这样C风格的所谓“算法”代码
In [9]: def swap_chars(s, iBgn, iEnd):
...: """ Reverse chars in buffer s ranging from iBgn to iEnd (
exclusive).
...: """
...: for i in range(iBgn, (iBgn+iEnd)//2):
...: j = iBgn + iEnd - i - 1
.... 阅读全帖 |
|
p**o
发帖数: 3409 | 43 只要意识到递归关系：后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5
实现就异常elegant（Python3.3+）
def gen5 (n):
""" Generate all k-digit (1<=k<=n) decimals with digit 5 in ascending
order. """
if n>=1:
POW = 10**(n-1)
yield from (x * POW + y for x in range(5) for y in gen5(n-1))
yield from (5 * POW + y for y in range(POW))
yield from (x * POW + y for x in range(6,10) for y in gen5(n-1))
如果你只是要顺序输出打印“所有含5的N位十进制数”，简单地
>>> list(gen5(0))
[]
>>> list(gen5(1))
[5]
>>> list(gen5(2))
[5, 15, 25, 3... 阅读全帖 |
|
p**o
发帖数: 3409 | 44 我11楼那个方法，“后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5”，
从most significant digit开始递归，保证输出有序，
所以容易根据给定的最大值终止生成器。
此前我的思路是从个位数往高位开始左移递归：
“前n位含5 当且仅当 第n位是5 或 前n-1位含5”。
这种方法的缺陷是：结果无序，所以不方便根据给出的最大值跳出生成器。
DIGIDS_NO5 = (0,1,2,3,4,6,7,8,9)
# Generate all k-digit (1<=k<=n) numbers without digit 5
def genno5 (n):
if n == 1: yield from DIGIDS_NO5
else:
for x in genno5(n-1):
for y in DIGIDS_NO5:
yield 10 * y + x
# Generate all k-digit (1<=k<=n) numbers with digit 5
def gen5 (n):
... 阅读全帖 |
|
p**o
发帖数: 3409 | 45 只要意识到递归关系：后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5
实现就异常elegant（Python3.3+）
def gen5 (n):
""" Generate all k-digit (1<=k<=n) decimals with digit 5 in ascending
order. """
if n>=1:
POW = 10**(n-1)
yield from (x * POW + y for x in range(5) for y in gen5(n-1))
yield from (5 * POW + y for y in range(POW))
yield from (x * POW + y for x in range(6,10) for y in gen5(n-1))
如果你只是要顺序输出打印“所有含5的N位十进制数”，简单地
>>> list(gen5(0))
[]
>>> list(gen5(1))
[5]
>>> list(gen5(2))
[5, 15, 25, 3... 阅读全帖 |
|
p**o
发帖数: 3409 | 46 我11楼那个方法，“后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5”，
从most significant digit开始递归，保证输出有序，
所以容易根据给定的最大值终止生成器。
此前我的思路是从个位数往高位开始左移递归：
“前n位含5 当且仅当 第n位是5 或 前n-1位含5”。
这种方法的缺陷是：结果无序，所以不方便根据给出的最大值跳出生成器。
DIGIDS_NO5 = (0,1,2,3,4,6,7,8,9)
# Generate all k-digit (1<=k<=n) numbers without digit 5
def genno5 (n):
if n == 1: yield from DIGIDS_NO5
else:
for x in genno5(n-1):
for y in DIGIDS_NO5:
yield 10 * y + x
# Generate all k-digit (1<=k<=n) numbers with digit 5
def gen5 (n):
... 阅读全帖 |
|
p**o
发帖数: 3409 | 47 (Please use monospaced font to read)
Example:
i: 0 1 2 3 4 5 6 7 8 9
S0: a a b x c a b x c b
T0: a b c b
expected output: [5,10)
n=len(S0), m=len(T0)
Collect indices in S0: O(n) time
a: 0 1 5
b: 2 6 9
c: 4 8
I wanted to use dynamic programming,
but I did not find any optimal substructure.
So I chose to backtrack on these indices instead.
T0: a b c b
i: 0 1 2 3 4 5 6 7 8 9
S0: a a b x c a b x c b
S1: a _ b _ c _ b _ _ _ -> [0,7)
S2: a _ b _ c _ _ _ _ b -> [0,10)
S3: a _ b _ _ _ _ _ c b -> [0... 阅读全帖 |
|
f******h
发帖数: 45 | 48 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
k***s
发帖数: 6 | 49 抛低轨砖
def __min_cost_rec(self, cuts, start, end, memory):
if memory[start][end] is None:
fix_cost = cuts[end] - cuts[start]
min_cost = float('Inf')
for i in range(start + 1, end):
min_cost = min(min_cost,
self.__min_cost_rec(cuts, start, i, memory) +
self.__min_cost_rec(cuts, i, end, memory) +
fix_cost)
memory[start][end] = min_co... 阅读全帖 |
|
w****r
发帖数: 28 | 50 一起循环似乎不可以，需要一个颜色一个颜色来， 而且只需要排2个颜色就可以了
color = ["B", "R", "R", "R", "B", "B", "G", "G", "G"]
def exchange(color, i, j):
temp = color[i]
color[i] = color[j]
color[j] = temp
def arrange(color, c, pos):
j = pos
for k in range(len(color)):
if ((color[k] == c) & (k%3 != pos)):
while (color[j] == c):
j += 3
exchange(color, k, j)
arrange(color, "R", 0)
arrange(color, "G", 1) |
|
