由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G 家电面面经
相关主题
问个amazon面试题。求大数加1题目的细节
一道面试题(integer to binary string)出一道题plusone变种
问一个facebook的电面一道面试题
G家onsite面经求看代码 Plus One
请教一个bloomberg题目leetcode plus one 书上答案是不是错了?
除法有什么规律吗?Uber onsite为什么要带电脑?
google phone interview,直接跪了,以前没做过,做过的应该不难郁闷死了,顺便贴个Amazon电面面经
G家新鲜电面面经,onsite求blessGoogle 的外包,80块钱一小时
相关话题的讨论汇总
话题: int话题: return话题: string话题: ret话题: negative
进入JobHunting版参与讨论
1 (共1页)
j*****y
发帖数: 1071
1
50分钟。
就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
面试官一直让不断的优化。
后面8分钟就闲聊 project 了。
P**********g
发帖数: 30
2
问个菜菜的问题。
电面是开着电话免提,写code...?
j*****y
发帖数: 1071
3
我开着手机免提的。前面是电脑。下巴下面是手机

【在 P**********g 的大作中提到】
: 问个菜菜的问题。
: 电面是开着电话免提,写code...?

P**********g
发帖数: 30
4
就是只有一个大数加法的实现?
lz 你 onsite 肯定没问题啦,cong一个
j*****y
发帖数: 1071
5
多谢,多谢 :)
这个比大数加法应该要容易很多,因为另外一个数只是 1.

【在 P**********g 的大作中提到】
: 就是只有一个大数加法的实现?
: lz 你 onsite 肯定没问题啦,cong一个

M********5
发帖数: 715
6
你运气真好,这个羡慕都羡慕不来。。。
j*****y
发帖数: 1071
7
多谢 :)
现在我发现 做完 leetcode OJ 离 优化code到最好的地步还差的好远。

【在 M********5 的大作中提到】
: 你运气真好,这个羡慕都羡慕不来。。。
c********t
发帖数: 5706
8
我想到的就是in-place 硬做,遇到数组越界,要重新开新空间
还有什么优化吗?

【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。

j*****y
发帖数: 1071
9
中间的时候如果遇到了不进位的话,就 break

【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做,遇到数组越界,要重新开新空间
: 还有什么优化吗?

j*****y
发帖数: 1071
10
你这个in place 是很好的一个优化。

【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做,遇到数组越界,要重新开新空间
: 还有什么优化吗?

相关主题
除法有什么规律吗?求大数加1题目的细节
google phone interview,直接跪了,以前没做过,做过的应该不难出一道题plusone变种
G家新鲜电面面经,onsite求bless一道面试题
进入JobHunting版参与讨论
M********5
发帖数: 715
11
我也是这么想的,中间遇到不进位的时候就break,然后只要给出的数组不是9999这种
的,就不许要另外allocate space,如果是9999的话,那就另外做打算。。。是这样的
思路么?

【在 j*****y 的大作中提到】
: 中间的时候如果遇到了不进位的话,就 break
c********t
发帖数: 5706
12
嗯,明白了。肯定on-site了,提前恭喜!

【在 j*****y 的大作中提到】
: 你这个in place 是很好的一个优化。
A*****i
发帖数: 3587
13
昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单
不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊
j*****y
发帖数: 1071
14
对的。 :)

【在 M********5 的大作中提到】
: 我也是这么想的,中间遇到不进位的时候就break,然后只要给出的数组不是9999这种
: 的,就不许要另外allocate space,如果是9999的话,那就另外做打算。。。是这样的
: 思路么?

j*****y
发帖数: 1071
15
多谢多谢, 托您吉言 :)

【在 c********t 的大作中提到】
: 嗯,明白了。肯定on-site了,提前恭喜!
f*****e
发帖数: 2992
16
如果是二进制的话,是不是必须到2^32-1再进位?

【在 j*****y 的大作中提到】
: 对的。 :)
j*****y
发帖数: 1071
17
不是二进制的表示。就是 0-9之间的 digit表示。

【在 f*****e 的大作中提到】
: 如果是二进制的话,是不是必须到2^32-1再进位?
r*****e
发帖数: 146
18
Bless! 应该进入下一轮了,弱问一句,一般G家的电话,要做几道题啊?

【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。

