CareerCup

private static String getPeriod(String string) { // O(n * n)
        //for every possible period size i, check if it's valid
        for (int i = 1; i <= string.length() / 2; i++) {
            if (string.length() % i == 0) {
                String period = string.substring(0, i);
                int j = i;
                while(j + i <= string.length()) {
                    if (period.equals(string.substring(j, j + i))) {
                        j = j + i;
                        if(j == string.length()) { //period valid through entire string
                            return period;
                        }
                    } else {
                        break;
                    }
                }
            }

        }
        return null; //string is not periodic
    }

public static List<Integer> getAnagrams(String s, String word) {
        Map<Character, Integer> letters = new HashMap<>();
        int distinct_letters = 0;
        for(char c: word.toCharArray()) {
            if(!letters.containsKey(c)) distinct_letters++;
            letters.put(c, letters.getOrDefault(c, 0) + 1);
        }

        //search for anagrams with two pointers
        List<Integer> res = new ArrayList<>();
        int lo = 0, hi = 0;
        while(hi < s.length()) {
            if(!letters.containsKey(s.charAt(hi))) {
                while(lo < hi) {
                    char c = s.charAt(lo);
                    if(letters.get(c) == 0) distinct_letters++;
                    letters.put(c, letters.get(c) + 1);
                    lo++;
                }
                hi++;
                lo = hi;
            } else if(letters.get(s.charAt(hi)) == 0){
                char c = s.charAt(lo);
                if(letters.get(c) == 0) distinct_letters++;
                letters.put(c, letters.get(c) + 1);
                lo++;
            } else {
                char c = s.charAt(hi);
                letters.put(c, letters.get(c) - 1);
                if(letters.get(c) == 0) distinct_letters--;
                if(distinct_letters == 0) {
                    res.add(lo);
                }
                hi++;
            }
        }
        return res;
    }

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    long factorial(long n){
        long fact = 1;
        for (long i = 1; i<= n; ++i)
            fact *= i;
        return fact;
    }

    void DFS(const string &s1, int m, int i,
    const string&s2, int n, int j,
    string path,vector<string> &ret){
        if(i==m &&j==n)  {
            ret.push_back(path);
            return;
        }
        if(i < m)  DFS(s1, m, i+1, s2, n, j, path+s1, ret);
        if(j < n)  DFS(s1, m, i, s2, n, j+1, path+s2[j], ret);
    }

    vector<string> combineTowStrings(const string &s1,const string &s2) {
        int m =s1.length(), n = s2.length();
        long count =factorial(m+n)/factorial(n)/factorial(m);
        cout <<"count:" << count << endl;
        vector<string> ret;
        DFS(s1, m, 0, s2,n, 0, "", ret);
        return ret;
    }

    int main() {
        vector<string> ret = combineTowStrings("AB","CDF");
        cout <<ret.size() << endl;
        for(string &s: ret)  cout << s << endl;
        return 0;

}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

We provide ONE TO ONE courses that cover everything in an interview including
the latest interview questions categorized by companies,
algorithms,
SYSTEM DESIGN Courses(highly recommended for people interviewing with FLAG)
and mock interviews.

All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work.

Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Welcome to email us with any questions. Thanks for reading.

public static int mergeSegments(int[][] segments) {
        Arrays.sort(segments, (x, y) -> x[0] - y[0]);

        int result = 0;
        int last = 0;
        for(int[] seg : segments) {
            result += Math.max(seg[1] - Math.max(last, seg[0]), 0);
            last = Math.max(last, seg[1]);
        }
        return result;
    }

Looking for interview questions sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber.
Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Here has a google online assessment question list: aonecode.com/google-online-assessment

I. At first find found all primes <= N (sieve of Eratosthenes). Getting the sum will be easy then.
Follow-up:
Cache the sums for any given N to save time. {N:SUM}
Optimization: Don't have to store sums for every N.
When N = 7, N = 8, N = 9, N = 10, the prime sum remains 17.
For N between 11 to 12, the prime sum is 28.
For N between 13 to 16, the sum is 41.
Use a BST structure as the cache. For N = 16, cache:
{2:3, 4:6, 6:11, 10:17, 12:28, 16:41}

