[Bloomberg] 电面

今天面BB, 面傻了..第一题:

翻转,打印链表, 不能用任何数据结构, 不能改变指针和值

我用了20分钟想怎么不改变指针翻转链表, 用了10分钟证明了必须改变指针, 或者用stack存值, 但是面试官(ydr)依然不满意, 而且也没任何提示, 就说不行不行不行……以至于最后10分钟才知道还有下一道题.

然后, 然后我才明白, 原来不是翻转打印, 是print in reverse order..只要print就行….我当时就哭出来了, 这个用内存压,会爆栈的啊… 还不如用stack…算了..

第二题是在一个string后边加上最少的字符, 使得string成为回文, 这个面试见过. 10分钟就秒掉, 回头再看第一题还是不会….

本来特别想去bb的…哎..好好准备下周g家加面吧

public class ReverseList {
    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int x) {
            val = x;
        }
    }
    public static void reverse(ListNode head) {
        if (head == null)
            return;
        reverse(head.next);
        if (head != null)
        System.out.print(head.val+"->");
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next   = new ListNode(4);
        reverse(head);
    }
}

public static String getShortestPalindrome(String word) {
        if (word == null || word.equals("")) {
            return word;
        }

        int n = word.length();
        int left = 0;
        int right = n - 1;
        boolean previousCharWasMismatch = false;
        StringBuilder appendOnRight = new StringBuilder(n);
        StringBuilder matchedOnRight = new StringBuilder(n);

        while (left < right) {
            char leftChar = word.charAt(left);
            char rightChar = word.charAt(right);

            if (leftChar == rightChar) {
                matchedOnRight.append(leftChar);
                ++left;
                --right;
                previousCharWasMismatch = false;
            } else {
                appendOnRight.append(matchedOnRight);
                matchedOnRight.setLength(0);
                right = n - 1;

                if (previousCharWasMismatch) {
                    appendOnRight.append(leftChar);
                    ++left;
                }

                previousCharWasMismatch = true;
            }
        }
        
        return appendOnRight.toString();
    }

ps:上面code是quora找的