Airbnb电面

palemoon 发表于 2015-7-27 06:26
楼主用的是python. 我猜如果用java面试官会统一成return一个array吧, 只是第一个情况里面只有一个元素

应该是这样的，之前面试twitter也被问到了这道题，nested list, 嵌套的列表，要求打平结构。

得用stack来做。

jiebour 发表于 2015-7-27 07:05
所以，这个题的方法是什么？  stack嘛？

嗯,应该是stack加recursion

palemoon 发表于 2015-7-27 12:21
嗯,应该是stack加recursion

stack了为什么还有recurrsion，stack就是recursion的展开版本。。。。

I am not sure if I understand correctly? here is my code.

recursion

StringBuilder input = null;
        public List<Object> realParser(){

                List<Object> result = new LinkedList<Object>();
               
                StringBuilder sb = new StringBuilder();
                while( input.length() > 0 ){
                       
                        char c = input.charAt(0);
                        input.deleteCharAt(0);
                       
                        if( c == '[' ){
                                List<Object> tmp = realParser();
                                result.add(tmp);
                        }else if( c == ']' ){
                                if( sb.length() != 0 ){
                                        result.add( sb.toString());
                                        sb.setLength(0);
                                }
                                return result;
                        }else if( c == ',' ){
                                if( sb.length() != 0 ){
                                        result.add( sb.toString());
                                        sb.setLength(0);
                                }
                        }else{
                                sb.append( c );
                        }
                }
                if( sb.length() != 0 ){
                        result.add(sb.toString());
                        sb.setLength(0);
                }
                return result;
        }
       
        public List<Object> parse(String input){
               
                this.input = new StringBuilder(input);
                return realParser();
               
        }

blakesen 发表于 2015-7-27 09:53
customized 一個 DS, eg

public class specialNode {

你的specialnode只能存一个val？那[1, 2, 3, [4, 5]]  
你怎么办？

jiebour 发表于 2015-7-28 06:44
你的specialnode只能存一个val？那[1, 2, 3, [4, 5]]  
你怎么办？

存在arraylist

jiebour 发表于 2015-7-27 13:06
stack了为什么还有recurrsion，stack就是recursion的展开版本。。。。

你说的的stack是什么意思?怎么用呢?

我的想法是:用stack找到matching的()pair,然后对它做recursion.

palemoon 发表于 2015-7-27 06:26
楼主用的是python. 我猜如果用java面试官会统一成return一个array吧, 只是第一个情况里面只有一个元素

如果java只要求返回一个array的话，那这个题不就分分钟变成！纯！字符串解析了？不用任何别的数据结构了

贴一个code

1. class Solution():
   
2.     def miniParser(self, s):
   
3.         if s[0]!="[":
   
4.             return int(s)
   
5.         stack = []
   
6.         pos = 0
   
7.         cur = []
   
8.         while pos<len(s):
   
9.             if s[pos]=="[":
   
10.                 stack.append(cur)
    
11.                 next = []
    
12.                 cur = next
    
13.                 pos += 1
    
14.             elif s[pos]=="]":
    
15.                 prev = stack.pop()
    
16.                 prev.append(cur)
    
17.                 cur = prev
    
18.                 pos += 1
    
19.             elif s[pos].isdigit():
    
20.                 end = pos
    
21.                 while end<len(s) and s[end].isdigit():
    
22.                     end += 1
    
23.                 num = int(s[pos:end])
    
24.                 cur.append(num)
    
25.                 pos = end
    
26.             else:
    
27.                 pos += 1
    
28. 
    
29.         return cur[0]
    
30. 
    
31. 
    
32. sol = Solution()
    
33. result = sol.miniParser("[123,456,[788,799,833],[[]],10,[]]")
    
34. print(result)

复制代码

use stack :

def parse(s):
    stk = []
    i = 0
    while i < len(s):
        if s[i] == '[':
            stk.append(s[i])
            i += 1
        elif s[i].isdigit():
            j = i + 1
            while j < len(s) and s[j].isdigit():
                j += 1
            x = int(s[i:j])
            stk.append(x)
            i = j
        elif s[i] == ',':
            i += 1
        else: # s[i] == ']'
            t = []
            while stk[-1] != '[':
                t.append(stk.pop())
            stk.pop()
            t.reverse()
            stk.append(t)
            i += 1
    return stk