Leading Tech Donkey: June 2016

Sunday, 26 June 2016

Saturday, 25 June 2016

16. [Technical Interview] [Leetcode] - Minimum Path Sum

This post has been moved to the new and improved blog: http://belugacode.blogspot.ca/2017/02/6-technical-interview-leetcode-minimum.html

Wednesday, 22 June 2016

15. [Technical Interview] [Leetcode] - Counting Bits

You will need to see a table or integers and their binary representation to see a pattern where the formula f[i] = f[i / 2] + i % 2 can solve this question. Help from here: https://leetcode.com/discuss/92609/three-line-java-solution

import java.util.*;

public class HelloWorld{

     public static void main(String []args){
        System.out.println(Arrays.toString(countBits(5)));
     }
     
    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        
        for (int i = 1; i <= num; i++)
        {
            // To understand this logic, you will need to look at
            // a table showing numbers and their binary representation.
            // What you will see if that for a number, if you divide that
            // number by 2, the resulting number and its binary representation
            // will be the same as the current number, and only differentiate
            // by one bit.
            // For example, 10 is 1010 and 11 is 1011. 5 is the resulting number
            // after dividing 10 or 11 by 2. 5 binary representation is
            // 0101. The (i & 1) will determine if you need to add another count
            // for an extra bit or no need to add extra bit. 10 you don't, but 
            // 11 you do.
            result[i] = result[i >> 1] + (i & 1);
        }
        
        return result;
    }
}

14. [Technical Interview] [Leetcode] - Flatten Nested List Iterator

The code won't compile because we don't know the implementation of NestedInteger, but we just need to fill in the NestedInterator constructor, the next() method and the hasNext() method. Will use a stack and will need to traverse backwards because we want to put the end elements in the stack first and the beginning elements in the stack last. This will result in the beginning elements showing up at the top of the stack (LIFO).

import java.util.*;

public class HelloWorld{

     public static void main(String []args){
        System.out.println("Hello World");
     }
     
     /**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack = new Stack<NestedInteger>();
    
    public NestedIterator(List<NestedInteger> nestedList) {
        
        // need to do traversal in reverse because we want the
        // last nested integer elements at the bottom of the stack
        // and the first nested integers at the top of the stack
        for (int i = nestedList.size() - 1; i >= 0; i--)
        {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty())
        {
            NestedInteger current = stack.peek();
            
            // if current is an integer and not a list of integer
            // return true and let next() take care of the popping
            if (current.isInteger())
            {
                return true;
            }
            
            // else current is not an integer, so pop the list of integer off
            // then proceed to pushing each int in the current list of integer
            // to the stack, and let next() pop them later
            stack.pop();
            
            // need to traverse in reverse because we want the last ints in the
            // nested integer to be at the bottom of the stack and the first ints
            // in the nested integer to be at the top of the stack
            for (int i = current.getList().size() - 1; i >= 0; i--)
            {
                stack.push(current.getList().get(i));
            }
        }
        
        return false;
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
}

13. [Technical Interview] Integer Break

You will need to spot the repeating 3 pattern. Followed this link to understand the problem: https://github.com/haoel/leetcode/blob/master/algorithms/cpp/integerBreak/IntegerBreak.cpp

public class HelloWorld{

     public static void main(String []args){
        System.out.println(integerBreak(11));
     }
     
    // For any n greater than 4, so 5 or up, will always see a
    // repeating 3 as the pattern. With each 3, we subtract 3
    // from the original n and eventually we will get a number
    // that is <= 4 and that will be the last number in the multiplication.
    public static int integerBreak(int n) {
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;
        
        int result = 1;
        
        while (n > 4)
        {
            result = result * 3;
            n = n - 3;
        }
        
        result = result * n;
        return result;
    }
}

12. [Technical Interview] Top K Frequent Elements

You will use a max heap to place the most occurrences of a number at the top of the queue and going down in count.

import java.util.*;

public class HelloWorld{
     public static void main(String []args){
        
        int[] testIntArray = {1, 1, 1, 2, 2, 3};
        List<Integer> result = topKFrequent(testIntArray, 3);
        
        Iterator it = result.iterator();
        while (it.hasNext())
        {
            System.out.println(it.next());
        }
     }
     
    public static List<Integer> topKFrequent(int[] nums, int k) {
        // count the frequency of each number in nums and add
        // them to the map
        Map<Integer, Integer> counterMap = new HashMap<Integer, Integer>();
        for (int num : nums)
        {
            int countValue = counterMap.getOrDefault(num, 0);
            counterMap.put(num, countValue + 1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> b.getValue()-a.getValue());
        for (Map.Entry<Integer, Integer> entry : counterMap.entrySet())
        {
            pq.offer(entry);
        }
        
        Iterator it = pq.iterator();
       while (it.hasNext())
       {
        System.out.println ( "Value: "+ it.next()); 
       }
        
        List<Integer> result = new LinkedList<Integer>();
        int counter = 0;
        while (counter < k)
        {
            if (result == null)
                System.out.println ("bad result"); 
            if (pq == null)
                System.out.println ("bad pq"); 
            result.add(pq.poll().getKey());
            counter++;
        }
        
        return result;
    }
}

11. [Technical Interview] Given a list of non negative integers, arrange them such that they form the largest number.

Given a list of non negative integers, arrange them such that they form the largest number.

import java.util.*;

public class HelloWorld{
     public static void main(String []args){
        
        int[] testIntArray = {3, 30};
        System.out.println(largestNumber(testIntArray));
     }
     
     public static String largestNumber(int[] nums)
     {
         String result = "";
         String[] numAsStringsArray = new String[nums.length];
         
         for (int i = 0; i < nums.length; i++)
         {
             numAsStringsArray[i] = Integer.toString(nums[i]);
         }
         
         // The lambda expression must be (str1, str2) -> (str2 + str1).compareTo(str1 + str2)
         // because you are comparing str2 to str1. For example, str1 is 3 and str2 is 30.
         // so we must do (str2 + str1).compareTo(str1 + str2) and not (str1 + str2).compareTo(str2 + str1)
         // because we are comparing str2 to str1, so str2 must come before str1 so it will look like
         // 303 compare to 330, compareTo does natural order in ascending order so we want this way

         Arrays.sort(numAsStringsArray, (str1, str2) -> (str2 + str1).compareTo(str1 + str2));
         
         if (numAsStringsArray[0].equals("0"))
         {
             return "0";
         }
         
         StringBuilder sb = new StringBuilder();
         for (String str : numAsStringsArray)
         {
             sb.append(str);
         }
         
        return sb.toString();   
     }
}

Leading Tech Donkey

Sunday, 26 June 2016

19. [Technical Interview] [Leetcode] - Maximal Square

18. [Technical Interview] [Leetcode] - Kth Smallest Element in a BST

17. [Technical Interview] [Leetcode] - Missing Number