一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 752|回复: 12
收起左侧

Pocket Gems 2nd Phone Interview

[复制链接] |试试Instant~ |关注本帖
lgscoding 发表于 2015-12-1 11:57:23 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@PoketGem - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
发面经,攒人品。是个妹子给我面试的。上来一看不是sort color有点懵懵的。。。
1. Input:
  Array of numbers: A
  number: x
Output: find k < A.size(), such that the number of elements in A[0,..., k - 1]  == x is same as number of elements in A[k, ..., N - 1]  != x.
Return -1 if not found

Example:
A = [2, 4, 1, 5, 6, 2, 5, 6, 2, 6]
[0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3]
x = 2
Output: 7
follow up: O(n) time  O(1) space

2. find next largest node in BST with / without parent pointer
follow up: time complexity o(height)

评分

2

查看全部评分

no.9 发表于 2015-12-21 15:03:36 | 显示全部楼层
楼主,请问第一题的follow up 怎么做到O(1)space
回复 支持 反对

使用道具 举报

cutesnoopy1993 发表于 2015-12-21 15:09:45 | 显示全部楼层
第一题是k index吗
回复 支持 反对

使用道具 举报

cutesnoopy1993 发表于 2015-12-21 15:11:23 | 显示全部楼层
不是的... 我错了啦
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-12-22 09:18:40 | 显示全部楼层
楼主, 第一题, follow up 怎么做啊。
回复 支持 反对

使用道具 举报

 楼主| lgscoding 发表于 2015-12-27 11:42:10 | 显示全部楼层
hulahu 发表于 2015-12-22 09:18
楼主, 第一题, follow up 怎么做啊。

我记得就是一开始我用的一维DP,但是找我需要的变量之间的关系的时候 发现一维dp只是记录一下之前的数字,可以用一个变量表示,然后每个循环根据规律改变该变量的值就行了
回复 支持 反对

使用道具 举报

 楼主| lgscoding 发表于 2015-12-27 11:42:24 | 显示全部楼层
no.9 发表于 2015-12-21 15:03
楼主,请问第一题的follow up 怎么做到O(1)space

看楼上~~~~~
回复 支持 反对

使用道具 举报

 楼主| lgscoding 发表于 2015-12-27 11:42:42 | 显示全部楼层
cutesnoopy1993 发表于 2015-12-21 15:11.1point3acres缃
不是的... 我错了啦

不是的呢 就是用dp就行了
回复 支持 反对

使用道具 举报

Sense 发表于 2016-1-12 02:54:26 | 显示全部楼层
不用动态规划呀,只要扫一遍知道x在数列里出现的总数就行了呢。
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-1-22 11:41:20 | 显示全部楼层
第一题不能用左右指针来做吗?右边遇到不同的停下来,然后左边开始走直到遇到相同的,接着右边,不过得记录最后一次平衡状态,终止条件有点麻烦
回复 支持 反对

使用道具 举报

desperate500 发表于 2016-1-26 10:57:23 | 显示全部楼层
正着走一遍 得到[0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3] 反着走一遍 得到[7, 7, 6, 5, 4, 3, 3, 2, 1, 1] 返回相等的数的index 即是7

补充内容 (2016-1-26 10:57):
明天一面求好运...

补充内容 (2016-1-26 11:07):
正向得到的应该是[0, 1, 1, 1, 1, 1, 2, 2, 2, 3]
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-1-27 07:54:02 | 显示全部楼层
desperate500 发表于 2016-1-26 10:57
正着走一遍 得到[0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3] 反着走一遍 得到[7, 7, 6, 5, 4, 3, 3, 2, 1, 1] 返回 ...
. visit 1point3acres.com for more.
可以只走一趟
public int solution(String[] word, String x){
                int count=0;
                int ans=-1;
                int unequal=0;
                for(int i=0;i<word.length;i++){
                        if(word.equals(x)) count++;
                }
                for(int i=0;i<word.length;i++){
                        if(word.equals(x)) {
                                count--;

                        } else {
                                unequal++;//记录的是左边不等于x的值. 鍥磋鎴戜滑@1point 3 acres
                        }
                        if(i-unequal==word.length-i-count-1){//左边等于=x的总数==右边不等于x的总数,
                        (也就是左边-不等于x)==右边-等于x
                                ans=i;
                                return ans; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }
                }
                return ans;
                }
        }
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-1-27 07:54:21 | 显示全部楼层
cx00001 发表于 2016-1-27 07:54
可以只走一趟. 1point 3acres 璁哄潧
public int solution(String[] word, String x){
                int count=0;

其实也是两趟。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 20:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表