一亩三分地论坛

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

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

问两道linkedin的面试题,附两个小面筋

[复制链接] |试试Instant~ |关注本帖
kwang75 发表于 2015-1-5 05:56:40 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 本科 全职@ - 内推 - 技术电面 |Other

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

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

x
电话面了L的第一轮和G。正在准备L的第二轮。有两道题麻烦各位大神帮帮忙:第一题deep iterator
Implement a (Java) Iterable object that iterates lines one by one from a text file.. 1point 3acres 璁哄潧

** A reference to a file. */
public class TextFile implements Iterable<String>.鏈枃鍘熷垱鑷1point3acres璁哄潧
{
  public TextFile(String fileName) { // please implement this

  /** Begin reading the file, line by line. The returned Iterator.next() will return a line. */
  @Override
  public Iterator<String> iterator() { // please implement this

第二题print all unique combination of factors of a number.比如12就是1*12, 2*6, 2*2*3, 3*4这样。这题我按照combination sum来做,但是去重很麻烦,可能是我写的有问题。问了别人说可以通过排序去重,但一方面comparator用的不太熟,另一方面觉得这是不是有点费时?

大家写题的时候最好能说下思路,谢谢!
. 鍥磋鎴戜滑@1point 3 acres
G面我面的很非主流,我不知道是否和我有工作经历有关(应该无关吧?)。大概就是有个词典,给一个String,这个string代表一类词,然后在字典里面找出所有这类词。面试官很喜欢follow up,所以就不断改这道题。我记得好像改了两次吧。但我一共就写了一次代码,还非常少,因为有些部分拿interface表示了。面的时候很紧张,因为题意经常搞不清楚所以浪费了些时间。大概面试官上来第一问让我写了个signature,然后改了一下题,让我写整题代码,然后最后一题改的比较复杂,就问我思路。核心应该是第二问。我上来给了个O(N),然后说用hashtable来分组。最后一题我就说用trie树。。。

L面经在这: http://www.1point3acres.com/bbs/ ... kbox%26sortid%3D311


. 1point 3acres 璁哄潧


tbtc888 发表于 2015-1-5 06:22:19 | 显示全部楼层
第一题就写一个类一行行读文件就可以了..小trick就是那个类比较像buffer,把下一行存在一个var里面,每次调用返回var的值,更新var的值到下一行..hasnext就是check var是不是null.. 第二题用recursive的方法写起来就很简单了,for prev:sqrt(num)逐个check因子...当然1*12这一项得特殊处理一下,几行就写好了...当然,可以用map进一步优化.
回复 支持 反对

使用道具 举报

 楼主| kwang75 发表于 2015-1-5 07:04:00 | 显示全部楼层
tbtc888 发表于 2015-1-4 17:22. more info on 1point3acres.com
第一题就写一个类一行行读文件就可以了..小trick就是那个类比较像buffer,把下一行存在一个var里面,每次调 ...
.1point3acres缃
第一题我会用scanner做,应该就是用但据说bufferedreader比较好,可不大会用。。。

如果可以的话,能提供个简单的代码么?这题写起来应该不复杂

第二题你可能理解错了。不是找所有的factor,而是unique combination of factors。如果逐个check因子,那2*2*3和2*6就不太容易被区分,或者时间复杂度会比较高。。。
回复 支持 反对

使用道具 举报

tbtc888 发表于 2015-1-5 07:28:58 | 显示全部楼层
kwang75 发表于 2015-1-5 07:04
第一题我会用scanner做,应该就是用但据说bufferedreader比较好,可不大会用。。。

如果可以的话,能 ...

第一题要读文件,所以最好用BufferedReader.看下api就会了。.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题没理解错.可能没讲清楚..recursive(int num, StringBuilder e, int prev); 12: 1*12(special case,可通过check e是否empty判断)  2*recursive(6,"2*",2); recursive(6)那个会先输出2*6.然后recursive(3,"2*2*",2);  还有一个是recursive(4,"3*",3),因为4没有比3大的因子,所以只会输出3*4....不会有重复是因为因子有order..时间空间复杂度和iterative的方法是一样的,如果用map优化过后。你琢磨一下就应该能写出来了..
回复 支持 反对

使用道具 举报

dragon418 发表于 2015-1-5 12:10:03 | 显示全部楼层
这是我对第二题的代码,也许可以参考:

. 鍥磋鎴戜滑@1point 3 acreshttp://ideone.com/ld9taq
. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

 楼主| kwang75 发表于 2015-1-5 12:22:15 | 显示全部楼层
tbtc888 发表于 2015-1-4 18:28. From 1point 3acres bbs
第一题要读文件,所以最好用BufferedReader.看下api就会了。.1point3acres缃
第二题没理解错.可能没讲清楚..recursive(i ...

主要是那个public Iterator<String> iterator()怎么写?我看Iterator的API里面什么都没有。。。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2015-1-4 23:24):
我的理解是hasnext看readline是否为空,next就readline,然后remove就不大清楚了。。。-google 1point3acres
回复 支持 反对

使用道具 举报

zengm321 发表于 2015-1-10 07:45:38 | 显示全部楼层
用C++的去面,岂不是直接挂了?
必须用java?
回复 支持 反对

使用道具 举报

 楼主| kwang75 发表于 2015-1-10 11:59:25 | 显示全部楼层
zengm321 发表于 2015-1-9 18:45
用C++的去面,岂不是直接挂了?
必须用java?

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴应该不会吧。第一题考的面向对象,如果C++就不会出这题我猜。第二题都可以做的。
回复 支持 反对

使用道具 举报

jiqishou 发表于 2015-2-16 05:39:49 | 显示全部楼层
第二题练习写得代码,和楼主想法一样是用combination sum的方法做的,只是需要自己定义一下candidates是从2到value/2的范围就好,然后sum变成product

vector<vector<int> > combbinationFactor(int value){
  vector<int> candidates;
  for (int i=2; i<=value/2; i++)
     candidates.push_back(i);
   vector<vector<int> > res;
   vector<int> output;
   output.push_back(1);
   output.push_back(value);
   res.push_back(output);. 1point 3acres 璁哄潧
   output.clear();
   int product = 1;
   //sort(candidates.begin(), candidaes.end());
   combination(res, output, candidates, value, 0, product);
   return res;
}

void combination(vector<vector<int> > &res, vector<int> output, vector<int> candidates,
    int value, int step, int product){
  if (product == value){
    res.push_back(output);
    return;. from: 1point3acres.com/bbs
  }

  if (product > value)
    return;

  for (int i=step; i<(int)candidates.size(); i++){. 鍥磋鎴戜滑@1point 3 acres
    output.push_back(candidates[i]);
    product *= candidates[i];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    combination(res, output, candidates, value, i, product);
    product /=candidates[i];. visit 1point3acres.com for more.
    output.pop_back();
  }. 1point3acres.com/bbs

  return;
}
回复 支持 反对

使用道具 举报

cuiyang36 发表于 2015-2-18 02:18:31 | 显示全部楼层
第二题我的一种java解法,思路和楼上差不多,也是用backtracking,希望和大家多交流,感觉这种题目一看还是至少有一套方法可以做的:

public class UniqueFactor { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        public static List<List<Integer>> uniqueFactor(int n){
                List<List<Integer>> result = new ArrayList<List<Integer>>();
                if (n <= 0){
                        return result;
                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                List<Integer> general = new ArrayList<Integer>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                general.add(1);
                general.add(n);
                result.add(general);
                List<Integer> solution = new ArrayList<Integer>();
                helper(result, solution, n, 2);
                return result;
        }
       
        private static void helper(List<List<Integer>> result, List<Integer> solution, int n, int factor){
                if (solution.size() > 0){
                        solution.add(n);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        result.add(new ArrayList<Integer>(solution));
                        solution.remove(solution.size() - 1);
                }
                for (int i = factor; i <= n / factor; i++){. from: 1point3acres.com/bbs
                        if (n % i == 0 && n / i >= i){. visit 1point3acres.com for more.
                                solution.add(i);
                                helper(result, solution, n / i, i);
                                solution.remove(solution.size() - 1);
                        }
                }
        }
       
        public static void main(String[] args){
                int n = 48;. from: 1point3acres.com/bbs
                List<List<Integer>> result = uniqueFactor(n);
                for (List<Integer> list: result){
                        for (Integer ele: list){
                                System.out.print(ele + " ");
                        }
                        System.out.println();
                }
        }

}
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-8-25 23:35:52 | 显示全部楼层
怎么全JAVA
他家招不招new grad
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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