r*****e
发帖数: 146
19
弱问一下,啥是DAP?

【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单
: 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊

j*****y
发帖数: 1071
20
你说的是 DAG 吗?

【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单
: 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊

相关主题
求看代码 Plus One郁闷死了,顺便贴个Amazon电面面经
leetcode plus one 书上答案是不是错了?Google 的外包,80块钱一小时
Uber onsite为什么要带电脑?Fresh CS PhD, MS 面经
进入JobHunting版参与讨论
j*****y
发帖数: 1071
21
多谢。 :)
我也不知道,可能看你水平,像我这种弱水平的,面试官也没有时间让你做两道题目。

【在 r*****e 的大作中提到】
: Bless! 应该进入下一轮了,弱问一句,一般G家的电话,要做几道题啊?
B*******1
发帖数: 2454
22
你这道算法题用了多久时间啊? 50分钟就一道题?

【在 j*****y 的大作中提到】
: 多谢。 :)
: 我也不知道,可能看你水平,像我这种弱水平的,面试官也没有时间让你做两道题目。

j*****y
发帖数: 1071
23
我花了 20分钟写完,然后20分钟在提示下一步一步优化。
这40分钟就这一道题。
后面的时间就闲聊了。

【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊? 50分钟就一道题?
s**s
发帖数: 70
24
祝onsite成功~
j*****y
发帖数: 1071
25
多谢吉言 :)

【在 s**s 的大作中提到】
: 祝onsite成功~
M********5
发帖数: 715
26
所以他是真的很幸运啦。。。这种东西嫉妒不来,咱们得move on。。。

【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊? 50分钟就一道题?
A*****i
发帖数: 3587
27
矮油我擦,一着急写错了,DAG,不是DAP

【在 r*****e 的大作中提到】
: 弱问一下,啥是DAP?
s********l
发帖数: 998
28
只加一边1
还是没完没了的加啊?

【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。

j*****y
发帖数: 1071
29
加一次 1
比如对于 19
计算 19 + 1
只不过 19存在数组里面而已

【在 s********l 的大作中提到】
: 只加一边1
: 还是没完没了的加啊?

s********l
发帖数: 998
30
哦~ 这样子 thanks.

【在 j*****y 的大作中提到】
: 加一次 1
: 比如对于 19
: 计算 19 + 1
: 只不过 19存在数组里面而已

相关主题
请教一道面试题一道面试题(integer to binary string)
一道很简单的面试题,但是不知道哪个算法好问一个facebook的电面
问个amazon面试题。G家onsite面经
进入JobHunting版参与讨论
s********l
发帖数: 998
31
你最后 优化成什么样子的了?

【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。

s********l
发帖数: 998
32
这个 你最后优化成什么样了?

【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单
: 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊

j*****y
发帖数: 1071
33
这是最后的 code
vector plusOne(vector &input)
{
if(input.size() == 0)
{
return vector(1, 1);
}

int remainder = 1;
for(int i = input.size() -1 ; i > -1; --i)
{
int tmp = input[i] + remainder;
if(tmp >= 10)
{
input[i] = tmp - 10;
remainder = 1;
}
esle
{
input[i] = tmp;
remainder = 0;
break;
}
}
if(remainder != 0)
{
vector tmp(1, remainder);
input.insert(input.begin(), tmp.begin(), tmp.end());
}
return input;
}

【在 s********l 的大作中提到】
: 你最后 优化成什么样子的了?
l*********8
发帖数: 4642
34
能不能把数字反过来存?
[9, 9,3, 1] 表示1399

【在 j*****y 的大作中提到】
: 这是最后的 code
: vector plusOne(vector &input)
: {
: if(input.size() == 0)
: {
: return vector(1, 1);
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)

j*****y
发帖数: 1071
35
没有discuss这个 :)

【在 l*********8 的大作中提到】
: 能不能把数字反过来存?
: [9, 9,3, 1] 表示1399

s********l
发帖数: 998
36
这个好 多谢多谢

