Nelson Perez
BAN USER
ABOUT
•Nelson has 10+ years of software development and leading experience.
•Passionate about Big Data, Business Intelligence (BI), Web Development & Cloud highly scalable & highly available services
•Always excited to rapidly ramp-up & learn new skills and technologies.
•Definitely looking for interesting opportunities to skills, passion and agility to provide direct innovation and value to customers.
•Startup/Hackathon cultures are always welcome!
HIGHLIGHTS
•Architected & leaded a company-wide automation platform from build to feature progress & burn down reports for Action Engine.
•Developed service health optics for Windows Azure Active Directory.
•Developed Exchange Online Storage service a big data pipeline.
•Delivered new big data behavioral targeting segments for display and email ads for Bing, Hotmail and Live Messenger marketing teams
•Leaded the solution that saved $3.7 Million/year optimizing Search Engine Marketing budget for Bing Search Cashback online campaign.
EDUCATION
•B.S. in Computer Engineering [CS + EE] + Project Manager Certificate @ University of Puerto Rico – Mayaguez, PR 1999-2005
•Certifications: Project+, Technical Trainer, Project+, MCP
- 1of 1 vote
AnswersConvert a binary tree into a In Order traversal circular list re-purposing the node's pointers Left & Right as Previous and Next respectively.
- Nelson Perez in United States
Hint: A single node Left & Right points to itself.
Note: This is not a binary search tree.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Coding
Oops! wrong answer. I'm to sleepy to think I though it was just returning the merged set.
The problems seems to be simpler just add to a list everything found that supports the conditions and return that back without the need to calculate the big merged overlapped range.
public static List<Range> MergeRanges(List<Range> ranges, Range overlap)
{
int start = overlap.start;
int end = overlap.end;
List<Range> result = new List<Range>();
for(int i = 0; i < ranges.Count; i++)
{
Ranges r = ranges[i];
// This also covers the case where r is larger than overlap
if(r.start < overlap.start && r.end >= overlap.start)
{
start = r.start;
}
else if(r.start <= overlap.end && r.end > overlap.end)
{
end = r.end;
}
else if(r.start < overlap.start && r.end > overlap.end)
{
start = r.start;
end = r.end;
}
else if(r.end < overlap.start || r.start > overlap.end)
{
result.Add(r);
}
}
result.Add(new Range(start, end));
return result;
}
I felt that this problem ate me alive. I need to practice more.
For this solution I used multiplication having precedence over sum so I've used a stack to hold the values of for multiplication so when there is a summation I resolve all the multiplications.
void Main()
{
Console.WriteLine(Evaluate("3*5+8"));
}
public static int Evaluate(string S)
{
Stack<int> values = new Stack<int>();
int total = 0;
int prev = 0;
for(int i = 0; i < S.Length; i++)
{
if('+' == S[i])
{
while(values.Count != 0)
{
prev*= values.Pop();
}
total += prev;
prev = 0;
}
else if('*' == S[i])
{
values.Push(prev);
prev = 0;
}
else
{
prev *= 10;
prev += S[i] - '0';
}
}
while(values.Count != 0)
{
prev*= values.Pop();
}
total += prev;
return total;
}
I though of that many times before but you don't really need to any information to stack them you can just count them and make sure that there are the same number of parenthesis closing.
- Nelson Perez February 23, 2015This reminded be of a nasty problem of calculating or possible parenthesis based on an integer.
public static int CountMaxParenthesis(string S)
{
if(S == null)
throw new ArgumentNullException();
int count = 0;
int max = 0;
for(int i = 0; i < S.Length; i++)
{
char s = S[i];
if(s == '(')
{
count++;
if(count > max)
{
max = count;
}
}
else if(s == ')')
{
count--;
}
}
if(count != 0)
throw new ArgumentException(
"Parameter S does not have a balanced parenthesis nesting");
return max;
}
In this case the string comparisons requires more operations thus in this 3n/2 would be a better choice for string comparisons or anything more complex than integers.
This is because the comparison become the bottom-neck so less comparisons mean less operations.
But for original problem which compares integers my argument still stands as a comparison is a single operation.
This is the solution that I though in the interview.
So in order to make the tree a linked list you need to get the the last element from the list from the right and the first element from the list of the left.
Previously I've solved it returning a Tuple<Node,Node> with the first and last node of the "list".
But this is the right solution some variables could be removed but it is a mess not to have then for reference.
public static Node ConvertToList(Node root)
{
Node first = root;
Node last = root;
if(root == null)
return null;
Node previous = ConvertToList(root.Left);
Node next = ConvertToList(root.Right);
root.Left = root;
root.Right = root;
if(previous != null)
{
first = previous;
last = first.Left;
last.Right = root;
root.Left = last;
first .Left = root;
root.Right = first;
last = root;
}
if(next != null)
{
last = next.Left;
last.Right = first;
next.Left = root;
root.Right = next;
}
return first;
}
Just made the process High Priority I finally saw it beating twice.
These are the best cases for 3n/2 been 96% the linear:
Populate Array: 443.0253
-199999924, 199999855 Linear Took: 108.0062
-199999924, 199999855 3n/2 Took: 104.006
Populate Array: 449.0257
-199999970, 199999980 Linear Took: 100.0057
-199999970, 199999980 3n/2 Took: 97.0056
This is the Average linear is 90% of 3n/2 faster:
Populate Array: 422.0241
-199999921, 199999945 Linear Took: 92.0053
-199999921, 199999945 3n/2 Took: 102.0058
This are two example of the best cases linear is %69 the 3n/2:
Populate Array: 482.0276
-199999966, 199999981 Linear Took: 81.0046
-199999966, 199999981 3n/2 Took: 117.0067
Populate Array: 397.0227
-199999958, 199999975 Linear Took: 78.0044
-199999958, 199999975 3n/2 Took: 113.0065
Not sure if it works as the signature of the function changed when you call it.
But I did had the same mistake as I forgot to make the current.Right.Left = current and current.Left.Right = current to make it a double linked list even though in the pseudo code I did.
I do not know if it works as it is very messy how it is displayed in CareerCup.
But this is indeed for sure n^2.
It does not matter if you run from for a segment of the array as it is not a constant subset of n because approaches infinity it becomes so the subset of n is infinite as well so it is n^2.
@variksla: Thanks for the comment
True I though about using memoization but then though that for that to work I need to create a my own hash function which created a hash using the ropes left in the dictionary and the N and I though it was not a good idea to do this specially in an interview.
Yes it is similar to the subset problem where ask you to select of certain number from an array A which adds to an integer N.
To tell you the truth I did not understood quite well the problem I just assume that a list of ropes were given.
But if the ropes were infinite and you had various options 2, 5, 6 then memoization would be an option based on N. :-)
Comparisons really does not matter what matters are operations.
Even though there there are 3n/2 comparisons there are 13n/2 operations.
All these operations divided by two(2) as the for loop jumps by 2:
4 for getting the value using the index
2 for (i + 1)
3 comparisons
2 assignments
3 operations in the for loop
This are 7n operations.
While in a linear approach there would have comparisons order of 1n, 3n/2, 2n for best, average, worst respectively.
Taking the worst case:
There are:
2 indexing operations
2 comparisons
1 assignment
3 operations in the for loop
Which is 8n operations which on operation more than 7n of the operations of the 3n/2 comparisons solution.
The 3n/2 algorithm does 87.5% comparison compared to the linear approach.
How about the average case number operations assuming 1/3 of the numbers will be in between min and max:
6 indexing operations
1/3 assignment
3 operations in the for loop
The average case takes 69% operations of what the 3n/2 comparison solution would take.
7n => 7
23n/6 => 4.833..
I personally would take that trade off of the linear approach based on average case performance.
In real world scenario I've tested both and the linear approach was never beaten against the 3n/2 comparison one.
The closest in in milliseconds I saw was:
Populate Array: 448.0256
-199999999, 199999940 Linear Took: 95.0055
-199999999, 199999940 3n/2 Took: 97.0055
In average I saw:
Populate Array: 445.0254
-199999995, 199999995 Linear Took: 84.0048
-199999995, 199999995 3n/2 Took: 104.0059
Feel free to verify this by yourself using C# you can download LINQPad.
void Main()
{
DateTime start;
DateTime end;
int[] array = new int[10000000];
Random rand = new Random();
start = DateTime.Now;
for(int i = array.Length-1; i >= 0; i--)
{
array[array.Length - i -1] = rand.Next(-20*array.Length, array.Length*20);
}
end = DateTime.Now;
Console.WriteLine("Populate Array: " + (end - start).TotalMilliseconds);
Tuple<int, int> result;
try
{
start = DateTime.Now;
result = FindMinimunMax(array);
end = DateTime.Now;
Console.WriteLine(result.Item1 + ", " + result.Item2 + "\t Linear \t Took: " + (end - start).TotalMilliseconds);
start = DateTime.Now;
result = FindMinimunMax3n2(array);
end = DateTime.Now;
Console.WriteLine(result.Item1 + ", " + result.Item2 + "\t 3n/2 \t\t Took: " + (end - start).TotalMilliseconds);
}
catch(Exception e)
{
Console.WriteLine(e.ToString());
}
}
public static Tuple<int, int> FindMinimunMax(int[] A)
{
if(A == null || A.Length == 0)
throw new ArgumentNullException();
int max = A[0];
int min = A[0];
for(int i = 0; i < A.Length; i++)
{
if (max < A[i] )
{
max = A[i];
}
else if(min > A[i])
{
min = A[i];
}
}
return new Tuple<int, int>(min, max);
}
public static Tuple<int,int> FindMinimunMax3n2(int[] A)
{
int mi = int.MaxValue;
int ma = int.MinValue;
for(int i = 0; i<A.Length; i+=2){
if (A[i]<A[i+1]){
mi = Math.Min(mi, A[i]);
ma = Math.Max(ma, A[i+1]);
}else{
mi = Math.Min(mi, A[i+1]);
ma = Math.Max(ma, A[i]);
}
}
return new Tuple<int, int>(mi, ma);
}
variables but I'm not a fan of those.
@- ninhnnsoc I meant there is an anwer above that clains 3n/2 is better than n.
@trophygeek
Answering the questions:
I return a Tuple<int, int> as it is a coding interview question and as simple as possible is better.
To make it more clear I would document it like i did bellow.
But another ways could be use "out" could be create a struct or class that return both values but it is a bit of an overkill for a simple function in an interview.
I knew about doing only one comparison but I fixed so I I though about it and I said what the heck it was late and I was tired.
Implementing this with an array of floats is out of scope but I did here is an implementation for anything that can be compared.
In terms of the 3n/2 coparissons theme:
You are right about the 3n/2 comparisons worst/average/best cases remain the same on YOUR solution but in the linear solution has a worst case is 2n, best case 1n and in average it is 3n/2 which is a trade off depending any statistical hint of the stream.
I was looking at the first solution by @Skur that did go sort of twice and did all kind of extra operations which they did not make any sense to me.
----
Here is the fix for the question that you had above:
/// <summary>
/// Finds the minimun and maximun of an array if the array is empty it will return null.
/// </summary>
/// <param name="A">
/// Array with the <paramref name="T"/></param>
/// <typeparam name="T">IComparable type</typeparam>
/// <returns>
/// <see cref="Tuple<T, T>"/> where Item1 is the minimun and Item2 is the maximun values of the array.
/// If the array is empty the it will return null
/// </returns>
public static Tuple<T, T> FindMinimunMax<T>(T[] A)
where T:IComparable
{
if (A == null || A.Length == 0)
return null;
T max = A[0];
T min = A[0];
foreach (T a in A)
{
if (max.CompareTo(a) > 0)
{
max = a;
}
else if(min.CompareTo(a) < 0)
{
min = a;
}
}
return new Tuple<T, T>(min, max);
}
This is just crazy adding unnecessary operations going twice through the array the order of growth still is O(n) but it is way less efficient offering O(3n/2) which is > O(n)
This is a very simple going through the array and track the min and max as there is no statistics about the array you can't have other strategy than read the entire array once to determine the min and max.
If this would be finding the nth element it would be a bit more complicated problem but it is less code.
Sorting is O(nlogn) which growths larger than plain O(n)
- Nelson Perez February 22, 2015I don't understand why over complicating the problem reading the array twice doing O(3n/2) which is scales worst than O(n) and reads the array multiple times that is nonsense.
Here is a how simple it is:
public static Tuple<int, int> FindMinimunMax(int[] A)
{
int max = int.MinValue;
int min = int.MaxValue;
foreach(int a in A)
{
if(max < a)
{
max = a;
}
if(min > a)
{
min = a;
}
}
return new Tuple<int, int> (min, max);
}
public static bool DrRopes(List<int> ropes, int N)
{
if(N == 0)
return true;
if(N < 0)
return false;
for(int i = 0; i < ropes.Length; i++)
{
int r = ropes[i];
ropes.RemoveAt(i);
if(DrRopes(ropes, N-r))
{
return true;
}
ropes.Insert(i, r);
}
return false;
}
I'm getting to hate this problem as I'm having trouble to come up with a clean solution.
Anyway this one O(n) solution.
I think this can be cleaned up if I do not use the Queue and just the array itself.
I'll send that later once I have it.
void Main()
{
char[] p = new char[]{'a','b','c'};
string a1 = "abbcbcba";
Console.WriteLine(GetMinDistance(a1, p));
}
public static string GetMinDistance(string S, char[] P)
{
HashSet<char> hs = new HashSet<char>(P);
Dictionary<char, int> ht = new Dictionary<char, int>();
Queue<Tuple<char, int>> q = new Queue<Tuple<char,int>>();
int pos = -1;
foreach(char h in hs)
{
ht.Add(h, 0);
}
for(int i = 0; i < S.Length; i++)
{
char s = S[i];
if(ht.ContainsKey(s))
{
ht[s]++;
q.Enqueue(new Tuple<char, int>(s, i));
if(hs.Contains(s))
{
hs.Remove(s);
if(hs.Count == 0)
{
pos = i;
break;
}
}
}
}
int minStart = q.Peek().Item2;
int min = pos - minStart + 1;
if(hs.Count > 0)
throw new ArgumentException("S does not contains P");
while(true)
{
Tuple<char, int> t = q.Dequeue();
ht[t.Item1]--;
bool found = false;
if(ht[t.Item1] == 0)
{
for(int i = pos + 1; i < S.Length; i++)
{
char s = S[i];
if(ht.ContainsKey(s))
{
ht[s]++;
q.Enqueue(new Tuple<char, int>(s, i));
if(s == t.Item1)
{
found = true;
pos = i;
break;
}
}
}
if(!found)
{
break;
}
}
if((pos - q.Peek().Item2 + 1) < min)
{
minStart = q.Peek().Item2;
min = pos - minStart + 1;
}
}
return S.Substring(minStart, min);
}
Here I find the maximun and then find min before the maximun.
Then find the minnimun and then find the max after minimun.
Compare which one is greater.
void Main()
{
int[] A = new int[]{
3,4,5,7,8,9,11,12,15,4,6,7,8,100,0,99
};
Console.WriteLine(MaxDifference(A));
}
public static int MaxDifference(int[] A)
{
int max = int.MinValue;
int max_min = int.MaxValue;
int max_index = -1;
int min = int.MaxValue;
int min_max = int.MinValue;
int min_index = -1;
for(int i = 0; i < A.Length; i++)
{
int a = A[i];
if(max < a)
{
max_index = i;
max = a;
}
if(min > a)
{
min_index = i;
min = a;
}
}
// Max Diference of max
for(int i = 0; i < max_index; i++)
{
int a = A[i];
if(max_min > a)
{
max_min = a;
}
}
for(int i = min_index + 1; i < A.Length; i++)
{
int a = A[i];
if(min_max < a)
{
min_max = a;
}
}
int min_diff = (min_max - min);
int max_diff = (max - max_min);
return (max_diff > min_diff)?max_diff:min_diff;
}
void Main()
{
Console.WriteLine(LongestRepeatingChar("this is a test sentence"));// => [t, h, i, s, i, s, a, t, e, s, t, s, e, n, t, e, n, c, e]
Console.WriteLine(LongestRepeatingChar("thiis iss a teest seentennce"));// => [i, s, e, e, n]
Console.WriteLine(LongestRepeatingChar("thiiis iss aa teeest seentennnce"));// => [i, e, n]
Console.WriteLine(LongestRepeatingChar("thiiiis iss a teeest seeentennncccce"));// => [i, c]
}
public static List<char> LongestRepeatingChar(string S)
{
var result = new Dictionary<char, List<int>>();
char prev = ' ';
if(S.Length > 0)
{
prev = S[0];
result.Add(S[0], new List<int>(){1});
}
int count = 1;
int max = 0;
for(int i = 1; i < S.Length; i++)
{
char s = S[i];
if(s == prev)
{
count++;
}
else
{
if(result.ContainsKey(prev))
{
result[prev].Add(count);
}
else
{
result.Add(prev, new List<int>(){count});
}
if(max < count)
max = count;
count = 1;
prev = s;
}
}
if(result.ContainsKey(prev))
{
result[prev].Add(count);
}
else
{
result.Add(prev, new List<int>(){count});
}
if(max < count)
max = count;
Console.WriteLine(result);
List<char> lResult = new List<char>();
foreach(char s in S)
{
if(s != ' ')
{
var list = result[s];
for(int i = 0; i < list.Count; i++)
{
int r = list[i];
if(r == max)
{
lResult.Add(s);
list.RemoveAt(i);
break;
}
}
}
}
return lResult;
}
I solved using recursion but I see that an iterative is possible.
void Main()
{
char[] p = new char[]{'a','b','c'};
string a1 = "abbcbcba";
Console.WriteLine(GetMinDistance(a1, p));
}
public static string GetMinDistance(string A, char[] P)
{
Dictionary<char, int> ht = new Dictionary<char, int>();
foreach(char p in P)
{
if(!ht.ContainsKey(p))
{
ht.Add(p, 1);
}
else
{
ht[p]++;
}
}
Tuple<int, int> min = new Tuple<int, int>(0, int.MaxValue);
int minDistance = min.Item2 - min.Item1;
for(int i = 0; i < (A.Length - P.Length + 1); i++)
{
Tuple<int, int> temp = GetMinDistanceHelper(A, ht, i, P.Length);
Console.WriteLine(temp);
// This means the reamining string did not found the set P
if(temp.Item2 == int.MaxValue) break;
int tempDistance = (temp.Item2 - temp.Item1);
if( tempDistance < minDistance)
{
min = temp;
minDistance = tempDistance;
// Means this is the minimum possible set
if(minDistance == P.Length - 1)
break;
}
// Move the i to the first occurence of a char in the set
if(temp.Item1 > i)
{
i = temp.Item1 + 1;
}
}
if(min.Item2 == int.MaxValue) throw new ArgumentException("Array P is not present in string A");
return A.Substring(min.Item1, minDistance);
}
private static Tuple<int, int> GetMinDistanceHelper(
string A,
Dictionary<char, int> ht,
int start,
int remaining)
{
Console.WriteLine(remaining);
Console.WriteLine(ht);
if(remaining == 0)
return new Tuple<int,int>(start, start);
for(int i = start; i < (A.Length - remaining + 1); i++)
{
char c = A[i];
if(ht.ContainsKey(c) && ht[c] > 0)
{
ht[c]--;
Tuple<int, int> temp = GetMinDistanceHelper(A, ht, i + 1, remaining - 1);
ht[c]++;
return new Tuple<int, int>(i, temp.Item2);
}
}
return new Tuple<int,int>(A.Length, int.MaxValue);
}
Seems that everyone has a O(n^3) solution except for one written but you can do it O(n^2) using a HashTable/HashSet/HashMap as the last number you just need to look up.
public static bool FindSum10Combo(int[] A)
{
// This takes O(n) to populate.
HashSet<int> map = new HashSet<int>(A);
for(int i = 0; i < A.Length-2; i++)
for(int j = i + 1; j < A.Length-1; j++)
{
int missing = 10 - (A[i] + A[j]);
if(map.Contains(missing))
{
return true;
}
}
return false;
}
You probably needed to clarify with questions like:
What does it mean to be efficient? What does it mean by in place?
Does it mean with a low memory profile, only write the file once or really fast?
Because depending on the response you should design the algorithm.
Low memory profile in place:
Might mean write directly at another file and replace the original one once done.
No additional memory than the array then perform just swaps in memory.
Really fast might mean just load into an array in and write in reverse order.
Seems a bit ambiguous as not sure if need to print all words of just the duplicates.
I'll let the caller decide to print only dupes or not.
O(n) Solution is the actual leanest way to do this reading words twice (once in the array and once on the Dictionary);
public static void PrintArrayCounts(string[] A, bool printOnlyDupes)
{
var words = Dictionary<string, int>(StringComparer.OrdinalIgnoreCase); // Either this or making to Lower every word
foreach(string a in A)
{
if(!words.ContainsKey(a))
{
words.Add(a, 1);
}
else
{
words[a]++;
}
}
StringBuilder sb = new StringBuilder();
foreach(KeyValuePair<string, int> word in words)
{
if(d.Value > 1 || !printOnlyDupes)
{
sb.Append(d.Key);
sb.Append("--");
sb.Append.(d.Value));
}
}
Console.WriteLine(sb.ToString());
}
Good I tried that strategy of using null for space and I could not get it to work right.
- Nelson Perez January 11, 2015The problem seems a bit unclear as find the maximum non intersecting events in a Calendar. So either is actually asking for all non-intersecting events or asking for max per day anyway it is trivial to find per day so I'll implement both.
public class Event
{
public int Start {get; set; }
public int End {get; set; }
}
public static int GetNonIntersectingEvents(List<Event> events)
{
// Count== 0 is 0 intersection, Count == 1 is 1 intersection
if(events.Count < 2)
{
return events.Count;
}
// This acts like a heap so sorting is O(n log n) as every insertion is O(logn)
SortedDictionary<int, Event> sb = new SortedDictionary<int, List<Event>>();
foreach(Event e in events)
{
if(sb.ContainsKey(e.Start))
sb[e.Start].Add(e);
else
sb.Add(e.Start, new List<Event>(){ e});
}
List<Event> sortedEvents = new List<Events>();
foreach(var kvp in sd)
{
sortedEvents.AddRange(kvp.Value);
}
int result = 0;
bool intersect = false;
Event prev = sortedEvents[0].Clone;
for(int i = 1; i < sortedEvents.Count; i++)
{
Event curr = sortedEvents[i];
if(prev.End > curr.Start)
{
intersect = true;
if(curr.End > prev.End)
{
// Union of intersections
prev.End = curr.End
}
}
else // Means that current breaks the previous
{
// Check if the prev had an intersection
if(intersect == false)
{
results++;
}
intersect = false;
prev = curr.Clone();
}
}
if(intersect == false)
{
result++;
}
return result;
}
In the case where it is asking for the max intersections based on Days
// Assuming events on two days will be two separate events per day.
public class Day
{
public readonly List<Event> Events = new List<Events>();
...
...
}
public static int CalculateMaxNonIntersectingEvents(List<Day> days)
{
int max = 0;
if(days == null || days.Count == 0) return 0;
foreach(Day d in days)
{
int temp = GetNonIntersectingEvents(d.Events);
if(temp > max)
{
max = temp;
}
}
return max;
}
Sort on what?
- Nelson Perez January 09, 2015I like how you use the count to make the new lines. I wish I though of that as I could not figure out how to maintain the level.
- Nelson Perez January 09, 2015Actually you could do that using a Queue and anther Queue just to maintain in the right order when printing.
public class Node<T>
{
public Node<T> Left {get; set;}
public Node<T> Right {get;set;}
public T Data {get; set;}
}
private class NodeLevel<T>
{
public Node<T> Node {get; set;}
public int Level {get; set;}
}
static public string GetBinaryTreeRows<T>(Node<T> root)
{
if(root == null) return null;
Queue<NodeLevel<T>> Q = new Queue<NodeLevel<T>>();
Queue<NodeLevel<T>> S = new Queue<NodeLevel<T>>();
Q.Enqueue(new NodeLevel<T>(){ Node=root, Level=0});
while(Q.Count > 0)
{
NodeLevel<T> np = Q.Dequeue();
Node<T> n = np.Node;
S.Enqueue(np);
if(n.Left != null)
{
Q.Enqueue(new NodeLevel<T>(){
Node = n.Left,
Level = np.Level + 1});
}
if(n.Right != null)
{
Q.Enqueue(new NodeLevel<T>(){
Node = n.Right,
Level = np.Level + 1});
}
}
StringBuilder sb = new StringBuilder();
int lastLevel = 0;
while(S.Count > 0)
{
NodeLevel<T> np = S.Dequeue();
if(np.Level != lastLevel)
{
lastLevel= np.Level;
sb.Append("\n");
}
sb.Append(np.Node.Data.ToString());
sb.Append(" ");
}
return sb.ToString();
}
I've tested using this code. Does not seem clear the tree but it looks like this:
(d)
/ \
(b) (g)
/ \ / \
(a) (c) (e) (h)
\
(f)
void Main()
{
// Tree
// a - h
Node<string> root = new Node<string>(){
Data = "d",
Left = new Node<string>(){
Data = "b",
Left = new Node <string> ()
{
Data = "a"
},
Right = new Node<string>()
{
Data = "c"
}
},
Right = new Node<string>()
{
Data = "g",
Left = new Node<string>()
{
Data = "e",
Right = new Node<string>()
{
Data = "f"
}
},
Right = new Node<string>()
{
Data = "h"
}
}
};
string expected = "d \nb g \na c e h \nf ";
string output = GetBinaryTreeRows(root);
Console.WriteLine(output);
if(output != expected)
{
throw new Exception("Test Failed");
}
}
One standard solution could be:
1) Each server sort their own numbers (radix sort seems rational approach)
2) If memory is an issue (which the problem does not state that)
Write the result to a file
4) Have one machine at a time merge all files till memory is full then to the next continue where the first left of and so on til reaching half of the total count of numbers and that is the exact median.
O(n) as radix is O(n) and merge is O(n/2) so => O(n)
A more sophisticated solution which "approximates" the mean would be to using a hashing algorithm that warranties even distribution and minimal collision of the numbers across the machines like MD5 for example.
So all the machines will contain the same numbers or close to that and sort or (n/2)th number and the median.
1) Each machine calculate a (HashCode + state)%10,000 and send the number over to the resulting 0-9,999 machine.
2) Calculate on the servers the (n/2)ht number and you got average the approximate mean and you got a very approximate mean calculation.
Here is the meat of the problem I'll let the consumer print the output to the console.
public static List<int> FindABEqualsCD(int[] A)
{
var memo = new Dictionary<int, List<int>>();
for(int i = 0; i < A.Length; i++)
{
for(int j = i + 1; j < A.Length, j++)
{
int t = A[i] + A[j]
if(!memo.ContainsKey(t))
{
memo.Add(t, new List<int>() { i, j };
}
else
{
memo[t].Add(i);
memo[t].Add(j);
return memo[t];
}
}
}
}
return null;
Also easily draw all the lines in a matrix marking each point with the line object and if there are more than one passing in the same matrix put in a structure where for each intersection is represented.
Another way is to convert each point as either a degrees or radian point in the circle. In this way we can say a line intersect if in between a line starts in A and ends in B there are another point that starts in between A & B but end outside A & B.
For example if Line (A, B) and Line (C,D) if in degrees do not intersect if you find them in the following orders ABCD, ACDB or CABD in that orders in radians or degrees otherwise the they intersect when they are like ACBD, CADB
Using recursion to find the largest subset
As mentioned before it is hierarchical as you will have many tags inside a tag.
A way to represent this is using a Tree with multiple children nodes for each of the sub-tags.
Fun easy one.
public static List<int> CalculatePattern(int level)
{
if(level < 0)
throw new ArgumentException("level");
List<int> result = new List<int>() { 1 };
for(int i = 1; i <= level; i++)
{
List<int> temp = new List<int>();
int number = result[0];
int count = 0;
foreach(int r in result)
{
if(r == number)
{
count++;
}
else
{
temp.Add(count);
temp.Add(number);
number = r;
count = 1;
}
}
temp.Add(count);
temp.Add(number);
result = temp;
}
return result;
}
List<int> FindMissingNumbers(int[] array, int missing)
{
return CoreFindMissingNumbers(array, 0, array.Length);
}
List<int> CoreFindMissingNumbers(int start, int end)
{
List<int> result = new List<int>();
if(end-start) == (A[end] - A[start]); // Do nothing as there is no missing numbers here
else if(end-start == 2)
{
for(int i = A[start] + 1; i < A[end]; i++)
{
result.Add(i);
}
}
else
{
int pivot = (end+start)/2;
result.AddRange(CoreFindMissingNumbers(pivot, end);
result.AddRange(CoreFindMissingNumber(start, pivot + 1);
}
return result;
}
No you don't need to read the entire stream when you know what range of numbers are present for example
1 2 3 3 3 4 5 6 6 7 7
Because it is sorted you can assume that the range of the numbers will be 1-7
And just look when the numbers change and the algorithm becomes.
O(k*long(n))
mmm.... Well the sublinear occurs when there is tons of repetition though if there is not a log of repetition it become nlogn.
I agree that it can be done sublinear but it is a specific case.
I though of a solution where it assumes that the ages from start till end every are represented in the array and i just look for all of those ages.
Well I saw a couple of O(klogn) where k <<<< n becomes O(log(n)) solutions and some O(n)
The way I see it is that there are two options here. either O(n-1) where you go all the way till you find A[n] value and based on the difference on the array length is the count of the last age.
The second one is looking if there are no repetitions what is the most ages we will see.
You can determine that by looking at the first and last and age and assume that everything in between exist and if there is more in the array than expected those should be considered the number of duplicates that exists.
Do a binary search from start till end where:
start : current change A[i] < A[i+1]
end : min(Missing numbers to find + remaining duplicates, A.Length)
So the solution I see is of run time.
T(n) => { O(n-1) when: n < k*log(n)
{ O(k log n)
Also because these are ages smaller compare to n with goes to infinity meaning (k << n) so O(klogn) really becomes O(log(n)).
First Option of O(n-1) which is really O(n)
Dictionary<int, int> FindAges_N_minus_1_(int[] A)
{
Dictionary<int, int> result = new Dictinary<int, int();
int k = A[A.Length -1] - A[0]; // Difference of ages
int n = A.Length;
// Solution #1 for smaller sets with lots of age difference
if((n-1) < k*Math.Log(2, n))
{
int last = A[A.Length-1]
int i;
for(i = 0; A[i] != last; i++)
{
if(result.ContainsKey(i))
{
result[i]++;
}
else
{
result.Add(result[i], 1);
}
}
result.Add(last, A.Length - i);
}
else
{
int lastAge = A[A.Length-1]
int duplicates = A.Length - k;
int start = 0;
int end = 0;
for(int i = A[0]; i < lastAge;)
{
int age = A[start];
end = BinarySearchEnd(
A,
start,
A.Length) + 1;
int count = end - start;
int skipped = A[end] - age;
// Removing skipped numbers remaining numbers from the jump
k -= skipped ;
// Removing found duplicates and consider skipped as duplicates
duplicates = duplicates - count + skipped -1;
result.Add(age, count);
start = end;
}
}
return result;
}
int BinarySearchEnd(
int[] A,
int start,
int end)
{
if((start+1) > (A.Length - 1) || A[start] != A[start + 1])
{
return start;
}
if(A[start] == A[A.Length - 1])
{
return A.Length-1;
}
int i = start + 1;
int k = A[start];
while(start < i && (i + 1) < A.Length)
{
if(A[i] == k && A[i+1] != k)
return i;
else if(A[i] > k) {
end= 1;
i = (start + i) / 2;
}
else {
start = i;
i = (i + end) / 2;
}
if( i >= A.Length-1)
return i;
}
return i;
}
This seems to be linear time
- Nelson Perez December 31, 2014I see that many people only considered to be only a concatenation of two words but the specifications states that can be composed of an arbitrary number of words in the dictionary.
public static boo l IsComposed(Hashset<string> dictionary, string word)
{
// Validate input
ValidateInput(dictionary, word);
// Call recursibly
return CoreIsComposed(dictionary, word, 0);
}
private static void ValidateInput(Hashset<string> dictionary, string word)
{
if(dictionary == null)
throw ArgumentNullException("dictionary");
if(string.IsNullOrEmpty(word)
throw ArgumentNull Exception("word");
}
private static bool CoreIsComposed(Hashset<string> dictionary, string word, int start)
{
if(word.Length == start) return true;
for(int i = start + 1; i < word.Length; i++)
{
if(IsWord(dictionary, word.Subsctring(start, i-start)) &&
CoreIsComposed(dictionary, word, start + 1))
{
return true;
}
}
return false;
}
private static bool IsWord(Hashset<string> dictionary, string word)
{
return dictionary.Contains(word);
}
static bool IsPalindrome(string S)
{
int forward = 0;
int backward = S.Length - 1;
while(forward < backward)
{
char fs = SanitizeChar(S[forward]);
char bs = SanitizeChar(S[backward]);
if(fs == bs)
{
forward++;
backward--;
}
else if(bs == (char) 0)
{
backward--;
}
else if(fs == (char) 0)
{
forward++;
}
else
{
return false;
}
}
}
char SanitizeChar(char C)
{
if(C >= 'a' && C <= 'z')
return C;
if(C >= 'A' && C <= 'Z')
{
C = C - 'A' + 'a';
return C;
}
else
return (char)0;
}
Do not why everyone goes iterative with this problem.
In my case I went recursive as is the way I could come up with an understandable solution.
static bool IsHopable(int[] array, int start = 0)
{
for(int i = array[start]; j > 0; i--)
{
if(array[start] >= (array.Length -1))
return true;
else if(IsHopable(array, start + i)
return true;
}
return false;
}
A simple counting is the answer here.
enum Priority
{
High = 0,
Med = 1,
Low = 2
}
IEnumerable<Priority> SortPriorities(IEnumerable<Priority> priorities)
{
Dictionary<Priority, int> hResult = new Dictionary<Priority, int>();
Priority[] ordered = new Priotity[](){ High, Med, Low}
foreach(Priority op in ordered )
{
hResult.Add(op, 0);
}
foreach(p in priorities)
{
hResult[p]++;
}
List<Priority> result = new List<Priority>();
foreach(Priority op in ordered )
{
for(int i = 0; i < hResult[op];i++)
{
result.Add(op);
}
}
return result;
}
Well I can do it in a "single query line of code" which gives a n*Log(n) but there might be a better solution to do a linear selection for the top k if K < Log(n).
Si this algorithm worst running time is either:
{ n*log(n) for k > log(n)
{ n*k for k < log(n)
Note: I don't need to calculate square root nor the power just the Absolute value for comparisons but I did it anyway.
Point
{
public int x {get;set}
public int y {get;set;}
public Point(int ix, int iy)
{
this.x = ix;
this.y = iy;
}
static IEnumerable<Point> ClosestKPoints(IEnumerable<Point> point, int k)
{
Point target = new Point(5,5);
// Calculate which method is better for performance as it depends on the input
// Sorting n * log(n) if k > log(n)
// Linear selection n * k if k < log(n)
if(k > Math.Log(point.Count, 2))
{
// Cheated here a little bit by using Linq instead of sorting myself but
// I think is ok as other people used PriorityQueues and I did not
// Other ways could be using a heap which is what the PriortyQueues uses
return (from p in points
order by Math.Sqrt(
Math.Power(p.x-target.x, 2) +
Math.Power(p.y-target.y,2))
select p).Take(k)
}
else
{
var tuplet = (from p in points
select
new Tuple<Point, int> {
item1 = p,
item2 = Math.Sqrt(
Math.Power(p.x-target.x, 2) +
Math.Power(p.y-target.y,2))
}
List<Point> result = new List<Point>();
while(k > 0)
{
Tuple<Point, int> max = new Tuple<Point, int>(){item1=null, item2= int.MinValue};
foreach(var t in tuplet)
{
if(t.item2 > max.item2)
max = t;
}
result.Add(max);
k--;
}
return result;
}
}
As above the tricky part is how the numbers offset the tree printing I did a minor fix adding the length of the node.data.ToString() as part of how many spaces will leave before printing the parent.
static void PrintBinaryTree(Node root)
{
List<List<Node>> matrix = new List<List<Node>>();
TraverseTree(
0, /* Level */
matrix,
root);
PrintMatrix(matrix);
}
static int TraverseTree(int level, List<List<Node>> matrix, Node root)
{
if(root == null)
{
return 0;
}
int leftSpace = TraverseTree(level + 1, matrix, root.left);
int rightSpace = TraverseTree(level + 1, matrix, root.right);
AddNodeToMatrix(matrix, level, root, leftSpace, rightSpace + 1);
return leftSpace + node.data.ToString().Length + rightSpace + 1;
}
static void AddNodeToMatrix(
List<List<Node>> matrix,
int level,
Node root,
int leftSpace,
int rigthSpace)
{
while(matrix.Length < level)
matrix.Add(new List<Node>());
while(leftSpace > 0)
{
matrix[level].Add(null);
leftSpace--;
}
matrix[level].Add(node);
while(rightSpace > 0)
{
matrix[level].Add(null);
rightSpace--;
}
}
PrintMatrix(List<List<Node>> matrix)
{
foreach(List<Node> line in matrix)
{
foreach(Node node in line)
{
if(node == null)
{
Console.Write(" ");
}
else
{
Console.Write(node.data);
}
}
Console.WriteLine();
}
}
yep I stumble into the printing the numbers how is that going to offset the tree printing.
I solved it using a "matrix" populating List<List<Node>>
It took me wayyy more than half an hour. :-(
Seems that they just want to crawl the internet to know the URLs.
I don't buy the idea of using a Graph to connect the URLs as it is not part of the requirement but I do think it is usefully to do if you want to keep the relationships between URLs
I do not see the point of doing deduplication on memory by threads that query as this can be done separate thread as connection speeds is more limiting than CPU speed and having a non-blocking thread querying is more useful time than waiting for deduplication.
The best way is to use some data store to be somewhat of a Queue every time you find a new URL hash or index all of the URLs and check for duplicates and stop if it is a duplicate as some other thread or machine or itself has already crawl them.
Here are the bottlenecks and solutions for them:
Memory: Distribute in different machines
CPU: Distribute in different machines
Disk: Distribute the Queues or Databases partitioning the data using a evenly distributed Hash Algorithm
Connection of Speed Crawler: Pre-Compute as much as possible before doing the query like pre-read the queue till memory is full and pre-create required querie objects.
Connection Speed of Sites: Use a Thread Pool to handle slow connections to not block if a connection is slower.
The solution presented in the page is O(n) as it traverse the list in the worst case 4 times.
- Nelson Perez August 05, 2013It is probably simple to don't check for a null everytime or any other flag but just provide the maximum and minimum numbers of the int.Max and int.Min
class Node
{
int data;
Node left;
Node right;
}
public bool IsBST(Node root)
{
return IsBST(root, int.Max, int.Min);
}
private bool IsBSTCore(Node root, int min, int max)
{
if(root == null)
{
return true;
}
// Assuming that values can be repeated on either right or left
if(root.data < min || root.data > max)
{
return false;
}
return IsBST(root.left, min, root.data) && IsBST(result.right, root.data, max);
}
RepNellieWheeler212, None at Service Now
Hey Everyone! My name is Nellie Wheeler and I live in the constantly radiant and wonderful San Francisco, CA, and ...
- Nelson Perez February 25, 2015