一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 5088|回复: 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,[]]. From 1point 3acres bbs
也就是将字符串转换成对应的格式的数据.
其实题不算难,楼主答得不好,面完就知道挂了
.鐣欏璁哄潧-涓浜-涓夊垎鍦

-google 1point3acres

评分

4

查看全部评分

本帖被以下淘专辑推荐:

blakesen 发表于 2015-7-27 09:53:52 | 显示全部楼层
billyli8866 发表于 2015-7-26 08:24. Waral 鍗氬鏈夋洿澶氭枃绔,
java的array元素不能又是数又是array吧,用java怎么做呢。。。

customized 一個 DS, eg

. visit 1point3acres.com for more.public class specialNode {

}

补充内容 (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>();
               
                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);. From 1point 3acres bbs
                        }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());. from: 1point3acres.com/bbs
                                        sb.setLength(0);
                                }
                        }else{
                                sb.append( c );. 1point3acres.com/bbs
                        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                if( sb.length() != 0 ){
                        result.add(sb.toString());
                        sb.setLength(0);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }
                return result;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        .鏈枃鍘熷垱鑷1point3acres璁哄潧
        public List<Object> parse(String input){
               
                this.input = new StringBuilder(input);
                return realParser();
               
        }
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

就是输入一个整数的字符串, 要返回一个整数. more info on 1point3acres.com
输入一个数组的字符串, 要返回一个数组, 里面每一个元素是要么一个整数, 要么是一个数组
但是注意数组可以多层嵌套. 楼主就是这里理解错了,最后才发现要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怎么做呢。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主用的是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. visit 1point3acres.com for more.
楼主用的是python. 我猜如果用java面试官会统一成return一个array吧, 只是第一个情况里面只有一个元素

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

得用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

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]]  . from: 1point3acres.com/bbs
你怎么办?
回复 支持 反对

使用道具 举报

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

存在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 = []
  6.         pos = 0
  7.         cur = []. 鍥磋鎴戜滑@1point 3 acres
  8.         while pos<len(s):-google 1point3acres
  9.             if s[pos]=="[":
  10.                 stack.append(cur)
  11.                 next = [].鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.                 cur = next. 1point 3acres 璁哄潧
  13.                 pos += 1
  14.             elif s[pos]=="]":
  15.                 prev = stack.pop()
  16.                 prev.append(cur)
  17.                 cur = prev. more info on 1point3acres.com
  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.         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):
    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().1point3acres缃
            t.reverse()
            stk.append(t)
            i += 1
    return stk
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-18 20:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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