@Sarah
2015-12-29T04:26:30.000000Z
字数 6077
阅读 1511
1strStr
算法
第1章
从strStr谈面试技巧与Coding Style【免费试听】
北京时间 2016-01-10 10:30
本节大纲
通过strStr这一道常见面试题讲解面试中的常见误区
从面试官的角度分析面试的考察点
从Subset中了解算法面试中模板的重要性
面试常见问题答疑
去大公司：因为接下来找工作会顺利很多
沟通重要 告诉对问题的理解，多沟通
有的数组里有没有重复的这一点很重要
沟通题目的各种细节，想清楚，说思考过程，面试官才知道你有没有走错方向】
面试官会告诉你应该朝着哪个方向走 是合作 不是考你 你们以后都是同事
沟通完了 你说 她说可以 你就写
她说不行 你别不沟通就开始写
这时候你告诉她算法会得到一个反馈 不会为你的面试减分 她要是给你否定 你还可以转换
你面对的是人 不是机器
Google 实习面挂了之后投full time不影响不是一个系统里。
沟通过程保持愉快
1程序风格
2coding习惯
3沟通：千万别闷头干！！！反应你平时工作会怎么做
4测试：自己出一个testcase走一遍，考虑情况，面试官不用动脑子去走
不是你算法想出来就能过！！
大部分面试是在白纸上写程序 锻炼你有没有想清楚 不要边写边擦边写边擦
刷300个题 给你做你做过的 你一时半会儿还是做不出来 刷了也白刷
不是刷了多少题 刷差不多100题就够了 吃透
刷题标准：再给你出 你马上想出来怎么做 有什么陷阱 不会错
不是数字和题量
面试官为难你：正常！会有加一些条件，不是你原来的方法错了，但想再看看你的灵活应对的能力，哈西表不是想用就能用的 哈希表耗费内存啊。
双重循环都想不到。。你连展示程序没有bug的机会都没有
做了很多题记不住解法、新题还是不会、kmp浪费时间还没有用！！网上那么多答案到底哪个对？
leetcode
30天足够
1刷题注意总结归类，不要一题一题刷和记忆，一百道题就九种类别，九种解法解决一百道题，
2找出适合同一类题的模板程序，递归搜索，不要每一次都重新想一遍算法，
40分钟2个题 15：25 还要有时间扯想法 也就十分钟写出一个简单题 另一个15-20分钟写另一个题
基本功非常熟练地掌握 模板
否则会浪费很多时间
递归很重要 能不能写递归非常重要
至少一个月 高强度练习 才能长久的进步 每次课周六周日 上午 一共九次
建议会写复合循环 有一点程序基础
备注自己报名邮箱
算法是保障 面什么职位都要用 能说明你这个人聪不聪明
应届生招聘问的主要是算法 100%
非应届生：聊以前的工作 算法 system desighn
直接做题就行
cc150的书
实习区别：
大公司：project做完了就没用了
小公司：接触到一线额东西
7 8 月投明年的职位
准备三个月 强很多 比较好 提前一个月的话每天要6个小时
了解公司产品和公司文化，公司什么做的不好，问你XXX有什么不好，能留下好印象
每个公司不一样
面试对女生有照顾、公司要调节男女比例，要求不一样，大公司招女生就是只要会写程序就可以了，
实习：
学校招聘会马上就会得到面试，直接就onsite。
现在内推很多，有时候简历还是可能悲剧，但比什么都没有好很多。
linkedin facebook难吗？误区！
越大的公司面试的题目会越简单，因为对人就没有那么挑剔了，能干活就行，反而是很house的小公司，对你的方向match要求比较高，明星公司面试很难，因为高速发展需要的不是很闲的人，上市公司问的都很简单
自己别给自己挖太多坑，你写精通，结果一问就惨了 实事求是的写会到什么程度
越小的公司越希望你对XX越精通
面试大公司，会算法就够了
uber需要很难的算法
面试小公司，你要看这个公司用什么 ，需要跟你match，小公司难准备
毕业三个月内 半年以内都算应届
简历千万别把以前的工作经验写的和CS太无关，往那个方向去写，
刷题，算法基础，
挑某一方面去准备，去学校做项目， 有项目CS经验，就针对某一个方面去做，比如就做html5
你看Google题目难，但是不是你必须作对，把双重循环写溜了就已经达到平均水平了。
如果实在没有相关经验：
简历花钱找人帮你看看 改一改，学生干部这种与CS无关的没用
不是CS的别写，无关的也要写成相关的
找资料我是写爬虫找的，用关键词算法看的资料，虽然事情就是找资料做PPT
会JAVA C++ python 会一门基础的语言，能写出来就足够了 不在于会多少种语言 能偶coding就可以了
GPA低就不要写了
Oracle只看GPA
转专业，与工作无关的学历要写。。
Google是直接去某个组，自己准备好，公司要找人。。什么时候投简历，招的人多的时候感觉呢投简历，找的人少的时候多准备准备
安卓 iOS 比较热 移动互联网 App方向缺人
嵌入系统也很缺
做web更是缺
只学JAVA足够了 C++不用学 太难，一种语言会了就不错了，
不用太介意语言 任何语言都可以 面试和语言不会太相关
5-6月是前一年的缺口，
8-9月是正式招人，
用intcode 按难度刷题
collabedit.com
有的上来想用哈希，觉得集合效率低，但其实占用内存
你说会KMP没用，面试官不希望你通过背诵，不是背熟了上去抄答案
能用两重循环写出来就够了。
你的代码看起来舒服，不用同事从头教你，写的简洁一点，
有缩进有空格，如果没有说明你写代码不超过一年，
习惯：异常检测，边界处理/ 空、越界 、溢出
沟通能力：有交流 不要闷着写，不说话！！
活用模板：每个都适用20-30题
下图是回溯法 ：放进去 删除 放进去 删掉
字符串查找题目：对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。
样例
如果 source = "source" 和 target = "target"，返回 -1。
如果 source = "abcdabcdefg" 和 target = "bcd"，返回 1。
挑战
O(n2)的算法是可以接受的。如果你能用O(n)的算法做出来那更加好。（提示：KMP）
说明
在面试中我是否需要实现KMP算法？
不需要，当这种问题出现在面试中时，面试官很可能只是想要测试一下你的基础应用能力。当然你需要先跟面试官确认清楚要怎么实现这个题。
这道题不用哈希表：效率得不到体现
for target和sourse,一个一个比 如果匹配成功就break
要做异常检测 和边界处理
class Solution {/*** Returns a index to the first occurrence of target in source,* or -1 if target is not part of source.* @param source string to be scanned.* @param target string containing the sequence of characters to match.*/public int strStr(String source, String target) {if (source == null || target == null) {return -1;}//如果两个字符串都是空的直接返回-1for (int i = 0; i < source.length() - target.length() + 1; i++) {int j = 0;for (j = 0; j < target.length(); j++) {if (source.charAt(i + j) != target.charAt(j)) {break;}}// finished loop, target foundif (j == target.length()) {return i;}}return -1;}}
面试官眼中的求职者
你可能是他未来的同事
● 你的代码看起来舒服么
○ TA需要多少时间Review你的代码)
● 你的Coding习惯好么
○ TA不会在未来疲于帮你DEBUG,你不会动不动
就搞出SEV
程序风格(缩进,括号,变量名) Coding习惯(异常检查,边界处理) 沟通(让面试官时刻明白你的意图) 测试(主动写出合理的Testcase)
你做题之前,先在白纸上写一遍么? 刷了200多题?你吃透了几题? 题目不会直接说不会么? 是不是觉得面试官在为难你?
在刷题时,总结、归类相似题目 ● 找出适合同一类题目的模板程序
1告诉面试官你的理解
2思考的过程也可以说出来，让面试官知道你方向对不对，朝着哪个思路走，给面试官一个帮助你的机会。
3面试官说思路没问题，再开始写。保持愉快的沟通过程。
子集subset
给定一个含不同整数的集合，返回其所有的子集
样例
如果 S = [1,2,3]，有如下的解：
[
[3],
1,
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
注意
子集中的元素排列必须是非降序的，解集必须不包含重复的子集
思路：简化成一棵树{1，2}
首先{}
然后{1}{2}
两类：1开头：2开头
约定顺序{12}
回溯法：back tracing/tracking
从空集开始，尝试把1加进去，再尝试把2加进去，后面没数了，把2删掉回到1这个状态，再把1删掉，现在是空集-再把2放进来
（把数放进来，一个接一个都进来，都尝试一遍，再删除。再放下一个数进来）
{1,2,3}
{}-{1}-{1,2}-{1,2,3}
{1,2}-{1}-{1,3}
{1}
{}
{2}-23-2-{}
{3}
一共八个结果
public class Solution {public ArrayList<ArrayList<Integer>> subsets(int[] num) {ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();if(num == null || num.length == 0) {return result;}ArrayList<Integer> list = new ArrayList<Integer>();Arrays.sort(num);subsetsHelper(result, list, num, 0);return result;//调用helper函数//result最后要保留的结果，list:中间我添加又删掉操作的子集，numbers：我可以选择的数。//position:1,2和2,1是一样的，list是有顺序的，如果2放进来了，1就不能进来了，要从2这个Position往后找，下一个数从posiyion开始找，我现在要从Numbers的哪个位置开始挑数放list里。函数：将numbers从position开始的那些数再拼上list做成子集1开头的做出来，把1傩掉，尝试2开头的，傩掉2，尝试312开头 13开头 递归的做这件事情。}private void subsetsHelper(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list, int[] num, int pos) {result.add(new ArrayList<Integer>(list));for (int i = pos; i < num.length; i++) {list.add(num[i]);subsetsHelper(result, list, num, i + 1);list.remove(list.size() - 1);}}}//
子集2（有重复）
带重复元素的子集
给定一个可能具有重复数字的列表，返回其所有可能的子集
样例
如果 S = [1,2,2]，一个可能的答案为：
[
[2],
1,
[1,2,2],
[2,2],
[1,2],
[]
]
注意
子集中的每个元素都是非降序的
两个子集间的顺序是无关紧要的
解集中不能包含重复子集
比之前八种情况少了两种
-{3}
-{13}
和上一个题很像，联系：有关，需要把subset模板背下来
这个要求是排除掉重复的
1，2
1，2
1，2
1. 与Subsets有关,先背下Subsets的模板
2. 既然要求Unique的,就想办法排除掉重复的。
3. 思考哪些情况会重复?如{1, 2(1), 2(2), 2(3)},规定{1, 2
(1)}和{1, 2(2)}重复,{1, 2(1), 2(2)}和{1, 2(2), 2(3)}重复。
观察规律。
4. 得出规律:我们只关心取多少个2,不关心取哪几个。
5. 规定必须从第一个2开始连续取(作为重复集合中的代
表),如必须是{1, 2(1)}不能是{1, 2{2})
6. 将这个逻辑转换为程序语言去判断
与之前子集1有两个区别1sort 2后面那个if是判断“如果取2要从第一个开始取”
public class Solution {public ArrayList<ArrayList<Integer>> subsets(int[] num) {ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();ArrayList<Integer> list = new ArrayList<Integer>();if(num == null || num.length ==0) {return result;}Arrays.sort(num);subsetsHelper(result, list, num, 0);//sort很重要 因为要把重复的数放在一起return result;}private void subsetsHelper(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list, int[] num, int pos) {result.add(new ArrayList<Integer>(list));for (int i = pos; i < num.length; i++) {if ( i != pos && num[i] == num[i - 1]) {continue;}//内层这个if：跳过了这个Position要看跳过的是谁，不能跳过了2去取下一个2，因为要取就要从第一个开始取list.add(num[i]);subsetsHelper(result, list, num, i + 1);list.remove(list.size() - 1);}}}
递归循环全部都长这个样子，把一个东西加上来，把这个东西往下递归，再把一个东西删掉，然后循环。所有东西都是树形的顺序。不是一层一层的。
不但适合组合，还适合排列（）适用于所有的搜索问题。
需要改动的地方：1什么时候输出2什么时候需要跳过3要不要排序
使用范围
● 几乎所有的搜索问题 根据具体题目要求进行改动
● 什么时候输出
● 哪些情况需要跳过
适用范围：
所有涉及到回溯的问题lintcode有几十道{recursing,backtracing ,array search,back checking}几乎所有搜索题
Combination Sum
Letter Combination of a Phone Number Palindrome Partitioning
Restore IP Address
挑一个方面深入的，有一个工程，具备真实码农的实力，比如html5方面不是门外汉，就可以了
和APP相关比较缺人，做web是个公司就要。
只学java就够了
跟着课程做一个项目，做东西！！！
做东西+刷算法
