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讲计算过的结果存储起来。


public class Solution {
    public int numTrees(int n) {
        
        return numTree(1,n);  
    }
    
    int numTree(int start, int end)  
    {  
        if (start >= end)  
            return 1;  
  
        int totalNum = 0;  
        for (int i=start; i<=end; ++i)  
            totalNum += numTree(start,i-1)*numTree(i+1,end);  
        return totalNum;  
    }  
}

Advertisements
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 is hard-coded. As in the landscape mode, the frame.x will be larger than frame.x in portrait mode if centered, the frame.y will be smaller than frame.y in portrait mode though.

2.Memory: What memory management policy do you use for an object’s delegate? Why?

Use assign in non-ARC, and weak reference in ARC mode. The object should not grab ownership of the delegate object. Its life cycle should not be determined by the delegate message sender object.

Example: A view that has a button on it, the button delegate its touch event to the view. It’s easy that we find both view and button hold strong reference if the delegate is strong reference. To avoid retain cycle, the delegate should be weak.

3.UX: When would you use a home-screen navigation or tab-bar navigation?

DashBoard: What I like: Good feature overview; a “hub” for all functions and information. What I don’t like: All menu items have more or less the same priority; if there are many items they don’t fit on one screen.

Tab-bar: The bar would always be there, the home screen would be the most important functionality of the app. What I like: No navigation needed if you want to use the main functionality; many apps use this approach so I guess users are quite familiar with this pattern. What I don’t like: You shouldn’t put more than 5 items on the bar so we would have a “more” button and (see this article: The iPhone Tab Bar)

A: no more than 5 items, use tab bar,put the most important at the home screen. A lot of items of the same priority, use home style navigation.

4.Understanding of platform: What is toll-free bridging?

A: So there are two framework : Core Foundation & Foundation. Core Foundation is a C language programming API set. Foundation is objective-C language programming API set. The type will be CF and NS. To use them in iOS, need to cast CF to NS if needed. Toll-free bridge is the feature to realize it.

Tip: __bridge_transfer will treat CF object as ARC. _bridge need to be released manually.

5.How will you describe iOS manual memory management for a new developer in few words?

Every object exists in memory must have a reference counter more than 0, retain the object reference will increase the counter by 1, assign will not change counter, but use the object reference, release will decrease the counter by 1, copy will copy the object in memory and retain the new allocated object reference. When the counter is 0 the object will be freed, any more references to the object will return nil.

6.How would you implement call for canceling queued blocks with dispatch_after?

A: first, grand central dispatch(GCD) is a low-level way of managing things. Anything currently running in the queue cannot be stopped.

dispatch_after will dispatch things after set-up delay time.


@interface Canceller : NSObject

@property (atomic, strong) BOOL shouldCancel;

@end


@implementation Canceller;
//synthesize the shouldCancel, create ivar for it
@synthesize shouldCancel = _shouldCancel;

@end




static void test(int a){
    static Canceller * canceller = nil;

    if(q){
        [canceller setShouldCancel:YES];
        [canceller release];
        dispatch_suspend(q);
        dispatch_release(q);
        q=nil;
    }
    canceller = [[Canceller alloc] init];
    q=dispatch_get_global_queue(0,0);
    dispatch_async(q,^ {
        while(![canceller shouldCancel]){NSLog(@"query %d",a);sleep(2);}
    });

}


int main(int argc, const char* argv[]){
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    test(1);

    //blah blah blah

    test(2);

    while(1){}
    [pool release];
    return 0;
}

The above code should stop the test(1) and continue to run on test(2), notice that it is in non-ARC mode, will continue to write about cases in ARC mode.

The whole point is: if you are sure you need to stop the queue at some point, u need to give a boolean sign to the certain queued task, so you are able to check the boolean when really to execute the queue.

To be continued;

7. Find the kth point that is closest to the origin.

This question is basically asking: find the kth minimum value from an unsorted array.

The easiest solution is to use insertion sort, so we will find the minimum value in each round, until we find the kth minimum in the array. The time comlexity is O(kn).

