数据结构面试题与答案

数据结构面试题与答案

  数据结构面试的时候我们需要面试题,大家可以看看下面的数据结构面试题与答案哦!

  数据结构面试题与答案

  1、给出一个函数来输出一个字符串的所有排列。

  ANSWER 简单的回溯就可以实现了。当然在排列的产生也有很多种算法,去看看组合数学,

  还有逆序生成排列和一些不需要递归生成排列的方法。

  印象中Knuth 的第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底,也需要一定的.灵感,有兴趣最好看看。

  ANSWER:

  Have done this.

  2、题目:设计一个类,我们只能生成该类的一个实例。

  分析:只能生成一个实例的类是实现了Singleton 模式的类型。

  ANSWER

  I’m not good at multithread programming... But if we set a lazy initialization, the “if” condition could be interrupted thus multiple constructor could be called, so we must add synchronized to the if judgements, which is a loss of efficiency. Putting it to the static initialization will guarantee that the constructor only be executed once by the java class loader.

  public class Singleton {

  private static Singleton instance = new Singleton();

  private synchronized Singleton() {

  }

  public Singleton getInstance() {

  return instance();

  }

  }

  This may not be correct. I’m quite bad at this...

  3、题目:实现函数double Power(double base, int exponent),求base 的exponent 次方。

  不需要考虑溢出。

  分析:这是一道看起来很简单的问题。可能有不少的人在看到题目后30 秒写出如下的代码:

  double Power(double base, int exponent)

  {

  double result = 1.0;

  for(int i = 1; i <= exponent; ++i)

  result *= base;

  return result;

  }

  ANSWER

  …

  double power(double base, int exp) {

  if (exp == 1) return base;

  double half = power(base, exp >> 1);

  return (((exp & 1) == 1) ? base : 1.0) half half;

  }

  4、输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。

  分析:可能很多人都写过判断一个字符串是不是对称的函数,这个题目可以看成是该函数的

  加强版。

  ANSWER

  Build a suffix tree of x and inverse(x), the longest anagram is naturally found.

  Suffix tree can be built in O(n) time so this is a linear time solution.

  74.数组中超过出现次数超过一半的数字

  题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。

  分析:这是一道广为流传的面试题,包括百度、微软和Google 在内的多家公司都

  曾经采用过这个题目。要几十分钟的时间里很好地解答这道题,

  除了较好的编程能力之外,还需要较快的反应和较强的逻辑思维能力。

  ANSWER

  Delete every two different digits. The last one that left is the one.

  int getMajor(int a[], int n) {

  int x, cnt=0;

  for (int i=0; i<n; i++) {

  if (cnt == 0) {

  x = a[i]; cnt++;

  } else if (a[i]==x) {

  cnt ++;

  } else {

  cnt --;

  }

  }

  return x;

  }

相关文章

经典JS闭包面试题

都答对了么?如果都答对了恭喜你在js闭包问题当中几乎没什么可以难住你了;如果没有答案,继续往下分析。AD:由工作中演变而来的面试题这是一个我工作当中的遇到的一个问题,似乎很有趣,就当做了一道题去面试,...
面试题2018-05-03
经典JS闭包面试题

百事可乐面试题集锦

百事公司(Pepsico.,Inc.)是一家饮料和休闲食品公司。为全球第四大食品和饮料公司。公司总部设在纽约市。公司附属机构近百个,主要有百事可乐饮料公司、弗利托-莱公司(快餐馆)、啤咂餐馆(供应意大...
面试题2011-04-08
百事可乐面试题集锦

会计类面试题含答案

很多考生进入面试之后会有短暂的雀跃,而后便是无限的惆怅。因为面试更为侧重测查大家的临场应变能力和综合素质,而这恰恰是很多考生望而却步的短板。下面是小编整理的会计类面试题(含答案),可参考!  会计类面...
面试题2019-07-08
会计类面试题含答案

财务面试题目及答案

在学习、工作生活中,我们最不陌生的就是试题了,试题是学校或各主办方考核某种知识才能的标准。你知道什么样的试题才是规范的吗?以下是小编整理的最新的财务面试题目及答案,欢迎大家分享。最新财务面试题目及答案...
面试题2016-08-07
财务面试题目及答案

甲骨文(Oracle)面试题目

这也许是你一直期待的文章,在关注这部分技术问题的同时,请务必阅读有关面试中有关个人的问题和解答,甲骨文(Oracle)面试题目。这里的回答并不是十分全面,这些问题可以通过多个...
面试题2012-04-06
甲骨文(Oracle)面试题目

十道常见的面试题及回答

一、为什么来单位应聘?说出该单位吸引你的地方,比如说规模较大,有发展前途,表达你想到该单位工作的愿望。二、为何选择这份工作?分析自己的志趣、专长所在,说明自己所学专业、工作经历以及对这项工作的期待 一...
面试题2018-09-08
十道常见的面试题及回答