Monthly Archives: July 2014

Unique Binary Search Trees leetcode

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s. 这道题目,乍一看很吓人,其实仔细分析,有如下规律:当我们在1-n中选择i作为根,其可能出现的情况为[1,i-1]中BST种类 和 [i+1,n]中BST种类的 乘积, 因此n个节点的总可能性就是把1到n逐步作为根节点的情况总数,而每一个情况又可以按照同样的方式继续计算,因此,我们可以将问题逐步缩小。tip:可以用DP讲计算过的结果存储起来。

Posted in 算法题, Tree | Leave a comment

iOS developer facebook面试问题

A few facebook iOS interview questions, 查阅了一些资料,整理了一下。 1.Views: A square subview is centered when viewed in landscape. When the device is rotated to portrait, the square ends up closer to the top-right corner. What’s wrong? A:The frame of the subview … Continue reading

Posted in Uncategorized | Leave a comment

iOS UIView frame, bounds, center 区别与用法

Frame是一个view在它的superview坐标系下的position和size,从top left开始向右(x坐标)和下扩展(y坐标)。 Bounds代表一个view在其本身坐标系下的position和size。 Center是view在其superview坐标系下的中心点坐标。 在放置UIView在superview的时候,应当使用frame。 从网上找来一张神图: 注意,当View被rotate的时候,frame.size将不再等于bounds.size,因为坐标系不同。

Posted in iOS | Tagged | Leave a comment

iOS block用法&注意点

看了好几篇和block有关的总结, 也打算来总结一下,让自己记得更清楚一些。 block是一种C language level的语法,其本质是一段代码,但是在objective c中,我们可以用指针把block当做参数,变量进行传递,也就是说这段代码,可以被当做一个参数,带入另一个函数中执行。 这会极大的方便许多之前编写麻烦的delegate method,因为可以续写代码意味着我们不需要再去conform protocol而只需要在初始化后面的跟着的completion block中写我们需要的代码。 先来看block的基本语法: 定义一个叫testBlock的block,等号右边为实现。 不过在实际应用过程中,我经常用typedef定义一种类型的block,具体的代码实现则可以等到使用时按具体情况编写。使用如下: 上面是一种常见的用法,completionBlock通常使用成功或失败两种情况,并且返回相关信息。由于不用像delegate method那样分开和update执行分开,block显得更加直观。 下面讨论一下block的作用域: 1. 当block定义在某函数内部时,allocation位于栈上,也就是说当函数执行结束,栈内内容会被释放,再使用这个block有可能会导致程序的崩溃. 2. block也可以在堆上,如果想要将其转移到堆上,应在定义时加上strong指针(ARC)情况下,这样block就可以有效的继续存在了! 3. block 不但可以修改传入的变量,也可以修改作用域内的任何变量, 但是必须在前面加上__block修饰符,不然会报错,另外。即使外部变量不会在block中被修改,我们也应该尽量加上__block字样,因为不加入修饰符会将该变量在block定义处之前的value存成常量供block使用,如果调用block的地方在函数最后,而block定义之后该变量经过了大量改变,那么我们想要的结果会与得到的结果南辕北辙。 这大致就是block比较重要的注意点。 给几个我觉得比较好的相关link: http://www.cnblogs.com/biosli/archive/2013/05/29/iOS_Objective-C_Block.html http://blog.csdn.net/yhawaii/article/details/7556739 http://yhawaii.github.io/ios/2013-12-20-iOS-Block.html 最近又偷懒了,老想着和室友打dota2,你个学渣!

Posted in iOS | Tagged | Leave a comment

Facebook HR关于iOS developer的面试题

今天为了等FB HR的电话推迟了上午的工作,真的太不好意思了。一定要加倍努力的把公司的产品做好才是硬道理,不管在哪里工作,都应当尽心尽力把分内分外的工作做妥当。 言归正传,其实去年就和F家的HR联系密切,可是因为自己当时算法水平太差,一直没敢去面试,最近一联系发现他已经不管mobile team hiring了,于是把我推给了另一个HR。 这个HR吧,搞笑的是她还不知道我电话,直到约定的时间过了她才发现。之后一路聊下来两个人倒都感觉不错,不过最后她提出要问我iOS的技术问题,把我吓了一跳,因为我一直以为HR是不会问技术问题的,这真的是完全没有防备。 问题都是选择题,可单选可多项。 第一题,UIView.frame 和 UIView.bounds 区别。 easy 第二题,NSString, NSNull, NSInteger, NSNotification 哪个不能被message release。 easy 第三题,block 的性质,具体选项记不住了,大概就是有类似于可以被当做参数,选的是不能被subclass。 第四题, 从头到尾没听明白,吓出一身冷汗,大概是为block的 underscore什么时候可以被使用,这点真的完全没注意过,只好从实说不记得,回头要弄清楚。 第五题,ARC代指什么 easy。 然后她说除了不记得的都做对了,可以去参加inital interview,我这才松了一口气,倒在HR这里可是滑天下之大稽了。 :( 下面要做的就是老老实实准备iOS的面试了,顺便把许多冷门的知识点都补上,以前用java写代码现在可用不上了,得用ojective C 一遍写出bug free 的code, 加油! ————————————————————————————————————————————— 通过前两天的学习,第五题就很清楚了,应该是问block要调用自身定义外围的参数的时候,什么时候应该加 __block, 实际上如果在定义内调用不改变也是可以的,但是会有风险, 详细应当参照iOS … Continue reading

Posted in iOS | Tagged | Leave a comment

Permutations I & Permutations II

Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 用DFS的方法,recursive不断寻找下一个数字,用一个boolean的数组visited来记录已经访问过的数字,避免重复。在访问结束的时候,只有满足条件sublist.size() 和 num.length 相等的情况下才能拷贝sublist并加入list中间。 我出现的问题: 由于对recursive的过程不够熟悉,所以在每次loop前拷贝了当前的sublist用在下一层中, 这样会大大增加space complexity,也是完全不必要的, 因为recursive不会同时执行两个loop,所以在某层recursive结束后我们只要删除加入的数字并且修改visited情况就可以保证sublist对下次loop使用的初始化是正确的。 Permutations II Given a collection of … Continue reading

Posted in Uncategorized | Leave a comment

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without … Continue reading

Posted in 算法题 | Tagged | Leave a comment