面试剖析守望者在线,在线教育,watchmen,C和指针,linux视频,面试视频 -

面试剖析

3 点赞 1 评论

【守望者 java基础】实现多线程对共享资源的随机访问

1813 次浏览 2014-09-24 12:20 显示评论

问题描述: NHN经典面试题目查看更多>>

11 这个题目可以简单更加形象化的理解为多线程随机的操作共享的数组，比如数组 int []num={A,B,C}。一共有三个线程随机的访问这个共享的数组。第一个线程假如访问A，第二个线程也可能访问A。第三个线程有可 ... zhouy 2014-09-26 15:57

3 点赞 3 评论

[守望者 java算法]说说生活中遇到的二叉树，用java实现二叉树

1482 次浏览 2014-09-22 17:14 显示评论

5 这是组合设计模式。 我有很多个(假设10万个)数据要保存起来，以后还需要从保存的这些数据中检索是否存在某个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，那么，碰巧要 ... watchmen 2014-09-22 19:51

5

这是组合设计模式。
我有很多个(假设10万个)数据要保存起来，以后还需要从保存的这些数据中检索是否存在某个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，那么，碰巧要找的数字位于99999那个地方，那查找的速度将很慢，因为要从第1个依次往后取，取出来后进行比较。平衡二叉树（构建平衡二叉树需要先排序，我们这里就不作考虑了）可以很好地解决这个问题，但二叉树的遍历（前序，中序，后序）效率要比数组低很多，原理如下图：
代码如下：
package com.huawei.interview;

publicclass Node {
public int value;
public Node left;
public Node right;

public void store(intvalue)
{
   if(value<this.value)
   {
         if(left ==null)
         {
            left = new Node();
            left.value=value;
         }
         else
         {
            left.store(value);
         }
   }
   else if(value>this.value)
   {
         if(right ==null)
         {
            right = new Node();
            right.value=value;
         }
         else
         {
            right.store(value);
         }
   }
}

public boolean find(intvalue)
{
   System.out.println("happen" +this.value);
   if(value ==this.value)
   {
         return true;
   }
   else if(value>this.value)
   {
         if(right ==null)returnfalse;
         return right.find(value);
   }else
   {
         if(left ==null)returnfalse;
         return left.find(value);
   }

}

public  void preList()
{
   System.out.print(this.value+ ",");
   if(left!=null)left.preList();
   if(right!=null) right.preList();
}

public void middleList()
{
   if(left!=null)left.preList();
   System.out.print(this.value+ ",");
   if(right!=null)right.preList();
}
public void afterList()
{
   if(left!=null)left.preList();
   if(right!=null)right.preList();
   System.out.print(this.value+ ",");
}
public static voidmain(String [] args)
{
   int [] data =new int[20];
   for(inti=0;i<data.length;i++)
   {
         data = (int)(Math.random()*100)+ 1;
         System.out.print(data +",");
   }
   System.out.println();

   Node root = new Node();
   root.value = data[0];
   for(inti=1;i<data.length;i++)
   {
         root.store(data);
   }

   root.find(data[19]);

   root.preList();
   System.out.println();
   root.middleList();
   System.out.println();
   root.afterList();
}
}
-----------------又一次临场写的代码---------------------------
importjava.util.Arrays;
importjava.util.Iterator;

public class Node{
private Node left;
private Node right;
private int value;
//private int num;

public Node(int value){
   this.value = value;
}
public void add(int value){

   if(value > this.value)
   {
         if(right != null)
            right.add(value);
         else
         {
            Node node = new Node(value);
            right = node;
         }
   }
   else{
         if(left != null)
            left.add(value);
         else
         {
            Node node = new Node(value);
            left = node;
         }
   }
}

public boolean find(int value){
   if(value == this.value) return true;
   else if(value > this.value){
         if(right == null) return false;
         else return right.find(value);
   }else{
         if(left == null) return false;
         else return left.find(value);
   }

}

public void display(){
   System.out.println(value);
   if(left != null) left.display();
   if(right != null) right.display();

}

/*public Iterator iterator(){

}*/

public static void main(String[] args){
   int[] values = new int[8];
   for(int i=0;i<8;i++){
         int num = (int)(Math.random() * 15);
         //System.out.println(num);
         //if(Arrays.binarySearch(values,num)<0)
         if(!contains(values,num))
            values = num;
         else
            i--;
   }

   System.out.println(Arrays.toString(values));

   Node root = new Node(values[0]);
   for(int i=1;i<values.length;i++){
         root.add(values);
   }

   System.out.println(root.find(13));

   root.display();

}

public static boolean contains(int [] arr,int value){
   int i = 0;
   for(;i<arr.length;i++){
         if(arr == value) return true;

   }
   return false;
}

}

