L*****k
发帖数: 327 | 1 看过这道题目，也很感兴趣怎么严格证，而不是枚举。提一个思路，不确定是对的
denote the prob as p(x1,x2,y1,y2), x1+x2=y1+y2=C, x1<=x2
1) p(x1,x2,y1,y2) <= p(x1,x2,0,C)
2) then we prove p(x1,x2,0,C) <= p(1,C-1,0,C) |
|
l*********8
发帖数: 4642 | 2 Look at the new formulas again:
if A[i]>j
S[i][j] = 0;
else if A[i] == j
S[i][j] = 1;
else
S[i][j] = SS[i-1][j-A[j]] // SS[x][y] 代表 sum (S[k][y]} | when
k = 0...k );
SS[i][j] = SS[i-1][j] + S[i][j];
Every time we only use SS[i-1][j]. So SS[i-2][*], SS[i-3][*] ... are not
useful and don't need to be saved.
So we use an array, int SS[m] to do same job. Just denote SS[j] as "up to
now, the count of the combinations that have numbers sum to j".
Similarly, we can reduce S from a matri... 阅读全帖 |
|
c**********e
发帖数: 2007 | 3 •Balanced Partition:
Given a set of n integers, each in the range 0 ... K, partition the integers
into two subsets to minimize |S1 - S2|, where S1 and S2 denote the sums of
the elements in each of the two subsets. |
|
l*********8
发帖数: 4642 | 4 problem:
有一段楼梯有n级台阶,规定每一步只能跨一级或两级或三级,要登上第n级台阶有几种不
同的走法?
solution:
let f(i) denote the number of different methods to climb the stairs.
Then
f(0) = 1
f(1) = 1
f(2) = 2
f(3) = f(0) + f(1) + f(2)
....
f(n) = f(n-3) + f(n-2) + f(n-1)
Is this what you talked about? |
|
s*********5
发帖数: 514 | 5 这个解法漏掉了一个重要的点，就是要记住beginning node, 来查当前的link是否是
circle还是lollipop. 如果只是简单的circle, 就give up. 而且其中遍历过的数字
，要变成负数，这样不用再把这个数当成linked list的head再查一遍。
比如， 2， 1， 4， 3， 6， 5， 8， 7， 8
会有3个circle, 1个lollipop
2<=>1
4<=>3
6<=>5
8<=>7<-8
Phase I needs to find the lollipop entrance
Proof: Let s and c denote the lengths of the stick and the cycle portions of
the lollipop. If the slow pointer in Phase I ends in s + x rounds, then 2(s
+x) = s+x + mc, where m is a positive integer. In other words, s+x = mc. So
in ... 阅读全帖 |
|
C***U
发帖数: 2406 | 6 1 Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
2 Use Longest Common Subsequence on with A and B. DP(O(n^2)时间）
是O(n^2)时间了 比最优的要差一些了
刚才搞错了 |
|
g*****e
发帖数: 282 | 7 给定时间内只完成对O（MN）的优化，没能想出O（M+N）。感觉这题目挺有意思的现在
继续想，欢迎bs，欢迎版友讨论 =)
A new kind of cannon is being tested. The cannon shoots cannonballs in a
fixed direction. Each cannonball flies horizontally until it hits the ground
, and then it rests there. Cannonballs are shot from different heights, so
they hit the ground at different points.
You are given two zero-indexed arrays, A and B, containing M and N integers
respectively. Array A describes the landscape in the direction along which
the cannon is shooting... 阅读全帖 |
|
g****y
发帖数: 240 | 8 如果有这个条件，那就可以参考matrix multiplication的解法。
c[i，j]: denotes the optimal cost of merging array i to array j
then the subproblem structure can be:
c[i,j] = min(c[i,k] + c[k+1,j] + cost of merging array[i:k] and array[k + 1,
j]) for k = i to j - 1
time complexity: O(n^3)
def merge_array(arrays):
assert arrays
n = len(arrays)
if n == 1:
return 0
c = [[sys.maxsize for j in range(n)] for i in range(n)]
for i in range(n):
c[i][i] = 0
for i in range(1, n):
c[i... 阅读全帖 |
|
h**u
发帖数: 35 | 9 Suppose nodes are indexed from 1 to n.
d[i,j] = distance from i to j for 1<=i<=n and 1<=j<=n
d[0,j] = 0 for 0<=j<=n
Then, let C[i, j] denote "minimal cost with one stopping at i and another
stopping at j".
C[i,j] = {
C[i,j-1] + d[j-1,j] (if i < j-1)
min {C[k,i] + d[k,j]} for 0 <= k < i (if i = j-1)
}
Base: C[0,1]=0
Output min{C[k,n]} for 0 <= k <= n |
|
c**y
发帖数: 172 | 10 I come up with some questions when considering the following problem. A
related discussion is found here
http://stackoverflow.com/questions/1017821/find-whether-a-tree- but I didn't find the answer to my particular questions.
Problem: given two binary trees T1 (large) and T2 (small), how do we check
whether or not T2 is a subtree of T1? Brutal force solution is out of scope
of this post. Another solution is as follows. A general idea is to serialize
T1 and T2 into two arrays A(T1) and A(T2) firs... 阅读全帖 |
|
x***y
发帖数: 633 | 11 来自主题: JobHunting版 - G 家面经 Just write to mark for personal reference purpose
>>>>>>>>>>
一个 m x n 二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角
(m-1, 0)出发，终点是 右上角(0, n-1), 在每个点只能向右或者向上走，
现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到
的钱的和的最大值
>>>>>>>>>>
(1) Find one single optimal path P which contains m+n point
(2) For each point (i,j), (k,h) in P, denoting P((i,j)->(k,h)) as the path
connecting 2 points in P, there is one property
* For all the possible paths between (i,j) and (k,h), the P((i,j)->(k,h)) is
op... 阅读全帖 |
|
x***y
发帖数: 633 | 12 来自主题: JobHunting版 - G 家面经 Just write to mark for personal reference purpose
>>>>>>>>>>
一个 m x n 二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角
(m-1, 0)出发，终点是 右上角(0, n-1), 在每个点只能向右或者向上走，
现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到
的钱的和的最大值
>>>>>>>>>>
(1) Find one single optimal path P which contains m+n point
(2) For each point (i,j), (k,h) in P, denoting P((i,j)->(k,h)) as the path
connecting 2 points in P, there is one property
* For all the possible paths between (i,j) and (k,h), the P((i,j)->(k,h)) is
op... 阅读全帖 |
|
r*********n
发帖数: 4553 | 13 idea:
first use rand5() to generate a binary random function with p = 1/7 as
follows
express 1/7 in base 5
e.g. 0.abc......
(Note if x can be expressed in base 5 with finite digits, after the last
digit, we assume an infinite number of 0s are padded)
check first digit a:
if rand5() < a return 1
else if rand5() > a return 0
else proceed to the next digit
similarly generate binary random functions with p=1/6, 1/5, ..... 1/2
denote these binary random functions as rand(), N = 2,3,...,7
if rand<7... 阅读全帖 |
|
d*****n
发帖数: 44 | 14 来自主题: JobHunting版 - 问道数学题 Every person is Bernoulli distribution with various success probabilities.
Denote the i-th person has success probability Pi. And I assume we do not
count the last repeated b-day.
1st: P1 = 1
2nd: P2 = p(1st and 2nd have different b-days) = 1*(364/365)
3rd: P3 = p(1st, 2nd, and 3rd have different b-days) = p(3rd person
different b-day|1st and 2nd people different b-days)*p(1st and 2nd people
different b-days) = (363/365) *[1*(364/365)]
4th: P4 = p(4th person different b-day|1st, 2nd, and 3rd peo... 阅读全帖 |
|
c**y
发帖数: 172 | 15 第3题想到直观的解法是：每一个组合等价一个数组w，里面有m个元素。其中w[i]（i=0
,1,...m-1)是在集合i中相应元素的索引index。这样只要对于每个集合i，把其中所有
元素都输出一次，就输出了所有结果。下面是pseudo code。
let denote the original m sets by vector > sets.
vector getCombination(vector > &sets, int set_idx, vector
curr_comb)
{
for (int i = 0; i < sets[set_idx].size(); i++) {
vector ret_comb;
ret_comb = curr_comb;
ret_comb.push_back(sets[set_idx][j]);
if (set_idx == 0) {
// process the fi... 阅读全帖 |
|
r*********n
发帖数: 4553 | 16 you know the center and the orientation (assuming card is rectangle) for
each card
to test whether a point falls onto a particular card is equivalent to test
whether a 2D point is within a rectangle.
one way to do this is to write down the line equations for all sides in the
form f(X,Y) = aX + bY + c = 0... and check
f_1(x, y)*f_2(x, y) <= 0 && f_3(x, y)*f_4(x, y) <= 0
here f_1 and f_2 denote the line equations of parallel sides and similarly f
_3, f_4. f_1(x, y)*f_2(x, y) <= 0 means point (x,y... 阅读全帖 |
|
r*********n
发帖数: 4553 | 17 最后那个问题是martingale stopping time的升级版
如果p不等于0.5，不是martingale，但是可以算出均值(2p-1)n
Let X_n = S_n + (2p-1)n, where S_n is a martingale, E(S_n) = 0，n is # steps
Let Z_n = exp{sigma*S_n}*(2/(exp{sigma}+exp{-sigma})), which is a martingale
, E(Z_n) = 0, and sigma is a design parameter. Then you can express Z_n in
terms of X_n.
A martingale stopped at stopping time is still a martingale
E(Z_{min{n,tau}}) = 0, where tau denotes stopping time
Now you can choose X_n = 1 and X_n = -infinity as the stopping crite... 阅读全帖 |
|
d*k
发帖数: 207 | 18 It can be solved by the 'classic' method.
There are three kinds of point:
1. The start points of an interval
2. The end points of an interval
3. The points in second array.
Put them into one array and sort it by increasing position. One detail: for
points with same position, use the order: type1 < type3 < type2
Iterate the sorted array and maintain on status: number of opening intervals
so far. Let's denote it as N.
Initially, N = 0.
For each point, if it's type1, let N = N + 1. If it's type2, L... 阅读全帖 |
|
s*****b
发帖数: 8 | 19 我来贴一个。
Rocket fule (Software Engineer - Machine Learning Scientist ) 技术电面后code
test. code通过了所有test cases. 人家看过code 后就拒了。问题在哪里呢？请各位
牛人不吝赐教。题目本版以前贴过
You are standing in a rectangular room and are about to fire a laser toward
the east wall. Inside the room a certain number of prisms have been placed.
They will alter the direction of the laser beam if it hits them. There
are north-facing, east-facing, west-facing, and south-facing prisms. If the
laser beam strikes an east-facing prism, its cours... 阅读全帖 |
|
r****r
发帖数: 159 | 20 ReplacementGrammar
Problem:
You will receive a message that must be translated by several string
replacement rules. However, the exact replacement rules are not fixed - they
will be provided as part of the input. You are to write a program that
receives a list of string replacements rules followed by a message, and
outputs the translated message.
Details:
0) A 'newline' consists of a carriage feed 'r' followed by a line feed 'n'.
1) The input will begin with any number of 'string replacement rul... 阅读全帖 |
|
g********t
发帖数: 39 | 21 贡献刚做的online test，职位是Machine Learning related。
Question 1 / 2 (LaserMaze)
You are standing in a rectangular room and are about to fire a laser toward
the east wall. Inside the room a certain number of prisms have been placed.
They will alter the direction of the laser beam if it hits them. There
are north-facing, east-facing, west-facing, and south-facing prisms. If the
laser beam strikes an east-facing prism, its course will be altered to be
East, regardless of what direction it had been goi... 阅读全帖 |
|
M****g
发帖数: 162 | 22 Question 1 / 2 (LaserMaze)
You are standing in a rectangular room and are about to fire a laser toward
the east wall. Inside the room a certain number of prisms have been placed.
They will alter the direction of the laser beam if it hits them. There
are north-facing, east-facing, west-facing, and south-facing prisms. If the
laser beam strikes an east-facing prism, its course will be altered to be
East, regardless of what direction it had been going in before. If it hits
a south-facing prism... 阅读全帖 |
|
x***y
发帖数: 633 | 23 3 is interesting: use color to denote parity. |
|
w*****d
发帖数: 105 | 24 Assume there are no obstacles (Unique Path I), then the total path number is
Let P(x, y) denotes the number of unique paths through (x, y) to reach the
end, then:
P(x, y) = Paths from (0, 0) to (x, y) times paths from (x, y) to (m, n) = C(
x+y, x) * C((m-x)+(n-y), m-x).
So the probability that the robot walks through position (x, y) is P(x, y)/T.
Hope there is no misunderstanding. |
|
h****j
发帖数: 15 | 25 Here are my 5 cents.
It will be easier to understand if we denote the position explicitly in the
iteration.
Let g_k[x] be the longest continuous `x` ending at position k, (exactly, not
at most) one change has been made.
Let f_k[x] represent the longest continous `x` ending at position k, no
change has been made.
Then we have the following iterative equations.
Update changed
g_{k+1} [x] = g_k [x] + 1
g_{k+1} [1-x] = f_k [1-x] + 1
Update unchanged
f_{k+1} [x] = f_k[x] + 1
f_{k+1} [... 阅读全帖 |
|
a****n
发帖数: 26 | 26 Given a company structure where every employee reports to a superior, all
the way up to the CEO,
how would you print out all the employees that a particular individual
oversees?
Write a method that implements this, given the below:
//Employee object contains a string denoting the employee name, and an //
array containing employees who report to this employee
Employee {
String name;
Array employees;
}
求思路，感觉不应该是binary tree. |
|
b********a
发帖数: 70 | 27 you are given a server log file containing billions of lines. Each line
contains a number of fields. For this problem the relevant field is a string
denoting the page that was accessed.
Write a function to read a log file line with O(1) time complexity, and a
function to find the k most visited pages with O(k) time complexity.
想不出来怎么可以用这么少的时间做到
呼唤大牛 |
|
w*******u
发帖数: 267 | 28 如果毛毛虫数量多于3，这个求交集的运算也变得很麻烦。到底用inclusion-exclusion
principle解是最好的吗？
There are a large number of leaves eaten by caterpillars. There are 'K"'
caterpillars which jump onto the leaves in a pre-determined sequence. All
caterpillars start at position 0 and jump onto the leaves at positions 1,2,3
...,N. Note that there is no leaf at position 0.
Each caterpillar has an associated 'jump-number'. Let the jump-number of the
i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating
leaves in t... 阅读全帖 |
|
M******1
发帖数: 90 | 29 import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class UberTest {
List data = new ArrayList<>();
public void fillData(){
//Use integer to denote Time here.. you can change it to DateTime
type.
data.add(new TimedKvPair(new KvPair("name1","Bnn"), 1) );
data.add(new TimedKvPair(new KvPair("name2","Dee"), 2) );
data.add(new Time... 阅读全帖 |
|
发帖数: 1 | 30 题目如下，可以直接google "hackrank stock maximize",测试自己代码是否正确：
https://www.hackerrank.com/challenges/stockmax
Your algorithms have become so good at predicting the market that you now
know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for
the next N days.
Each day, you can either buy one share of WOT, sell any number of shares of
WOT that you own, or not make any transaction at all. What is the maximum
profit you can obtain with an optimum trading strategy?
Input
The first line con... 阅读全帖 |
|
发帖数: 1 | 31 Given n items with size nums[i] which an integer array and all positive
numbers, no duplicates. An integer target denotes the size of a backpack.
Find the number of possible fill the backpack.
Each item may be chosen unlimited number of times
Example
Given candidate items [2,3,6,7] and target 7,
A solution set is:
[7]
[2, 2, 3]
return 2
class Solution {
public:
int backPackIV(vector& nums, int target) {
vector f(target + 1);
f[0] = 1;
// for (auto num : nums... 阅读全帖 |
|
l*********r
发帖数: 13 | 32 在学校找了个Volunteer， 以前在版上看到过有人讨论这两个title的不同，有人倾向
于Unpaid Internship， 说对将来申请绿卡有帮助； OIS的adviser说都可以，但学校
的professor说Reseach Assistant比Internship好，说后者是对学生的training,前者
是usually denotes enough experience to satisfy an employment position。 到底
我该用那个呢？请有经验的人指教！ |
|
T*****r
发帖数: 207 | 33 It is very complicated to explain.....but it basically means that the
deed, which denotes ownership or who owns the property, has not been
recorded at the Franklin County Auditors office. Once a house changes
hands, the transaction has to be legally recorded at the Franklin Cnty
Auditors department. Then it becomes part of the legal ownership of the
property.
This property, the deed has not been recorded at the auditors dept. yet.
Since there are so many of these foreclosed properties, it has |
|
b*******7
发帖数: 907 | 34 official property description有一项评价，CDU为average，周围绝大多数都是good
，这大概是个什么情况？见过内部比这个还要陈旧的评价都还是good，不知道这个是不
是意味着什么隐含的问题？
CDU:
(Condition – Desirability – Utility) Codes denoting the composite rating
of the overall condition, desirability and usefulness of a property. The
codes used are: Excellent, Very Good, Good, Average, Fair and Poor. |
|
s*3
发帖数: 352 | 35 从relocation company手里买房（seller讲好价后交给relo 公司了）
合同上写的是Inspection发现要修的事项大于300刀可以提交维修请求，他们会在7天答
复修还是不修，还是给credit
还指望查出点毛病要credit呢； 结果inspector去验房时一个劲的说这个房子真好啊，
保养的真不错啊，加了不少upgrade，crawl space是最近看到最好的，之类的话 （
Inspector是realtor推荐的是不是都这样啊；没办法review好的都不能马上约到，只有
这个关系户第二天就能约到
）
废话不说；看报告（大家给看看要修的话大概的花销）
1. Fence: Wood
At right side against the house the fence post is very loose. Fence needs
general maintenance- cleaning, sealing, etc.
Post needs repair for safety. Consult contractor for repair.
2. C... 阅读全帖 |
|
f******I
发帖数: 769 | 36
i could never remember the serologic markers for hep b, but if your hep b
surface ag is positive, it often denotes that you have hep b infection, this
hep b surface ag normally goes away in 6-8 months, but if your hep b
surface ag remained positive after this period, that means you have chronic
infection,
you could have slightly high LFTs from metabolic syndrome from being
overweight, but that does not explain HBsAg being positive though, |
|
c********e
发帖数: 496 | 37 you may simply check the temperature, approximately 1 degree elevation
denoting ovulation (mechanism underlying is increase of progesterone).
The ovary cyst is a little big. Theoretically, pregnancy is still possible
with single ovary.
Try pregnancy and get it removed, it is a time bomb or at least follow up
with ultrasonic. |
|
c**i
发帖数: 6973 | 38 My comment:
(a) John 5: 5-13 (King James version)
http://www.biblegateway.com/passage/?search=John+5&version=KJV
(b)
(i) paraplegia (n; from Greek paraplēgiē para-, beyond + -plēgia,
paralysis from Greek plēssein to strike): "paralysis of the lower half of
the body with involvement of both legs"
(ii) paraplegic (n; adj): noun to denote a person of paraplegia while adj,
the condition.
Both definitions are from www.m-w.com.
(c) Based at Berkeley, Calif, Berkeley Bionics were founded in 2005 by... 阅读全帖 |
|
b******n
发帖数: 4559 | 39 从fatwallet上看来的：
“ posted: Aug. 18, 2009 @ 8:32p [link to this post]
Chase Freedom "Exclusive" does NOT automatically = $50 bonus for $200. The
term exclusive denotes if the CC is getting a specific benefit because of
having a Chase checking account.
The CCs are as follows:
Chase Freedom (OLD) (NO CHK ACCT) = 3% in TOP 3 categories and has the $50
bonus for getting to $200.
Chase Freedom Exclusive (OLD) (MUST HAVE CHK ACCT) = 3% in TOP 5 categories
and has the $50 bonus for getting to $200.
Chase |
|
g******u
发帖数: 827 | 40 There is unique on my method. If you find it ok, pai bao zi. If you find not
OK, there is no charge for that. I am new here, no much baozi to denote. If
I have, I will do. Thx. |
|
l*****1
发帖数: 540 | 41 I guess 500 denotes the threshold, maybe not the specific item (gc, in this
case). |
|
w****r
发帖数: 15252 | 42 我都是直接丢到那种超市门口的denote箱子里面的，早知道捐了抵税
也没多少，算了，不折腾 |
|
d********f
发帖数: 8289 | 43 为啥我看不到呢？
Share Draft Checking ( Dividend Rate: 0.000%, APY§: 0.000% ) ?
Other Product Interest(s)
Please let us know if you would like to receive information for other
products and services:
Credit Card
Credit Cards ?
FPS
Financial Planning Services ( Dividend Rate: , APY§: )
Home Loans
Mortgage / Equity Loans ?
Loans
Auto Loan ?
InstaCash-Line of Credit ?
Signature/Personal Loan ?
§APY denotes Annual Percentage Yield |
|
b******e
发帖数: 5547 | 44 上月账单被charge $100
denotes Pay Over Time activity
懒得找客服了，等报销了今年PRG 的100就销卡 |
|
az
发帖数: 16686 | 45 是那个再回来做妈妈的女儿那个吗？太伤心了，难受死了，到底为什么啊，6个月还能
SIDS啊？不是说月子才能那个的吗？6个月能自己翻身的吧，为什么啊，太可怕了。
SIDS in the general population. As it is defined by epidemiologists, risk
refers to the probability that an outcome will occur given the presence of a
particular factor or set of factors. Scientifically identified associations
between risk factors (eg, socioeconomic characteristics, behaviors, or
environmental exposures) and outcomes such as SIDS do not necessarily denote
causality. Furthermore, the best current work |
|
r*f
发帖数: 39119 | 46 co-ask, any link?
a
associations
denote |
|
I********y
发帖数: 63 | 47 她没说为什么。是在family care。。。的。
a
associations
denote |
|
c********y
发帖数: 743 | 48 天呢，我这两天刚看是让娃趴着睡，因为这样不吐奶，不会被漾奶搞行，否则我成晚上
都要给她拍咯。
SIDS in the general population. As it is defined by epidemiologists, risk
refers to the probability that an outcome will occur given the presence of a
particular factor or set of factors. Scientifically identified associations
between risk factors (eg, socioeconomic characteristics, behaviors, or
environmental exposures) and outcomes such as SIDS do not necessarily denote
causality. Furthermore, the best current working mode: l of SIDS suggests
tha |
|
T*********k
发帖数: 1767 | 49 so sad..bless to the mother who lost her baby
SIDS in the general population. As it is defined by epidemiologists, risk
refers to the probability that an outcome will occur given the presence of a
particular factor or set of factors. Scientifically identified associations
between risk factors (eg, socioeconomic characteristics, behaviors, or
environmental exposures) and outcomes such as SIDS do not necessarily denote
causality. Furthermore, the best current working mode: l of SIDS suggests
that |
|
x**s
发帖数: 1085 | 50 看过有些报道说，其实很多SIDs都是care giver虐待至死的，为了不承担法律责任而都
归结到SIDS上。
那个妈妈应该建议另找医生检查，尤其是脑子，看看有没有shaken baby syndrome。
SIDS in the general population. As it is defined by epidemiologists, risk
refers to the probability that an outcome will occur given the presence of a
particular factor or set of factors. Scientifically identified associations
between risk factors (eg, socioeconomic characteristics, behaviors, or
environmental exposures) and outcomes such as SIDS do not necessarily denote
causality. Furthermo |
|
