一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 9642|回复: 32
收起左侧

airbnb电面

[复制链接] |试试Instant~ |关注本帖
mm豆 发表于 2015-4-18 01:18:10 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Airbnb - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
1.
题目是关于如何Parse csv file:举个例子,给定一个CSV文件,格式是 “some_name|some_address|some_phone|some_job”,要求输出Json format “{name:some_name, address:some_addres,phone:some_phone, job:some_job}”
特殊情为两个引号之间的分号,不可作为分割字符 http://itjob.io/post/349
/*
John,                        Smith,                john.smith@gmail.com,        Los Angeles,                1
Jane,                        Roberts,        janer@msn.com,                "San Francisco, CA",        0
"Alexandra ""Alex""",        Menendez,        alex.menendez@gmail.com,        Miami,                        1
"""Alexandra Alex"""
John|                        Smith |                john.smith@gmail.com |         Los Angeles |                1
Jane|                        Roberts|        janer@msn.com|                San Francisco, CA|        0
Alexandra "Alex"|        Menendez|        alex.menendez@gmail.com|        Miami|                        1
"Alexandra Alex"
*/
要考虑 quote, escape \得情况
2.
Given a method decode(testEncStr) which will return the decoded int id if testEncStr is decodeable or will throw an exception (or return null) if not, implement a new method decodeFind(String badEncStr) which takes a string and returns the decoded int id
3.给一个2d array,要求写一个顺序访问这个2d array的Iterator,包括hasNext()与next()。注意2d array的每行中元素的个数可能不一样,也可能为空。跪在这最后一面上了。
二面的时候他忘了问culture, 所以加了一面。最后跪在最后一面上了,估计是culture不fit。 求加分,求安慰

评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| mm豆 发表于 2015-6-16 21:07:03 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
Often, we want to encode raw IDs in our database by hiding them behind some
2-way decodeable hash. So, a URL which would have at one time been:. 1point 3acres 璁哄潧
. 1point3acres.com/bbs
https://www.airbnb.com/rooms/848662

becomes. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. Waral 鍗氬鏈夋洿澶氭枃绔,
https://www.airbnb.com/rooms/kljJJ324hjkS_

We decode the ID kljJJ324hjkS_ to 848662 on our backend and serve the
relevant content. at some point, we start getting 404 errors from clients
requesting a certain URL of the form

https://www.airbnb.com/rooms/kljjj324hjks_. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

This can happen if certain clients, email services, or url shorteners "
sanitize" the url. Unfortunately, this change breaks decoding and the
resource cannot be found.. more info on 1point3acres.com
To assess how big of a deal this is, we may want to recover the IDs of the . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
targets that were 404ing..鏈枃鍘熷垱鑷1point3acres璁哄潧

Your task:
Given a method decode(testEncStr) which will return the decoded int id if
testEncStr is decodeable or will throw an exception or return null (. 鍥磋鎴戜滑@1point 3 acres
depending on the language) if not, implement a new method decodeFind(String
badEncStr) which takes a string and returns the decoded int id.

补充内容 (2015-6-16 21:07):
这是第二题
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-6-17 22:30:15 | 显示全部楼层
关注一亩三分地微博:
Warald
第一题
class Solution {
          public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            //#1
            ArrayList<String> output = parseCSV("John,Smith,john.smith@gmail.com,Los Angeles,1");
.鏈枃鍘熷垱鑷1point3acres璁哄潧            String strOutput = printStr(output);
            System.out.println(strOutput);
            //#2
            output = parseCSV("Jane,Roberts,janer@msn.com,\"San Francisco, CA\",0");
            strOutput = printStr(output);
            System.out.println(strOutput);
            output = parseCSV("\"Alexandra \"\"Alex\"\"\",Menendez,alex.menendez@gmail.com,Miami,1");. 1point3acres.com/bbs
            strOutput = printStr(output);
            System.out.println(strOutput);
          }. 1point 3acres 璁哄潧

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷          public static ArrayList<String> parseCSV(String str) {
            ArrayList<String> res = new ArrayList<String>();
            boolean inQuote = false;
            StringBuilder buffer = new StringBuilder();
            for(int i = 0; i < str.length(); i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
              if(inQuote) {
                if(str.charAt(i) == '"') {
                  if(i == str.length()-1) {
                    res.add(buffer.toString());
                    return res;-google 1point3acres
                  } else if(str.charAt(i+1) == '"') {-google 1point3acres
                    buffer.append('"');
                    i++;
                  } else {
                    res.add(buffer.toString());. 1point3acres.com/bbs
                    buffer.setLength(0);
                    inQuote = false;.1point3acres缃
                    i++;
                  }
                } else buffer.append(str.charAt(i));
              } else {
                if(str.charAt(i) == '"') {
                  inQuote = true;
                } else if( str.charAt(i) == ',') {
                  res.add(buffer.toString());
                  buffer.setLength(0);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                } else {
                  buffer.append(str.charAt(i));
                }. visit 1point3acres.com for more.


              }. more info on 1point3acres.com

            }
            if(buffer.length() > 0) res.add(buffer.toString());
            return res;
          }

          public static String printStr(ArrayList<String> list) {
            StringBuilder res = new StringBuilder();. visit 1point3acres.com for more.
            for(int i = 0; i < list.size()-1; i++) {
              res.append(list.get(i));
              res.append('|');
            }. more info on 1point3acres.com
            res.append(list.get(list.size()-1));
            return res.toString();
          }
        }
