传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 8096|回复: 19
收起左侧

Airbnb电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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



评分

4

查看全部评分

本帖被以下淘专辑推荐:

blakesen 发表于 2015-7-27 09:53:52 | 显示全部楼层
billyli8866 发表于 2015-7-26 08:24
java的array元素不能又是数又是array吧,用java怎么做呢。。。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
customized 一個 DS, eg
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public class specialNode {. visit 1point3acres.com for more.

}. from: 1point3acres.com/bbs

补充内容 (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);
                        }else if( c == ']' ){. Waral 鍗氬鏈夋洿澶氭枃绔,
                                if( sb.length() != 0 ){. more info on 1point3acres.com
                                        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){. Waral 鍗氬鏈夋洿澶氭枃绔,
                . 1point 3acres 璁哄潧
                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
能详细一点么...我没怎么看懂...

就是输入一个整数的字符串, 要返回一个整数
输入一个数组的字符串, 要返回一个数组, 里面每一个元素是要么一个整数, 要么是一个数组
. from: 1point3acres.com/bbs 但是注意数组可以多层嵌套. 楼主就是这里理解错了,最后才发现要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怎么做呢。。。

楼主用的是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, 嵌套的列表,要求打平结构。. visit 1point3acres.com for more.

得用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
. 1point3acres.com/bbs
stack了为什么还有recurrsion,stack就是recursion的展开版本。。。。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-28 06:44:14 | 显示全部楼层
blakesen 发表于 2015-7-27 09:53
customized 一個 DS, eg

public class specialNode {
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你的specialnode只能存一个val?那[1, 2, 3, [4, 5]]  
你怎么办?
回复 支持 反对

使用道具 举报

blakesen 发表于 2015-7-28 06:56:54 | 显示全部楼层
jiebour 发表于 2015-7-28 06:44. 1point 3acres 璁哄潧
你的specialnode只能存一个val?那[1, 2, 3, [4, 5]]  . 1point 3acres 璁哄潧
你怎么办?
. 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 = []
  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.         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] == '[':
.鏈枃鍘熷垱鑷1point3acres璁哄潧            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]). Waral 鍗氬鏈夋洿澶氭枃绔,
            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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-23 08:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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