【Java】面试的季节到了,老哥确定不来复习下数据结构吗

面试的季节到了,老哥确定不来复习下数据结构

Silently9527发布于 7 分钟前

前言

在上一次《面试篇》Http协议中,面试官原本想的是http问的差不多了,想要继续问我JAVA相关的一些问题,结果我突然觉得嗓子不舒服咳嗽了几声,(在这个敏感的时候)吓退了面试官,面试官带起口罩后就说面试先暂时到这里,下次再聊;两周之后我又收到了HR的电话;

HR:感冒好了吗?上次面试的结果不错,你什么时候有时间来我们公司二面呢?

我:随时准备着

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

到公司后,我依然被带到了那个小黑屋,等待着面试官的到来。没想等来的是一位美女小姐姐。

我:人美声甜的小姐姐,你是本次的面试官?(我窃喜中)

美女面试官:是的,上次面试你的面试官开会去了,这次面试我来和你聊聊

面试官:看你这么会说话,让我先来帮你开个胃,说说二分查找吧

我:(果然是开胃啊,这位小姐姐竟然如此善良)

我:二分查找法是在一个有序的数组中查到一个值,如果存在就返回在数组中的索引,否则就返回-1;算法维护了两个变量lo(最小)和hi(最大),每次查找都与中间值(mid)进行比较,如果等于就返回mid,大于就查询右半边的数组,小于就查询左半边数组。二分查找法之所以快是因为每次一次查询都会排除掉一半的值。

public class BinarySearch {

/**

* 二分查找

* @param key

* @param arr

* @return 存在返回对应的下标,不存在返回 -1

*/

public static int search(int key, int[] arr) {

int lo = 0, hi = arr.length - 1;

while (lo <= hi) {

int mid = lo + (hi - lo) / 2;

if (key > arr[mid]) {

lo = mid + 1;

} else if (key < arr[mid]) {

hi = mid - 1;

} else {

return mid;

}

}

return -1;

}

}

对于一个包含n个元素的列表,用二分查找法最多需要log2n(前面的2是底数)次就可以判断出元素是否存在;所以二分查找法的时间复杂度是O(log n)

面试官:说说使用数组如何实现栈?

我:小姐姐,栈的特点就是后进先出,使用数组和链表都可以实现栈的功能,首先看下栈的定义:

public interface Stack<T> extends Iterable {

void push(T item); //向栈添加元素

T pop(); //从栈中弹出

boolean isEmpty();

int size(); //返回元素的个数

}

栈在使用的时候有可能也会遍历全部的元素,所以继承了Iterable,使用数组实现栈的完整代码:

public class FixCapacityArrayStack<T> implements Stack<T> {

private T[] arr;

private int size;

public FixCapacityArrayStack(int capacity) {

this.arr = (T[]) new Object[capacity]; //初始化数组大小

}

@Override

public void push(T item) {

this.arr[size++] = item;

}

@Override

public T pop() {

return this.arr[--size];

}

@Override

public boolean isEmpty() {

return size == 0;

}

@Override

public int size() {

return this.size;

}

@Override

public Iterator<T> iterator() {

return new Iterator<T>() {

int index;

@Override

public boolean hasNext() {

return index < size;

}

@Override

public T next() {

return arr[index++];

}

};

}

}

面试官:你刚才实现的栈是定容的,那如何实现动态调整栈的大小

我:(已猜到你会问这个问题了,刚才故意没说动态调整大小;经过多年的面试经验总结,最和谐的面试过程就是与面试官你推我挡,一上来就说出了最优解,如何体现面试官的优越感?)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

我:要实现动态的调整大小,首先需要在提供一个 resize 的方法,把数组扩容到指定的大小并拷贝原来的数据到新的数组中;

private void resize(int newCapacity) {

Object[] tmp = new Object[newCapacity];

for (int index = 0; index < size; index++) {

tmp[index] = arr[index];

}

this.arr = (T[]) tmp;

}

需要push方法中检查当前的size是否已经达到了数组的最大容量,如果是,就把数组扩容2倍

@Override

public void push(T item) {

if (this.arr.length == size) {

this.resize(2 * this.arr.length);

}

this.arr[size++] = item;

}

pop方法中需要检查当前占用的空间是否是数组的四分之一,如果是,就需要把数据的容量缩小到原来的一半

@Override

public T pop() {

T item = this.arr[--size];

this.arr[size] = null; //避免游离对象,让垃圾回收器回收无用对象

if (size > 0 && size == this.arr.length / 4) {

this.resize(this.arr.length / 2);

}

return item;

}