watchmen

2014-09-22 19:51

5

生活中太多二叉树了！

costan

2014-09-23 11:13

3

好多啊！

costan

2014-09-23 11:14

2 点赞 1 评论

[守望者智力面试题]孩子分糖果

1345 次浏览 2014-09-23 12:05    显示评论

问题描述: N个孩子站成一排，每个人分给一个权重。按照如下的规则分配糖果：1. 每个孩子至少有一个糖果2. 所分配权重较高的孩子，会比他的邻居获得更多的糖果问题是，最少需要多少个糖果？ ... ... 查看更多>>

3

参考思路:

这个题目是要求找到最少需要多少个糖果。最少的糖果是存在的，体现在哪里呢？权重较高的孩子，会比他的邻居们获得更多的糖果，那么多多少呢？可以是 1个，2个，或者更多个，但显然，当多一个 ...

zhouy
2014-10-17 14:57

3

参考思路:

这个题目是要求找到最少需要多少个糖果。最少的糖果是存在的，体现在哪里呢？权重较高的孩子，会比他的邻居们获得更多的糖果，那么多多少呢？可以是 1个，2个，或者更多个，但显然，当多一个的时候。总的糖果的数量是最少的，除此之外呢？当某一个孩子的邻居的权重都比他大，那他应该获得多少个糖果呢？只有一个——每个孩子至少要得到一个。

所以根据上面的分析，我们可以想办法找到权重数组A中的波谷（也就是权重小于邻居们的孩子），很显然这些孩子每人只可以分得一个糖果。我们开辟一个新的数组B，表示每个孩子可以得到的最少的糖果数。扫描一遍A，得到所有的波谷的孩子，然后将对应的B的值设置为1.对于第一个和最后一个权重，只要 A[0]

然后该如何确定其他孩子的糖果数呢？我们看一个具体的例子，来更加形象的说明如何求得。如下表：

A 1 2 3 4 2 6
B 1 1
现在已经确定B中两个孩子的最少糖果数，然后：

1. B[0]=1，那么B[1]=2,B[2]=3,B[3]=4，是一定的。原因是要满足题目中的第2个条件。

2. 同理，B[5]=2。

3. 上面的是按照数据的正向看的，如果逆向，则B[3]=2,因为B[4]=1。这时，出现了冲突，要满足最少的糖果数，似乎要取B[3]=2，但是不满足条件2.所以遇到这个情况，则选取较大的。得到表格如下：
A 1 2 3 4 2 6
B 1 2 3 4 1 2
则最少糖果数为(1+2+3+4+1+2) = 13个。

总结算法步骤如下：

1. 找到数组的波谷，将波谷的孩子的糖果数设置为1.此步：时间复杂度O(n)，空间复杂度O(n)

2. 从左到右遍历数组，从每一个1开始，其后的孩子的糖果比前一个孩子多1个，直到波峰。此步：时间复杂度O(n)

3. 从右向左遍历数组，从每一个1开始，其后的孩子的糖果比前一个孩子多1个。波峰的孩子，与2步中的相比，取最大的糖果个数。

4. B数组每一个元素求和，即可得到最少需要的糖果数。
整体算法的时间复杂度为O(n)，空间复杂度为O(n)。进一步优化，可以将找波谷的一次循环省略。

zhouy

2014-10-17 14:57

1 点赞 0 评论

【守望者名企笔试题目】google经典笔试题目

1049 次浏览 2014-09-24 12:17

