At the request of the students, I will sort out the algorithm questions encountered in the interview in these two weeks, which need to be implemented by hand (Java, Android, and the flutter surface guide please go to the android-flutter surface guide juejin.cn/post/684490… It is recommended to use the computer to view, more content)

My algorithm is quite dish, before the interview also did not brush the concept of the question, so the algorithm answer is very bad, the following simply say what have met

Check if a single linked list has rings

This question has been asked three times, which should be quite frequent. For the first time, I only thought of the first method below, and the interviewer was very nice and guided me to give the second solution

Method 1: loop through the node, each node will be marked, and the traversal process to determine whether it is marked, if it is marked, it indicates that there is a ring. Public class Solution {public Boolean hasCycle(ListNode head) {// Declare onesetSet<ListNode> Set<ListNode>set = new HashSet<>();
        while(head! =null) {if(set.contains(head)) {
                return true;
            }else{ set.add(head); head = head.next; }}return false; If the list has a loop, it will catch up with the slow pointer. If the list has no loop, it will reach the end of the list. Public class Solution {public Boolean hasCycle(ListNode head) {== quick = head; ListNode slow = head; // When the fast pointer can go to the end, it is acyclicwhile(quick! =null&&quick.next! =null){ quick = quick.next.next; slow = slow.next;if(quick==slow){
                return true; }}return false; }}Copy the code

Swaps the order of all adjacent nodes in a linked list

1->2->3->4 after the exchange, 2->1->4->3.

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null)
            return null;
        if(head.next==null){
            return head;
        }
        ListNode newHead = head.next;
        while(head.next! =null){ ListNode nextNode = head.next;if(nextNode.next==null){
                head.next = null;
            }else{
                if(nextNode.next.next==null)
                    head.next = nextNode.next;
                else
                    head.next = nextNode.next.next;
            }
            ListNode temp = head;
            head = nextNode.next;
            nextNode.next = temp;
            if(head==null){
                break; }}returnnewHead; }}Copy the code

package listnode; /** * @author Gavenyeah * @date Start_Time: 2016 apr 1 4:22:55 * @date End_Time: */ public class SwapPairs {public static void main(String[] args) {Node head=ListNode.getSingleList(); ListNode.printList(head); head=new SwapPairs().swapPairs(head); ListNode.printList(head); } public Node swapPairs(Node head) { Node root=head;if(head! =null&&head.next! =null){ root=head.next; Node pre=head; Node p=null; Node q=null;while(head! =null&&head.next! =null){ p=head.next; q=p.next; pre.next=p; p.next=head; head.next=q; pre=head; head=q; }}returnroot; }} (2) Change the value of adjacent node pairs, Public ListNode swapPairs(ListNode head){public ListNode swapPairs(ListNode head){ListNode p=head;while(p! =null){ ListNode q=p.next;if(q! =null){ int temp=p.val; p.val=q.val; q.val=temp; p=p.next; } p=p.next; }returnhead; }} the original link: https://blog.csdn.net/y999666/article/details/51037888Copy the code

String inversion

Asked twice, the first is the company’s technical director, super good, I am the first one solution with the stack, and then ask me what is time complexity and space complexity, patience to give me about these two concepts and how to calculate, then let me think a second method, the second I write is chartAt implementation, The interviewer asked me how much time complexity and space complexity are, and then asked me to think of a better solution. Finally, under the guidance of the interviewer, I wrote the following third implementation, especially thanks to the interviewer.

    public String reverseWithSwaps(String string) {
        final char[] array = string.toCharArray();
        final int length = array.length - 1;
        final int half = (int) Math.floor(array.length / 2);
        char c;
        for (int i = length; i >= half; i--) {
            c = array[length - i];
            array[length - i] = array[i];
            array[i] = c;
        }
        return String.valueOf(array);
    }
Copy the code

Java Fibonacci sequence 1, 1, 2, 3, 5, 8, 13

I wrote it out in general but I got the threshold wrong

    public int fibonacci(int n) {
        int[] res = {0, 1};
        if (n < 2) {
            return res[n];
        }
        int first = 0;
        int second = 1;
        int fibn = 0;
        for (int i = 2; i <= n; i++) {
            fibn = first + second;
            first = second;
            second = fibn;
        }
        return fibn;
    }Copy the code

Handwritten parseInt

It was written at that time, but the method is very stupid, then went to see the source code, worship ah

    public static int parseInt(String s){
        return parseInt(s, 10);
    }

    public static int parseInt(String s , int radix){
        int result = 0;
        int i = 0;
        int digit ;
        boolean nagitive = false;
        int length = s.length();
        if(length > 0){ char firstChar = s.charAt(0); / / +, -,if(firstChar < '0') {if(firstChar == The '-'){
                    nagitive = true;
                }else if(firstChar ! ='+'){ throw new NumberFormatException(); } // There is only one symbolif(length == 1){ throw new NumberFormatException(); } // take the numeric bit backwards i++; }while(I < length){int digit = character. digit(s.char (I ++), radix); // result *= radix; Result -= digit; }}else {
            throw new NumberFormatException();
        }
        returnnagitive ? result : -result; } the original link: https://blog.csdn.net/thqtzq/java/article/details/86442001Copy the code

So I came across these five algorithms, and one of them appeared three times, and one of them appeared twice, and I think I’m pretty lucky. I hope you look at the algorithm before looking for a job, this is the interview will ask, and is handwritten implementation, the last two days are also looking at the algorithm, feel the gods of the idea is really too good, it is difficult to think of these ideas.

That’s all for now. The rest is to ask about the comprehensive quality of the project and the individual. Oh, yes, and the resume is very important.