面试官:刚才你提到了链表,那么使用链表如何实现栈

我:(这就是你推我挡的结果,和小姐姐的互动很和谐)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

我:使用链表,首先需要先定义个Node,单向的链表包含了值和下一个节点的引用

public class Node<T> {

private T item;

private Node next;

}

采用链表实现的栈相对于数组实现还较为简单一些,不需要考虑扩容的问题。

public class LinkedListStack<T> implements Stack<T> {

private Node<T> first;

private int size;

@Override

public void push(T item) {//先栈顶添加元素

this.first = new Node<>(item, first);

size++;

}

@Override

public T pop() { //从栈顶删除元素

T item = first.getItem();

size--;

first = first.getNext();

return item;

}

@Override

public boolean isEmpty() {

return first == null;

}

@Override

public int size() {

return this.size;

}

@Override

public Iterator<T> iterator() {

return new Iterator<T>() {

private Node<T> current = first;

@Override

public boolean hasNext() {

return current != null;

}

@Override

public T next() {

T item = current.getItem();

current = current.getNext();

return item;

}

};

}

}

面试官:使用链表如何实现先进先出队列

我:与栈的实现过程类似,首先需要定义出队列

public interface Queue<T> extends Iterable {

void enqueue(T item); //入队列

T dequeue(); //出队列

int size();

boolean isEmpty();

}

使用链表实现队列需要维护两个变量first、last;first表示的是队列的头结点,last表示队列的尾结点;当入队列时enqueue向尾部结点添加元素,当出队列时dequeue从头结点删除元素。

public class LinkedListQueue<T> implements Queue<T> {

private Node<T> first;

private Node<T> last;

private int size;

@Override

public void enqueue(T item) {

Node<T> node = new Node<>(item, null);

if (isEmpty()) {

first = node; //当队列为空,first和last指向同一个元素

} else {

last.setNext(node);

}

last = node;

size++;

}

@Override

public T dequeue() {

T item = first.getItem();

first = first.getNext();

if (isEmpty()) { //当队列为空时,需要把last设置为null

last = null;

}

size--;

return item;

}

@Override

public int size() {

return this.size;

}

@Override

public boolean isEmpty() {

return first == null; //首节点为空

}

@Override

public Iterator<T> iterator() {

return new Iterator<T>() {

private Node<T> current = first;

@Override

public boolean hasNext() {

return current != null;

}

@Override

public T next() {

T item = current.getItem();

current = current.getNext();

return item;

}

};

}

}

面试官:胃开的差不多了,来聊一点算法吧;你来设计一个算法对算术表示式求值,比如:( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

我:(昨天晚上熬夜看算法没白辛苦啊,刚好看到了这个解法。)

我:(挠挠头),这个问题有点麻烦,我需要思考一会。(这样显得我是没有提前准备的,属于临场发挥)

我:定义两个栈,一个用于保存运算符,一个用户保存操作数;具体的操作过程如下:

  • 忽略左边括号
  • 遇到数字就压入操作数栈
  • 遇到符号就压入符号栈
  • 遇到右括号,弹出一个运算符,弹出所需要的操作数,将计算的结果再次压入到操作数栈

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

public static int calculate(String expression) {

Stack<String> operate = new LinkedListStack<>();

Stack<Integer> numbers = new LinkedListStack<>();

String[] split = expression.split(" ");

for (String str : split) {

if ("(".equals(str)) {

} else if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {

operate.push(str);

} else if (")".equals(str)) {

String op = operate.pop();

int resut = 0;

if ("+".equals(op)) {

resut = numbers.pop() + numbers.pop();

} else if ("-".equals(op)) {

resut = numbers.pop() - numbers.pop();

} else if ("*".equals(op)) {

resut = numbers.pop() * numbers.pop();

} else if ("/".equals(op)) {

resut = numbers.pop() / numbers.pop();

}

numbers.push(resut);

} else {

numbers.push(Integer.valueOf(str));

}

}

return numbers.pop();

}

面试官:一个int类型的数组,其中存在三个数字相加等于0,你来设计个算法帮我统计出有多少组这样的数字

我:这个简单,请看代码:

public static int count1(int[] arr) {

int length = arr.length;

int count = 0;

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

for (int j = i + 1; j < length; j++) {

for (int k = j + 1; k < length; k++) {

if (arr[i] + arr[j] + arr[k] == 0) {

count++;

}

}

}

}

return count;

}