问题描述: 1) 一个range的序列（链表或数组），如, , ，写程序合并有重叠的range，比如上面的序列合并为, , 如果这个序列不是静态的，而是一个数据流，如何处理？　　后来听说了interval tree，不过还是不太清楚具体如何解 ... 查看更多>>

1 点赞 1 评论

【守望者海量数据】最大间隙问题

759 次浏览 2014-09-24 12:10    显示评论

问题描述: 给定n个实数，求着n个实数在实轴上向量2个数之间的最大差值，要求线性的时间算法。查看更多>>

4

思路:

方案1：最先想到的方法就是先对这n个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法：

s> 找到n个数据中最大和最小数据ma ...

zhouy
2014-10-17 14:33

4

思路:

方案1：最先想到的方法就是先对这n个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法：

s> 找到n个数据中最大和最小数据max和min。

s> 用n-2个点等分区间[min,max]，即将[min, max]等分为n-1个区间（前闭后开区间），将这些区间看作桶，编号为1,2,...,n-2,n-1，且桶 i 的上界和桶i+1的下届相同，即每个桶的大小相同。每个桶的大小为：dblAvrGap=(max-min)/(n-1)。实际上，这些桶的边界构成了一个等差数列（首项为min，公差为d=dblAvrgap），且认为将min放入第一个桶，将max放入第n-1个桶。

s> 将n个数放入n-1个桶中：将每个元素x分配到某个桶（编号为index），其中 index= (x-min)/dblAvrGap 的下限 + 1 ，并求出分到每个桶的最大最小数据。

s> 最大间隙：除最大最小数据max和min以外的n-2个数据放入n-1个桶中，由抽屉原理可知至少有一个桶是空的，又因为每个桶的大小相同，所以最大间隙不会在同一桶中出现，一定是某个桶的上界和某个桶的下界之间隙，且该两桶之间的桶一定是空桶。也就是说，最大间隙在桶i的上界和桶j的下界之间产生 j>=(i+1)。一遍扫描即可完成。

参考c源码:

#include <iostream>
#include <vector>
using namespace std;

struct  Bucket{
double min;
double max;
int flag;
};
//桶排序，计算最大间隙
double MaxGap( double *arr, int len){
if( len<0 ) return 0;
double max=arr[0],min=arr[0];
for( int i=0; i<len; i++){          //找最大最小值
      if( arr>max) max=arr;
      if( arr<min) min=arr;
}

vector<Bucket> bucket(len-1);
for( int i=0; i<len-1; i++){          //初始化桶
         bucket.max= min+i*(max-min)/(len-1);
         bucket.min= min+(i+1)*(max-min)/(len-1);
         bucket.flag=0;
}

double gap=(max-min)/(len-1);
for( int i=0; i<len; i++){          //分入桶中
      int index=(int)((arr-min)/gap);
      if( index>=len-1) index = len-2;
      if( bucket[index].flag==0 ){
         bucket[index].max=arr;
         bucket[index].min=arr;
      }
      if( bucket[index].max<arr )
         bucket[index].max=arr;
      if( bucket[index].min>arr)
         bucket[index].min=arr;
      bucket[index].flag=1;
}

double maxgap=0;
double low=bucket[0].max;
for( int i=0; i<len-1; i++){          //找最大间隙
      while( bucket.flag==0 ) i++;
      if( i<len-1){
      double t = bucket.min-low;
      maxgap = t>maxgap?t:maxgap;
      low=bucket.max;
      }
}

return maxgap;
}
int main()
{
double arr[] = {-31,-41,4,-3,4,-1,-97,-93,-23,-84};
cout<<"MAX:"<<MaxGap(arr, sizeof(arr)/sizeof(double));
return 0;
}

zhouy

2014-10-17 14:33

1 点赞 0 评论

【守望者名企笔试题目】2014哈尔滨小米笔试题

1131 次浏览 2014-09-24 11:41

问题描述: 今年小米的笔试共三道大题，时间90分钟　　第一道输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于所有偶数的前面，例如输入的数组为{1,2,4,7,9,8,10,15,14,20}，调整后的数组 {1,7,9,15,2,4,8,10,14,20} ... 查看更多>>

