Author: Designed or collected by Amin Ariana Audience: Computer Scientist | Software Engineer Status: In Progress
Skill evaluation per problem:
None answered: Not qualified
Only part (a) answered: Intern Parts (a) and (b) answered: Junior developer / entry analyst Parts (a), (b) and (c) answered: Intermediate developer / programmer analyst Parts (a), (b), (c) and (d) answered: Senior developer / design engineer |
posted Feb 15, 2011 3:53 PM by Amin Ariana
[
updated Feb 15, 2011 4:11 PM
]
Tags: Moderate, graphs Problem descriptionYou have a directed connected graph. (for bonus points, drop the "connected" assumption) Write an algorithm that detects a cycle, if any exists, and returns its nodes. Alternatively if you need to simplify the problem, just return a boolean indicating whether you found a cycle.
Grading- Completeness of the C# or pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Is the most efficient solution, O (n), offered? (25%)
Bonus points:- Did you do it for a possibly disconnected graph?
- Did you return the cycle nodes instead of just a boolean?
- Is your code impressively short and clean?
HintsHint #1 - Try to solve the problem on your own. Read this if you're desperate... Ready? Use of an extra hash table or the addition of dirty bits are both acceptable solutions, as long as you qualify the ugliness of your answer and suggest that a better answer may exist. Hint #2 - If you use this hint without coming up with it yourself, you lose the opportunity to look like a genius in the interview. But here it is if you want to use it anyway: If you and your friend are sitting in a race car each, how can you tell if the very long race track is looped? Hint #3 - Still don't get it? OK. Two words for you: Pointers, and Speed. ReferencesA Senior Developer at Amazon in the Mechanical Turk team asked me this question during a 7-hour interview. |
posted Feb 4, 2011 5:24 PM by Amin Ariana
[
updated Feb 4, 2011 5:53 PM
]
Tags: Moderate, dynamic programming Problem description
Given an N-dimensional matrix of n elements of signed integer type, find the contiguous sub-matrix with the maximum sum. Simplified version: Given a 2 dimensional matrix of n elements of signed integer type, find the contiguous 2-dimensional sub-matrix with the maximum sum (see example figure). The simplified 1-dimensional array version of this problem was first posed in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images. Grading - Completeness of the C# or pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Is the most efficient solution offered? (25%)
ReferencesNorman, a fellow engineer at Adify, asked me this question during a seven hour final round interview. Maximum subarray problem. Wikipedia. http://en.wikipedia.org/wiki/Maximum_subarray_problem (accessed Feb. 2011)
|
posted Jan 3, 2011 1:13 PM by Amin Ariana
[
updated Nov 30, 2011 3:30 PM
]
Tags: Moderate, data structure transformation Problem descriptionYou have a tree data structure. The ancestors of a given node are defined to be the node itself, its direct parent, or the ancestors of the parent node. The root node has no parent and is its own only ancestor. Write an algorithm that takes any two nodes and gives their closest common ancestor.
Grading- Completeness of the C# or pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Is the most efficient solution, O (lg n), offered? (25%)
Source codeC# public interface Node
{
Node Parent { get; }
}
public static Node GetLeastCommonAncestor(Node a, Node b)
{
Stack<Node> aStack = GetStack(a);
Stack<Node> bStack = GetStack(b);
while (aStack.Count > 0 && bStack.Count > 0 && aStack.Pop() == bStack.Peek())
zipper = bStack.Pop();
return zipper;
}
private static Stack<Node> GetStack(Node me)
{
Stack<Node> stack = new Stack<Node>();
while (me != null)
{
stack.Push(me);
me = me.Parent;
}
return stack;
}
ReferencesRon Logan asked me this question in my interview with Microsoft. |
posted Jan 3, 2011 12:37 PM by Amin Ariana
[
updated Feb 4, 2011 5:21 PM
]
Tags: Difficult, dynamic programming Problem description(From Wikipedia) In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e. an edit distance). The term edit distance is often used to refer specifically to Levenshtein distance.
The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who considered this distance in 1965.
For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits: - kitten → sitten (substitution of 'k' with 's')
- sitten → sittin (substitution of 'e' with 'i')
- sittin → sitting (insert 'g' at the end).
Given a list of strings representing all the words and phrases in English, and a query string, return the string from the list with the least edit distance from the query string.Grading- Completeness of the C# or pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Is the most efficient solution offered? (25%)
ReferencesLars, a Google engineer and a University of Waterloo alumnus, asked me this during a two hour Google screening interview. Levenshtein distance. Wikipedia. http://en.wikipedia.org/wiki/Levenshtein_distance (accessed Jan. 2011) The Levenshtein-Algorithm. Levenshtein. http://www.levenshtein.net/ (accessed Jan. 2011) |
|