面试官:假如这个数组有100万的int值,你这个算法得运行到什么时候

我:(对的哦,这个算法的时间复杂度是O(n³),在遇到数据量较大时效率极低)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

(经过大脑快速思考后)

我:这个算法确实有问题,我大意了,没有考虑到大量数据的情况;用这个算法会浪费小姐姐的大好青春,所以刚才我思考了下,对这个算法进行改进一下;

首先把3-sum简化成2-sum

2-sum中,一个数a[i]要与另一个数相加等于0;有两种方法:

第一种:与3-sum实现类似使用两层循环,时间复杂度是O(n²)

第二种:只需要找出数组中是否有-a[i],查找的算法使用二分查找法

public static int count2(int[] arr) {

Arrays.sort(arr); //首先排序

int length = arr.length;

int count = 0;

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

if (BinarySearch.search(-arr[i], arr) > i) {

count++;

}

}

return count;

}

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

对待3-sum也是用类似的方法,直接上机撸代码:

public static int count3(int[] arr) {

Arrays.sort(arr);

int length = arr.length;

int count = 0;

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

for (int j = i + 1; j < length; j++) {

if (BinarySearch.search(-arr[i]-arr[j], arr) > j) {

count++;

}

}

}

return count;

}

我:小姐姐,这个算法改进之后的时间复杂度是O(n²log n),我已经尽力了,只能这么快了。(面试官露出迷人的微笑)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

面试官:假如你是微信的开发人员,随便给你两个用户,如何判断这两个用户是否连通的。何为连通?A是B的好友,B是C的好友,那么A与C就是连通的

我:(这小姐姐的问题是越来越难了)

我:美丽的面试官,今天烧脑严重,我可以趴下休息一会吗?(其实是没想到好的解法,拖延时间战术)

面试官:可以,那你先休息10分钟。

面试未完,待续

最后(点关注,不迷路)

文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。

最后,写作不易,请不要白嫖我哟,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源🙏

java算法数据结构和算法

阅读 12发布于 7 分钟前

本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议


贝塔学JAVA

公众号:贝塔学JAVA Java程序员所需要掌握的核心知识: 集合框架、JVM机制、多线程与并发框架、网络协议...

avatar

Silently9527

公众号:贝塔学JAVA

238 声望

26 粉丝

0 条评论

得票时间

avatar

Silently9527

公众号:贝塔学JAVA

238 声望

26 粉丝

宣传栏

前言

在上一次《面试篇》Http协议中,面试官原本想的是http问的差不多了,想要继续问我JAVA相关的一些问题,结果我突然觉得嗓子不舒服咳嗽了几声,(在这个敏感的时候)吓退了面试官,面试官带起口罩后就说面试先暂时到这里,下次再聊;两周之后我又收到了HR的电话;

HR:感冒好了吗?上次面试的结果不错,你什么时候有时间来我们公司二面呢?

我:随时准备着

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

到公司后,我依然被带到了那个小黑屋,等待着面试官的到来。没想等来的是一位美女小姐姐。

我:人美声甜的小姐姐,你是本次的面试官?(我窃喜中)

美女面试官:是的,上次面试你的面试官开会去了,这次面试我来和你聊聊

面试官:看你这么会说话,让我先来帮你开个胃,说说二分查找吧

我:(果然是开胃啊,这位小姐姐竟然如此善良)

我:二分查找法是在一个有序的数组中查到一个值,如果存在就返回在数组中的索引,否则就返回-1;算法维护了两个变量lo(最小)和hi(最大),每次查找都与中间值(mid)进行比较,如果等于就返回mid,大于就查询右半边的数组,小于就查询左半边数组。二分查找法之所以快是因为每次一次查询都会排除掉一半的值。

public class BinarySearch {

/**

* 二分查找

* @param key

* @param arr

* @return 存在返回对应的下标,不存在返回 -1

*/

public static int search(int key, int[] arr) {

int lo = 0, hi = arr.length - 1;

while (lo <= hi) {

int mid = lo + (hi - lo) / 2;

if (key > arr[mid]) {

lo = mid + 1;

} else if (key < arr[mid]) {

hi = mid - 1;

} else {

return mid;

}

}

return -1;

}

}

对于一个包含n个元素的列表,用二分查找法最多需要log2n(前面的2是底数)次就可以判断出元素是否存在;所以二分查找法的时间复杂度是O(log n)

面试官:说说使用数组如何实现栈?

