Momenta实习面试

Momenta实习面试

两个部门面了我

一.java后台开发

第一个部门是写java的但是我表现的很差

1. redis的底层结构（只记得动态数组，双向链表，跳表，忘了hash）
2. 让我描述实现一个str转int，剑指offer最后附录的第一个案例，完美的复现了书上的失败案例，以此为戒
3. java中的容器（map，set，list，vector，忘了数组）
4. 设计题，百万数据的ip，设计一个容器删除，添加，查找O(1)（说了半天没有说对，这个是leetcode 380题，当时也没想到）

二.模拟仿真组

这个部门是写汽车的模拟仿真的主要是C++和Python，设计算法和计算机视觉，没有问java和数据库，问题都比较有意思

一面

1. 不递减的数组中找到某个数的范围，问思路（二分）在写代码发过去（写的不好）
2. 好的算法为什么快，本质上是什么（回答是减少了不必要的重复计算）
3. 三个箱子里面有一个礼物，先选一个，上帝再在剩下的两个箱子中选一个不含礼物的箱子，问你是否和用你选取的箱子换取剩下的那个箱子。如果让你选择，你换还是不换，请说明你的推理过程
4. 接着上题，如果有一百个箱子，你选一个，上帝选98个空箱子，问你换不换，说出你的推到过程
   第一个问题，换得到礼物的概率是2/3，不换的概率是1/3
   第二个问题，换得到礼物的概率是99/100，不换的概率是1/100
   比较可惜的我想了好久才想出来，面试官很有耐心很nice

二面

1. 数组中找到超过一半的那个数字（剑指offer的原题，1.使用快排的 partition思想时间复杂度O(n)空间复杂度O(log(n)) 2.使用数组的特性，时间复杂度O(n)，空间复杂度O(1)）
2. 一个岛上有红眼睛m个和蓝眼睛n个两种人，他们不可以互相交流，其中如果蓝眼睛意识到自己是蓝眼睛就会在当天的晚上自杀，一天一个游客来到岛上告诉岛上的人他们其中至少有一个蓝眼睛，请问需要多少天岛上的蓝眼睛会死完（想了一会就可以明白是n，你想到了吗）
3. 有四个线程1、2、3、4。线程1的功能就是输出1，线程2的功能就是输出2，以此类推。现在有四个文件ABCD。初始都为空。现要让四个文件呈如下格式：
   A. 1 2 3 4 1 2…
   B. 2 3 4 1 2 3…
   C. 3 4 1 2 3 4…
   D. 4 1 2 3 4 1…
   请设计程序。（第二天突然就想到了，不知道符不符合答案）

重构优化版本：

public class ThreadOrderRun3 {File fileA = new File(&#");File fileB = new File(&#");File fileC = new File(&#");File fileD = new File(&#");FileWriter fwA;FileWriter fwB;FileWriter fwC;FileWriter fwD;public ThreadOrderRun3() throws IOException {//初始化创建文件A Ｂ C Dif (ists() || ists() || ists() || ists()) {fileA.delete();fileB.delete();fileC.delete();fileD.delete();}ateNewFile();ateNewFile();ateNewFile();ateNewFile();fwA = new FileWriter(fileA);fwB = new FileWriter(fileB);fwC = new FileWriter(fileC);fwD = new FileWriter(fileD);}private void firstRun(String str) throws IOException, InterruptedException {while (true) {
//            try {
//                lock1.lock();
//                if (lock1id != 1) {
//                    condition11.await();
//                }
//                fileWriter("fileA", "1 ");
//                lock1id = 2;
//                condition12.signal();
//            } catch (IOException e) {
//                e.printStackTrace();
//            } finally {
//                lock1.unlock();
//            }synchronized (fileA) {fileWriter("fileA", str);}Thread.sleep(50);synchronized (fileD) {fileWriter("fileD", str);}Thread.sleep(50);synchronized (fileC) {fileWriter("fileC", str);}Thread.sleep(50);synchronized (fileB) {fileWriter("fileB", str);}Thread.sleep(50);}}private void secondRun(String str) throws IOException, InterruptedException {while (true) {synchronized (fileB) {fileWriter("fileB", str);}Thread.sleep(50);synchronized (fileA) {fileWriter("fileA", str);}Thread.sleep(50);synchronized (fileD) {fileWriter("fileD", str);}Thread.sleep(50);synchronized (fileC) {fileWriter("fileC", str);}Thread.sleep(50);}}private void thirdRun(String str) throws IOException, InterruptedException {while (true) {synchronized (fileC) {fileWriter("fileC", str);}Thread.sleep(50);synchronized (fileB) {fileWriter("fileB", str);}Thread.sleep(50);synchronized (fileA) {fileWriter("fileA", str);}Thread.sleep(50);synchronized (fileD) {fileWriter("fileD", str);}Thread.sleep(50);}}private void fourthRun(String str) throws IOException, InterruptedException {while (true) {synchronized (fileD) {fileWriter("fileD", str);}Thread.sleep(50);synchronized (fileC) {fileWriter("fileC", str);}Thread.sleep(50);synchronized (fileB) {fileWriter("fileB", str);}Thread.sleep(50);synchronized (fileA) {fileWriter("fileA", str);}Thread.sleep(50);}}private void fileWriter(String fileName, String str) throws IOException {if (fileName == null) {return;}if (fileName.equals("fileA")) {fwA.write(str);fwA.flush();}if (fileName.equals("fileB")) {fwB.write(str);fwB.flush();}if (fileName.equals("fileC")) {fwC.write(str);fwC.flush();}if (fileName.equals("fileD")) {fwD.write(str);fwD.flush();}}public static void main(String[] args) throws IOException {ThreadOrderRun3 threadOrderRun3 = new ThreadOrderRun3();new Thread(new Runnable() {@Overridepublic void run() {try {threadOrderRun3.firstRun("1 ");} catch (IOException e) {e.printStackTrace();} catch (InterruptedException e) {e.printStackTrace();}}}).start();new Thread(new Runnable() {@Overridepublic void run() {try {threadOrderRun3.secondRun("2 ");} catch (IOException e) {e.printStackTrace();} catch (InterruptedException e) {e.printStackTrace();}}}).start();new Thread(new Runnable() {@Overridepublic void run() {try {threadOrderRun3.thirdRun("3 ");} catch (IOException e) {e.printStackTrace();} catch (InterruptedException e) {e.printStackTrace();}}}).start();new Thread(new Runnable() {@Overridepublic void run() {try {threadOrderRun3.fourthRun("4 ");} catch (IOException e) {e.printStackTrace();} catch (InterruptedException e) {e.printStackTrace();}}}).start();}
}