一亩三分地论坛

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

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

Cisco 两轮面经 (全印阵容)

[复制链接] |试试Instant~ |关注本帖
yi1san3fendi 发表于 2016-7-2 14:46:53 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Cisco - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
Cisco网上自己投过,也找人内推过,一天突然一个印度recruiter发邮件过来联系电面,也不知是哪个起了作用
两轮面试后再无消息,3个多月过去了,估计是印度人把我当作炮灰做political correctness了
. 鍥磋鎴戜滑@1point 3 acres
第一轮:一个印度人用webex给我电话面试,开视频,出了道 Phonebook 的 OO design, 并且有一些客户要求如果Phonebook上某些人联系方式改变,会被通知;我意识到用obeserver pattern,写了java code,  通过,说会有下一轮面试

第二轮:印度recruiter联系我,说onsite面试报销太麻烦(现在想起来应该是只不过准备把我当炮灰),说继续用webex video面试,但是需要一个下午时间,面试官全印阵容, 4个印度人
1. 有一堆文档,给一个单词,返回包含这个单词的所有文档路径,并且返回这些文档跟这个单词对应的instances
        word ->  <docPath1, docPath2, ..., docPathn>. visit 1point3acres.com for more.

package cisco;
import java.io.*;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
import java.util.*;

public class Solution1 {//assume the doc path is unique, and we can use it as ID
    HashMap<String, HashMap<String, Integer>> wordPathHm;//<word, <docID/path, number of instances>>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    public Solution1(){
        wordPathHm = new HashMap<String, HashMap<String, Integer>>();
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
   
    public void buildIndex(String path) throws IOException{. visit 1point3acres.com for more.
        Scanner doc = new Scanner(new FileReader(path));
        while(doc.hasNextLine()){.1point3acres缃
            String line = doc.nextLine();
            String[] words = line.split("\\s+");
            for(String word : words){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if(wordPathHm.containsKey(word)){//if the word already exists, update the hashmap
                    HashMap<String, Integer> oldlist = wordPathHm.get(word);
                    Integer currCnt = oldlist.get(path);
                    oldlist.put(path, currCnt+1);
                } else {//if the word does not exist, add a new entry
                    HashMap<String, Integer> newlist = new HashMap<String, Integer>();
                    newlist.put(path, 1);
                    wordPathHm.put(word, newlist);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            }
        }
        doc.close();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }
   
    public List<String> getDocsPaths(String word){
        List<String> paths = new ArrayList<String>();
        if(wordPathHm.containsKey(word)){
            HashMap<String, Integer> hmRecord = wordPathHm.get(word);
            for(String docPath : hmRecord.keySet()){. From 1point 3acres bbs
                paths.add(docPath);.鏈枃鍘熷垱鑷1point3acres璁哄潧
            }
        }
        
        return paths;
    }
   
    public int getDocInstanceNum(String word, String docPath){
        if(wordPathHm.containsKey(word)){.鐣欏璁哄潧-涓浜-涓夊垎鍦
            HashMap<String, Integer> hmRecord = wordPathHm.get(word);
            if(hmRecord.containsKey(docPath)){
                return hmRecord.get(docPath);
            } else {. 1point 3acres 璁哄潧
                return -2; //the doc does not exist
            }
        } else {
            return -1; // the word does not exist
        }         鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    }. 1point 3acres 璁哄潧

}

然后又问如果用户很多该怎么办
DHT.鐣欏璁哄潧-涓浜-涓夊垎鍦
hash(docID/path) -> which server should be queried for this doc
    the queried server should return the path of the documents, and how many instances in each document
multiple hashmaps
each hashmap return the number of instances for this key word, and add the count  together

.1point3acres缃

2. 问了操作系统调度问题,我刚好看了一点
Completely Fair Scheduler   Linux 2.6
we have different priority weights for different tasks.鐣欏璁哄潧-涓浜-涓夊垎鍦
it is difficult for us to predict how much time

previous exectuion time
virtual running time(vrt) = already execution time/ priority weights

build red-black tree -> an approximately balanced binary search tree
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷if vrt is smaller , it means it should be assigned to the processor earlier
start from leftmost nodes.1point3acres缃

               18. visit 1point3acres.com for more.
        12           26
    4        16     20    28

又问top K words
package cisco;
import java.io.FileReader;
import java.util.*;. From 1point 3acres bbs
. more info on 1point3acres.com
public class Solution2 {
    public List<String> getTopKWords(String path, int k) throws Exception{
        List<String> result = new ArrayList<String>();
        if(k <= 0). From 1point 3acres bbs
            return result;
. from: 1point3acres.com/bbs         Scanner doc = new Scanner(new FileReader(path));
        HashMap<String, Integer> wordCnt = new HashMap<String, Integer>();
        while(doc.hasNextLine()){ // find the total number of occurrences for each word
            String line = doc.nextLine();
            String[] words = line.split("\\s+");. Waral 鍗氬鏈夋洿澶氭枃绔,
            for(String word : words){
                   if(wordCnt.containsKey(word)){
                       wordCnt.put(word, wordCnt.get(word)+1);
                   } else {. Waral 鍗氬鏈夋洿澶氭枃绔,
                       wordCnt.put(word, 1);
                   }
                }
        }
        doc.close();

        Set<Map.Entry<String, Integer>> set = wordCnt.entrySet();
        List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(set);
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>(){
            @Override. 1point 3acres 璁哄潧
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2){
                return o2.getValue()-o1.getValue(); // from the highest occurrences to the lowest occurrences
            }
        });.鐣欏璁哄潧-涓浜-涓夊垎鍦
        
