h******3 发帖数: 351 | 1 按奈住沉痛的心情, 写下面经. 准备的时间不短, 前后两个星期, 但是表现差强人意.
应该没啥希望.
1. why Amazon?
2. difference between Abstract class and interface?
my answer:
relationship between subclasses of abstract class are related because they
inherit from abstract class
interface is polymorphism, so the implementation classes are unrelated.
3. print out all prime number between one start number and one end number?
How to improve performance? How to test them?
my answer:
public static void printPrime(int startnum, int endnum)
{
for |
p******r 发帖数: 2999 | 2 2. basic concept problem
3. performance->time complexity, yours is O(mn)
test->test case
.
【在 h******3 的大作中提到】 : 按奈住沉痛的心情, 写下面经. 准备的时间不短, 前后两个星期, 但是表现差强人意. : 应该没啥希望. : 1. why Amazon? : 2. difference between Abstract class and interface? : my answer: : relationship between subclasses of abstract class are related because they : inherit from abstract class : interface is polymorphism, so the implementation classes are unrelated. : 3. print out all prime number between one start number and one end number? : How to improve performance? How to test them?
|
h******3 发帖数: 351 | 3 time complexity是说了的, 我能想到的是从data structure上进行优化, 比如用hash
table, hash map, linked list. 当时感觉很messy. 似乎希望我从小数据到大数据的
角度来考虑这个问题.厂
test 当时说了要产生pure random 数据进行测试, 但是似乎
他期望 - 如何测试证明我的verfiyPrime的正确性.我只能说从prime的properties角度
来考虑, 但是具体的prime property 说不上来.
【在 p******r 的大作中提到】 : 2. basic concept problem : 3. performance->time complexity, yours is O(mn) : test->test case : : .
|
p******r 发帖数: 2999 | 4 prime的算法不需要数据结构
public static void prime(int a, int b) {
if (b < 1 || a > b) return;
boolean[] p = new boolean[b + 1];
for (int i = 2; i <= b; i ++) {
if (p[i]) continue;
int j = i + i;
while (j <= b) {
p[j] = true;
j += i;
}
}
for (int i = a; i <= b; i ++) {
if (!p[i]) System.out.print(i + " ");
}
}
test case就是检验你的算法的对错
例如prime(-100, -2), prime(1, 1), prime(2, 20)
这些你都知道结果,你的算法应该输出你想要的东西
第一次面试我也弄得很糟糕(事后发现算法有问题),但是还是拿到了第二次面试
good luck
hash
【在 h******3 的大作中提到】 : time complexity是说了的, 我能想到的是从data structure上进行优化, 比如用hash : table, hash map, linked list. 当时感觉很messy. 似乎希望我从小数据到大数据的 : 角度来考虑这个问题.厂 : test 当时说了要产生pure random 数据进行测试, 但是似乎 : 他期望 - 如何测试证明我的verfiyPrime的正确性.我只能说从prime的properties角度 : 来考虑, 但是具体的prime property 说不上来.
|
z*****9 发帖数: 86 | 5 第二个问题,只是基本的Java概念:
Abstract Class里面可以有未实现的方法,这样的方法必须以abstract关键字声明,也
可以有已经实现的方法(也就是说有花括号括起来的method body)。
Concrete Class里面所有的方法都必须是实现了的。一般用的就是这种类。
Interface里面所有的方法都是未实现,因此Interface就是一组method signature的集
合,是一个protocol,implements这个接口的类必须为这个接口内部的所有方法提供具
体的实现。
如有不足之处,请参考Java的有关文档。
.
【在 h******3 的大作中提到】 : 按奈住沉痛的心情, 写下面经. 准备的时间不短, 前后两个星期, 但是表现差强人意. : 应该没啥希望. : 1. why Amazon? : 2. difference between Abstract class and interface? : my answer: : relationship between subclasses of abstract class are related because they : inherit from abstract class : interface is polymorphism, so the implementation classes are unrelated. : 3. print out all prime number between one start number and one end number? : How to improve performance? How to test them?
|
g**e 发帖数: 6127 | 6 one more thing, you can have any variables in abstract class. but only
static final in an interface.
【在 z*****9 的大作中提到】 : 第二个问题,只是基本的Java概念: : Abstract Class里面可以有未实现的方法,这样的方法必须以abstract关键字声明,也 : 可以有已经实现的方法(也就是说有花括号括起来的method body)。 : Concrete Class里面所有的方法都必须是实现了的。一般用的就是这种类。 : Interface里面所有的方法都是未实现,因此Interface就是一组method signature的集 : 合,是一个protocol,implements这个接口的类必须为这个接口内部的所有方法提供具 : 体的实现。 : 如有不足之处,请参考Java的有关文档。 : : .
|
t**r 发帖数: 512 | 7
it is better to use i<=sqrt(b) here
【在 p******r 的大作中提到】 : prime的算法不需要数据结构 : public static void prime(int a, int b) { : if (b < 1 || a > b) return; : boolean[] p = new boolean[b + 1]; : for (int i = 2; i <= b; i ++) { : if (p[i]) continue; : int j = i + i; : while (j <= b) { : p[j] = true; : j += i;
|
p******r 发帖数: 2999 | 8 you don't understand the algo at all.
【在 t**r 的大作中提到】 : : it is better to use i<=sqrt(b) here
|
t**r 发帖数: 512 | 9 我的理解是:
用一个boolean数组表示1。。b是否是prime number。
初始都是false.//表明是prime number
i从2开始,i的所有倍数都不是prime,设置为true,直到b
你的循环是2到b做如上动作。。
但实际上2到sqrt(b)作如上动作就可以。。。
有什么问题吗?
【在 p******r 的大作中提到】 : you don't understand the algo at all.
|
l****q 发帖数: 177 | 10 问题是,test case 1-10, 跟sqrt10有关系么? |
|
|
l****q 发帖数: 177 | 11 是不是测2---b/2就可以了?
【在 p******r 的大作中提到】 : prime的算法不需要数据结构 : public static void prime(int a, int b) { : if (b < 1 || a > b) return; : boolean[] p = new boolean[b + 1]; : for (int i = 2; i <= b; i ++) { : if (p[i]) continue; : int j = i + i; : while (j <= b) { : p[j] = true; : j += i;
|
b********h 发帖数: 119 | 12 试试b=16, sqrt(b) = 4, 所以10会被作为prime打印出来。
【在 t**r 的大作中提到】 : 我的理解是: : 用一个boolean数组表示1。。b是否是prime number。 : 初始都是false.//表明是prime number : i从2开始,i的所有倍数都不是prime,设置为true,直到b : 你的循环是2到b做如上动作。。 : 但实际上2到sqrt(b)作如上动作就可以。。。 : 有什么问题吗?
|
f*********5 发帖数: 576 | 13 u begin from 2,why can't u set 2*5 to non-prime number?since 2*5
【在 b********h 的大作中提到】 : 试试b=16, sqrt(b) = 4, 所以10会被作为prime打印出来。
|
b********h 发帖数: 119 | 14 I agree sqrt(b) is enough. This can be proved by contradiction.
【在 f*********5 的大作中提到】 : u begin from 2,why can't u set 2*5 to non-prime number?since 2*5
|
l****q 发帖数: 177 | 15 想了一下,你是对的
当一个nonprime数有因子〉sqrt(n)的时候,至少有一个因子比sqrt(n)小
特来致歉~
【在 t**r 的大作中提到】 : 我的理解是: : 用一个boolean数组表示1。。b是否是prime number。 : 初始都是false.//表明是prime number : i从2开始,i的所有倍数都不是prime,设置为true,直到b : 你的循环是2到b做如上动作。。 : 但实际上2到sqrt(b)作如上动作就可以。。。 : 有什么问题吗?
|