Implementation of pdist in Theano

There days I come cross a problem that need me to compute pairwise distance for two given matrix in theano. Such functionality is built as pdist() function in scipy. As far as I know there is no such equivalent function in theano for all of them at once. However, each specific distance, being a closed form mathematical expression, can be written down in Theano as such and then compiled.

Take as an example the minkowski p norm distance (wiki)

Note that abs calls the built-in __abs__, so abs is also a theano function. We can now compare this to pdist:

LeetCode Q200: Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Round 2 solution:
DFS

Rnd3 sol:

LeetCode Q199: Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <--- 2="" 3="" 4="" 5="" pre="">



You should return [1, 3, 4].



Solution:

Rnd3

LeetCode Q198: House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution:

DP, if to decide whether to robber nums[i], we need to decide the maximum profit between following two options:

max ( profit( nums[0:i-1] ), profit( nums[0:i-2 ]+profit(nums[i]) )

LooetCode Q191: Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

My solution: Time complexity O(1) it counts entire 32 bits.
Optimal solution: Although the time complexity is also O(1), it takes k steps to finish, where k is the number of 1s in int. The idea is to remove an 1 at a time. The trick is: An elegant way to check is an integer has exactly one bit set to 1. Given integer say int i=k, we could check if (i & (i-1))==0, if true then only one bit is 1 in i. In the same time (i & (i-1))==0 actually check if number i is a power of 2.

LeetCode Q190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

My solution:

A cool solution using divide and conquer you should not miss!
Another solution you have to know !

Round 2 solution:

LeetCode Q189: Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

More solutions are shown in https://leetcode.com/discuss/27387/summary-of-c-solutions

My Solution:

LeetCode Q188: Best Time to Buy and Sell Stock IV (hard)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Using DP. Iinspired buy solution of Sell Stock III, we keep track the price and profit at current transaction.

LeetCode Q187: Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution 1:
Using unordered_map to save substring.


Solution 2:
Converting substring to integer and hash integer instead of substring. Need to use different code for 'A', 'C', 'G', 'T'.

A blog for reviewing system design in about 1 month, highly recommended.

System Design Study Group

LeetCode Q186: Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

LeetCode Q179: Largest Number

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

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution:

Since we need to decide which number is in front of another for each pair of numbers, we could come up a new rule for comparison in sort function.

LeetCode Q174: Dungeon Game (hard)

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Solution:

Use hp[i][j] to store the min hp needed at position (i, j), then do the calculation from right-bottom to left-up.

Note: adding dummy row and column would make the code cleaner.

Q: Why do we start from the bottom right corner?

A: Because it is known that the knight has to reach the end with at least one health point and the health point with which the knight should start with is not known.

LeetCode Q173: Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Round 2 solution:

LeetCode Q172: Factorial Trailing Zeros

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution:

Zeros is produced by "5 x even number", so count how many 5s in each number.

LeetCode Q171: Excel Sheet Coumn Numer

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

LeetCode Q170: Two Sum III - Data structure desing

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Solution:
O(1) add
O(n) find: using hash table.

Need to care about when two numbers are equal. In this case, this number has to be added at least twice.

By using unordered_map::count() is much faster than unordered_map::find().

LeetCode Q169: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Solution 1:
Using hash table:

Solution 2:
Actually there are many other solutoins, please see: Here

Round 2 solution:

LeetCode Q168: Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Solution:
At the first glimpse, one may think this question as an one that convert decimal number to number with base 26. Unfortunately, it is not. the difference here is, there is no number represent 0 !!! The range here for each character is from [1, 26], not [0, 25].




Round 2 solution:

LeetCode Q167: Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

LeetCode Q166: Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

Solution:

Consider how the long division is done. Compute residual and result of division in each iteration. In the meantime keep track the residual using hash map in order to detect repeating pattern. Basically, the repetition happens when the same residual value appears again. Need to consider some boundary case such as "-2147483648", "-1"

 

Round 2 solution:

LeetCode Q165: Compare Version Number

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Round 2 solution:

LeetCode Q164: Maximum Gap (hard)

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Solution:
Radix sort!!!

Round 2 solution:

Rnd3 sol:

LeetCode Q163: Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].