【在 j*****y 的大作中提到】
: 这是最后的 code
: vector plusOne(vector &input)
: {
: if(input.size() == 0)
: {
: return vector(1, 1);
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)

j*****y
发帖数: 1071
37
可是刚才拷贝的时候,我发现了一个错误 :(
else 写成了 esle

【在 s********l 的大作中提到】
: 这个好 多谢多谢
l*****a
发帖数: 14598
38
why input.size()==0, then u return 1?
if input==0, then u can return 1

【在 j*****y 的大作中提到】
: 这是最后的 code
: vector plusOne(vector &input)
: {
: if(input.size() == 0)
: {
: return vector(1, 1);
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)

s********l
发帖数: 998
39
这个肯定不会有影响的~~

【在 j*****y 的大作中提到】
: 可是刚才拷贝的时候,我发现了一个错误 :(
: else 写成了 esle

j*****y
发帖数: 1071
40
多谢。 希望如此,托您吉言 :)

【在 s********l 的大作中提到】
: 这个肯定不会有影响的~~
相关主题
G家onsite面经google phone interview,直接跪了,以前没做过,做过的应该不难
请教一个bloomberg题目G家新鲜电面面经,onsite求bless
除法有什么规律吗?求大数加1题目的细节
进入JobHunting版参与讨论
j*****y
发帖数: 1071
41
should return an array

【在 l*****a 的大作中提到】
: why input.size()==0, then u return 1?
: if input==0, then u can return 1

l*****a
发帖数: 14598
42
i mean since nothing in the input, why u return int [] a={1};

【在 j*****y 的大作中提到】
: should return an array
j*****y
发帖数: 1071
43
i asked him if it is OK to return [1] in this case, he gave yes.

【在 l*****a 的大作中提到】
: i mean since nothing in the input, why u return int [] a={1};
l*****a
发帖数: 14598
44
why not throw something like illegalArgumentException?

【在 j*****y 的大作中提到】
: i asked him if it is OK to return [1] in this case, he gave yes.
j*****y
发帖数: 1071
45
too complicated to me :)

【在 l*****a 的大作中提到】
: why not throw something like illegalArgumentException?
j*****y
发帖数: 1071
46
bless.
昨天电面的今天就给消息了 ?

【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单
: 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊

l*****k
发帖数: 1059
47
这种题对new graduate来说最危险了,算法很简单,完全
看写代码的功力。
a**********e
发帖数: 157
48
谢谢分享。

【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。

e****w
发帖数: 19
49
google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
部分打括号
比如输入1,3 输出0.(3)
输入1,2 输出0.5(0)


bless.昨天电面的今天就给消息了 ?

【在 j*****y 的大作中提到】
: bless.
: 昨天电面的今天就给消息了 ?

B*******1
发帖数: 2454
50
这题有意思啊:
比如输入1,3 输出0.(3)
输入1,2 输出0.5(0)
记得有个数学trick在里面,你怎么做的啊?


【在 e****w 的大作中提到】
: google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
: 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
: 部分打括号
: 比如输入1,3 输出0.(3)
: 输入1,2 输出0.5(0)
:
:
: bless.昨天电面的今天就给消息了 ?

相关主题
出一道题plusone变种leetcode plus one 书上答案是不是错了?
一道面试题Uber onsite为什么要带电脑?
求看代码 Plus One郁闷死了,顺便贴个Amazon电面面经
进入JobHunting版参与讨论
w**********o
发帖数: 140
51
This is cool:
public class Solution {
public int[] plusOne(int[] digits) {
// Start typing your Java solution below
// DO NOT write main() function
int carry=1;
for(int i=digits.length-1;i>=0;i--){
if(carry==0)
break;
if(digits[i]==9){
digits[i]=0;
}
else{
digits[i]++;
carry=0;
}
}
if(carry==0) return digits;
int[] array =new int[digits.length+1];
array[0]=1;
for(int i=0;i array[i+1]=digits[i];
return array;
}
}
// copied from http://www.tsechung.com/wordpress/2012/07/19/plus-one/
e****w
发帖数: 19
52
哈哈 大牛想想呗
其实没啥tricky
但是一开始被这题唬住了 而且那时候还没啥面试经验
所以就面挂了~

【在 B*******1 的大作中提到】
: 这题有意思啊:
: 比如输入1,3 输出0.(3)
: 输入1,2 输出0.5(0)
: 记得有个数学trick在里面,你怎么做的啊?
:

M********5
发帖数: 715
53
以前没有见过这个题,intuitive的想法:
先计算整数部分的商,这个不难,整数部分的商先保存在一个变量里面
再计算小数部分的商,怎么判断是否进入小数部分:如果商为0余数不为0,就进入小数
部分
接下来,把小数部分的商用string保存起来,并且把小数部分的结果建立trie(为了后
面计算循环部分,因为像单个的循环节好计算,但是比如1/7这种循环节很长的,就不
是那么好计算),不断地计算结果,计算到一定长度的时候如果发现某个string总是重
复出现,就可以判断为循环节。这个时候再对计算的小数部分的商做处理,只取到第一
个循环节为止(可以用简单的substring操作)
我不知道相关的数学trick,一点愚见。。。

【在 B*******1 的大作中提到】
: 这题有意思啊:
: 比如输入1,3 输出0.(3)
: 输入1,2 输出0.5(0)
: 记得有个数学trick在里面,你怎么做的啊?
:

e****w
发帖数: 19
54
怎么判断出循环的string啊?
这一段能再详细说下?

【在 M********5 的大作中提到】
: 以前没有见过这个题,intuitive的想法:
: 先计算整数部分的商,这个不难,整数部分的商先保存在一个变量里面
: 再计算小数部分的商,怎么判断是否进入小数部分:如果商为0余数不为0,就进入小数
: 部分
: 接下来,把小数部分的商用string保存起来,并且把小数部分的结果建立trie(为了后
: 面计算循环部分,因为像单个的循环节好计算,但是比如1/7这种循环节很长的,就不
: 是那么好计算),不断地计算结果,计算到一定长度的时候如果发现某个string总是重
: 复出现,就可以判断为循环节。这个时候再对计算的小数部分的商做处理,只取到第一
: 个循环节为止(可以用简单的substring操作)
: 我不知道相关的数学trick,一点愚见。。。

M********5
发帖数: 715
55
等一下,我仔细想了一下具体的做法,差不多有了个大概的思路,等我先整理整理。。。
不过实在觉得这一题作为电话面试太难了,你比我还倒霉。。。

【在 e****w 的大作中提到】
: 怎么判断出循环的string啊?
: 这一段能再详细说下?

f*****e
发帖数: 2992
56
其实就是小数部分不断取余,然后判断第一个重复余出现的时刻:
比如1/7
取余是:1,3,2,6,4,5,1
thus...

【在 M********5 的大作中提到】
: 以前没有见过这个题,intuitive的想法:
: 先计算整数部分的商,这个不难,整数部分的商先保存在一个变量里面
: 再计算小数部分的商,怎么判断是否进入小数部分:如果商为0余数不为0,就进入小数
: 部分
: 接下来,把小数部分的商用string保存起来,并且把小数部分的结果建立trie(为了后
: 面计算循环部分,因为像单个的循环节好计算,但是比如1/7这种循环节很长的,就不
: 是那么好计算),不断地计算结果,计算到一定长度的时候如果发现某个string总是重
: 复出现,就可以判断为循环节。这个时候再对计算的小数部分的商做处理,只取到第一
: 个循环节为止(可以用简单的substring操作)
: 我不知道相关的数学trick,一点愚见。。。

M********5
发帖数: 715
57
这个我也知道,不过要用代码表达出来。。。

【在 f*****e 的大作中提到】
: 其实就是小数部分不断取余,然后判断第一个重复余出现的时刻:
: 比如1/7
: 取余是:1,3,2,6,4,5,1
: thus...

p*****2
发帖数: 21240
58

是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
比如1/70 输出 0.0(142857)

【在 f*****e 的大作中提到】
: 其实就是小数部分不断取余,然后判断第一个重复余出现的时刻:
: 比如1/7
: 取余是:1,3,2,6,4,5,1
: thus...

l*****i
发帖数: 136
59
没有测试很多case,只是把idea表达了出来
感觉面试的时候现写,只能跪了
string afterPoint(int a, int b)
{
string ret;
unordered_map m;
if (a==0)
{
ret += "(0)";
return ret;
}

int p=0;
while(true)
{
m[a] = p;
a *= 10;
int d = a/b;
int r = a%b;
ret += char(d+'0');
if ( m.find( r)!= m.end() ) // find the cycle
{
ret.insert(m[r], "(");
ret += ')';
return ret;
}
p++;
a = r;
}
}
string Solution(int a, int b)
{
string ret;
int d = a/b;
ret = to_string(d);
ret += ".";
ret += afterPoint(a%b, b);
return ret;
}

【在 p*****2 的大作中提到】
:
: 是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0(142857)

B*******1
发帖数: 2454
60
的确不好写,店面这个比较坑爹了。 我以前就看过这题,但是就一次,但是从来没有
练过。

【在 p*****2 的大作中提到】
:
: 是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0(142857)

相关主题
Google 的外包,80块钱一小时一道很简单的面试题,但是不知道哪个算法好
Fresh CS PhD, MS 面经问个amazon面试题。
请教一道面试题一道面试题(integer to binary string)
进入JobHunting版参与讨论
f*****e
发帖数: 2992
61
试了试,好像1/70也可以用乘10取余这种方法:
1/70,每一个元素都是它前一个元素乘10取余:
1, 10, 30, 20, 60, 40, 50, 10, duplicate found
也可以判断如果分子比分母小就继续乘10,不用存map或set。
不过overflow确实需要考虑啊。

【在 p*****2 的大作中提到】
:
: 是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0(142857)

M********5
发帖数: 715
62
你这个思路不错,但是有没有可能出现这样的一种case,比如说有一个商是
0.3323232323(23)...
这样在出现第二个3的时候,你就觉得3就是循环节了,结果后面都没有计算了?只是提
供一个case供讨论。。。

【在 l*****i 的大作中提到】
: 没有测试很多case,只是把idea表达了出来
: 感觉面试的时候现写,只能跪了
: string afterPoint(int a, int b)
: {
: string ret;
: unordered_map m;
: if (a==0)
: {
: ret += "(0)";
: return ret;

M********5
发帖数: 715
63
不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。

【在 f*****e 的大作中提到】
: 试了试,好像1/70也可以用乘10取余这种方法:
: 1/70,每一个元素都是它前一个元素乘10取余:
: 1, 10, 30, 20, 60, 40, 50, 10, duplicate found
: 也可以判断如果分子比分母小就继续乘10,不用存map或set。
: 不过overflow确实需要考虑啊。

f*****e
发帖数: 2992
64
我就是手算看出规律的,我觉得没什么难度。不信你手算试试。

【在 M********5 的大作中提到】
: 不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。
M********5
发帖数: 715
65
我明白你的意思,不过我的意思是,这个规律是仅仅适用于7的倍数做分母,还是适用
于所有的数,这个还不好说。。。

【在 f*****e 的大作中提到】
: 我就是手算看出规律的,我觉得没什么难度。不信你手算试试。
j*****y
发帖数: 1071
66
调试了无数次,似乎搞了一个 work的, 花了两个小时阿。换作是我,当场悲剧的更惨。
string func(int a, int b)
{
bool negative = false;
if(a < 0)
{
negative = true;
a = -a;
}
if(b < 0)
{
if(negative)
{
negative = false;
}
else
{
negative = true;
}
b = -b;
}
int x = a / b;
int y = a % b;
string s;
stringstream ss;
ss << x;
s=ss.str();
if(negative)
{
s = "-" + s;
}
if(y == 0)
{
return s;
}
s += ".";
int pos[b];
for(int i = 0; i < b; ++i)
{
pos[i] = 0;
}
string tail;
int next_y = y;
int count = 0;
while(y != 0)
{
pos[y] = ++count;
x = 10 * y;
next_y = x % b;
tail.append(1, x / b + '0');
if(next_y == 0)
{
tail += "(0)";
break;
}
if(pos[next_y] != 0)
{
tail.insert(tail.begin() + pos[next_y] - 1, '(');
tail.append(1, ')');
break;
}
y = next_y;
}
s = s + tail;
return s;
}

【在 e****w 的大作中提到】
: google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
: 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
: 部分打括号
: 比如输入1,3 输出0.(3)
: 输入1,2 输出0.5(0)
:
:
: bless.昨天电面的今天就给消息了 ?

l*****i
发帖数: 136
67
我觉的不会吧,我这是看余数是否相等,余数相等的话,后面的除法就是在重复前面的
某个序列开始的过程,所以商肯定开始重复了

【在 M********5 的大作中提到】
: 你这个思路不错,但是有没有可能出现这样的一种case,比如说有一个商是
: 0.3323232323(23)...
: 这样在出现第二个3的时候,你就觉得3就是循环节了,结果后面都没有计算了?只是提
: 供一个case供讨论。。。

M********5
发帖数: 715
68
这个解释make sense。。。
enlinw挂在这题上确实情理之中,我也直接给跪了。。。我现在再也不觉得自己冤枉了。
。。

【在 l*****i 的大作中提到】
: 我觉的不会吧,我这是看余数是否相等,余数相等的话,后面的除法就是在重复前面的
: 某个序列开始的过程,所以商肯定开始重复了

p*****2
发帖数: 21240
69
练练第一道题
def plusOne(num)
c=1
for i in -1.downto(-num.length)
c+=num[i]
num[i]=c%10
c/=10
end

if c>0
num.unshift(c)
end
end
p*****2
发帖数: 21240
70

就是这样。结果还不能输出,要存起来,遇到过的余数也要用个hashtable存起来,并
且指向结果的位置。一旦发现有重复的。从这个位置开始画(),之前的直接输出。

【在 f*****e 的大作中提到】
: 试了试,好像1/70也可以用乘10取余这种方法:
: 1/70,每一个元素都是它前一个元素乘10取余:
: 1, 10, 30, 20, 60, 40, 50, 10, duplicate found
: 也可以判断如果分子比分母小就继续乘10,不用存map或set。
: 不过overflow确实需要考虑啊。

相关主题
一道面试题(integer to binary string)请教一个bloomberg题目
问一个facebook的电面除法有什么规律吗?
G家onsite面经google phone interview,直接跪了,以前没做过,做过的应该不难
进入JobHunting版参与讨论
e****w
发帖数: 19
71
没有吧 用商和用余数找循环不一样的 用余数要简单很多
我只是想听听你是怎么用商找循环的
其实面试时候他给我提示的 让我用余数找循环
其实后来想想思路清楚之后 还是能写的

【在 M********5 的大作中提到】
: 这个我也知道,不过要用代码表达出来。。。
e****w
发帖数: 19
72
嗯嗯 对就是这个思路 不能用商来找循环
要用余数来找循环
大致是把余数存在linkedlist l1里,对应的商存在另一个linkedlist l2里,然后每来
一个新余数,都和l1里的比较,如果有出现过,那么从出现的那个到最后就是循环部分
(这里只是循环的位置,不是结果)把对应位置的商(l2里的结果)用括号括起来,之
前的商的结果就放在前面就行了,如果没有出现过,那就加到l1里面,也把商加到l2里面

【在 l*****i 的大作中提到】
: 我觉的不会吧,我这是看余数是否相等,余数相等的话,后面的除法就是在重复前面的
: 某个序列开始的过程,所以商肯定开始重复了

o***d
发帖数: 313
73
请教一下:
1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数
本身做返回?
2) 他要求用vector的?还是你自己挑的?

【在 j*****y 的大作中提到】
: 这是最后的 code
: vector plusOne(vector &input)
: {
: if(input.size() == 0)
: {
: return vector(1, 1);
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)

o***d
发帖数: 313
74
最后的两个数组赋值,copy不快些么?为什么要loop?

【在 w**********o 的大作中提到】
: This is cool:
: public class Solution {
: public int[] plusOne(int[] digits) {
: // Start typing your Java solution below
: // DO NOT write main() function
: int carry=1;
: for(int i=digits.length-1;i>=0;i--){
: if(carry==0)
: break;
: if(digits[i]==9){

o***d
发帖数: 313
75
大牛觉得楼上某个的java实现怎么样?你这样%运算慢吧?他那个基本只有if, else, +
+,应该很快似乎

【在 p*****2 的大作中提到】
: 练练第一道题
: def plusOne(num)
: c=1
: for i in -1.downto(-num.length)
: c+=num[i]
: num[i]=c%10
: c/=10
: end
:
: if c>0

o***d
发帖数: 313
76
还有个问题,似乎我看大家一般都用index来loop stl container,but normally, we
are suggested to use iterator, right?
do you guys think that will be a problem when we write the code onsite/at
phone interview?
tks
j*****y
发帖数: 1071
77
自己挑的, 说 vector 对自己比较奥 comfortable一下 :)

【在 o***d 的大作中提到】
: 请教一下:
: 1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数
: 本身做返回?
: 2) 他要求用vector的?还是你自己挑的?

o***d
发帖数: 313
78
还有个问题,似乎我看大家一般都用index来loop stl container,but normally, we
are suggested to use iterator, right?
do you guys think that will be a problem when we write the code onsite/at
phone interview?
tks
p*****2
发帖数: 21240
79
为什么用链表

里面

【在 e****w 的大作中提到】
: 嗯嗯 对就是这个思路 不能用商来找循环
: 要用余数来找循环
: 大致是把余数存在linkedlist l1里,对应的商存在另一个linkedlist l2里,然后每来
: 一个新余数,都和l1里的比较,如果有出现过,那么从出现的那个到最后就是循环部分
: (这里只是循环的位置,不是结果)把对应位置的商(l2里的结果)用括号括起来,之
: 前的商的结果就放在前面就行了,如果没有出现过,那就加到l1里面,也把商加到l2里面

o***d
发帖数: 313
80
thanks to let me know!

【在 j*****y 的大作中提到】
: 自己挑的, 说 vector 对自己比较奥 comfortable一下 :)
相关主题
G家新鲜电面面经,onsite求bless一道面试题
求大数加1题目的细节求看代码 Plus One
出一道题plusone变种leetcode plus one 书上答案是不是错了?
进入JobHunting版参与讨论
e****w
发帖数: 19
81
只是为了知道位置咯~~

【在 p*****2 的大作中提到】
: 为什么用链表
:
: 里面

M********5
发帖数: 715
82
我想了一下,其实用商也是可以找到循环的,只不过会麻烦很多。。。并且这个做法存
在一个假设,就是假设循环节不能太长了,比如suppose循环节不能长于某个数字。
具体的想法是这样子的,比如说我把这个数一直除,除到小数点后面100位,这样我就
有了一个长度为100的string,两个整数相除,肯定是有循环节的,那么我可以从循环
小数的特点来看,最后一位一定是循环节里面的某一位,然后我再从后往前找,找到一
个跟str[99]相同的数字的时候,判断str[pos]到str[99]是不是循环节,如果不是的话
,再接着找,直到找到循环节为止;如果是的话,我们就找到了循环节的长度,接下来
就是判断循环节里面的哪一个数字是这个循环节的开头,因为这个时候循环节的长度已
经知道了,假设为len,我们就把这个循环节里面的每一个数字不断地往前移len,然后
判断最前端可以移到哪个数字,直到不是循环节了为止,这就是循环节的最开始。。。
我说了这是个很麻烦的办法,但是如果说只要循环节没有个50,60位长,这个办法应该
是正确的,不过会比用余数麻烦很多,因为它需要足够长的string来作为样本

【在 e****w 的大作中提到】
: 没有吧 用商和用余数找循环不一样的 用余数要简单很多
: 我只是想听听你是怎么用商找循环的
: 其实面试时候他给我提示的 让我用余数找循环
: 其实后来想想思路清楚之后 还是能写的

M********5
发帖数: 715
83
并且我由此想到了一个衍生的题目,如果说给了一个无限循环小数的string表示方法(
这个string表示方法的最后一个数字不一定是循环节的最后一个数字,可以是整个循环
节里面的任何一个数字),只是告诉已知条件是一个无限循环小数的表示,但是没有说
循环节有多长或者说循环节的起始位置在哪,让你找出循环节,你怎么找?我觉得我说
的这个方法就可以判断。。。

【在 M********5 的大作中提到】
: 我想了一下,其实用商也是可以找到循环的,只不过会麻烦很多。。。并且这个做法存
: 在一个假设,就是假设循环节不能太长了,比如suppose循环节不能长于某个数字。
: 具体的想法是这样子的,比如说我把这个数一直除,除到小数点后面100位,这样我就
: 有了一个长度为100的string,两个整数相除,肯定是有循环节的,那么我可以从循环
: 小数的特点来看,最后一位一定是循环节里面的某一位,然后我再从后往前找,找到一
: 个跟str[99]相同的数字的时候,判断str[pos]到str[99]是不是循环节,如果不是的话
: ,再接着找,直到找到循环节为止;如果是的话,我们就找到了循环节的长度,接下来
: 就是判断循环节里面的哪一个数字是这个循环节的开头,因为这个时候循环节的长度已
: 经知道了,假设为len,我们就把这个循环节里面的每一个数字不断地往前移len,然后
: 判断最前端可以移到哪个数字,直到不是循环节了为止,这就是循环节的最开始。。。

l**h
发帖数: 893
84
/**
* 比如输入1,3 输出0.(3)
* 输入1,2 输出0.5(0)
* 输入1,700, 输出 0.00(142857)
* 暂不考虑输入为负数
*/
public class Division {
public static String getQuotientInString(int i, int j) {
StringBuffer quotient = new StringBuffer();
quotient.append(i/j);
quotient.append(".");
int modular = i%j * 10;
while(modular/j == 0) {
quotient.append("0");
modular = modular * 10;
}

int a[] = new int[10];
Arrays.fill(a, 0);
int dividend = modular;
while(true) {
int tmpQuotient = dividend/j;
if (a[tmpQuotient] != 0) {
quotient.insert(a[tmpQuotient], "(");
quotient.append(")");
break;
}
else {
a[tmpQuotient] = quotient.length();
quotient.append(tmpQuotient);
}
dividend = (dividend%j) * 10;
}
return quotient.toString();
}
}

【在 e****w 的大作中提到】
: 怎么判断出循环的string啊?
: 这一段能再详细说下?

j*****y
发帖数: 1071
85
通过商就可以判断是循环了吗? 感觉还是要通过余数吧
比如 0.1323.....
后面的不知道了,这个时候不见的就是 0.1(32)
感觉只有出现了相同的余数才能断定循环了。

【在 l**h 的大作中提到】
: /**
: * 比如输入1,3 输出0.(3)
: * 输入1,2 输出0.5(0)
: * 输入1,700, 输出 0.00(142857)
: * 暂不考虑输入为负数
: */
: public class Division {
: public static String getQuotientInString(int i, int j) {
: StringBuffer quotient = new StringBuffer();
: quotient.append(i/j);

M********5
发帖数: 715
86
这样单单地比较商确实是不行的,比如说0.3332323(23)

【在 l**h 的大作中提到】
: /**
: * 比如输入1,3 输出0.(3)
: * 输入1,2 输出0.5(0)
: * 输入1,700, 输出 0.00(142857)
: * 暂不考虑输入为负数
: */
: public class Division {
: public static String getQuotientInString(int i, int j) {
: StringBuffer quotient = new StringBuffer();
: quotient.append(i/j);

l**h
发帖数: 893
87
对,要改一下,用余数

【在 j*****y 的大作中提到】
: 通过商就可以判断是循环了吗? 感觉还是要通过余数吧
: 比如 0.1323.....
: 后面的不知道了,这个时候不见的就是 0.1(32)
: 感觉只有出现了相同的余数才能断定循环了。

p*****2
发帖数: 21240
88

感觉复杂度比较高吧?

【在 e****w 的大作中提到】
: 只是为了知道位置咯~~
p*****2
发帖数: 21240
89

+
我也不是很清楚%慢多少。大牛讲讲。

【在 o***d 的大作中提到】
: 大牛觉得楼上某个的java实现怎么样?你这样%运算慢吧?他那个基本只有if, else, +
: +,应该很快似乎

p*****2
发帖数: 21240
90
第二题练了练
def divide(a,b)
if b==0
return
end
print("#{a/b}.")
a=(a%b)*10
arr=[]
hm={}
while hm[a]==nil
hm[a]=arr.length
if(a!=0 && a a*=10;
arr.push(0)
else
arr.push(a/b)
a=(a%b)*10
end
end

for i in 0..hm[a]-1
print(arr[i])
end

print("(")
for i in hm[a]..arr.length-1
print(arr[i])
end
print(")\n")
end
1 (共1页)
进入JobHunting版参与讨论
相关主题
Google 的外包,80块钱一小时请教一个bloomberg题目
Fresh CS PhD, MS 面经除法有什么规律吗?
请教一道面试题google phone interview,直接跪了,以前没做过,做过的应该不难
一道很简单的面试题,但是不知道哪个算法好G家新鲜电面面经,onsite求bless
问个amazon面试题。求大数加1题目的细节
一道面试题(integer to binary string)出一道题plusone变种
问一个facebook的电面一道面试题
G家onsite面经求看代码 Plus One
相关话题的讨论汇总
话题: int话题: return话题: string话题: ret话题: negative