For a given N, call cache.ceilingKey(N) to find the bucket for N.

N/log(n) * log(N)


Complexity
Time:
sieve of Eratosthenes takes O(NloglogN) time.
Insert an element into BST takes O(logN), there are N/logN primes in total to be added.
So building the cache takes logN * N / LogN = O(N) time
requesting primeSum(N) takes O(logN)

Space:
sieve of Eratosthenes takes O(N) extra space which will later be release after the cache is created.
Cache: O(N/logN)

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.

import java.util.TreeMap;
public class PrimeSum {

    TreeMap<Integer, Integer> sums;

    public PrimeSum(int n) { //input the upper limit for all Ns
        sums = new TreeMap<>();
        // init an array to track prime numbers
        boolean[] primes = new boolean[n + 1];
        for (int i = 2; i < n; i++)
            primes[i] = true;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (primes[i]) {
                for (int j = i + i; j < n; j += i)
                    primes[j] = false;
            }
        }
        // insert sums into cache
        int sum = 0;
        for(int i = 2; i <= n; i++) {
            if(primes[i]) {
                sums.put(i - 1, sum);
                sum += i;
            }
        }
        if(primes[n]) {
            sums.put(n, sum);
        }
    }

    public int primeSum(int N) {
        Integer ceiling = sums.ceilingKey(N);
        //if(ceiling == null) {
            //Exception("input value overflows");
        //}
        return sums.get(ceiling);
    }

}

This is a 'merge set' question. Given a graph, figure out which nodes belong to the same connected component and put them into a set.
Since the input comes in as an edge set, UNION FIND will be a good way to solve this.

Initially every node sources to itself. As we read the statement X = Y, we point the source of Y to the source of X so that they join the same set. After all connected components are sorted out. We check the unequal statements X != Y. If any of the X, Y pairs do share the same source, then X != Y contradicts with the equal statements.

public class CheckStatements {
    public boolean validStatements(char[][] equal, char[][] unequal) {
        int[] sets = new int[26];
        for(int i = 0; i < 26; i++) {
            sets[i] = i;
        }

        for(char[] pair: equal) {
            mergeSets(sets, pair[0] - 'A', pair[1] - 'A');
        }
        for(int i = 0; i < 26; i++) {
            findSrc(sets, i);
        }

        for(char[] pair: unequal) {
            if(sets[pair[0] - 'A'] == sets[pair[1] - 'A']) return false;
        }
        return true;
    }

    private int findSrc(int[] sets, int i) {
        int src = i;
        while(src != sets[src]) {
            src = sets[src];
        }
        int tmp;
        while (i != sets[i]) {
            tmp = sets[i];
            sets[i] = src;
            i = tmp;
        }
        return src;
    }

    private void mergeSets(int[] sets, int a, int b) {
        int srcA = findSrc(sets, a);
        int srcB = findSrc(sets, b);
        sets[srcB] = srcA;
    }
}

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

Typical Dynamic Programming

public void printSums(int c1, int c2, int c3) {

        Set<Integer> sums = new HashSet<>();
        sums.add(0);

        for(int sum = 1; sum <= 1000; sum++) {

            if(sums.contains(sum - c1) || sums.contains(sum - c2) || sums.contains(sum - c3)) {
                System.out.println(sum);
                sums.add(sum);
            }
        }
    }

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.

Our students got offers from G, U, FB, Amzn, Yahoo and other top companies after a few weeks of training.

Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

import java.util.Stack;
class CharNode {
    char ch;
    CharNode prev;
    CharNode next;

    public CharNode(char ch) { this.ch = ch; }
}

class Edit {
    String edition; //"DEL", "INS", "LEFT", "RIGHT"
    CharNode data;
    public Edit(String edition, CharNode cur) {
        data = cur;
        this.edition = edition;
    }
}

public class TextEditor {
    private Stack<Edit> undo_stack;
    private CharNode cursor;
    private CharNode end;

    public TextEditor() {
        undo_stack = new Stack();
        end = new CharNode('\0');
        cursor = end;
    }

    public void moveCursorLeft() {
        if(cursor.prev == null) return;
        cursor = cursor.prev;
        undo_stack.push(new Edit("RIGHT", null));
    }