我:小姐姐,栈的特点就是后进先出,使用数组和链表都可以实现栈的功能,首先看下栈的定义:

public interface Stack<T> extends Iterable {

void push(T item); //向栈添加元素

T pop(); //从栈中弹出

boolean isEmpty();

int size(); //返回元素的个数

}

栈在使用的时候有可能也会遍历全部的元素,所以继承了Iterable,使用数组实现栈的完整代码:

public class FixCapacityArrayStack<T> implements Stack<T> {

private T[] arr;

private int size;

public FixCapacityArrayStack(int capacity) {

this.arr = (T[]) new Object[capacity]; //初始化数组大小

}

@Override

public void push(T item) {

this.arr[size++] = item;

}

@Override

public T pop() {

return this.arr[--size];

}

@Override

public boolean isEmpty() {

return size == 0;

}

@Override

public int size() {

return this.size;

}

@Override

public Iterator<T> iterator() {

return new Iterator<T>() {

int index;

@Override

public boolean hasNext() {

return index < size;

}

@Override

public T next() {

return arr[index++];

}

};

}

}

面试官:你刚才实现的栈是定容的,那如何实现动态调整栈的大小

我:(已猜到你会问这个问题了,刚才故意没说动态调整大小;经过多年的面试经验总结,最和谐的面试过程就是与面试官你推我挡,一上来就说出了最优解,如何体现面试官的优越感?)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

我:要实现动态的调整大小,首先需要在提供一个 resize 的方法,把数组扩容到指定的大小并拷贝原来的数据到新的数组中;

private void resize(int newCapacity) {

Object[] tmp = new Object[newCapacity];

for (int index = 0; index < size; index++) {

tmp[index] = arr[index];

}

this.arr = (T[]) tmp;

}

需要push方法中检查当前的size是否已经达到了数组的最大容量,如果是,就把数组扩容2倍

@Override

public void push(T item) {

if (this.arr.length == size) {

this.resize(2 * this.arr.length);

}

this.arr[size++] = item;

}

pop方法中需要检查当前占用的空间是否是数组的四分之一,如果是,就需要把数据的容量缩小到原来的一半

@Override

public T pop() {

T item = this.arr[--size];

this.arr[size] = null; //避免游离对象,让垃圾回收器回收无用对象

if (size > 0 && size == this.arr.length / 4) {

this.resize(this.arr.length / 2);

}

return item;

}

面试官:刚才你提到了链表,那么使用链表如何实现栈

我:(这就是你推我挡的结果,和小姐姐的互动很和谐)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

我:使用链表,首先需要先定义个Node,单向的链表包含了值和下一个节点的引用

public class Node<T> {

private T item;

private Node next;

}

采用链表实现的栈相对于数组实现还较为简单一些,不需要考虑扩容的问题。

public class LinkedListStack<T> implements Stack<T> {

private Node<T> first;

private int size;

@Override

public void push(T item) {//先栈顶添加元素

this.first = new Node<>(item, first);

size++;

}

@Override

public T pop() { //从栈顶删除元素

T item = first.getItem();

size--;

first = first.getNext();

return item;

}

@Override

public boolean isEmpty() {

return first == null;

}

@Override

public int size() {

return this.size;

}

@Override

public Iterator<T> iterator() {

return new Iterator<T>() {

private Node<T> current = first;

@Override

public boolean hasNext() {

return current != null;

}

@Override

public T next() {

T item = current.getItem();

current = current.getNext();

return item;

}

};

}

}

面试官:使用链表如何实现先进先出队列

我:与栈的实现过程类似,首先需要定义出队列

public interface Queue<T> extends Iterable {

void enqueue(T item); //入队列

T dequeue(); //出队列

int size();

boolean isEmpty();

}

使用链表实现队列需要维护两个变量first、last;first表示的是队列的头结点,last表示队列的尾结点;当入队列时enqueue向尾部结点添加元素,当出队列时dequeue从头结点删除元素。

public class LinkedListQueue<T> implements Queue<T> {

private Node<T> first;

private Node<T> last;

private int size;

@Override

public void enqueue(T item) {

Node<T> node = new Node<>(item, null);

if (isEmpty()) {

first = node; //当队列为空,first和last指向同一个元素

} else {

last.setNext(node);

}

last = node;

size++;

}

@Override

public T dequeue() {

T item = first.getItem();

first = first.getNext();

if (isEmpty()) { //当队列为空时,需要把last设置为null

last = null;

}

size--;

return item;

}

@Override

public int size() {

return this.size;

}

@Override

public boolean isEmpty() {

return first == null; //首节点为空

}

@Override

public Iterator<T> iterator() {

return new Iterator<T>() {

private Node<T> current = first;

@Override

public boolean hasNext() {

return current != null;

}

@Override

public T next() {

T item = current.getItem();

current = current.getNext();

return item;

}

};

}

}

