Saturday, November 1, 2014

Facebook: High-Frequency II

19. Given a set of n jobs with[start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum?
A wrong solution:
The idea is first simply sort the array according to the start time. 


public class Solution {
    public List<Interval> findInterval(List<Interval> intervals) {
        List<Interval> result = new ArrayList<Interval>();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        
        if (intervals.size() == 1) {
            result.addAll(intervals);
            return result;
        }
        
        Collections.sort(intervals, new IntervalComparator());
        
        List<Interval> curList = new ArrayList<Interval>();
        int maxCost = 0;
        int curCost = 0;
        
        curList.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start <= intervals.get(i - 1).end) {
                if (curCost > maxCost) {
                    maxCost = curCost;
                    result.clear();
                    result.addAll(new ArrayList<Interval>(curList));
                }
                curList.clear();
                curList.add(intervals.get(i));
                curCost = intervals.get(i).cost;
            } else {
                curList.add(intervals.get(i));
                curCost += intervals.get(i).cost;
            }
        }
        
        return result;
    }
}


20. Write a function that calculates input strings with opeartors +, -, *, / eg. "5 + 5 * 6" should output 35







21. Print the nodes of a linked list in reverse order
Method 1: Recursive Solution:
Traverse the linked list until the end, then print the nodes in reverse order. 

Code (Java):
public class Solution {
    public void printListReverse(ListNode head) {
        if (head == null) {
            return;
        }
        
        printListReverse(head.next);
        System.out.print(head.val + " ");
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        ListNode head = new ListNode(0);
        ListNode p = head;
        for (int i = 1; i < 10; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
        p.next = null;
        
        sol.printListReverse(head);
    }
}

Method 2: Iterative using a stack
Traverse the nodes of the list and add them into a stack. Then pop the stack and print out the values.

Code (Java):
import java.util.*;

public class Solution {
    public void printListReverse(ListNode head) {
        if (head == null) {
            return;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        
        System.out.println(" ");
    }
}

Method 3: Reverse the linked list, then print the nodes in order. 
Time: O(n) + O(n) = O(n)
Space: O(1)
Disadvantage: Modify the linked list. 

Code (Java):
public class Solution {
    public void printListReverse(ListNode head) {
        if (head == null) {
            return;
        }
        
        ListNode newHead = reverseList(head);
        
        while (newHead != null) {
            System.out.print(newHead.val + " ");
            newHead = newHead.next;
        }
        
        System.out.println(" ");
    
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        
        return prev;
    }
}


22. Finding maximum subarray sum (similar to Kadane's Algorithm) with the constraint that two numbers in the array that form the max sum cannot be next to each other. 

http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/
A wrong solution:
public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length < 3) {
            return 0;
        }
        
        int maxSum = 0;
        int start = 0;
        int sum = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (sum < 0) {
                sum = A[i];
                start = i;
            } else {
                sum += A[i];
            }
            
            if (i - start > 1) {
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      int[] A = new int[] {-4, -1, 3, 4, -8, 1};

      int result = sol.maxSubArray(A);

      System.out.println("Result is " + result);
    }
}


23. Write all solutions for a^3 + b^3 = c^3 + d^3, where a, b, c, and d lie between [0, 10^5]
Wrong Method:
Try every possible combinations of a,b,c and d, so the time complexity is O(n^4).

Code (Java):
public class Solution {
    public List<List<Integer>> sum(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if (n < 0) {
            return result;
        }
        
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                for (int c = 0; c < n; c++) {
                    for (int d = 0; d < n; d++) {
                        if ((int) pow(a, 3) + (int) pow(b, 3) == (int) pow(c, 3) + (int) pow(d, 3)) {
                            List<Integer> temp = new ArrayList<Integer>();
                            temp.add(a);
                            temp.add(b);
                            temp.add(c);
                            temp.add(d);
                            result.add(temp);
                        }
                    }
                }
            }
        }
        
        return result;
    }
}

Ramanujan's taxi. S. Ramanujan was an Indian mathematician who became famous for his intuition for numbers. When the English mathematician G. H. Hardy came to visit him in the hospital one day, Hardy remarked that the number of his taxi was 1729, a rather dull number. To which Ramanujan replied, "No, Hardy! No, Hardy! It is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways." Verify this claim by writing a program Ramanujan.java that takes a command line argument N and prints out all integers less than or equal to N that can be expressed as the sum of two cubes in two different ways - find distinct positive integers abc, and d such that a3 + b3 = c3 + d3. Use four nested for loops.





24: Write a function to check that if two trees are Isomorphic.
http://www.geeksforgeeks.org/tree-isomorphism-problem/









No comments:

Post a Comment