Yahoo on site 面试题2道 最新


2轮,每轮一个算法题
第一题 判断链表是否是回文,要求O(n)时间,O(1)空间。
第二题 求求子数组和接近0的子数组,要求的算法是O(nlgn)时间,空间没要求

设计题是设计IM系统,问到分布式架构。
还有一些系统调优问题。
已邀请:

helifort - 70后老码农

赞同来自: william athur


第一题,如果没有空间限制,最简单的是用一个stack 保存前半部分的节点,然后挨个比较后半部的节点,要注意如果奇数情况的处理

要求空间O(1)的话,就比较麻烦,算法是这样
1 快慢指针找到中点,把链表分成两部分
2 原地翻转后部分链表,重点是要原地翻转,所以不能用递归,不过我觉得递归还不好理解,循环好理解,以下是原地翻转链表的代码,是这个算法的核心,这个搞定其他都不是很麻烦。
    ListNode current = head;
    ListNode pre = null;
    ListNode next = null;

    while (current != null) {
        //record second node
        next = current.next;
        current.next = pre;
        pre = current;
        current = next;
    }
    return pre;


3 比较前部分和翻转后的部分的节点是否相等
4 再把后部分翻转回来接上

要回复问题请先登录注册

返回顶部