面试初体验

前几天我经历了人生中的第一次工作面试,对于这次的整个面试过程我是记忆深刻的。总体来说,这次面试让我熟悉了整个面试流程,相信对以后找工作是有所帮助的。以下我整理了面试的大概问题。

  • 编译和解释的区别,你认为java属于哪一种(java在多平台上运行的原理)?
  • GC工作原理
  • 一个类能够继承多个类吗?C++行吗?如果想要实现此功能,java采用了哪种机制?
  • 抽象类和接口的区别
  • 叙述快速排序过程,时间复杂度
  • 叙述堆排序过程,如何存储,时间复杂度
  • 口述广度优先遍历、深度优先遍历伪代码
  • 判断一个整数是否为2的幂的方法

 

回答:

1.
  • 编译是编译器把源文件处理一遍,生成一个目标文件,而解释是边处理源文件边执行。我认为java是半编译半解释的语言,java的第一道工序是javac编译,生成目标文件BYTECODE。后续可能有三种情况:
  • 运行时,BYTECODE由JVM逐条解释执行
  • 运行时,部分代码可能由JIT(即时编译器)翻译为目标机器指令(以method为翻译单位,还会保存起来,第二次执行就不用翻译了)直接执行
  • RTSJ,继javac之后执行AOT(静态编译)二次编译,生成静态的目标平台代码(典型的就是WEBSHPERE REAL TIME)

补充:JVM结构http://blog.csdn.net/tonytfjing/article/details/44278233

2.
  • 对于GC来说,当程序员创建对象时,GC就开始监控这个对象的地址、大小以及使用情况。通常,GC采用有向图的方式记录和管理堆(heap)中的所有对象。通过这种方式确定哪些对象是\”可达的\”,哪些对象是\”不可达的\”.当GC确定一些对象为\”不可达\”时,GC就有责任回收这些内存空间。
3.
  • 在Java中一个类不能够继承多个类,但在C++中可以,如果想要实现此功能,java采取了接口的方式。
4.
  • 抽象类和接口的区别
  • 什么是接口?接口是一种规范,就像现实中生产主板和内存条或者网卡的不是同一家产商,但是为何内存或者网卡插入到主板上就能用呢,因为他们都遵守了某种规范。然后就可以使用。虽然他们的内部实现可能完全不同。就好比在java语言中的方法内部实现你不需要关心,只需要知道这个接口是怎样的干嘛的就行了,直接用。既然是一种规范,那他在编程语言中就能在架构中起到非常之大的作用,在一个应用程序之间的时候,接口体现的是一耦合标准。特别是在多个应用程序需要对接的时候。接口是多个应用程序的通信标准。
  • 什么是抽象类?就是对类更高的抽象。抽象类作为多个子类的共同父类。它所体现的是一种模版设计,抽象类作为多个子类的父类,可以把它理解为系统实现过程中的中间产品,这个中间产品已经实现了系统的部分功能,但是不能当成最终产品,还需要进一步的完善。
  • 他们的特征:接口和抽象类都不能实例化,他们都位于继承树的顶端,用于被其他类实现和继承。
  • 接口和抽象类都可以包含抽象方法,实现接口或继承抽象类的普通子类都必须实现这些抽象方法。
  • 他们的区别:
    • 属性:接口没有普通属性,只有静态属性,并且只能用public final static 修饰 (并且是默认的就算你在接口中定义Int i =0 它也会被隐式的加上public final static )。而抽象类可以有普通属性,可以有静态属性(类属性)
    • 方法:接口中的方法都没有方法体 并且都是默认使用public abstracrt 修饰,不能定义静态方法。 而抽象类可以有普通方法 也可以有没有抽象方法 也可以定义静态方法
    • 构造函数:接口中没有构造器,抽象类中有构造器,但是它不能用于new 对象 而是用于子类调用来初始化抽象类的操作。
    • 初始化块:接口中不能包含初始化块,而抽象方法中可以包含初始化块
  • 一个类只能有一个直接父类,包括抽象类,而类可以实现多个接口,弥补了java不能多继承的不足。
接口 抽象类
多继承 支持 不支持
类型限制 没有 有,只能是引用类型
方法实现 继承类型中必须给出方法实现 继承类中可以不给出
扩展性 比较麻烦 相对比较灵活
多层继承 比较麻烦,需要借助虚函数 比较灵活

 

5.
  • 快速排序(时间复杂度)

基本思想:

  • 从序列中选择一个基准数(pivot),一般选择第一个数或最后一个数作为基准数,这里选择第一个数作为基准数。
  • 设置两个指针分别指向第一个数(low)和最后一个数(high)。
  • 指向high的指针左移从右往左找出第一个比基准数小的数,把a[low]和a[high]交换。
  • 指向low的指针右移从左往右找出第一个比基准数大的数,把a[low]和a[high]交换。
  • 重复上述两步直到low和high相遇,返回low,以low为中心,把序列分为两个序列,依次从1步骤执行,直到所有子集中只有一个元素为止。

代码实现见八大排序

6.
  • 堆排序(时间复杂度)

基本思想:

  • 首先将序列元素依次放入完全二叉树中,构建成大顶堆,父节点的值大于子节点。
  • 取出当前大顶堆的根节点,将其与序列最后一个元素进行交换。
  • 对交换后的n-1个序列元素进行大顶堆调整。
  • 重复上面两个步骤,直到堆中只有一个元素。

补充:调整时先从最后一个元素的父节点((length-1)/2)开始,其左孩子节点为2*父节点+1。

代码实现见八大排序

7.
  • 深度优先遍历

基本思想:

  • 访问顶点v;
  • 从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;
  • 重复上述两步,直到图中所有顶点和v有路径相通的顶点被访问到;

伪代码:

递归实现:

  • 访问顶点v;visited[v]=1;visited[n]=0;
  • w=顶点v的第一个邻接点;
  • while(w存在)

if(w未被访问)

从顶点w出发执行递归算法

else

w=顶点v的下一个邻接点

非递归实现:

  • 栈s初始化;visited[n]=0;
  • 访问顶点v,visited[v]=1,顶点v入栈;
  • while(栈s非空)

x=栈s的顶元素

if(存在未被访问到的x的邻接点w)

访问w,visited[w]=1,w入栈

else

x出栈

广度优先遍历:

基本思想:

  • 顶点v入队列
  • 当队列非空时,则继续执行,否则运算结束
  • 出队列取得对头顶点v,访问顶点v并标记顶点v已被访问
  • 查找顶点v的第一个邻接点w
  • 若顶点v的第一个邻接点未被访问过,则w入队列
  • 继续查找顶点v的下一个邻接点,转到步骤5,直到顶点v的所有未被访问过的邻接点处理完

伪代码:

  • 初始化队列Q,visited[n]=0
  • 访问顶点v,visited[v]=1,顶点v入队列Q
  • While(队列Q不为空)

v=队列Q的队头元素,出队

w=顶点v的第一个邻接点

while(w存在)

if(w未被访问)

w入队,visited[w]=1,w=v的下一个邻接点

8.
  • 两种方法
  • 对2取余,判断是否有余数,除2。时间复杂度
  • 2的幂的本质是二进制只有一个1,则可以采用n&(n-1)判断是否为0

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注