c*********t
发帖数: 2921 | 1 过去这个班上讨论了interleave数组的问题，
给定数组： A B C D E 1 2 3 4 5
输出: A 1 B 2 C 3 D 4 E 5
可是这个问题的对偶题，就是说
给定数组：A 1 B 2 C 3 D 4 E 5
如何in-place把数组变成 A B C D E 1 2 3 4 5
?
谢谢了！ |
|
b******g
发帖数: 1721 | 2 我没搜索，不过我想到了冒泡算法。
因为是interleaving而且字符和数字已经排好序了, 所以就是简单的扫一遍，过程中数
字和后面的字符交换。
准确讲是O(n/2)=>O(n). |
|
g****y
发帖数: 240 | 3 Edit： 好像不对，还是更复杂的情况。
想了一个O（n）的解法。请帮忙看一下对不对。
if A and B have no duplicate char: easy problem. just traverse C. increase A
's
index if A's char matches or increase B's index if B's char matches.
if A and B have duplicate chars, we assume A[i, j] == B[m, n].
when we traverse C and in the position where C[k] == A[i] == B[m], we have
two ways to go: increase A's index or increase B's index. in this kind of
situation, we will always select to increase A's index.
if we are lucky, A is the right way to ... 阅读全帖 |
|
a*******y
发帖数: 1040 | 4 leetcode那个interleave的例子怎么是true的啊
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
那个true的case |
|
C***U
发帖数: 2406 | 5 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false. |
|
C***U
发帖数: 2406 | 6 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false. |
|
N*********6
发帖数: 4372 | 7 看到板上有网友报面经，往前翻翻发现大家讨论过很多次
小弟有几个问题
String a 长度 m
String b 长度 n
String c 长度 m+n
verify c 是不是a 和 b的interleaving
1. 这道题用DP的话时间上应该是O(m*n),空间上填2d table的话是O(m*n)
如果重复利用行的话可以到O(n)
2. 如果是Recursion的话复杂度是多少呢？我不理解的是如果c
当前字符和a的当前字符以及b的当前字符都一样的话，要分两路
去查找，当然第一路如果返回true的话第二路就没必要了，可是
一个比较极端的例子
a: aaaaa
b: aaaad
c: aaaadaaaaa
如果算法在遇到相同的字符是先假定是从a string来的，这个例子
就会非常time consuming，需要不停back tracking，请问这种情况
下recursion的复杂度是多少呢？
昨天在leetcode上用recursion发现small data可以过，large的
就超时了
3. 如果递归，我个人觉得不应该在开始比较字符串长度是否相等吧？
因为每次获取... 阅读全帖 |
|
p***g
发帖数: 135 | 8 “Automotive DC-DC bidirectional converter made with many interleaved buck
stages,” Garcia, O., Zumel, P., de Castro, A., Cobos, A., Power Electronics
, IEEE Transactions on Volume 21, Issue 3, May 2006 Page(s):578 – 586
Thanks, |
|
c*****n
发帖数: 96 | 9 bool isInterleave(String a, String b, String c){
return isInterleave(a, b, c, "");
}
bool isInterleav(String a, String b, String c, String interleave){
if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)){
return c.equals(interleave);
}
if (String.IsNullOrEmpty(a))
return c.equals(interleave + b);
if (String.IsNullOrEmpty(b))
return c.equals(interleave + a);
return isInterleave(a.SubString(1), b, c, interleave + a.SubString(0,1))
|| isInterl... 阅读全帖 |
|
t****a
发帖数: 1212 | 10 a lisp solution, O(n) complexity
;; O(n) solution
(defn interleave? [a b c]
(cond (and (= (count a) 0) (= (count b) 0) (= (count c) 0)) true
(not= (+ (count a) (count b)) (count c)) false
(= (last a) (last c)) (interleave? (butlast a) b (butlast c))
(= (last b) (last c)) (interleave? a (butlast b) (butlast c))
:else false))
(interleave? "ef" "gh" "egfh") ; returned true
(interleave? "ef" "gh" "ehgf") ; returned false
(interleave? "abcc" "ac" "aabccc") ; return... 阅读全帖 |
|
s***d
发帖数: 15421 | 11 那么快速度，不flash 怎么整？也可能可以interleave sar，或者interleave
pipeline，不过功耗要ok，其实还是要做interleave sars。NXP 还有fujitsu 有类似
IP，好像都是sar。
华为国内有个组，再搞也是interleave sar。 |
|
d******a
发帖数: 238 | 12 ab ac => acab 这种情况应该返回true. 我面完后想了用递归写了个简单的，不知道可
能会有啥bug..
bool interleave(const char *a, const char *b, const char *c)
{
assert(a != NULL && b != NULL && c!= NULL);
if (*a == '\0' && *b == '\0' && *c == '\0')
return true;
if (*a == *c && *c != '\0' && interleave(a + 1, b, c + 1) )
return true;
if (*b == *c && *c != '\0' && interleave(a, b + 1, c + 1) )
return true;
return false;
} |
|
g*******y
发帖数: 1930 | 13 你先给interleaving定义一下？
我做的算法课的作业题里面，interleaving的定义是，string的一个subsequence是A的
repeation，剩下的subsequence是B的repeation
repetion的定义是：
ABC的repetion就是ABCABCABC...ABC + '空/A/AB'
one. |
|
b***e
发帖数: 1419 | 14 // I don't see why I didn't explain enough, or, you didn't understand
enough?
"A path from (0, 0) to (i, j)" is not a bit different from "an
interleaving of A[1...i] and B[1...j]".
is an interleaving of A[1...i] and B[1...j] |
|
x********u
发帖数: 1150 | 15 来自主题: JobHunting版 - G新鲜面经 非牛人. 供讨论.
1.2 一个数组，找出一个solution使得1st《2nd， 2nd》3rd。。比如15462就是数组1
，2，4，5，6的一个solution。
从结果到条件往前推:
结果: aceg
分开来看:
a
b>c>e>g
明显, b是一个特殊的数, 它大于一半的数, 小于一半的数. 所以b应该是中数. a应该
是b之前的一个数.
d and f 应该是中数后面的数; c,e,g 应该是中数前面的数.
那这样的分析后, 我们可以这么做:
1. 把input array先sort.
2. 把中数和中数前的数挑出来, 做b and a.
3. 中数后面的数挑出来做 d, f, ...
4. 中数前面的数挑出来做 c, e, g, ...
5. interleave 3 and 4
example:
1，2，3, 4，5，6, 7, 8
A. let b be 5, a be 4
B. 4<5<6<7<8
C. 5>3>2>1
interleave 后.
4<5>3<6>2<7>1<8 |
|
v*****r
发帖数: 2325 | 16 get ready --- deep breath and rope jumping
3 sets of 5 reps (5 sets of 2 reps)
push (1 arm push up) interleave with pull (bent over row)
core stability (kb bottom up carry, tgu)
compound (double kb/db swing)
hip and knee (1 leg dead lift interleave with 1 leg squat , suitcase deadlift)
cool down with with stretch
3 times a week, 4th week use 50% intensity
cardio |
|
l****p
发帖数: 5 | 17 随便说说关于turbo code和ldpc。
在turbo code原作者的某篇文章中提到，（sorry，记不清楚了，好像是某年ieee paper
award 的介绍文章中）turbo
code是从硬件实现的问题出发的。后来人们才认为它的interleave和香农的随机编码的id
ea类似，并由此来解释它的突出性能。但interleave本身是很早就有的概念，为了避免突
发错误带来的致命影响，或者说，更好的利用时间diversity.
至于ldpc，我不记得在Gallager 的博士论文中有提到他是在香农随机编码的影响下来设
计自己的矩阵的，固然，他的矩阵是随机产生的。
当然，香农那样划时代的论文对其他人所施加的潜在的影响是肯定存在的。只是觉得，无
论是从turbo code和ldpc来看，很难发现信息论对实际的真正制导价值。从另一方面来说
，turbo code的原型是并联的卷级码。但利用多种码来提高性能是非常自然的想法，我觉
得turbo code的关键贡献是在于设计了sova和iterative decoding。ldpc也有同样的情形
。
香农的贡献是全方位的和勿庸置疑的。或 |
|
h*********g
发帖数: 43 | 18 常见的on-chip DC DC Converter结构中，除了LDO，switching converter，还有只采
用电容的switched capacitor converter。这个方向最近在on-chip power delivery中
很热门，在2012年的ISSCC,CICC中都有多篇收录，主要结构就是interleaving加上
reconfigurable。Interleaving可以降低输出的ripple，reconfigurable结构可以克服
switched capacitor converter的conversion ratio是离散的这个缺点。可是在工业界
中，switched capacitor converter（可能也叫charge pump）却还是没有在on-chip
DC DC中有什么大的应用。请教板上做DC DC的大牛对这个方向怎么看，是只是学术界的
小打小闹，还是有应用的前景? 个人认为，switched capacitor converter的优势就是
不用电感，易于集成，但是缺点也很大，就是conversion ratio只有一个，所以... 阅读全帖 |
|
a****1
发帖数: 175 | 19 【 以下文字转载自 Returnee 讨论区 】
发信人: mingfm (carol), 信区: Returnee
标 题: 关于所谓“放弃45万美元年薪，留美博士南充“安家”的回复
发信站: BBS 未名空间站 (Tue Feb 15 17:03:06 2011, 美东)
◇◇新语丝(www.xys.org)(xys5.dxiong.com)(www.xinyusi.info)(xys2.dropin.org)
◇◇
关于所谓“放弃45万美元年薪，留美博士南充“安家”的回复
作者：母其文
亲爱的Fred，
谢谢你的兴趣与留意
（http://xinyusi.s3.amazonaws.com/xys/ebooks/others/science/dajia12/muqiwen.txt）。
首先我得告诉你我不是“千人人才计划”引进人才，也不是任何
国内所谓“人才计划”引进人才，我只是“回家”或者“回国”看看， 因为医
学院毕业后我曾经在该医院工作过8年再读博再出国。医院没有给我分文。 至今
尚未确定是在国内发展还是呆在美国，而且乔治博士正在给我的新offer （见下
文）， 我现在就在... 阅读全帖 |
|
m*****t
发帖数: 3477 | 20 是的，军工的还是挺难渗透的。
商业公司应该不难才对。我奇怪像intel, amd, freescale,ti这种老中扎堆的地方，咋
就没人能弄出点核心技术，一个cpu国产还搞不定，先不说工艺。
analog, mixed signal的，国内技术力量已经很强了。
下午海豚说的示波器，偶觉得瓶颈不应该在adc片子吧。这玩意无外乎，高速pipeline,
高精sigmadelta。然后几个通道interleave一下，要是不计较功耗，直接flash最快。
我认为system engineering应该是难点。 |
|
y*h
发帖数: 25423 | 21 示波器，system engineering当然是难点，做好比ADC还难，因为能买到美帝
最快民用ADC的日本也造不出像样的高端示波器。但是ADC对tg来讲是最大的客观
限制，要象你想的那么简单“这玩意无外乎，高速pipeline,: 高精sigmadelta。
然后几个通道interleave一下”tg就能做出来的话，美帝就不用禁运了，tg也就
不用通过“特殊渠道”走私了，公开的理论都不难，难的是把一个真的东西做
出来。你如果有朋友在国内的电子行业，你可以问问他你在美国Analog Devices
等半导体公司的网站随便能免费要样品的高取样率高转换bit的ADC芯片有多少
他在国内的代理那里是买不到的。好像500MSPS、12bit的就已经在禁运之列了。
你用多篇顺序采样是可以做到比单片ADC更高的取样率，但是在精度可接受的
范围是有限度的，不然美帝的禁运也就没用了。根本没有办法用100MSPS
的芯片做个能用的40GSPS的示波器出来。
我为什么说示波器呢，因为在军民两用的设备里面示波器是电子行业最高端的
产品了，它能体现出一个国家的电子工业的水平。日本做示波器就比美国差远了，
所... 阅读全帖 |
|
g****t
发帖数: 31659 | 22 国内是工程组织问题，倒不一定是技术最难。
这几天EE不是大家在讨论，为什么我国生产不出来激光打印机？
我觉得，很重要的原因是需要慢工细磨的东西国内人往往看不上眼去做。
是的，军工的还是挺难渗透的。
商业公司应该不难才对。我奇怪像intel, amd, freescale,ti这种老中扎堆的地方，咋
就没人能弄出点核心技术，一个cpu国产还搞不定，先不说工艺。
analog, mixed signal的，国内技术力量已经很强了。
下午海豚说的示波器，偶觉得瓶颈不应该在adc片子吧。这玩意无外乎，高速pipeline,
高精sigmadelta。然后几个通道interleave一下，要是不计较功耗，直接flash最快。
我认为system engineering应该是难点。 |
|
H****y
发帖数: 2992 | 23 多谢大家鼓励！终于写完了。希望共同探讨。
On Scientific Writing
“The ancient historians gave us delightful fiction in the form of fact; the
modern novelist presents us with dull facts under the guise of fiction.” (
Oscar Wilde)
1. Adopt the Right Attitude
Just like everything else, before we start, we have to believe what we do
matters. If we can’t persuade ourselves, how are we going to persuade
others? Writing scientific essays should not be considered as an obligation,
or a pain we go through t... 阅读全帖 |
|
a****1
发帖数: 175 | 24 【 以下文字转载自 Returnee 讨论区 】
发信人: mingfm (carol), 信区: Returnee
标 题: 关于所谓“放弃45万美元年薪，留美博士南充“安家”的回复
发信站: BBS 未名空间站 (Tue Feb 15 17:03:06 2011, 美东)
◇◇新语丝(www.xys.org)(xys5.dxiong.com)(www.xinyusi.info)(xys2.dropin.org)
◇◇
关于所谓“放弃45万美元年薪，留美博士南充“安家”的回复
作者：母其文
亲爱的Fred，
谢谢你的兴趣与留意
（http://xinyusi.s3.amazonaws.com/xys/ebooks/others/science/dajia12/muqiwen.txt）。
首先我得告诉你我不是“千人人才计划”引进人才，也不是任何
国内所谓“人才计划”引进人才，我只是“回家”或者“回国”看看， 因为医
学院毕业后我曾经在该医院工作过8年再读博再出国。医院没有给我分文。 至今
尚未确定是在国内发展还是呆在美国，而且乔治博士正在给我的新offer （见下
文）， 我现在就在... 阅读全帖 |
|
g*******y
发帖数: 1930 | 25 In fact, element[i][j] is a boolean, indicating whether string[1...i+j] is an interleaving of A[1...i] and B[1...j] |
|
C**********n
发帖数: 100 | 26 那也就是说，
不用看什么从[0][0]到[M][N]有什么路径，而是直接看[M][N]=1就可以了把？
an interleaving of A[1...i] and B[1...j] |
|
c*****z
发帖数: 182 | 27 interweaved or interleaved?
Didn't hear of interweaved before |
|
r**u
发帖数: 1567 | 28 Design an algorithm to find whether a given string s3 is formed by the
interleaving of two given strings s1, s2 or not.
如果用3个pointer扫这3个string，当*s1 == *s2，我怎么觉得要判断很多情况？谁给
个clean的code，谢谢 |
|
v*****t
发帖数: 127 | 29 complexity
O(s3.size^2)
or
O(s1.size*s2.size*s3.size) if s1 and s2 are very short and you allow s1 and
s2 to be repeative in the interleaving |
|
r**u
发帖数: 1567 | 30 interleaving不能改变原来序列中char的顺序吧。
s3 can be:aaab aaba abaa but not baaa |
|
m*****f
发帖数: 1243 | 31 interleaving原来是这个意思, 抱歉 英文不行.
then if *s1 == *s2, recursive on left strings and 回溯解决就可以了吧 |
|
l***i
发帖数: 1309 | 32 This comment is obviously stupid. I don't have any problem with English
interleaving with Chinese. And most time people do this because the English
words make more sense to others. |
|
g*****a
发帖数: 340 | 33
何实现。
不太明白。。。
一个盒子拿一个，可能是两白一黑或者两黑一白，不一样的那个应该是纯色的。然后把
label全部颠倒过来就好
两个上面一定要都有1和2，因为有11和22，剩下一共8个面，把0-9剩下的8个分别填进
去就好
..
这俩有啥不同？我去google什么是interleave..
.g |
|
A********l
发帖数: 184 | 34 2.3 只需要从标着“mix”的盒子中draw一个就可以了。
如果是白的，这个盒子装的全是白旗子。
然后标着“black”的盒子一定是混合的
标着“white”的是黑色的
2.4 应为需要表示11，22，所以两个dice必须必须有1和2。你不可能把1-9的数字标在
一个dice上，所以要表示01--09,两个dice必须都要0。所以
dice A: 0 1 2
dice B: 0 1 2
剩下的6个位置放3--8（9可以用6来代替）
4.2 也许interleave不是很好的描述。这个需要判断c是否由a和b组成，同时a和b都是c
的子序列。
a = [A, B, C], b =[D, E, F]
如果c = [B， A， D，C，E， F]，那么a就不是c的子序列（order变了），所以return
false
如果a和b没有overlap的话，用类似merge sort就可以搞定。如果有overlap，好像比较
麻烦。 |
|
c****l
发帖数: 1280 | 35 4.2 也许interleave不是很好的描述。这个需要判断c是否由a和b组成，同时a和b都是c
的子序列。
a = [A, B, C], b =[D, E, F]
如果c = [B， A， D，C，E， F]，那么a就不是c的子序列（order变了），所以return
false
如果a和b没有overlap的话，用类似merge sort就可以搞定。如果有overlap，好像比较
麻烦。
==> evern there is overlap, we can still use merge to get it, right?
1) sort a, sort b and sort c
2) meger a and b => tempArray
3) check c is the same as tempArray.
correct me if i am wrong. thanks
是c |
|
vn
发帖数: 6191 | 36 maybe i have some misunderstandings about the interleave... correct me if i
m wrong:
e.g, u have p1 for [a b c] and p2 for [a b d] and the combined array is [a b
d a b c], how u decide to move p2 first rather than p1? |
|
A********l
发帖数: 184 | 37 网上扔的简历，一周后recruiter来电话约了电话面试。
hiring manager打来电话，问了简历上的问题，比较简单。然后问了一个简单的题目:
如何找出apache weblog中访问最多的几个url。用linux shell如何实现，用java如何实现。
过几天另一个组的hiring manager也来电话，聊了聊，比较开心。
几天后约了onsite，见了10个人，每次两个人。问题都比较简单。
round 1:
hiring manager 1， 聊天，很开心。
round 2:
一个在akamai干了11年的老年软工
2.1 设计course registration的数据库schema
2.2 Fibonacci递归和非递归实现
2.3 三个盒子，一个装的全是白旗子，一个全是黑棋子，一个是混合，但是所有的
label都是错误的，你可以从盒子中draw几个棋子。如何纠正盒子的label，同时保证
draw的次数最少
2.4 两个dice，如何label，使得他们的可以表示01-31中的所有数字
round 3：
两个老年软工:
3.1 聊天
3.2 程序找错，一个计算两个集... 阅读全帖 |
|
s******n
发帖数: 21 | 38 两个字符串 "ABC" "XYZ", 请问如何生成 all possible interleaved combinations
include all character from both sets but still keep the order from their
original forms
sample output:
"AXBCYZ"
"ABXYCZ"
要求打印出所有可能 这题怎么做? 谢谢! |
|
w***o
发帖数: 109 | 39 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
，我还真以为自己找到一个好的算法了。 |
|
i**********e
发帖数: 1145 | 40 small judge 过了而没过 large 肯定是漏了某些状况没测好。
如果你还有当时那个代码，请问可以发一份给我吗？
这样我可以针对更全面的测试来设计 small case 。
interleaving
case |
|
w***o
发帖数: 109 | 41 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
，我还真以为自己找到一个好的算法了。 |
|
i**********e
发帖数: 1145 | 42 small judge 过了而没过 large 肯定是漏了某些状况没测好。
如果你还有当时那个代码，请问可以发一份给我吗？
这样我可以针对更全面的测试来设计 small case 。
interleaving
case |
|
c********t
发帖数: 5706 | 43 这么好的帖子，怎么沉了两年，幸亏有考古者挖了出来。
interleaving
case |
|
g*********e
发帖数: 14401 | 44 my solution.
sort the start & end O(nlogn)
then
O(n) time to get the length.
do a traversal,
use a variable (t) to store level of interleaving at the current position.
once encounter a start, t++,
once encounter an end, t--,
add the accumulated length at each step as long as t>0 |
|
|
b******g
发帖数: 1721 | 46 我觉得就是把ABCD变成数字，然后排序。
1. scan array once to find minimum number, min
2. for each character c1, c1 -'A' - min
3. quick sort
O(nlogn) |
|
|
d*******d
发帖数: 2050 | 48 have fun
void swap_cs(char *a, int i, int j, int n){
for(int k = 0; k
char temp = a[i+k];
a[i+k]=a[j+k];
a[j+k] = temp;
}
return;
}
void switch_string_back(char *a, int i, int j){
if( j-i <=1)
return;
int mid = (i+j)/2;
switch_string_back(a, i, mid);
switch_string_back(a, mid+1, j);
int first_half_mid = (i+mid)/2;
int first_half_n = mid-i+1;
if( first_half_n & 1){
swap_cs(a, first_half_mid+1, j- first_half_n/2 + 1, first_half_n/2);
}else{
sw... 阅读全帖 |
|
r*******g
发帖数: 1335 | 49 难道不是一样采用分枝法？
原题的解答是
A B C D E 1 2 3 4 5 => A B C 1 2 3 D E 4 5 => ....
就是说先交换在分治
你现在这个题的解答是
A 1 B 2 C 3 D 4 E 5 => A B C 1 2 3 D E 4 5 => 。。。。
先分治再交换。
O(n)的算法就算了，nlogn挺好的了。 |
|
|