面试官:胃开的差不多了,来聊一点算法吧;你来设计一个算法对算术表示式求值,比如:( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

我:(昨天晚上熬夜看算法没白辛苦啊,刚好看到了这个解法。)

我:(挠挠头),这个问题有点麻烦,我需要思考一会。(这样显得我是没有提前准备的,属于临场发挥)

我:定义两个栈,一个用于保存运算符,一个用户保存操作数;具体的操作过程如下:

  • 忽略左边括号
  • 遇到数字就压入操作数栈
  • 遇到符号就压入符号栈
  • 遇到右括号,弹出一个运算符,弹出所需要的操作数,将计算的结果再次压入到操作数栈

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

public static int calculate(String expression) {

Stack<String> operate = new LinkedListStack<>();

Stack<Integer> numbers = new LinkedListStack<>();

String[] split = expression.split(" ");

for (String str : split) {

if ("(".equals(str)) {

} else if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {

operate.push(str);

} else if (")".equals(str)) {

String op = operate.pop();

int resut = 0;

if ("+".equals(op)) {

resut = numbers.pop() + numbers.pop();

} else if ("-".equals(op)) {

resut = numbers.pop() - numbers.pop();

} else if ("*".equals(op)) {

resut = numbers.pop() * numbers.pop();

} else if ("/".equals(op)) {

resut = numbers.pop() / numbers.pop();

}

numbers.push(resut);

} else {

numbers.push(Integer.valueOf(str));

}

}

return numbers.pop();

}

面试官:一个int类型的数组,其中存在三个数字相加等于0,你来设计个算法帮我统计出有多少组这样的数字

我:这个简单,请看代码:

public static int count1(int[] arr) {

int length = arr.length;

int count = 0;

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

for (int j = i + 1; j < length; j++) {

for (int k = j + 1; k < length; k++) {

if (arr[i] + arr[j] + arr[k] == 0) {

count++;

}

}

}

}

return count;

}

面试官:假如这个数组有100万的int值,你这个算法得运行到什么时候

我:(对的哦,这个算法的时间复杂度是O(n³),在遇到数据量较大时效率极低)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

(经过大脑快速思考后)

我:这个算法确实有问题,我大意了,没有考虑到大量数据的情况;用这个算法会浪费小姐姐的大好青春,所以刚才我思考了下,对这个算法进行改进一下;

首先把3-sum简化成2-sum

2-sum中,一个数a[i]要与另一个数相加等于0;有两种方法:

第一种:与3-sum实现类似使用两层循环,时间复杂度是O(n²)

第二种:只需要找出数组中是否有-a[i],查找的算法使用二分查找法

public static int count2(int[] arr) {

Arrays.sort(arr); //首先排序

int length = arr.length;

int count = 0;

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

if (BinarySearch.search(-arr[i], arr) > i) {

count++;

}

}

return count;

}

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

对待3-sum也是用类似的方法,直接上机撸代码:

public static int count3(int[] arr) {

Arrays.sort(arr);

int length = arr.length;

int count = 0;

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

for (int j = i + 1; j < length; j++) {

if (BinarySearch.search(-arr[i]-arr[j], arr) > j) {

count++;

}

}

}

return count;

}

我:小姐姐,这个算法改进之后的时间复杂度是O(n²log n),我已经尽力了,只能这么快了。(面试官露出迷人的微笑)

【Java】面试的季节到了,老哥确定不来复习下数据结构吗

面试官:假如你是微信的开发人员,随便给你两个用户,如何判断这两个用户是否连通的。何为连通?A是B的好友,B是C的好友,那么A与C就是连通的

我:(这小姐姐的问题是越来越难了)

我:美丽的面试官,今天烧脑严重,我可以趴下休息一会吗?(其实是没想到好的解法,拖延时间战术)

面试官:可以,那你先休息10分钟。

面试未完,待续

最后(点关注,不迷路)

文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。

最后,写作不易,请不要白嫖我哟,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源🙏

以上是 【Java】面试的季节到了,老哥确定不来复习下数据结构吗 的全部内容, 来源链接: www.h5w3.com/114014.html

回到顶部