Question

You are given two 32-bit numbers, N andM, and two bit positions, i and j. Write a method to insert M into Nsuch that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all ofM. That is, ifM= 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j-3 and i=2, because M could not fully fit between bit 3 and bit 2.

EXAMPLE:

Input: N = 16000000000, M = 10011, i = 2, j = 6

Output: N = 10001001100

Solution

This is a basic bit manipulation question. The key is to use binary maks. Two things to note:

1. The ‘~’ means negate. So (~0) is a sequence of 1 (the value equals to -1).

2. When shifting bits, DO NOT USE ‘>>’ because it’s signed shift. Instead, use ‘>>>’ (unsigned right shift operator).

Code

written by me

public static int myAnswer(int n, int m, int i, int j) {
    int rr = (~0 >>> (31 - j));
    int ll = (~0 << i);
    // printBinary(rr);
    // printBinary(ll);

    int middleMask = ll & rr;
    int twoEndMask = ll ^ rr;

    n = n & twoEndMask;
    m = (m << i) & middleMask;

    return n | m;
}

Question

An animal shelter holds only dogs and cats. People must adopt either the “oldest” animals, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like.

Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat. You may use the built-in LinkedList data structure.

Solution

There are 2 solutions.

First one is using a single queue. This makes ‘dequeueAny’ easy, but ‘dequeueCat’ and ‘dequeueDog’ difficult.

Second approach would be using 2 queues for dogs and cats. We need something like timestamp to be stored (more space usage).

When we return, we peek both queues are choose the older one. This is recommended solution in the book.

Code

from the book

Animal.java

public abstract class Animal {
    int order;
    String name;

    public Animal(String n) {
        name = n;
    }

    public abstract String name();

    public boolean isOlderThan(Animal a) {
        return this.order < a.order;
    }
}

class Cat extends Animal {
    public Cat(String n) {
        super(n);
    }

    public String name() {
        return "Cat: " + name;
    }
}

class Dog extends Animal {
    public Dog(String n) {
        super(n);
    }

    public String name() {
        return "Dog: " + name;
    }
}

AnimalQueue.java

public class AnimalQueue {
    LinkedList<Dog> dogs = new LinkedList<Dog>();
    LinkedList<Cat> cats = new LinkedList<Cat>();
    private int order = 0;

    public void enqueue(Animal a) {
        a.order = order;
        order++;
        if (a instanceof Dog) {
            dogs.addLast((Dog) a);
        } else if (a instanceof Cat) {
            cats.addLast((Cat) a);
        }
    }

    public Animal dequeueAny() {
        if (dogs.size() == 0) {
            return dequeueCats();
        } else if (cats.size() == 0) {
            return dequeueDogs();
        }
        Dog dog = dogs.peek();
        Cat cat = cats.peek();
        if (dog.isOlderThan(cat)) {
            return dogs.poll();
        } else {
            return cats.poll();
        }
    }

    public Animal peek() {
        if (dogs.size() == 0) {
            return cats.peek();
        } else if (cats.size() == 0) {
            return dogs.peek();
        }
        Dog dog = dogs.peek();
        Cat cat = cats.peek();
        if (dog.isOlderThan(cat)) {
            return dog;
        } else {
            return cat;
        }
    }

    public int size() {
        return dogs.size() + cats.size();
    }

    public Dog dequeueDogs() {
        return dogs.poll();
    }

    public Dog peekDogs() {
        return dogs.peek();
    }

    public Cat dequeueCats() {
        return cats.poll();
    }

    public Cat peekCats() {
        return cats.peek();
    }
}

Question

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element?

Push, pop and min should all operate in 0(1) time.

Solution

This is a very tricky question.

The key is how to use the minimum space to achieve O(1) query min operation. The trick is to count how many times the same min-value occur. Eg.

input: 5,3,3,1,1,2,2,2,2,2,2,2.

stack: 5,3,3,1,1.

So we can pop ‘1’ twice, pop ‘3’ twice, and pop ‘5’ once. Read the code!

Code

public class StackMyAnswer extends Stack<Integer> {

    Stack<Integer> min = new Stack<Integer>();

    public void push(int value) {
        if (min.isEmpty() || value <= min.peek()) {
            min.push(value);
        }
        super.push(value);
    }

    public Integer pop() {
        int val = super.pop();
        if (!min.isEmpty() && val == min.peek()) {
            min.pop();
        }
        return val;
    }

    public int min() {
        if (min.isEmpty()) {
            return Integer.MAX_VALUE;
        }
        return min.peek();
    }
}

Question

Implement a function to check if a linked list is a palindrome.

Solution

There are multiple solutions for this question.

First, maybe the simplest solution of all, is to compare the list with the reversed list (compare first half would be enough). This is a very nice idea.

Second solution is iterative approach to use a Stack. Alternatively, we can also use fast/slow pointer to find the mid point.

Third solution is recursive. We basically uses a public pointer to:

1. get starting value
2. check middle parts
3. get ending value
4. if starting == ending and middle part is valid, then true.

This code is pretty hard to think. Read it below.

Code

Recursive

private static LinkedListNode p;

public static boolean isPalindromeRecursive(LinkedListNode head) {
    p = head;
    int len = getListLength(head);
    return recursiveHelper(0, len - 1);
}

private static int getListLength(LinkedListNode node) {
    int count = 0;
    while (node != null) {
        count++;
        node = node.next;
    }
    return count;
}

public static boolean recursiveHelper(int from, int to) {
    if (from > to) {
        return true;
    } else if (from == to) {
        p = p.next;
        return true;
    } else {
        // first get fromVal, then check middle part, last, get toVal
        int fromVal = p.data;
        p = p.next;
        if (!recursiveHelper(from + 1, to - 1)) {
            return false;
        }
        int toVal = p.data;
        p = p.next;
        if (fromVal != toVal) {
            return false;
        }
    }
    return true;
}

Question

Implement a stack.

Solution

Stack uses LinkedNode to implement.

Code

public class MyStack {

    Node top;

    public int pop() {
        if (top == null) {
            return -1;
        }
        int returnVal = top.val;
        top = top.next;
        return returnVal;
    }

    public int peek() {
        if (top == null) {
            return -1;
        }
        return top.val;

    }

    public void push(int val) {
        Node newNode = new Node(val);
        newNode.next = top;
        top = newNode;
    }

    class Node {

        int val;
        Node next;

        Node(int value) {
            val = value;
        }
    }
}

Question

Implement an algorithm to find the kth to last element of a singly linked list.

Do it recursively.

Solution

Iterative solution is easy, recursive is not.

Code

public static int nthToLastRecursive(LinkedListNode head, int n) {
    if (n == 0 || head == null) {
        return 0;
    }
    int k = nthToLastRecursive(head.next, n) + 1;
    if (k == n) {
        System.out.println(n + "th to last node is " + head.data);
    }
    return k;
}

Question

What protocol is used for communicating with a DNS?

Answer

Domain Name System (DNS) is a hierarchical distributed naming system for computers, services, or any resource connected to the Internet or a private network. It associates various information with domain names assigned to each of the participating entities. Most prominently, it translates easily memorized domain names to the numerical IP addresses needed for the purpose of locating computer services and devices worldwide. The Domain Name System is an essential component of the functionality of the Internet.

DNS primarily uses User Datagram Protocol (UDP) on port number 53 to serve requests.

DNS queries consist of a single UDP request from the client followed by a single UDP reply from the server.

Question

link

You have a room with n people. A celebrity walks in. Everyone knows the celebrity, the celebrity knows no one.

Non-celebrities may/may not know anyone in the room.

Give an algorithm to find the celebrity. Discuss the complexity.

Solution

Classic brute-force solution would take O(n²) time to build a map. That’s not good, and we have a very simple solution that works in O(n) time:

Make all of them stand in a row. Let’s say the people are a,b,c,d,e,f,g,h,i,j,…….n

Compare a and b. If a knows b, a is not celebrity. If a doesn’t know b, b is not celebrity.

At the end, the probable celebrity who survives is the certain celebrity. (better do a check)

Total number of comparison is 3(N-1) times.

Code

not written

Question

link

2d array ＊代表障碍物 ＃代表货物 空白就是正常的路

问如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍需要绕开，拿到以后要放回出发点，然后再取另一个.

＊＊＊＊＊＊＊＊＊＊
＊  #           ＊
＊  ＊＊＊  ＊   ＊
＊              ＊
＊     ＊＊   ＊ ＊
＊  #    # # ＊＊＊
＊＊＊＊＊＊＊＊＊＊

Solution

This looks like a very difficult question, especially during a phone interview.

The 10th floor gives the best solution:

BFS from every box. in each box, a non-blocking cell (include box position, but exclude hazard position) will have a weight value, stand for the distance to the box.

after bfs from all the boxes, each cell will have k weight, k is the number of boxes. sum all the weight in each cell, and find the cell with smallest sum of weight.

One problem of this solution may lead to a cell of a box. We can then sort the cell by sum of weight and find the first position that is not a box.

complexity O(k*n²)

Suggested at this post, we can also use A* search (with heuristic function) to solve.

Code

not written

Question

link

Given a sorted set, find if there exist three elements in Arithmetic Progression or not.

Solution

This is a rather simple Arithmetic Progression question.

To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater).

O(n²) time.

Code

written by me

public boolean longest(int[] A) {
    int len = A.length;
    for (int i = 1; i < len - 1; i++) {
        int left = i - 1;
        int right = i + 1;
        while (left >= 0 && right < len) {
            int total = A[left] + A[right];
            if (total > 2 * A[i]) {
                left--;
            } else if (total < 2 * A[i]) {
                right++;
            } else {
                return true;
            }
        }
    }
    return false;
}