一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 6396|回复: 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 | 显示全部楼层
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:

https://www.airbnb.com/rooms/848662
-google 1point3acres
becomes

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.鏈枃鍘熷垱鑷1point3acres璁哄潧

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.
To assess how big of a deal this is, we may want to recover the IDs of the
targets that were 404ing.

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 (.鐣欏璁哄潧-涓浜-涓夊垎鍦
depending on the language) if not, implement a new method decodeFind(String . Waral 鍗氬鏈夋洿澶氭枃绔,
badEncStr) which takes a string and returns the decoded int id.

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

使用道具 举报

 楼主| mm豆 发表于 2015-6-17 22:30:15 | 显示全部楼层
第一题
class Solution {
          public static void main(String[] args) {
            //#1. 1point3acres.com/bbs
            ArrayList<String> output = parseCSV("John,Smith,john.smith@gmail.com,Los Angeles,1");
            String strOutput = printStr(output);
            System.out.println(strOutput);
            //#2-google 1point3acres
            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");
            strOutput = printStr(output);
            System.out.println(strOutput);. 1point3acres.com/bbs
          }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
          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;
                  } else if(str.charAt(i+1) == '"') {
                    buffer.append('"');
                    i++;. visit 1point3acres.com for more.
                  } else {
                    res.add(buffer.toString());
                    buffer.setLength(0);
                    inQuote = false;
                    i++;. 1point3acres.com/bbs
                  }
                } 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);
                } else {
                  buffer.append(str.charAt(i));. visit 1point3acres.com for more.
                }
.鏈枃鍘熷垱鑷1point3acres璁哄潧

              }

            }.鐣欏璁哄潧-涓浜-涓夊垎鍦
            if(buffer.length() > 0) res.add(buffer.toString());
            return res;
          }

          public static String printStr(ArrayList<String> list) {
            StringBuilder res = new StringBuilder();
            for(int i = 0; i < list.size()-1; i++) {
              res.append(list.get(i));
              res.append('|');
            }
            res.append(list.get(list.size()-1));
            return res.toString();
          }
        }
public static ArrayList<String> parseCSV1(String str) {
. more info on 1point3acres.com        boolean mark = false;
        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());. 1point 3acres 璁哄潧
//                                        return ret;
//                                } else if (str.charAt(i + 1) == '\"') {
//                                        //""asdf""
//                                        dMark = false;
//                                        part.append('\"');
//                                        i++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
//                                } else
//                                        part.append(c);
//                        }else part.append(c);
//                } else
                if (mark) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        if (c == '\"') {
                                if (i == str.length() - 1) {
. From 1point 3acres bbs                                        ret.add(part.toString());
                                        return ret;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                } else if (str.charAt(i + 1) == '\"') {.1point3acres缃
                                        // “asdf“fdsa”fdas”
                                        part.append('\"');. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                        i++;
                                } else
                                        mark = false;
                        } 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;. 1point 3acres 璁哄潧
                                }
//                                else if (str.charAt(i + 1) == '\"') {
//                                        part.append('\"');.鏈枃鍘熷垱鑷1point3acres璁哄潧
//                                        dMark = true;
//                                        i++;
//                                } .1point3acres缃
                                else 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                        mark = true;. visit 1point3acres.com for more.
                        } else
                                part.append(c);
                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
        ret.add(part.toString());-google 1point3acres
        return ret;
}.鏈枃鍘熷垱鑷1point3acres璁哄潧
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++) {. From 1point 3acres bbs
                char c = str.charAt(i);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                if (isQuote) {
                        if (c == '\"') {
                                if (i == str.length() - 1)
                                        return ret.append(part.toString()).toString();
                                else if (str.charAt(i + 1) == '\"') {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                        part.append('\"');. visit 1point3acres.com for more.
                                        i++;
                                } else
                                        isQuote = false;
                        } else
                                part.append(c);
                } else {
                        if (c == ',') {
                                part.append('|');
                                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 | 显示全部楼层
第三题.1point3acres缃
public static void main(String[] args) {. From 1point 3acres bbs
        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);
                }. visit 1point3acres.com for more.
                ad.addLine(a);
        }
        for(Iterator<Integer> i = ad.iterator(); i.hasNext();){.1point3acres缃
                Integer num = i.next();
                System.out.print(num + " ");
                if (num == 3)
                        i.remove();
        }
        System.out.println();
        for(Iterator i = ad.iterator(); i.hasNext();){
                System.out.print(i.next() + " ");
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
}
public class Array2D<T> {
        ArrayList<ArrayList<T>> array;.1point3acres缃
        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){.1point3acres缃
                if(x >= array.size()) return null; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                ArrayList<T> l = array.get(x);
                if(l == null || y >= l.size()) return null;.1point3acres缃
                return l.get(y);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }. visit 1point3acres.com for more.
        public Iterator iterator() {
                // TODO Auto-generated method stub
                return new a2Iterator();
        }
        private class a2Iterator implements Iterator<T>{
                int r;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                int c;
                ArrayList<T> curArray;
                public a2Iterator(){
                        r = 0;
                        c = 0;.1point3acres缃
                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                @Override.1point3acres缃
                public boolean hasNext() {
                        if(curArray == null && array.size() == 0){
                                return false;. 1point 3acres 璁哄潧
                        }else if(r >= array.size()) return false;
                        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
                                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--;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        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每个长度一样比较好办,如果长度不一样需要使用额外空间吗? ...
-google 1point3acres
用一个array保存所有array 然后挨个便利
回复 支持 反对

使用道具 举报

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

谢谢~ -google 1point3acres

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

使用道具 举报

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那 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我刚看了下题目,觉得你的算法是对的,不过不记得当时我是怎么做的了~
回复 支持 反对

使用道具 举报

 楼主| 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是'|',但给出的例子是同时有','和'|',这是个什么情况

好像逗号是输入,|是输出。太久了,记不清了
回复 支持 反对

使用道具 举报

xuyirio 发表于 2015-7-13 12:38:22 | 显示全部楼层
mm豆 发表于 2015-7-13 09:23
好像逗号是输入,|是输出。太久了,记不清了
. From 1point 3acres bbs
只有一种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 ...

"Alexandra ""Alex""" 变成了 Alexandra "Alex" 这个是遇到双引号中的双引号去掉就好,其他的就不记得了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 05:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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