        int upperbound = Math.min(k, list.size());
        for(int i=0; i<upperbound; i++){// if k is larger than the number of words, then return all words. 鍥磋鎴戜滑@1point 3 acres
            result.add(list.get(i).getKey());
        }.1point3acres缃
        
        return result;
    }
. 1point3acres.com/bbs
}
. Waral 鍗氬鏈夋洿澶氭枃绔,

. 鍥磋鎴戜滑@1point 3 acres最后还剩8分钟,拷贝粘贴扔给我一道大题,关于字符串编码解码的,题目文字描述其中还有一堆乱码;他说这题你还能用java来做?我跟他确认题目意思都用了8分钟;最后说我可以面试完后做了发给他(好吧,他拿到了java版本的答案,真精明) 为了方便大家看,我剔除乱码,整理如下:
Where Did Those Numbers Come From?
In both modes, the program maintains a linked list of words that have appeared in the input. In compression mode, the program reads the next word from the input file and searches for it in the list. If it is not found, the program writes the word to the output file and inserts it at the front of the list. If the word is found in the i-th position in the list, the program writes out i, removes the word from the list, then reinserts it at the front (this is the move-to-front feature). For example, let us consider the text:
LOVE,   LOVE   ME   DO!      YOU   KNOW   I   LOVE   YOU,   YOU,   YOU.
which after compression becomes     
LOVE,   1   ME   DO!      YOU   KNOW   I   6   4,   1,   1.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Notice that LOVE is replaced by both 1 and 6, and that 1 replaces both LOVE and YOU. This is due to word insertions in the list and the effect of move-to-front. After the second LOVE is processed, the word list is simply
. 鍥磋鎴戜滑@1point 3 acres(LOVE)
hence the second instance of LOVE is replaced by the number 1. After the I is processed, the word list is
(I, KNOW, YOU, DO, ME, LOVE). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Next, the third instance of LOVE is processed, the word is found in the 6th position (thus it is
replaced by number 6), and the list becomes:. more info on 1point3acres.com
(LOVE, I, KNOW, YOU, DO, ME) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
When the second YOU is processed, YOU is found in the 4th position, and the list becomes:
(YOU, LOVE, I, KNOW, DO, ME)
Finally, when the last two instances of YOU are processed, the word is found in the first position.
In decompression mode, a word read from input is written out again and inserted at the front of the list. When the number i is read, the word in the i-th position is written out, then the word is deleted from the list and reinserted at the front. Decompression ends when the number 0 is read. The decompressed version should be identical to the original in every respect! (In Unix, you can use the utility diff to check this.)


package cisco;

import java.util.*;

//the requirement does not specify "LOVE" or "love" is the same word, so I assume words are all in uppercase
public class MoveToFrontCoding {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    public String compression(String str) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        LinkedList<String> list = new LinkedList<>();
        StringBuilder ret = new StringBuilder();
        int last = 0;
        for (int i = 0; i < str.length(); i++) {
            if (Character.toUpperCase(str.charAt(i)) >= 'A' && Character.toUpperCase(str.charAt(i)) <= 'Z') {
                continue;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            } else {
                if (last != i) {
                    String s = str.substring(last, i);
                    int idx = list.indexOf(s);. visit 1point3acres.com for more.
                    if (idx >= 0) {// if the word already exists, replace it with a number. more info on 1point3acres.com
                        list.remove(idx);
                        ret.append(idx + 1);
                    } else {// if the word does not exist, keep it
                        ret.append(s);
                    }
                    list.offerFirst(s);//insert the word at the beginning. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
                last = i + 1;
                ret.append(str.charAt(i));//insert the word at the beginning
            }
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if (last != str.length()) {
            String s = str.substring(last, str.length());
            int idx = list.indexOf(s);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            if (idx >= 0) {// if the word already exists, replace it with a number
                list.remove(idx);
                ret.append(idx + 1);
            } else {// if the word does not exist, keep it
                ret.append(s);. 鍥磋鎴戜滑@1point 3 acres
            }
            list.offerFirst(s);//insert the word at the beginning
        }
        return ret.toString();
    }

    public String decompression(String str) {
        LinkedList<String> list = new LinkedList<>();-google 1point3acres
        StringBuilder ret = new StringBuilder();
        int last = 0;
        for (int i = 0; i < str.length(); i++) {. 1point3acres.com/bbs
            if ((str.charAt(i) >= '0' && str.charAt(i) <= '9') || (Character.toUpperCase(str.charAt(i)) >= 'A' && Character.toUpperCase(str.charAt(i)) <= 'Z')) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                continue;
            } else {
                if (last != i) {
                    String ss = str.substring(last, i);-google 1point3acres
                    if (ss.matches("\\d+")) {//  the word already exists, replace the index with the word
                        int idx = Integer.parseInt(ss) - 1;
                        ret.append(list.get(idx));
                        String s = list.remove(idx);
                        list.offerFirst(s);//insert the word at the beginning. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                    } else {
                        ret.append(ss);
                        list.offerFirst(ss);//insert the word at the beginning
                    }
                }
                last = i + 1;
                ret.append(str.charAt(i));
            }
        }
        if (last != str.length()) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            String ss = str.substring(last, str.length());
. more info on 1point3acres.com            if (ss.matches("\\d+")) {//  the word already exists, replace the index with the word
                int idx = Integer.parseInt(ss) - 1;
                ret.append(list.get(idx));
                String s = list.remove(idx);
                list.offerFirst(s);//insert the word at the beginning
            } else {
                ret.append(ss);
                list.offerFirst(ss);//insert the word at the beginning 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            }
.1point3acres缃        }
        return ret.toString();
    }