1 点赞 0 评论

【守望者名企笔试题目】百度2014校招移动研发笔试题

1220 次浏览 2014-09-24 11:38

问题描述: 一.简答题　　1.简述计算机的存储系统分为哪几个层次，为什么这样的分层能够提高程序的执行效率。　　2.浮点数在计算中如何表示，如何对浮点数判等。　　3.简述TCP与UDP协议的差别，两者与HTTP的关系。并列举HTTP的 ... 查看更多>>

1 点赞 0 评论

【守望者名企笔试题目】望海康信研发招聘笔试题

800 次浏览 2014-09-24 11:26

问题描述: 一.计算机基础部分　　1. CISC体系与RISC体系分别指什么?　　2. 面向对象的三个基本特征是什么?　　3. 抽象类与接口有什么区别?　　4. ISO\OSI网络参考模型分哪些层?　　5. 简述TCP/IP协定的特性及TCP和IP代表什么协 ... 查看更多>>

1 点赞 0 评论

【守望者名企笔试题目】阿里巴巴集团2014年校园招聘系统工程师北京笔试题

3046 次浏览 2014-09-24 11:15

问题描述: 第一部分单选题(前10题，每题2分;后10题，每题3分;共50分。选对得满分，选错倒扣一分，不选得0分。)　　1.字符串”alibaba”有()个不同的排列。　　A. 5040 B. 840 C. 14 D.420　　2.下列一段C++代码的输出是　　。 ... 查看更多>>

1 点赞 0 评论

【守望者名企笔试题目】百度2014校园招聘南京PC客户端开发笔试题

968 次浏览 2014-09-24 10:58

问题描述: 一、问答题：50分　　1、写出new和malloc、delete和free的区别　　2、写两个继承类，解释虚表指针和虚表的作用　　　　3、写出static的用法和作用　　　4、写出计算机的存储器层次，及原因　　　5、写出对windows中 ... 查看更多>>

1 点赞 0 评论

【守望者名企面试题目】摩托罗拉c语言笔试题目

887 次浏览 2014-09-23 17:27

问题描述: 相信很多想要进入摩托罗拉公司的工作的朋友，一定想知道其招牌时笔试面试都会考什么内容吧！为此今天小编为大家整理的了一系列题目，以供大家参考！　　1.打印如下图案，共19行，只能有一个for循环。　　*　　***　 ... 查看更多>>

1 点赞 0 评论

【守望者名企笔试题目】迅雷2014年笔试题目

876 次浏览 2014-09-23 16:26

问题描述: 一、单选题(20题，每题2分)　　1、有变量int i = 0; int a = i++; int b=++a; int c = a+b; 请问表达式 a?b:c 的值是()　　A、0 B、1 C、2 D、3　　2、32位环境下，int *p=new int;请问sizeof(p)的值为()　　A、4 B ... 查看更多>>

1 点赞 0 评论

【守望者名企面试题】淘宝2011年校园招聘笔试题目

790 次浏览 2014-09-23 15:47

问题描述: 一、单选题　　1、我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时 ... 查看更多>>

1 点赞 0 评论

【守望者名企笔试题目】网易c/c++工程师笔试题目

1050 次浏览 2014-09-23 15:26

问题描述: 1. #i nclude 和#i nclude “filename.h” 有什么区别?　　　　2. 在C++ 程序中调用被C 编译器编译后的函数，为什么要加extern “C”?　　　3. 一个类有基类、内部有一个其他类的成员对象，构造函数的执行顺序是怎样 ... 查看更多>>

1 点赞 0 评论

【守望者名企笔试题目】2014年百度linux笔试题目

1160 次浏览 2014-09-23 14:36

问题描述: 1. 从a.log文件中提取包含"WARNING"或"FATAL"，同时不包含"IGNOR"的行，然后提取以":"分割的第5个字段2. 编写一个脚本，只想简单的减法运算，要求提示输入变量　　3. Shell脚本阅读(解释下面执行的功能)，请挑出下面 ... 查看更多>>

		自动登录	找回密码
密码			立即注册

面试剖析

推荐阅读