Given a number “n”, find the least number of perfect square numbers that sum to n
For Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)
Daily Archives: October 29, 2015
Search in a 2D Array or Matrix
Write an efficient algorithm that searches for a value in an m x n matrix.
Matrix can have two forms. Solve it for each form of the matrix. This matrix has the following properties:
Serialize and Deserialize Binary Tree
Design an algorithm to serialize and deserialize a binary tree.
There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Topological Sort
Given a graph G(V,E), find the topological sorted list of vertices.
First of , what is topological sorting?
From wikipedia, topological sort (sometimes abbreviated toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
Rearrange Characters in String With No Adjacent Duplicate Characters
Given a string, rearrange characters of the string such that no duplicate characters are adjacent to each other.
For example,
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output