    public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        MoveToFrontCoding s = new MoveToFrontCoding();
        String originalStr = "LOVE, LOVE ME DO!!  YOU KNOW I LOVE YOU, YOU, YOU.";
        System.out.println("original string: ");
        System.out.println(originalStr);
        System.out.println("Compressing...");
        String s1 = s.compression(originalStr);
        System.out.println(s1);
        System.out.println("Decompressing...");
        String s2 = s.decompression(s1);
        System.out.println(s2);
    }
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

. visit 1point3acres.com for more.

Result:


original string:
LOVE, LOVE ME DO!!  YOU KNOW I LOVE YOU, YOU, YOU.
Compressing.... 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
LOVE, 1 ME DO!!  YOU KNOW I 6 4, 1, 1.
Decompressing...
LOVE, LOVE ME DO!!  YOU KNOW I LOVE YOU, YOU, YOU.

3  这个印度人完全问我的项目经历

4. 这个印度人问完我的项目经历,让我用两种方法做string reverse,并且分析每一步的复杂度

A fox jumped over the fence

package cisco;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

public class Solution3 {
       public String reverseStr1(String input){
            String s = input.trim();.鏈枃鍘熷垱鑷1point3acres璁哄潧
            int len = s.length();
.鏈枃鍘熷垱鑷1point3acres璁哄潧            if(len == 0)
                return input;//the input only contains space, return it
            String[] arrStr = input.split("\\s+");  // compute O(n)  memory read O(n)  write O(n)
            StringBuilder sb = new StringBuilder();
            for(int i=arrStr.length-1; i>=0; i--){  // compute O(n)  memory read O(n)  write O(n)
                sb.append(arrStr[i]+" ");        
            }. Waral 鍗氬鏈夋洿澶氭枃绔,
            String result = new String(sb); //compute O(n)  read O(n)  write O(n)
            result = result.trim();// remove the last empty space  compute O(n) read O(n)  write O(1)
            return result;
       }.1point3acres缃
      
        public String reverseStr2(String input) {
            String s = input.trim();
            int len = s.length();
            if(len == 0). more info on 1point3acres.com
                return input;//the input only contains space, return it. From 1point 3acres bbs
            char[] cArr = s.toCharArray();
            for(int i=0; i<len/2; i++){// reverse the whole string  compute O(n)  memory read O(n)  write O(n)
                char tmp = cArr[i];
                cArr[i] = cArr[len-1-i];
                cArr[len-1-i] = tmp;
            }
            
            int m=0;-google 1point3acres
            for(int i=0; i<=len; i++){
                /* reverse each substring delimited by space
                 * compute O(n)  memory read O(n)  write O(n)*/. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                if(i==len || cArr[i]==' '){
                    int len1 = i-m;
                    for(int j=0; j<len1/2; j++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        char tmp1 = cArr[m+j];
                        cArr[m+j] = cArr[len1+m-1-j];
                        cArr[len1+m-1-j] = tmp1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    }
                    m = i+1;
                }
            }
            
            return String.valueOf(cArr);. more info on 1point3acres.com
        }      
}. Waral 鍗氬鏈夋洿澶氭枃绔,


现在感觉我完全在给印度人提供面试题答案了;还是分享给大家比较好

评分

2

查看全部评分

八和九生 发表于 2016-7-2 14:55:55 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我勒个去,这是new grad吗?感觉好难啊。。。
楼主好厉害= =
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 15:02:04 | 显示全部楼层
关注一亩三分地微博:
Warald
八和九生 发表于 2016-7-2 14:55
我勒个去,这是new grad吗?感觉好难啊。。。
楼主好厉害= =

楼主的top k words写的好棒啊= = 学习了。。。
回复 支持 反对

使用道具 举报

lajiwushi 发表于 2016-7-6 07:04:21 | 显示全部楼层
谢谢楼主的分享!!!
回复 支持 反对

使用道具 举报

yingchal 发表于 2016-9-30 12:20:46 | 显示全部楼层
谢谢楼主分享,第一题题干真的好长啊
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-26 02:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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