A better solution can use quick select. The same rule as in quick sort, we randomly assign a pivot in the array, and scan the array, put the smaller element in the left of pivot and bigger in the right side. Unlike in the quick sort, since we only need to find the kth minimum, we dont need to check both sides. If there are x > k elements in the left, we only need to sort the left half, vice versa, only when the pivot reposition is the same as k, we can simply return the [array objectAtIndex:k] value.

Here is the objc code for the method:


#import <Foundation/Foundation.h>

@interface Solution : NSObject

- (int)find:(int)position InPoints:(NSArray *)array;

@end



#import "Solution.h"

@implementation Solution

- (int)find:(int)position InPoints:(NSMutableArray *)array{
    
    
    
    return [self quickSelect:position-1 InPoints:array from:0 to:(int)[array count]-1];
    
    
}

- (int)quickSelect:(int)position InPoints:(NSMutableArray *)array from:(int) start to:(int)end{
    
    
    int result = [self partition:array from:start to:end];
    if(result == position)
        return [[array objectAtIndex:result] intValue];
    
    if(result > position){
        
        return [self quickSelect:position InPoints:array from:start to:result - 1];
        
    }else{
        
        return  [self quickSelect:position InPoints:array from:result + 1 to:end];
    }
    
}



- (int)partition:(NSMutableArray *)array from:(int)start to:(int)end{
    
    
    int pivot = [[array objectAtIndex:start] intValue];
    
    int low = start;
    int high = end;
    
    while(low < high){
        
        while(pivot > [[array objectAtIndex:low] intValue])
            low ++;
        
        while(pivot < [[array objectAtIndex:high] intValue])
            high --;
        
        if(low < high){
            
            NSNumber *temp = [array objectAtIndex:low];
            [array setObject:[array objectAtIndex:high] atIndexedSubscript:low];
            [array setObject:temp atIndexedSubscript:high];
            
        }else{
            
            return low;
        }
        
    }
    
    return low;
    
}


@end

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的基本语法:

int (^testBlock)(int a, int b) = ^(int a, int b){
   return a + b;
}

定义一个叫testBlock的block,等号右边为实现。
不过在实际应用过程中,我经常用typedef定义一种类型的block,具体的代码实现则可以等到使用时按具体情况编写。使用如下:


//define a block type, takes boolean and returned object, void return
typedef void ^(CompletionBlock)(BOOL success, NSArray *objectsOrNil);

//use settingManger for example
@class  SettingManager

//insert the block in method  --- interface
- (void)update:(CompletionBlock)completionBlock;

//---implementation
- (void)update:(CompletionBlock)completionBlock{

   //previous upload
   if(update fail){
      completionBlock(NO, nil);
   }else{
      completionBlock(YES, returnedObjects);
   };

}


//use the above method in reality
[settingManager update:^(BOOL success, NSArray objectsOrNil){

     if(success){
    
     }else{

     };

}];


上面是一种常见的用法,completionBlock通常使用成功或失败两种情况,并且返回相关信息。由于不用像delegate method那样分开和update执行分开,block显得更加直观。

下面讨论一下block的作用域:
1. 当block定义在某函数内部时,allocation位于栈上,也就是说当函数执行结束,栈内内容会被释放,再使用这个block有可能会导致程序的崩溃.


  CompletionBlock blockTest; 

  {

    CompletionBlock blockTest = ^(BOOL success, NSArray ObjectsOrNil){
       NSLog("hello");
    }
  } 

blockTest(YES,nil);

2. block也可以在堆上,如果想要将其转移到堆上,应在定义时加上strong指针(ARC)情况下,这样block就可以有效的继续存在了!


__strong CompletionBlock blockTest;

  {

       blockTest = ^(BOOL success, NSArray ObjectsOrNil){
       NSLog("hello");
    }
  } 

blockTest(YES,nil);

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 block的那篇,总之如果在block中调用外围变量,记住加上__block。

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使用的初始化是正确的。