public static ArrayList<String> parseCSV1(String str) {.1point3acres缃
        boolean mark = false;.1point3acres缃
        boolean dMark = false;
        ArrayList<String> ret = new ArrayList<String>();
        StringBuilder part = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
//                if (dMark) {
//                        if(c == '\"'){
//                                if (i == str.length() - 1) {
//                                        ret.add(part.toString());
//                                        return ret;
//                                } else if (str.charAt(i + 1) == '\"') {
//                                        //""asdf"". 1point3acres.com/bbs
//                                        dMark = false;
//                                        part.append('\"');
//                                        i++;. 1point 3acres 璁哄潧
//                                } else
//                                        part.append(c);
//                        }else part.append(c);
//                } else
                if (mark) {
                        if (c == '\"') {
                                if (i == str.length() - 1) {
                                        ret.add(part.toString());
                                        return ret;
                                } else if (str.charAt(i + 1) == '\"') {
                                        // “asdf“fdsa”fdas”. 鍥磋鎴戜滑@1point 3 acres
                                        part.append('\"');
                                        i++;. Waral 鍗氬鏈夋洿澶氭枃绔,
                                } else. more info on 1point3acres.com
                                        mark = false;.1point3acres缃
                        } else
                                part.append(c);
                } else {
                        if (c == ',') {
                                ret.add(part.toString()); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                part.setLength(0);
                        } else if (c == '\"') {
                                if (i == str.length() - 1) {
                                        ret.add(part.toString());
                                        return ret;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                }
//                                else if (str.charAt(i + 1) == '\"') {
//                                        part.append('\"');
//                                        dMark = true;
//                                        i++;
//                                }
                                else
                                        mark = true;
                        } else
                                part.append(c);
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }. from: 1point3acres.com/bbs
        ret.add(part.toString());
        return ret;
}
public static String parseCSV1(String str) {
        StringBuilder ret = new StringBuilder();
        StringBuilder part = new StringBuilder();
        boolean isQuote = false;
        for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);. from: 1point3acres.com/bbs
                if (isQuote) {
                        if (c == '\"') {
                                if (i == str.length() - 1). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                        return ret.append(part.toString()).toString();
                                else if (str.charAt(i + 1) == '\"') {. From 1point 3acres bbs
                                        part.append('\"');
                                        i++;
                                } else
                                        isQuote = false;. visit 1point3acres.com for more.
                        } else
                                part.append(c);. From 1point 3acres bbs
                } else {
                        if (c == ',') {
                                part.append('|');. 1point3acres.com/bbs
                                ret.append(part.toString());
                                part.setLength(0);
                        } else if (c == '\"') {
                                isQuote = true;
                        } else
                                part.append(c);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
        }
        return ret.append(part.toString()).toString(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-6-17 22:32:05 | 显示全部楼层
第三题
public static void main(String[] args) {
        test t = new test();
        Array2D<Integer> ad = t.new Array2D<Integer>();
        for(int i = 1 ; i < 3; i++){
                ArrayList<Integer> a = new ArrayList<Integer>();
                for(int j = 2; j < 4; j++){
                        a.add(i*j);
                        System.out.println(i* j);
                }.1point3acres缃
                ad.addLine(a);
        }
        for(Iterator<Integer> i = ad.iterator(); i.hasNext();){
                Integer num = i.next();
                System.out.print(num + " ");
                if (num == 3)
                        i.remove();. 1point 3acres 璁哄潧
        }
        System.out.println();
        for(Iterator i = ad.iterator(); i.hasNext();){
                System.out.print(i.next() + " ");
        }
}
public class Array2D<T> {
        ArrayList<ArrayList<T>> array;
        public Array2D(){
                array = new ArrayList<ArrayList<T>>();
        }
        public void addLine(ArrayList<T> nums){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                array.add(new ArrayList(nums));
        }
        public T get(int x, int y){
                if(x >= array.size()) return null;. visit 1point3acres.com for more.
                ArrayList<T> l = array.get(x);
                if(l == null || y >= l.size()) return null;
                return l.get(y);
        }
        public Iterator iterator() {. visit 1point3acres.com for more.
                // TODO Auto-generated method stub-google 1point3acres
                return new a2Iterator();
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        private class a2Iterator implements Iterator<T>{. from: 1point3acres.com/bbs
                int r;
                int c;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                ArrayList<T> curArray;-google 1point3acres
                public a2Iterator(){
                        r = 0;
                        c = 0;
                }
                @Override
                public boolean hasNext() {
                        if(curArray == null && array.size() == 0){
                                return false;
                        }else if(r >= array.size()) return false;.1point3acres缃
                        return true;
                }
                @Override
                public T next() {
                        if(c == 0) curArray = array.get(r);
                        T ret = curArray.get(c);
                        if(curArray.size()-1 == c){
                                r ++;
                                c = 0;
                        }else. more info on 1point3acres.com
                                c ++;
                        return ret;
                }
                @Override
                public void remove() {
                        ArrayList pre = curArray;
                        int x = c;
                        int y = r;
                        if(x == 0){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                y--;
                                pre = array.get(y);
                                x = pre.size();
                        }
                        x--;
                        pre.remove(x);
                        if(pre.size() == 0){
                                array.remove(y);
                                r--;
                        }
                        if(c != 0) c--;
                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }
}
回复 支持 1 反对 0

使用道具 举报

jiebour 发表于 2015-8-28 10:15:36 | 显示全部楼层
楼主,我收到邮件是20-30分钟的phone conversation,所以想问下楼主是第一个面试就考算法?
回复 支持 0 反对 1

使用道具 举报

houqingniao 发表于 2015-4-18 02:57:51 | 显示全部楼层
mm豆 好多面试啊~~

这一个点面就面了这么多题啊。。。
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-4-18 04:48:40 | 显示全部楼层
houqingniao 发表于 2015-4-18 02:57
mm豆 好多面试啊~~

这一个点面就面了这么多题啊。。。

这不是一次面试的题目
回复 支持 反对

使用道具 举报

hami33 发表于 2015-5-18 06:10:41 | 显示全部楼层
请问一下楼主第三题是怎么做的?
如果2d array每个长度一样比较好办,如果长度不一样需要使用额外空间吗?比如把array先copy到一个一维list里面吗?或者有别的好方法?

谢谢!
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-5-18 23:35:40 | 显示全部楼层
hami33 发表于 2015-5-18 06:10
请问一下楼主第三题是怎么做的?
如果2d array每个长度一样比较好办,如果长度不一样需要使用额外空间吗? ...

用一个array保存所有array 然后挨个便利
回复 支持 反对

使用道具 举报

hami33 发表于 2015-5-19 00:55:43 | 显示全部楼层
mm豆 发表于 2015-5-18 23:35
用一个array保存所有array 然后挨个便利

谢谢~

字数字数字数
回复 支持 反对

使用道具 举报

transcendence 发表于 2015-6-16 15:10:54 | 显示全部楼层
For the second question, just find all combination of Capital and lower case?
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-6-16 21:08:06 | 显示全部楼层
transcendence 发表于 2015-6-16 15:10
For the second question, just find all combination of Capital and lower case?

看下置顶层
回复 支持 反对

使用道具 举报

transcendence 发表于 2015-6-17 04:36:31 | 显示全部楼层

谢谢,我看到题目了。

我是想问解法是就找出对这个string所有可能的大小写组合,然后一个一个去call那个函数来验证么?
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-6-17 07:17:01 | 显示全部楼层
transcendence 发表于 2015-6-17 04:36
谢谢,我看到题目了。

我是想问解法是就找出对这个string所有可能的大小写组合,然后一个一个去call那 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我刚看了下题目,觉得你的算法是对的,不过不记得当时我是怎么做的了~
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-6-17 22:34:11 | 显示全部楼层
hami33 发表于 2015-5-18 06:10
请问一下楼主第三题是怎么做的?
如果2d array每个长度一样比较好办,如果长度不一样需要使用额外空间吗? ...

最近找到了以前写的代码
回复 支持 反对

使用道具 举报

xuyirio 发表于 2015-7-13 05:58:52 | 显示全部楼层
第一题的input,文字描述里的delimiter是'|',但给出的例子是同时有','和'|',这是个什么情况
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-7-13 09:23:36 | 显示全部楼层
xuyirio 发表于 2015-7-13 05:58
第一题的input,文字描述里的delimiter是'|',但给出的例子是同时有','和'|',这是个什么情况
. 鍥磋鎴戜滑@1point 3 acres
好像逗号是输入,|是输出。太久了,记不清了
回复 支持 反对

使用道具 举报

xuyirio 发表于 2015-7-13 12:38:22 | 显示全部楼层
mm豆 发表于 2015-7-13 09:23
好像逗号是输入,|是输出。太久了,记不清了

只有一种delimiter的话,这题用Python会很简单,它的csv和json库很全。比如http://code.anjanesh.net/2012/02/convert-csv-to-json.html
回复 支持 反对

使用道具 举报

cedar 发表于 2015-8-4 12:24:24 | 显示全部楼层
楼主能讲下第一题为什么"Alexandra ""Alex""" 变成了 Alexandra "Alex", """Alexandra Alex""" 变成了"Alexandra Alex", 这个引号是按照什么规则去掉的? 谢谢~
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-8-6 10:09:33 | 显示全部楼层
cedar 发表于 2015-8-4 12:24
楼主能讲下第一题为什么"Alexandra ""Alex""" 变成了 Alexandra "Alex", """Alexandra Alex""" 变成了"Ale ...
. more info on 1point3acres.com
"Alexandra ""Alex""" 变成了 Alexandra "Alex" 这个是遇到双引号中的双引号去掉就好,其他的就不记得了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-29 10:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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