帆软后端笔试(9.10~9.13)

下午参加了帆软后端的笔试,其中包含6道单选,4道多选,5道逻辑填空题,以及一道算法题。总体感觉偏难,以下印象比较深的一道逻辑题及算法题进行介绍。

  1. 有一道逻辑题比较有意思,大意是存在1000份水与1份无色试剂,提供若干可与该试剂反应的试纸,每次反应的时间为20分钟,如果需要在1个小时内找出该试剂,大致需要多少张试纸?

提示:每张试纸可以滴不受数量限制的样品,滴样品时间不受限制。

这道题分析有点类似于二分查找,但由于反应时间的限制,相对更加复杂,后来想想这点没分析好,填的结果并不对。。。

  1. 另一道是算法题:假设有n个链表,每个链表长度的不一,链表中每个的节点包含key与value。不同链表比较时,如果key值相同,则value相加,题目目标是将n个无序链表转化为单个有序链表。

链表数目 n与单个链表长度k1, k2, ..., kn,及每个节点信息需要通过控制台扫描输入,控制台中的节点形式为 1:2,因此需要对此字符串解析。这道题糅合了控制台输入解析,链表排序,链表合并,如果单个链表长度为50万到100万时,需要考虑如何优化链表排序与链表合并。

最开始打算 key与value保存在hashmap, 但感觉由hashmap构造链表不合适,其实节点类定义key与value也可以解决问题,这道题感觉还是挺难的,没a出来。。。

下面是提交后写的答案,参考了链表排序(leetcode 148)与合并k个升序链表(leetcode 23)

public class SortLinkedListDemo {
	 /*测试用例依次为 链表数目为3 单个链表长度分别为2、3、4,以及每个节点长度
	 3 2 3 4 
	 1:2 2:3 
	 3:4 2:7 4:3 
	 7:3 9:1 4:3 12:2*/

	public static void main(String[] args) throws IOException {
		ListNode[] listNodes = scannrValue();
		for (int i = 0; i < listNodes.length; i++) {
			listNodes[i]=sortSingleList(listNodes[i]);
		}
		ListNode head = mergeKLists(listNodes);
		
		//输出检验
		int count = 0;
		while (head != null) {
			System.out.println("count: " + (++count) + " key: " + head.key + " val: " + head.val);
			head = head.next;
		}
	}

	//扫描输入
	private static ListNode[] scannrValue() {
		Scanner sc = new Scanner(System.in);
		int linkedListNum = sc.nextInt();//链表数目
		int[] linkedListLength = new int[linkedListNum];
		for (int i = 0; i < linkedListNum; i++) {
			//保存每个链表长度
			linkedListLength[i] = sc.nextInt();
		}

		//节点解析,并将每个链表头结点保存在ListNode[]数组中
		ListNode[] listNodes = new ListNode[linkedListNum];
		for (int i = 0; i < linkedListNum; i++) {
			ListNode dummy = new ListNode(0, 0);
			ListNode cur = dummy;
			dummy.next = cur;
			for (int j = 0; j < linkedListLength[i]; j++) { 
				//节点解析
				String[] str = sc.next().split(":");
				ListNode temp = new ListNode(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
				cur.next = temp;
				cur = temp;
			}
			//添加头结点
			listNodes[i] = dummy.next;
		}
		return listNodes;
	}

	//采用归并进行链表排序
	public static ListNode sortSingleList(ListNode head) {
		if (head == null || head.next == null) return head;
		ListNode slow = head, fast = head, pre = head;
		while (fast != null && fast.next != null) {
			pre = slow;//这两步顺序很重要
			slow = slow.next;
			fast = fast.next.next;
		}
		pre.next = null;
		return merge(sortSingleList(head), sortSingleList(slow));
	}

	//输入两个链表头节点,返回合并后头节点
	private static ListNode merge(ListNode l1, ListNode l2) {
		if (l1 == null) return l2;
		if (l2 == null) return l1;

		ListNode cur = null;
		if (l1.key == l2.key) {
			l1.next = merge(l1.next, l2.next);
			l1.val +=l2.val;
			cur = l1;
		}
		if (l1.key < l2.key) {
			l1.next = merge(l1.next, l2);
			cur = l1;
		}
		if (l1.key > l2.key) {
			l2.next = merge(l1, l2.next);
			cur = l2;
		}
		return cur;
	}

	//n个链表合并
	public static ListNode mergeKLists(ListNode[] lists) {
		if (lists == null || lists.length == 0) return null;
		if (lists.length == 1) return lists[0];
		if (lists.length == 2) return merge(lists[0], lists[1]);

		return merge(mergeKLists(Arrays.copyOfRange(lists, 0, lists.length / 2)),
				mergeKLists(Arrays.copyOfRange(lists, lists.length / 2, lists.length)));
	}

	//节点定义
	static class ListNode {
		//模拟包含键值对类型链表
		private int key;
		private int val;
		private ListNode next;

		public ListNode(int key, int val) {
			this.key = key;
			this.val = val;
		}
	}
}


#笔试题目##帆软软件#
全部评论
楼主大概多久接到面试通知呢
1 回复 分享
发布于 2020-09-24 19:08
我感觉前面计算机基础选择题的好难啊
2 回复 分享
发布于 2020-09-19 20:21
链表题上次31号的笔试也是这个一模一样 大佬还是实打实的写链表啊? 我是直接merge数组了 每个数组存entry对……
点赞 回复 分享
发布于 2020-09-14 00:39
老哥我的思路是直接用treemap,边读边存,最后有序输出,你觉得有问题吗
点赞 回复 分享
发布于 2020-09-18 18:25
老哥们,帆软这个考试时间是自己选择一个合适的两小时去参加,是这样嘛?
点赞 回复 分享
发布于 2020-09-24 17:00

相关推荐

object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
已注销:测开吗?网易给的有点少 建议干三个月跳槽 然后来一段一整年的大厂 然后再找一段大厂转正实习无敌了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
01-17 11:44
你在各大软件投了一份又一份,你打招呼的hr一个接一个,但是只要你投过的,很快就下线了,没关系你的能量是很强,你看过的岗位招到人的速度都增加了。朋友们一个个拿着丰厚的实习回报,你却默默在家刷新邮箱,等待着那寥寥无几的面试通知。你每天一睁眼就狂投简历,你一有面试邀约就点确认。过年亲戚们围坐聊天,谈论着他们孩子的职场成就,你试图插话说自己面试过的公司数量,但他们显然不太感兴趣。你在心里自嘲,觉得他们不懂面试的艰辛、不懂得每一次面试机会的珍贵,不懂得一张张精心准备的简历背后的努力。笑你那个小侄子只会在网上刷刷职位,而你已经是各大招聘网站的常客。亲戚们夸赞自己孩子一年的成就,儿子的新工作,女儿的晋升,而...
龚新化:这帖删了呗,这跟我朋友有点相似,不过我是无所谓的😀,没什么感觉,我不轻易破防的,但是我一个朋友可能有点汗流浃背了😕,他不太舒服想睡了,当然不是我哈,我一直都是行的,以一个旁观者的心态看吧,也不至于破防吧😃,就是想照顾下我朋友的感受,他有点破防了,还是建议删了吧😯,当然删不删随你,因为我是没感觉的,就是为朋友感到不平罢了🥺
点赞 评论 收藏
分享
评论
4
40
分享

创作者周榜

更多
牛客网
牛客企业服务