public List<List<Integer>> permute(int[] num) {
        
        boolean[] visited = new boolean[num.length];
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        for(int i = 0 ; i < num.length; i ++)
            visited[i] = false;
            
        List<Integer> subList = new ArrayList<Integer>();
        generate(list,subList, num, visited);
        
        return list;
    }
    
    private void generate(List<List<Integer>> list, List<Integer> subList, int[] num, boolean[] visited){
        
        if(subList.size() == num.length){
            
            list.add(new ArrayList<Integer>(subList));
            return;
        }
        
        
        for(int i = 0; i < num.length; i ++){
        
            if(visited[i] == false){
                
                subList.add(num[i]);
                visited[i] = true;
                generate(list, subList, num, visited);
                visited[i] = false;
                subList.remove(subList.size()-1);
                
            }
        }
        
    }

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

和第一题类似,只是多了需要检验重复的情况。方法还是DFS,只是我们发现相同元素如果顺序的执行的话其实结果是重复的。

例如[1,1,2]
对第一个元素 先取 1, 剩下的选择就是 [1,2]
而如果从第二个元素开始 取 1, 剩下可以选择的仍然是[1,2]
这不是我们想要的情况,因此我们应该跳过连续选择相同元素的情况。

如何能保证我们不会选择同样地元素进行recursive处理呢? 我这里用的built in 的sort 方法,保证有相同元素它们就必然相邻,这样的话,当我们对不重样的第一个元素处理完发现后面是重复元素时,我们就跳过它。


public List<List<Integer>> permuteUnique(int[] num) {
        
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        
        ArrayList<Integer> number = new ArrayList<Integer>();
        boolean visited[] = new boolean[num.length];
        
        
        for(int i = 0; i < num.length; i ++)
            number.add(num[i]);
        
        Collections.sort(number);
        List<Integer> subList = new ArrayList<Integer>();
        generate(list, subList, number, visited);
        
        return list;
        
    }
    
    private void generate(List<List<Integer>> list, List<Integer> subList, ArrayList<Integer> number, boolean[] visited){
        
        if(subList.size() == number.size()){
            List<Integer> copyList = new ArrayList<Integer>(subList);
            list.add(copyList);
            return;
        }
        
        for(int i = 0; i < number.size(); i ++){
            
            if(visited[i] == false){
                
                subList.add(number.get(i));
                visited[i] = true;
                //recurse
                generate(list, subList, number, visited);
                
                visited[i] = false;
                subList.remove(subList.size()-1);
                while(i + 1 < number.size() && number.get(i) == number.get(i+1))
                    i ++;
            }
            
        }
    
    }

把自己有疑惑的问题和想法写出来,下次遇到避免重复一样的问题。

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 any intervening characters.

For example, given:
S: “barfoothefoobarman”
L: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

这道题目很容易想到如何使用brute-force解决:随着 S 字符串逐个判断是否包含于 L 里。 由于 L 中的string 可以被重复出现,例如 [“foo”, “bar” , “foo”], 在这种情况下,必须在 S 中让 “foo” 字符串出现两次, 我使用的是 HashMap<String, Integer> 来保证相同字符的出现次数不会有问题。在每次做验证前,复制map带入保证有效性。

考虑的枝剪 : 由于必须包含所有字符, 因此index 必然会是小于 (S.length – count * word.length).

下面是我的java 代码,下回会根据网上的优化代码进行修改:

public List<Integer> findSubstring(String S, String[] L) {

        List<Integer> list = new ArrayList<Integer>();

        //if it's 0 length
        if(L.length == 0)
            return list;

        int len = L[0].length();

        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(int i = 0; i < L.length; i ++){

            if(map.get(L[i]) == null)
                map.put(L[i],1);
            else
                map.put(L[i],map.get(L[i]) + 1);

        }

        for(int i = 0; i < S.length() - L.length*len + 1; i ++){

            HashMap<String,Integer> copyMap = new HashMap<String, Integer>(map);
            if(matchStr(copyMap, S.substring(i),len))
                list.add(i);

        }

        return list;
    }

    private boolean matchStr(HashMap<String,Integer> map, String s, int len){

        int start = 0;

        while(!map.isEmpty()){

            String temp = s.substring(start, start + len);

            if(map.get(temp) != null){

                int count = map.get(temp);
                count --;
                if(count == 0)
                    map.remove(temp);
                else
                    map.put(temp, count);

                start += len;
                continue;
            }else
                return false;

        }

        return true;

    }

第一篇算法训练, 希望以后能够越写越专业详细。 每天都要加油!

Posted in 算法题 | Tagged | Leave a comment