    public void moveCursorRight() {
        if(cursor == end) return;
        cursor = cursor.next;
        undo_stack.push(new Edit("LEFT", null));
    }

    public void insertCharacter(char ch) {
        CharNode n = new CharNode(ch);
        insert(n);
        undo_stack.push(new Edit("DEL", null));
    }

    public void backspace() {
        if(cursor.prev == null) return;
        undo_stack.push(new Edit("INS", delete(cursor.prev)));
    }

    public void undo() {
        if(undo_stack.isEmpty()) return;
        Edit edit = undo_stack.pop();
        switch(edit.edition) {
            case "LEFT":
                cursor = cursor.prev; break;
            case "RIGHT":
                cursor = cursor.next; break;
            case "DEL":
                delete(cursor.prev); break;
            case "INS":
                insert(edit.data); break;
            default:
                return;
        }
    }

    public String toString() {
        StringBuilder text = new StringBuilder();
        CharNode n = end.prev;
        if(cursor == end) text.append('|');
        while(n != null) {
            text.insert(0, n.ch);
            if(cursor == n) text.insert(0, '|');
            n = n.prev;
        }
        return text.toString();
    }

    private void insert(CharNode node) {
        CharNode prev = cursor.prev;
        node.next = cursor;
        cursor.prev = node;
        if(prev != null) {
            prev.next = node;
            node.prev = prev;
        }
    }

    private CharNode delete(CharNode del) {
        if(del.prev != null) {
            del.prev.next = cursor;
        }
        cursor.prev = del.prev;
        return del;
    }
}

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

def solve(board):
    m, n = len(board), len(board[0])
    '''create adjacency list
    rows[0] has all the nodes in 1st row
    rows[1] has all the nodes in 2nd row
    etc.
    cols[0] has all the nodes in 1st column
    cols[1] has all the nodes in 2nd column
    etc.'''
    rows, cols = [set() for i in range(m)], [set() for j in range(n)]
    for i in range(m):
        for j in range(n):
            if board[i][j] is 'O':
                rows[i].add(j)
                cols[j].add(i)

    #count the degree (number of neighbors) of every orb
    degrees = dict()
    for i in range(m):
        for j in rows[i]:
            degree = len(rows[i]) + len(cols[j]) - 2
            if degree > 0:
                degrees[(i, j)] = degrees

    #erase the node with minimum positive degree until all nodes have 0 degree
    while degrees:
        erase_orb(degrees, board, rows, cols)

    #output
    for row in board:
        print row


#erase the orb with the minimum degree
def erase_orb(degrees, board, rows, cols):
    #find the node with minimum positive degree
    i, j = min(degrees.items(), key=lambda x: x[1])[0]
    #erase this node
    rows[i].remove(j)
    cols[j].remove(i)
    degrees.pop((i, j))
    board[i][j] = 'X'
    print 'erase ', (i, j)

    #remove one degree from every neighbor of the node erased
    for y in rows[i]:
        degrees[(i, y)] -= 1
        if degrees[(i, y)] is 0:
            degrees.pop((i, y))

    for x in cols[j]:
        degrees[(x, j)] -= 1
        if degrees[(x, j)] is 0:
            degrees.pop((x, j))


solve([
    ['X', 'X', 'X', 'X', 'X', 'O'],
    ['O', 'X', 'X', 'X', 'X', 'X'],
    ['O', 'X', 'X', 'X', 'X', 'O'],
    ['X', 'X', 'O', 'X', 'O', 'X'],
    ['X', 'O', 'X', 'X', 'X', 'O']
    ])

Solution:

int moveCoins(TreeNode root) {
        return dfs(root, new HashMap<>());
    }

    int dfs(TreeNode n, Map count) {
        if(!count.containsKey(n)) {
            count.put(n, n.val);
        }
        int coinsNum = count.get(n);
        int res = 0;
        for(TreeNode kid : n.children) {
            res += dfs(kid, count);
            coinsNum += count.get(kid);
            res += Math.abs(count.get(kid));
        }
        count.put(n, coinsNum - 1);
        return res;
    }

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!