l****q
发帖数: 177 | 1 想了一下，你是对的
当一个nonprime数有因子〉sqrt(n)的时候，至少有一个因子比sqrt(n)小
特来致歉~ |
|
p******r
发帖数: 2999 | 2 看了一下log和sqrt的源代码
log以浮点数乘法为主，没有循环
sqrt以整数位运算为主，有循环
算法很多，得考虑复杂度、精度和可移植性
在没有硬件代码的支持下，个人觉得log要快些 |
|
r******d
发帖数: 308 | 3 我写下我的思路， 看看行不行
题目就是要随机产生M个坐标为(x.y.z)的球
坐标原点为圆柱体下表面的圆心。
满足：
(1)球在圆柱里面：
高度方向约束：
0
0
半径方向约束是小球到圆柱轴线的距离比R-r小， 即：
sqrt(x*x+y*y) < R-r
(2)小球互相不相交,
对于任意两个小球， 两小球之间的距离大于(r1+r2):
sqrt( (x1-x2)^2+(y1-y2)^2 ) ) < r1-r2
那我能够想到的方法就是call c 的random(range) , 产生随即的数(x, y, z)， 如果
不满足以上的条件, 就继续产生新的随机数。。。。
不过如果新产生的随机数总是不在满足的范围那个loop 就长了， 应该可以继续优化 |
|
h******3
发帖数: 351 | 4 sorry, I can't input Chinese now.
I remember reading the idea of "验证K是不是质数的时候只要看是否能被比sqrt(K)
小的质数整除就行了" somewhere. what is the name of the theory? In order to
know all the primes that are less than sqrt(k) when k is 10^7, we might need
temporary storage, such as array.
sieve |
|
P********l
发帖数: 452 | 5 public void test() {
int num = 2147483646;
// num = 100;
num = 2147395601;
Set hs = new HashSet((int) (Math.sqrt(num)) + 100);
for (int i = 0; i < Math.sqrt(num); i++) {
hs.add(i * i);
}
for (Integer i : hs) {
int j = num - i;
if (j < i)
continue;
if (hs.contains(j)) {
System.out.println(i + ", " + j);
}
}
}
21473956... 阅读全帖 |
|
P********l
发帖数: 452 | 6 No. In java, the hashset does not preserve the original input order. There
is another set called linkedhashset has this property.
It is brute force but the complexity is o(sqrt(n)). Because it just scan one
through 1 to sqrt(n).
then |
|
y******5
发帖数: 43 | 7 Thank you.
Some quick thoughts about 6 and 7:
Possible input:
"0"
"+123"
"-123"
"+-123"
"0x123f"
"12.3"
non-number chars
Anything else?
Brute Force with improvements:
1. only consider odd numbers (except 2)
2. for current number, only check to its sqrt
3. for current number, only check prime numbers which are not more than its
sqrt |
|
g***s
发帖数: 3811 | 8 It is very quick even for n = Integer.MAX_VALUE;
public static void main(String arg[]){
preprocess();
int n=Integer.MAX_VALUE;
System.out.println("squares sum of " + n + " : ");
for (int num : getSquaresSum(n)){
System.out.print(" " + num);
}
System.out.println("\ntotal callCount= " + callCount);
}
public static Collection getSquaresSum(int n){
Stack cur = new Stack();
Stack阅读全帖 |
|
c********0
发帖数: 112 | 9 double r = sqrt(rand());
为什么要 sqrt 而不是直接 r = rand()?
不明白。。。 |
|
|
r*******e
发帖数: 7583 | 11 对n因数分解
任何一个小于sqrt(n)的因数，必然有一个对应的大于sqrt(n)的因数
n是平方数的时候，因数个数就不成对了 |
|
r*******y
发帖数: 1081 | 12 f(1,0,0) = 0
f(0,0,1) no output
f(0,1,0) = 0
f(1,0,1) = sqrt(-1) or -sqrt(-1)
f(1,1,0) = 0, -1 |
|
s****j
发帖数: 67 | 13 平面最近点对那题，提供一种方法供参考，该方法看似复杂度o(n^2)，但实际使用中几
乎是o(n)（不算nlgn排序的预处理）。主要是利用了三角形两边之差小于第三边的性质
，大大减枝。另外该方法实现简单，比传统o(nlgn)的实现简单很多也直观很多。
代码如下：
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
const double eps=1e-8;
struct Point
{
double x,y,dis;
} p[maxn];
int n;
bool cmpp(const Point &p1,const Point &p2)
{
return p1.dis
}
void solve()
{
sort(p,p+n,cmpp);
double ans=1e18,now;
int i,j;
for (i=0;i阅读全帖 |
|
y******n
发帖数: 47 | 14 周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.
* given a function on sorted dictionary to retrieve word by index,
string getWord(int i), how to i... 阅读全帖 |
|
z****c
发帖数: 602 | 15 试试写的短点。
double pow(double a, double b)
{
assert(a>0);
double result = 1.0;
if(b==0.0)
reutrn 1.0;
else if(b<0)
return pow(a,-b);
while(b > 0 && a > 0.000000001）
{
if(b>1)
{
result *= a;
b -= 1.0;
}
else if(b*2>1)
{
a = sqrt(a);
result *= a;
b = b*2 -1;
}
else
{
a = sqrt(a);
b *= 2;
}
}
return... 阅读全帖 |
|
S**I
发帖数: 15689 | 16 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
S**I
发帖数: 15689 | 17 ☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 00:18:17 2011, 美东) 提到:
周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.... 阅读全帖 |
|
w****o
发帖数: 2260 | 18 就是说函数原型是 double sqrt(int a)了？
如果要返回整数该怎么办？就是说函数原型为 int sqrt(int a)
好像ihasleetcode大牛在这个版贴过他的代码，找不到了 |
|
i**********e
发帖数: 1145 | 19 F:
3Sum
Add Binary
Combination Sum
Count and Say
Divide Two Integers
Edit Distance
Implement strStr()
Letter Combinations of a Phone Number
Longest Palindromic Substring
Merge Intervals
Multiply Strings
Next Permutation
Permutations, Permutations II
Regular Expression Matching
Remove Duplicates
Remove Element
Search in Rotated Sorted Array
String to Integer (atoi)
Sqrt(x)
Substring with Concatenation of All Words
Trapping Rain Water
Unique Paths, Unique Paths II
G:
3Sum
Climbing Stairs
Container... 阅读全帖 |
|
w****o
发帖数: 2260 | 20 求平方根的题，是用binary search?
还有这个函数的原型是什么？输入是float,还是int,输出呢？
就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
xiexie ! |
|
w****o
发帖数: 2260 | 21 求平方根的题，是用binary search?
还有这个函数的原型是什么？输入是float,还是int,输出呢？
就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
xiexie ! |
|
o******e
发帖数: 81 | 22 可不可以用sqrt？double的power可以拆成整数和小数部分。小数部分类似这样：
// Assume 0 < power <= 1
double Power(double value, double power)
{
const double Threshold = 1E-10;
double result = 1;
for (int p = 1; power > Threshold; value = Math.Sqrt(value), p /= 2)
if (power >= p)
{
power -= p;
result *= value;
}
return result;
} |
|
w****f
发帖数: 684 | 23 Should be stop at num/2, not sqrt(num). right?
eg. num=26 =2*13 while sqrt(num) =5. |
|
k*****n
发帖数: 117 | 24 先走x (x>1)，然后沿切线走到圆上 sqrt(x^2-1)，
假设此时半径和走出来的直线所夹圆心角为 a, (cos(a) = 1/x)
然后沿大圆弧走 2(pi-a) 就可以了
因为已覆盖圆心角为2*a的所有切线，只用走到下面对称的切点
总路程
1/cos(a) + tan(a) + (1-a/pi)*2*pi
0
当 a = pi/6 时上述值最小，为 5/6*sqrt(3) + 5/3*pi ~= 6.68
当然这个优化的是worst case
如果优化均值就更复杂了 |
|
D****3
发帖数: 611 | 25
其实没多个解。
xy=a,x+y=b;
(x-y)^2=x^2+y^2-2xy=(x+y)^2-4xy=b*b-4a;
x-y= (+/-)sqrt(b*b-4a), 咱就说x-y= +/- k吧
注意，这时候看起来有2个解，其实基于x+y=b, 那么x-y=k和x-y=-k (i.e. y-x=k)是一
样的。因为x和y对称。
不信的话我解一下：
x+y=b, x-y=k --> x=(b+k)/2, y=(b-k)/2
x+y=b, y-x=k --> x=(b-k)/2, y=(b+k)/2
这两个式子的解对称，第一个的x就是第二的y。因为这题里求2个重复数。随便取一个
式子就能算出。
也就是说，两个重复数字分别是(b+k)/2,和(b-k)/2。其中k=sqrt(b*b-4a)。
ps1：我计算可能出点小错误，但是大意应该是对的。
ps2：有人说直接算xy，这样会overflow，想想1*2*...*1000多大吧。不如算1*1+2*2+.
..+x*x+...+y*y+...+1000*1000,这样减去1-1000的平方和，算出来x*x+y*y即可根据x+
y推出xy. |
|
f*****e
发帖数: 2992 | 26 用级数或:
x=sqrt(5)
对y=5-x^2用newton。
初始(x0,5-x0^2)，此处的切线是y-(5-x0^2)=(-2x0)(x-x0)，
令y=0得x=(5-x0^2)/(2x0)+x0=(5+x0^2)/(2x0)
所以迭代就是
x(i+1)=(5+x(i)*x(i))/(2x(i))
x(n)->sqrt(5)
if x(0) = 1, x(3)^2=5.0，只要3步就搞定。 |
|
j*****o
发帖数: 394 | 27 好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“ |
|
j*****o
发帖数: 394 | 28 好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“ |
|
i******t
发帖数: 52 | 29 假设x是input， 大于1
我的方法（算指数的2进制表示）：
double x=134.56,bit=0,z=0.5,epsilon=1.0000001,k=sqrt(2),r;
r=x;
// scale r to [1,2]
while (r>2){
r=r/2;
bit+=1;
}
// r is in [1,2]
while(r>epsilon){
if(r/k>1){
bit+=z;
r=r/k;
}
k=sqrt(k);
z=z/2;
} |
|
c********t
发帖数: 5706 | 30 数学白痴是这么想的
如果想
Sum(sqrt((xi-x0)^2+(yi-y0)^2)) 最小
那么就要 Sum(sqrt(abs(xi-x0)+abs(yi-y0)))最小
就要 Sum(abs(xi-x0)+abs(yi-y0))最小
就要Sum(abs(xi-x0))最小 Sum(abs(yi-y0))最小
就是mean(x) mean(y)吧 |
|
t****a
发帖数: 1212 | 31 1. Sum(sqrt((xi-x0)^2+(yi-y0)^2)) 最小
2. 那么就要 Sum(sqrt(abs(xi-x0)+abs(yi-y0)))最小
3. 就要 Sum(abs(xi-x0)+abs(yi-y0))最小
4. 就要Sum(abs(xi-x0))最小 Sum(abs(yi-y0))最小
1->2, 2->3的逻辑我不懂，能给个解释么？ |
|
c********t
发帖数: 5706 | 32 1->2: (a^2 < b^2) => (abs(a) < abs(b))
2->3: 对于正整数 sqrt(a) < sqrt(b) => a |
|
D**********d
发帖数: 849 | 33 想到一个 O(n^3) 的解法：
1. sort on x axis -- O(nlg(n)) x1 <= .... <= xn
2. for each pair (n1,n4) check d(n1,n4) == sqrt(2)L,
if yes, check 2sum problem on x: s.t. x2+x3 = x1 + x4
if yes, check d(n2,n3) == sqrt(2)L,
if yes, output (x1,x2,x3,x4)
n^2 pairs * 2sum = O(n^3)
|
|
j*****y
发帖数: 1071 | 34 求 sqrt的是牛顿迭代吧？
牛顿多项式是拿来插值用的
sqrt |
|
y****n
发帖数: 743 | 35 来自主题: JobHunting版 - 关于尾递归 加一点难度。两个函数相互递归
public static double H(double val, int n)
{
if (n == 0)
return val;
else
{
double left = V(val - 1, n - 1);
double right = V(val + 1, n - 1);
return Math.Sqrt(Math.Abs(left * right));
}
}
public static double V(double val, int n)
{
if (n == 0)
return val;
else
{
double up = H(val * 2, n - 1);
double down = H(val / 2, n - 1);
return Math.Sqrt(Math.Abs(up + down));
}
} |
|
p*****2
发帖数: 21240 | 36 来自主题: JobHunting版 - 关于尾递归
尾递归的实现，不过Scala不支持这种递归的优化。
def H(value:Double, n:Int):Double={
H_helper(Array(value),n)(0)
}
def V(value:Double, n:Int):Double={
V_helper(Array(value),n)(0)
}
def H_helper(arr:Array[Double], n:Int):Array[Double]=n match{
case 0 => caclV(arr)
case _ => {
val ar=new Array[Double](arr.length*2)
for(i<- 0 until arr.length) {
ar(2*i)=arr(i)-1
ar(2*i+1)=arr(i)+1
}
... 阅读全帖 |
|
a*******3
发帖数: 27 | 37 median注意两个问题吧，第一个是相加溢出，这个hackrank上经常这么坑人的
第二个是如何保证较小的代价插入和寻找中间的数吧。我用C++的std::deque，主要是
写代码快，方便。插入近似O(sqrt(n)),随机访问也是O(sqrt(n))
其他语言如果没有的话，二叉树也可以模拟吧，只不过每个节点记录下自己子节点有多
少个数，这样寻找中间那个数就是O(logn)的吧，插入是O(logn) |
|
h**********w
发帖数: 39 | 38 new grad MS，F电面是版上大神refer的，G电面是学长帮忙拿到的
F：3 sum 和 sqrt，sqrt的牛顿迭代解释的不是很清楚，让分析了复杂度。周一面的周
三给的onsite
G：minimum window substring，就是在ACDBVNFFKADBC中找含有ABC的最小子串，三姐
和我死磕了半天非得说我错了，walk through了个例子她才看懂，差点被问跪。第二周
给了onsite
电面题目都是版上面经和leetcode的，各位大神都讨论过的。估计onsite写可能还会出
点啥小错啥的，想推迟一个月到4月底再去，期间练练bug free和白板啥的，看以往的
帖子好像推迟面试这事说法不一，诚心求各位大神赐教。 |
|
w***y
发帖数: 6251 | 39 周一／周三面了两家公司，也不知道有戏没戏。周一面T的时候，hr说快的话周三会有
结果，下午写email去follow up完全没回应，根据以前的经验，基本都是没戏了；但凡
pending/positive， hr都不会这么怠慢的。
今天面的G， 前面的都还好，最后一个烙印，跟我鬼扯一大堆system design问题，不
是design什么大系统，就是围绕找stream data里most frequent char, 不同条件下，
用什么方法去节省cost。瞎扯各种情况，最后连hard disk读取速度是多少G/sec都问，
我直接说我自己没做过这方面也不记得这个，不想乱猜。还不知道他最后的report会怎
么写
我的面经完全没有什么特色，去T都问我的数学题，有个欧洲姐们连reservoir
sampling的证明都要我推一遍。。。。。被问到的coding题目就类似，一个int array
，只保留<10k的数字，其他都ignore，怎么in place做ORZ 真不是是不是叫我去面
swe的
在G遇到的题目，前面都很传统，第一个人让我做graph的isConnected 判断... 阅读全帖 |
|
L*******e
发帖数: 114 | 40 sqrt(n) 不够吧，sqrt(10) = 3 while 10 =2 x5 |
|
g****o
发帖数: 547 | 41 你把所有小于等于sqrt(n)的质数都试了，如果发现还没被除完，那么剩下的必然是个
质数，比如你例子里面的5
如果p[0],p[1],....p[num-1]是所有小于等于sqrt(n)的质数
vector > factor(int n){
vector > ans;
int i==0;
while(n!=1&&i
int temp=0;
while(n%p[i]==0){
temp++;
n/=p[i];
}
if(temp!=0)ans.push_back(make_pair(p[i],temp));//prime and power
i++;
}
if(n!=1)ans.push_back(make_pair(n,1));
return ans;
} |
|
P****i
发帖数: 12972 | 42 F_n = \frac{psi^n-{-psi}^{-n}}{\sqrt{5}}
psi=\frac{1+\sqrt{5}}{2} |
|
z****e
发帖数: 54598 | 43 计算一个数组的mean和variance
由于这是两个normal相加，所以mean和variance都是两个独立的mean和variance的关系
翻统计书，我不太记得了，不过应该是如下关系
mean = (mean1 + mean2)/2
variance = variance1 + variance2 + 2Cov12
从题目看，这个Cov12应该是0
然后就是解二元二次方程组
java写sqrt什么要用Math.sqrt来做 |
|
|
|
x****g
发帖数: 1512 | 46 需要的是“没有common letter”。
无论字典树或者后缀树对于判定找出无common letter并不优。
将原来的s1....sn用26bit法转化成
A1.....An
对应的最大长度为： V1.....Vn
有两个好处：
1：判定无common letter即为：Ai & Aj == 0;
2：相同bit表示的不同字符串得到压缩，只需要记下长度最长的。
完了按Vn长度排序 N*Log(N)
V'n........V'1
A'n........A'1
从大到小搜索，如果Ai & Aj==0的话，L=V[i]*V[j].
那么大的那个下标就收缩到了k,V[k]>sqrt(L).
整体区间收缩到[l,r]满足
V[i]>V[l]
V[r]>V[j]
平均复杂度能N*Log(N)? ,最差当然还是N^2.
i =0;
j = n;
maxLen = 0;
highLen = INT_MAX;
lowLen = INT_MIN;
while(V[i]>sqrt(maxLen) && (i
{
if(V[i] < highL... 阅读全帖 |
|
x*******9
发帖数: 138 | 47 数组长度为N，把整个数组分为K段。这里取 K=sqrt(N)。
一段子数组我们用[st, end]来表示。
我们要统计每段子数组[st...x]的取值。
例如，[1, 2, 3]。sum([1]) = 1, sum([1, 2]) = 3, sum([1, 2, 3]) = 6。 然后排
序累加，使得类似“这一段子数组在和大于3有多少个”的Query的时间复杂度为O(log(
K))。
然后遍历数组，通过预处理好的子数组序列进行计算。
预计时间复杂度为O(n * sqrt(n) * log(n))。
比O(n^2)要好一点。不过比较难写。。。=。= |
|
b*****c
发帖数: 1103 | 48 来自主题: JobHunting版 - f家店面题 這道題要小心，我面過，我當時算法複雜度是大概o(n sqrt(n))
因為 dp(i,j) 要滿足 2*j<= sqrt(9+8i)-1 |
|
b*****c
发帖数: 1103 | 49 来自主题: JobHunting版 - f家店面题 這道題要小心，我面過，我當時算法複雜度是大概o(n sqrt(n))
因為 dp(i,j) 要滿足 2*j<= sqrt(9+8i)-1 |
|
M****w
发帖数: 11 | 50 来自主题: JobHunting版 - f家店面题 Complexity analysis for this problem
Maximum speed m will get if array items are 1s
1+2+...m < n+m // Can jump m-1 step out of array
m(m-1)/2
m < sqrt(2n)
Max distance traved should be n+m-1
Therefore DP matrix [Pos speed] size should be (n+m-1)*m = O(n*sqrt(n)) |
|
