Mathematical Method

Algorithm

---

This is the conclusion for those interview questions which contain mathematical method.

Part One: Geometry

1. CC 10.3: Determine whter the two lines would intersect on Cartesian plane.

            design a Line class:
                    double epsilon = 0.0000001;
                    double slope;
                    double yIntercept;
            Line(double slope, double yIntercept):
                    this.slope = slope;
                    this.yIntercept = yIntercept;
            boolean intersect(Line line2):
                    return Math.abs(this.slope-line2.slope) > epsilon
                    ||Math.abs(this.yIntercept - line2.yIntercept) < epsilon;

2. CC 10.5: find a line that would cut these two squares in half

            class Point:
                double x;
                double y;
                public Point(double x, double y){
                    this.x = x;
                    this.y = y;
                }
            class Line:
                Point p1;
                Point p2;
                public Line(Point p1, Point p2){
                    this.p1 = p1;
                    this.p2 = p2;
                }
            class Square:
                double left;
                double right;
                double top;
                double bottom;
                public Square(double left, double top, double size){
                    this.left = left;
                    this.top = top;
                    this.right = left+size;
                    this.bottom = top - size;
                }
                public Point middle(){
                    return new Point((this.left+this.right)
                         >>1,(this.top+this.bottom)>>1);
                }
                public Line cut(Square other){
                    Point middle_s = this.middle();
                    Point middle_t = other.middle();
                    if(middle_s == middle_t)
                        return new Line(new Point(left,top),
                            new Point(right,bottom));
                    else
                        return new Line(middle_s,middle_t);
                    }
                }

3. CC 10.6, LEETCODE: Max Points on a Line

a line can be represented by two ways a). a pairing of points; b) a slope and a y-intersect
b): every line segment on the sam greater line will have identical slopes and y-intercept
O(n^2) Time complexity, O(n) Space Complexity

            class Line{
                double epsilon = 0.00000001;
                double slope;
                double intercept;
                private boolean INFINITE_SLOPE = false;
                public Line(Point p, Point q){
                    if(Math.abs(p.x - q.x) > epsilon){
                        slope = (p.y - q.y) / (p.x - q.x);
                        intercept = p.y - slope*p.x;
                    }else{
                        INFINITE_SLOPE = true;
                        intercept = p.x;
                    }
                }
                public boolean isEqual(double a, double b){
                    return (Math.abs(a-b)<epsilon)
                }
                @Override
                public int hashCode(){
                    int sl = (int) slope*1000;
                    int in = (int) intercept*1000;
                            return sl|in;
                }
                @Override
                public boolean equals(Object o){
                    Line l = (Line)o;
                    if(isEqual(l.slope,this.slope)&&
                        isEqual(l.intercept,this.intercept)&&
                        (this.INFINITE_SLOPE == l.INFINITE_SLOPE))
                            return true;
                    return false;
                    }
            }
            int findMaxPoint(Point[] points){
                int max = Integer.MIN_VALUE;
                for(int i = 0;i<points.length;i++){
                    int localMax = Integer.MIN_VALUE;
                    HashMap<Line,Integer> map = new HashMap<Line,Integer>();
                    for(int j=i+1;j<points.length;j++){
                            Line line = new Line(points[i],points[j]);
                                if(!map.containsKey(line)){
                                    map.put(line,1);
                                }else{
                                    map.put(line,map.get(line)+1);
                                }
                                for(int x:map.values())
                                    localMax = Math.max(localMax,x);                                            max = Math.max(localMax,max);
                        }
                    }
                    return max;
                }

Part Two: Algebra

4. CC 10.4: USE "+" to implement *,/,- operation

subtraction:a+ (-1)*b but whether it is negative? and how to avoid *(-1)?

            int minus(int a, int b):
                    int newb = 0;
                    int neg = 0;
                    neg = b<0? 1:-1;
                    while(b!=0):
                        b+=neg; // b -> 0
                        newb+=neg; // newb = b‘s opposite number
                    return a+newb;

