20. [Moving] We've moved to the new and improved blog Beluga Code!

We've moved to a new and improved blog Beluga Code, come check us out!

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

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

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

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

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

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

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(); */ }