作者pttworld (批踢踢世界)
看板Soft_Job
标题Re: [心得] Wearisma 面试心得
时间Sat Mar 3 17:59:56 2018
※ 引述《gocreating (小平)》之铭言：
: 标题: [心得] Wearisma 面试心得
: 时间: Sat Mar 3 16:37:21 2018
:
: 网页好读版：https://goo.gl/ZegAep
:
: Technical Task
:
: 题目长这样：
:
: Given a string with left and right parentheses, how you verify the string is
: valid (balanced)
: Ex. ((())()()()) -> Valid, ()) → Invalid
这个问题仅需一个整数变数出值为0，定义遇到(整数+1，遇到)整数-1，
O(n)扫一遍，在扫的过程中整数为负即为Invalid，最後结果整数不为0即为Invalid
special case是空字串，预设整数为0为Valid，但是要看题目定义，
有些题目可能认为空字串是Invalid，这个case视情况客制。
:
:
: 第二阶段面试
:
: 第二阶段是纯粹的Coding Test，面试官开了一个共同编辑的google docs给我，上面已经
: 列好题目如下：
:
: Given an array A, write a function to move all 0's to the end of it while
: maintaining the relative order of the non-zero elements. For example, A = [0,
: 1, 0, 3, 12], after calling your function, A should be [1, 3, 12, 0, 0].
:
: 乍看下会觉得很简单，开新的阵列来存不就好了，但是往下一看附带了2项限制：
:
: Note:
: You must do this in-place without making a copy of the array.
: Minimize the total number of operations.
这个问题仅需使用二个整数变数扫一次O(n)解决。
二个变数都是当作index，一个负责遇到0，一个负责遇到非0
遇到非0就把值copy到0的index，然後0的index + 1
最後跑完把0的index後面位置全部填0
int zero_i = 0, non_zero_i = 0;
while(non_zero_i < length_of_array) {
if(A[non_zero_i] != 0) {
A[zero_i] = A[non_zero_i];
zero_i += 1;
}
non_zero_i += 1;
}
while(zero_i < length_of_array) {
A[zero_i] = 0;
zero_i += 1;
}
学生时期练ACM到800题AC打住，结果工作写组语，转行IT也没考过这类白板。
解题这真的要视行业是否有需要才练，能把心态调整成兴趣是最好了。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.184.19.168
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1520071199.A.7F4.html
1F：→ lNishan: )( 03/03 18:06
2F：→ lNishan: 连这种错都抓不出来还好意思在前面炮人 ~_~ 03/03 18:08
编辑了一下，再请你看一下了。
3F：→ lNishan: 这样是对的了 第一题这样做是最佳解 03/03 18:20
4F：推 drajan: leetcode上讨论区不都有答案了? 03/03 18:24
5F：→ Uzak: 第2题你忘了排序 03/03 20:08
maintaining the relative order
在你的英文翻译是什麽。
※ 编辑: pttworld (111.184.19.168), 03/03/2018 20:17:03
6F：推 Uzak: sorry我看错，原原po例子刚好有排序我以为要排序 03/03 20:21
7F：→ Uzak: 没有仔细看他的题目 03/03 20:22
8F：推 elements: 推 03/03 20:46
9F：→ dnabossking: 记得我在code war解过一样的题目 03/03 22:48
10F：推 a110605: 推，这样的思绪解题变得很简单 03/04 10:48
11F：→ steven11329: 第一题是遇到"("一定要有")" 配对吧，)( 是invalid 03/05 07:59
12F：推 cateran: 第二题有c++一行解 03/05 08:26
13F：→ cateran: fill(remove(nums.begin(),nums.end(),0),nums.end(),0) 03/05 08:27
14F：推 sorryla: 一行解也只是把很多function塞在一行而已，还不是要解释 03/06 09:41
15F：→ sorryla: 每个function在做甚麽给面试官听 03/06 09:41