Cisco 两轮面经 （全印阵容）

Cisco网上自己投过，也找人内推过，一天突然一个印度recruiter发邮件过来联系电面，也不知是哪个起了作用
两轮面试后再无消息，3个多月过去了，估计是印度人把我当作炮灰做political correctness了

第一轮：一个印度人用webex给我电话面试，开视频，出了道 Phonebook 的 OO design， 并且有一些客户要求如果Phonebook上某些人联系方式改变，会被通知；我意识到用obeserver pattern,写了java code,  通过，说会有下一轮面试

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

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{
        Scanner doc = new Scanner(new FileReader(path));
        while(doc.hasNextLine()){
            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);
                }
            }
        }
        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()){
                paths.add(docPath);
            }
        }
        
        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 {
                return -2; //the doc does not exist
            }
        } else {
            return -1; // the word does not exist
        }        
    }

}

然后又问如果用户很多该怎么办
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



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

               18
        12           26
    4        16     20    28

又问top K words
package cisco;
import java.io.FileReader;
import java.util.*;

public class Solution2 {
    public List<String> getTopKWords(String path, int k) throws Exception{
        List<String> result = new ArrayList<String>();
        if(k <= 0)
            return result;
      

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

rse,并且分析每一步的复杂度

A fox jumped over the fence

package cisco;

public class Solution3 {
       public String reverseStr1(String input){
            String s = input.trim();
            int len = s.length();
            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]+" ");        
            }
            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;
       }
      
        public String reverseStr2(String input) {
            String s = input.trim();
            int len = s.length();
            if(len == 0)
                return input;//the input only contains space, return it
            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;
            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++){
                        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);
        }      
}


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

我勒个去，这是new grad吗？感觉好难啊。。。
楼主好厉害= =

八和九生 发表于 2016-7-2 14:55
我勒个去，这是new grad吗？感觉好难啊。。。
楼主好厉害= =

楼主的top k words写的好棒啊= = 学习了。。。

谢谢楼主的分享！！！

谢谢楼主分享，第一题题干真的好长啊