一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4753|回复: 19
收起左侧

Airbnb电面

[复制链接] |试试Instant~ |关注本帖
palemoon 发表于 2015-7-26 03:25:43 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Airbnb - 内推 - 技术电面 |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
实现一个mini parser, 输入是以下格式的string:"324" or"[123,456,[788,799,833],[[]],10,[]]"
要求输出:324 or [123,456,[788,799,833],[[]],10,[]]
也就是将字符串转换成对应的格式的数据.
其实题不算难,楼主答得不好,面完就知道挂了



评分

4

查看全部评分

本帖被以下淘专辑推荐:

blakesen 发表于 2015-7-27 09:53:52 | 显示全部楼层
billyli8866 发表于 2015-7-26 08:24
java的array元素不能又是数又是array吧,用java怎么做呢。。。

customized 一個 DS, eg

public class specialNode {

}. 1point 3acres 璁哄潧

补充内容 (2015-7-27 09:55):
public class specialNode {
   int val;
   ArrayList<specialNode> contents = new ArrayList<>();
   ....
}
回复 支持 1 反对 0

使用道具 举报

homi 发表于 2015-7-28 05:55:13 | 显示全部楼层
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>();
                -google 1point3acres
                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 == ']' ){. Waral 鍗氬鏈夋洿澶氭枃绔,
                                if( sb.length() != 0 ){
                                        result.add( sb.toString());
                                        sb.setLength(0);
                                }
                                return result;
                        }else if( c == ',' ){
                                if( sb.length() != 0 ){-google 1point3acres
                                        result.add( sb.toString());. 鍥磋鎴戜滑@1point 3 acres
                                        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);. 1point3acres.com/bbs
                return realParser();
               
        }
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-7-26 03:42:44 | 显示全部楼层
能详细一点么...我没怎么看懂...
回复 支持 反对

使用道具 举报

 楼主| palemoon 发表于 2015-7-26 03:55:45 | 显示全部楼层
readman 发表于 2015-7-26 03:42
能详细一点么...我没怎么看懂...

就是输入一个整数的字符串, 要返回一个整数
输入一个数组的字符串, 要返回一个数组, 里面每一个元素是要么一个整数, 要么是一个数组
但是注意数组可以多层嵌套. 楼主就是这里理解错了,最后才发现要handle这个情况, 已经来不及code了, 就挂了
回复 支持 反对

使用道具 举报

tianz 发表于 2015-7-26 05:31:39 | 显示全部楼层
hmm 有点神奇。input是string output不确定吗?
回复 支持 反对

使用道具 举报

 楼主| palemoon 发表于 2015-7-26 06:30:09 | 显示全部楼层
tianz 发表于 2015-7-26 05:31
hmm 有点神奇。input是string output不确定吗?

output要么是integer, 要么是array
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-26 07:31:29 | 显示全部楼层
那是怎么返回啊。是打印吗?
回复 支持 反对

使用道具 举报

billyli8866 发表于 2015-7-26 08:24:42 | 显示全部楼层
java的array元素不能又是数又是array吧,用java怎么做呢。。。
回复 支持 反对

使用道具 举报

 楼主| palemoon 发表于 2015-7-27 06:26:36 | 显示全部楼层
billyli8866 发表于 2015-7-26 08:24
java的array元素不能又是数又是array吧,用java怎么做呢。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主用的是python. 我猜如果用java面试官会统一成return一个array吧, 只是第一个情况里面只有一个元素
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-27 07:05:03 | 显示全部楼层
所以,这个题的方法是什么?  stack嘛?
回复 支持 反对

使用道具 举报

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

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

得用stack来做。
回复 支持 反对

使用道具 举报

 楼主| palemoon 发表于 2015-7-27 12:21:29 | 显示全部楼层
jiebour 发表于 2015-7-27 07:05
所以,这个题的方法是什么?  stack嘛?

嗯,应该是stack加recursion
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-27 13:06:10 | 显示全部楼层
palemoon 发表于 2015-7-27 12:21
嗯,应该是stack加recursion
-google 1point3acres
stack了为什么还有recurrsion,stack就是recursion的展开版本。。。。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-28 06:44:14 | 显示全部楼层
blakesen 发表于 2015-7-27 09:53
customized 一個 DS, eg
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
public class specialNode {

你的specialnode只能存一个val?那[1, 2, 3, [4, 5]]  
你怎么办?
回复 支持 反对

使用道具 举报

blakesen 发表于 2015-7-28 06:56:54 | 显示全部楼层
jiebour 发表于 2015-7-28 06:44
你的specialnode只能存一个val?那[1, 2, 3, [4, 5]]  
你怎么办?

存在arraylist
回复 支持 反对

使用道具 举报

 楼主| palemoon 发表于 2015-7-28 10:20:32 | 显示全部楼层
jiebour 发表于 2015-7-27 13:06
stack了为什么还有recurrsion,stack就是recursion的展开版本。。。。

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

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

使用道具 举报

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

如果java只要求返回一个array的话,那这个题不就分分钟变成!纯!字符串解析了?不用任何别的数据结构了
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-20 15:35:28 | 显示全部楼层
贴一个code
  1. class Solution():. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  2.     def miniParser(self, s):
  3.         if s[0]!="[":
  4.             return int(s)
  5.         stack = []. From 1point 3acres bbs
  6.         pos = 0
  7.         cur = []
  8.         while pos<len(s):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.             if s[pos]=="[":
  10.                 stack.append(cur)
  11.                 next = []
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.                 cur = next
  13.                 pos += 1
  14.             elif s[pos]=="]":. 1point 3acres 璁哄潧
  15.                 prev = stack.pop().1point3acres缃
  16.                 prev.append(cur)
  17.                 cur = prev
  18.                 pos += 1
  19.             elif s[pos].isdigit():.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                 end = pos. 1point 3acres 璁哄潧
  21.                 while end<len(s) and s[end].isdigit():
  22.                     end += 1. visit 1point3acres.com for more.
  23.                 num = int(s[pos:end])
  24.                 cur.append(num)
  25.                 pos = end.鐣欏璁哄潧-涓浜-涓夊垎鍦
  26.             else:
  27.                 pos += 1

  28.         return cur[0]


  29. sol = Solution()
  30. result = sol.miniParser("[123,456,[788,799,833],[[]],10,[]]")
  31. print(result)
复制代码
回复 支持 反对

使用道具 举报

newlxnewlx 发表于 2016-1-28 15:46:03 | 显示全部楼层
use stack :
.鐣欏璁哄潧-涓浜-涓夊垎鍦
def parse(s):. from: 1point3acres.com/bbs
    stk = []
    i = 0
    while i < len(s):
        if s[i] == '[':
            stk.append(s[i])
            i += 1-google 1point3acres
        elif s[i].isdigit():
            j = i + 1.1point3acres缃
            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). more info on 1point3acres.com
            i += 1
    return stk
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表