multiplication: a*b = a+...+a with b times

                int getOppo(int i)
                    int newi = 0;
                    int neg = 0;
                    neg = i<0? 1:-1;
                    while(i!=0):
                        i+=neg; // i -> 0
                        newi+=neg; // newi = i‘s opposite number
                    return newi;
                int multiple(int a, int b):
                    // whether a,b is negtive 
                    int neg = 1;
                    neg = a>=0?1:-1;
                    neg += b>=0?1:-1;
                    if(a<0)
                        a = getOppo(a); // keep a positive
                    if(b>0)
                        b = getOppo(b); // keep b negtive
                    int sum = 0;
                    while(b!=0):
                        sum+=a;
                        b+=1;
                    if(neg==0)
                        sum = getOppo(sum);
                    return sum;
    division: a/b = a-b-...-b=0 with ? times 
                int division(int a, int b)
                    if(b==0)
                        throw new Exception;
                    int neg = 1;
                    neg = a>=0?1:-1;
                    neg += b>=0?1:-1;
                    if(a<0)
                        a = getOppo(a); // keep a positive
                    if(b>0)
                        b = getOppo(b); // keep b negtive
                    int quotient = 0;
                    while(a>1):
                        a += b;
                        quotient++;
                    if(neg==0)
                        quotient = getOppo(quotient);
                    return quotient;                                    

5. ** CC 10.7: find the kth number such that the only prime factors are 3, 5 and 7.

找到质因数为3、5、7的第k个数
    1. 初始化结果res=1和队列q3,q5,q7
    2. 分别往q3,q5,q7插入1*3,1*5,1*7
    3. 求出三个队列的队头元素中最小的那个x，更新结果res=x
    4. 如果x在：
        q3中，那么从q3中移除x，并向q3，q5，q7插入3*x,5*x,7*x
        q5中，那么从q5中移除x，并向q5，q7插入5*x,7*x
        q7中，那么从q7中移除x，并向q7插入7*x
    5. 重复步骤3－5，直到找到第k个满足条件的数

        int getKthMagicNumber(int k){
            if(k<=0)
                return 0;
            int val = 1;
            Queue<Integer> q3 = new LinkedList<Integer>();
            Queue<Integer> q5 = new LinkedList<Integer>();
            Queue<Integer> q7 = new LinkedList<Integer>();  
            q3.add(3);
            q5.add(5);
            q7.add(7);
            k--;
            while(k>0){
                val = Math.min(q3.peek(),Math.min(q5.peek(),q7.peek()));
                if(val = q7.peek()){
                        q7.remove();
                }else{
                    if(val = q5.peek()){
                            q5.remove();
                    }else{
                            q3.remove();
                            q3.add(val*3);
                    }
                    q5.add(val*7);
                }
                q7.add(val*7);
                k--;
            }   
            return val;
        }

6. GCD - Great Common Divisor

            Euclidean ALgorithm: - Recursion 
                int gcd(int a, int b):
                    if(b==0)
                        return a;
                    return (b, a%b);
                                 - Iteration
                int gcd(int a, int b):
                    while(b>0):
                        int tmp = a%b;
                        a = b;
                        b = tmp;
                    return a;
                    // based on subtraction:
                    while(a!=b):
                        if(a>b):
                            a -= b;
                        else
                            b -= a;
                    return a;
            LCM(Least Common Multiple) = a*b/gcd(a,b);

7. Extended Euclidean:

        ax + by = gcd(a, b) 
        因为 gcd(a,b)=gcd(b,a mod b)
        所以有 => ax1 + by1 = bx2 + (a-(a/b)*b)y2 = ay2 + bx2 - (a/b)*by2 
                = ay2 + bx2 - (a/b)*by2 
                = ay2 + b(x2 - (a/b)*y2)

        所以有 x1 = y2;        
                y1 = x2 - (a/b)*y2;

             int extend_Eulid(int a,int b){
                if (b==0){
                    x=1; y=0; return a;
                }else{
                    int r = extend_Eulid(b,a%b);
                    int temp=x;
                    x=y;
                    y=temp-a/b*y;
                    return r;
                    }
                } 

8. isPrime:

            n cannot be divided by any number in 1~n or 1~sqrt(n)

Notice:

1. **两个浮点数不能直接用=来进行比较，而应该用差值是否小于一个特定的小数来确定是否相等！epsilon < a certain value **