bp
BAN USERWhat am I missing here. Isn't the solution as simple has having master ask each server for their 10th URL and count. Then computing the top out of those, call it U. Then in a second round asking all servers for all URLs with count greater than that if U and finding the top 10 out of those? Why such a complicated solution has been invited so much? I'm honestly asking, am I missing something?
- bp November 07, 2015I think a simpler approach would be to just store the in-order traversal of the whole tree in one single array and pop one at a time from each side of the array.
I did the 2 array approach in the interview though. Not sure why I did that when I could have used just one array. May be I overestimated the question and tried to do something complicated. :)
But like you asked, when the tree is unbalanced, you will get one array smaller than the other. You just pop elements from the smaller to the larger array until they are even in size.
My mind is fried. But this seems to be working now.
public static BSTNode BSTToMaxHeap(BSTNode root)
{
if (root == null)
return null;
root.left = BSTToMaxHeap(root.left);
root.right = BSTToMaxHeap(root.right);
//sift root down
return SiftNodeDownInBST(root);
}
public static BSTNode SiftNodeDownInBST(BSTNode node)
{
BSTNode right = node.right;
BSTNode nodeToReturn = right;
BSTNode left = node.left;
while (right != null)
{
node.left = right.left;
node.right = right.right;
right.right = SiftNodeDownInBST(node);
right.left = left;
right = node.right;
left = node.left;
}
if (left != null)
{
if (left.value > node.value)
{
nodeToReturn = left;
BSTNode l = left.left;
BSTNode r = left.right;
left.right = node.right;
node.left = l;
node.right = r;
left.left = SiftNodeDownInBST(node);
}
}
return nodeToReturn??node;
}
Actually I was interviewed for SE in Test and the questions weren't any easier. And I got interviewed by both SEs and SETs. Yes, but they do ask you to extensively test the code that you write when you're interviewing for the SET position. Btw, SDET is a Microsoft thing. In Google it's SET.
- bp January 31, 2014Strange. May be my recruiter did not have the correct information then. Thanks for the clarification btw. And apologies for commenting like this. I just wanted to make sure what I was told was correct and I wanted everybody to be aware of it. Apparently, I was given incorrect information. Thanks.
- bp January 31, 2014private static List<string> shortestPath = new List<string>();
public static void ChessMoves(bool[,] matrix, int startX, int startY, int endX, int endY, List<string> path)
{
ChessMovesInternal(matrix, startX, startY, endX, endY, path);
foreach (string p in shortestPath)
Console.WriteLine(p);
}
public static void ChessMovesInternal(bool[,] matrix, int startX, int startY, int endX, int endY, List<string> path)
{
if (startX< 0
|| startY <0
|| startX>=matrix.GetLength(0)
|| startY>=matrix.GetLength(1)
|| matrix[startX, startY])
{
return;
}
if (startX == endX && startY == endY)
{
path.Add(endX + ", " + endY);
if (path.Count < shortestPath.Count
|| shortestPath.Count ==0 /*no path found yet*/)
{
shortestPath = new List<string>();
foreach (string p in path)
shortestPath.Add(p);
}
path.Remove(endX + ", " + endY);
return;
}
List<int[]> nextStep = new List<int[]>();
nextStep.Add(new int[] { startX - 1, startY - 1 });
nextStep.Add(new int[] { startX + 1, startY + 1 });
nextStep.Add(new int[] { startX - 1, startY + 1 });
nextStep.Add(new int[] { startX + 1, startY - 1 });
matrix[startX, startY] = true;//visited in this path
path.Add(startX + ", " + startY);
foreach (int[] nextStart in nextStep)
{
ChessMovesInternal(matrix, nextStart[0], nextStart[1], endX, endY, path);
}
path.Remove(startX + ", " + startY);
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Puzzle2
{
class Program
{
/*If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.
For example:
Input: "1123". You need to general all valid alphabet codes from this string.
Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23*/
public static Dictionary<int, char> map = new Dictionary<int,char>();
static void Main(string[] args)
{
for (int i = 1; i <= 26; i++)
{
map[i] = (char)('a' + (i - 1));
}
PrintCodes(string.Empty, "1123");
Console.ReadKey();
}
public static void PrintCodes(string codePrefix, string subString)
{
if(subString.Length==0)
Console.WriteLine(codePrefix);
for (int i = 1; i <= 2; i++)
{
if (i > subString.Length)
break;
else if (i == subString.Length)
Console.WriteLine(codePrefix + map[int.Parse(subString)].ToString());
else
{
string subSubString = subString.Substring(0, i);
string codePre = map[int.Parse(subSubString)].ToString();
PrintCodes(codePrefix + codePre, subString.Substring(i));
}
}
}
}
}
{{using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Puzzle2
{
class Program
{
/*If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.
For example:
Input: "1123". You need to general all valid alphabet codes from this string.
Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23*/
public static Dictionary<int, char> map = new Dictionary<int,char>();
static void Main(string[] args)
{
for (int i = 1; i <= 26; i++)
{
map[i] = (char)('a' + (i - 1));
}
PrintCodes(string.Empty, "1123");
Console.ReadKey();
}
public static void PrintCodes(string codePrefix, string subString)
{
if(subString.Length==0)
Console.WriteLine(codePrefix);
for (int i = 1; i <= 2; i++)
{
if (i > subString.Length)
break;
else if (i == subString.Length)
Console.WriteLine(codePrefix + map[int.Parse(subString)].ToString());
else
{
string subSubString = subString.Substring(0, i);
string codePre = map[int.Parse(subSubString)].ToString();
PrintCodes(codePrefix + codePre, subString.Substring(i));
}
}
}
}
}
}}
RepEdithJHarden, Random at Axiom Sources
Je suis un professionnel de la gestion des soins de santé avec 2 ans d'expérience en supervision d'établissements ...
Repchingdelisa, Accountant at ABC TECH SUPPORT
I'm a Creative director in San Diego, USA.I map out future plans and make sure the result and ...
RepSarahSKelly, Game Programmer at Akamai
I am Professor, and I am also a skilled fiction writer. I have a collection of novels published in the ...
Repmarkemorgan007, Applications Developer at Big Fish
I am Mark From Fresno city in USA.I working as a tour guide and also help for make a ...
Questions
- bp February 26, 2017How tiny?
If a URL is already shortened, do we shorten it again?
If a URL is a URL that does not lead anywhere, but is a made up URL, then do we still shorten it?
If the URL is already “short enough” do we shorten it further?
Do we shorten URLs that are short URLs generated by our short url system?
How many URLs are we talking about? -- Is it more than Long.MAX_VALUE?
Core Design
Insert URL to database and use something like base 62 [a-z,A-Z,0-9] encoding of the index column.
We look up if a URL is already shortened -- if it is then return that shortened version.
Go to URL and don’t create a short URL if you get a 404 or if DNS resolution fails (domain doesn’t even exist)
Check for malicious content.
Check against a blacklist of websites.
Send content to an API that tries to use AI to understand if malicious content.
When a user does a GET on a short URL, then do a 302 to redirect user to it.
Provide functionality to flag a URL.
Provide functionality to delete a URL?
There can be a potential problem here - If I insert a URL, delete it and then repeat this process a large number of times, I will extinguish available short URLs
Provide functionality to detect DOS attacks
Throttle number of requests per IP per URL.
Add frequently used URLs to cache.
Disk/Database -
--Replication
--Sharding - based on URL
--Disk striping (RAID0)
--Use SSD.
Cache
Distributed cache
Edge cache servers for regions.
Possible problems
If I insert a URL, delete it and then repeat this process a large number of times, I will extinguish available short URLs
-We can mark a URL deleted on delete, then while creating new URLs, first get the list of URLs marked deleted and replace the first one of those
-If no URL marked for delete, then insert new record into DB.