Round 2 solution:

LeetCode Q162: Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Soluton:

Binary search

Round 2 Solution:

LeetCode Q161: One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

Round 2 solution:

LeetCode Q160: Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Solution;

A hard question at the first glance, however, it is easy if you can figure out how many node each linkedlist has.

LeetCode Q159: Longest Substring with At Most Two Distinct Characters (hard)

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

Solution:

To solve substring problem, could use following template:

My solution is:

A better solution is:

Round 2 solution:
Rnd3 sol:

LeetCode Q157: Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

Round 2 solution:

LeetCode Q156: Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1  

Solution:
The most bottom left node will serve as a root in new tree. Using post-traversal. Remember that the right not will not have any children, so the recursion only apply to left node.



Round 2 solution:

LeetCode Q155: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution:

The essence of this question is to solve the problem of getting minimum element in remaining stack. To solve it we need to keep track the min in current stack. So, each entry in the stack have to domains, first one is used to save value of current element. the second domain contains the min value under the current element in the stack.

Round 2 solution: Anther way to track minimum element in current array is to use another stack. Similar to sliding window problem, the element inserted to the stack has to be strictly smaller or equal to current top element of the stack.

LeetCode Q154: Find Minimum in Rotated Sorted Array II (hard)

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution:

The solution is basically the same to the question in which there is no duplicate element. Basically, for questions like this one which allows duplicate elements when doing binary search, we need to shrink the range by moving either left or right pointer when meeting duplicate element.

Round 2 solution: For all rotated array questions with duplicates, we can compare middle elements with left/right boundary, if identical, we can shrink the boundary.

LeetCode Q153: Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution:

Binary search, each step move to branch where numbers are not in order. Need to consider the case where the given array is already sorted.

Round 2 solution: Questions like this, remember to illustrate all possible cases on paper first. It is easier to separate all cases from those examples.
For this question, find the middle element, and drop half of elements every iteration.

Round 2 solution: For questions like this one, first list all examples on paper. It is easier to separate all cases from those examples.
For this question, we find middle element every time and we decide which type of order the current array is. Then we can drop half of elements depends on the pattern we get from examples we listed on the paper.

LeetCode Q152: Maximum Product Subarray (hard)

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:

Use DP. Given an array with N integers, we can create a Nx2 table. For each 1x2 entry in the table, we keep track the largest product (most of time for positive product) and smallest product (most of time for negative product so far) met so far. So, the idea is to save all valid product met so far including the negative ones, because we don't know whether there will be more negative integer in the remaining part of the array. 

At the end of this design, we notice that, actually, there is no need to create a Nx2 table, all we need basically just two variables storing largest and smallest product obtained so far.

Round 2 solution:

LeetCode Q151: Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

Round 2 solution:

LeetCode Q150: Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:
Not hard, but need to careful about some corner cases, such as when token has only 1 elements and the order of operators when popped from stack.

LeetCode Q149: Max Points on a Line (hard)

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

Using hash, for each point, check the number of all other points that are co-linear with current point. The problem will encounter is how to represent a line in hash map. Directly using float/double as slope will have precision problem. So, here I represent a slope using x and y, where x=p1.x-p0.x, y=p1.y-p0.y. Then to ensure uniqueness of each slope, x and y are divided by their GCD.

LeetCode Q148: Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Solution:
Using merge sort.



Round 2 solution:

For God's sake, don't try sorting a linked list during the interview

Somebody gots some comments about his experience of interviewingin Google.

http://steve-yegge.blogspot.nl/2008/03/get-that-job-at-google.html
Might be helpful

LeetCode Q147: Insertioin Sort List

Sort a linked list using insertion sort.




Round 2 solution: I just aware that my 1st round solution is actually bubble sort. The insertion sort is given in below:

LeetCode Q:146 LRU Cache (hard)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Round 2 solution:
The key here is to keep a list iterator in hash map. We save a pair in list because we need know what key it is when we remove a value from list. So we can remove this key from hash map.

LeetCode Q145: Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Round 2 solution:

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.