Ninja Coder
BAN USERIt looks up the URL Host name in DNS cache (see ipconfig /flushdns) then it checks the real dns(see google dns) which maps the domain to an ip.
There is probably a slightly altered route for local DNS lookups (for domains).
Then the browser makes a get request to that url.
Go get fiddler to see the request.
Then the server gets the request.
Then the server parses the URLs/cookies/querystrings/etc and returns a response such as a web page with a 200 response. Sometimes it returns a 302 or 301 redirect. Sometimes it returns a 404 for file not found or 500 for error (Search google for http status codes for full list)
Then the browser parses the response.
It uses http header to know if its a text/html file or some other file which should pop a download dialog.
Then it also does some content sniffing if it does not believe the Http Header content type.
Assuming it is a web page it then parses the markup and turns it into DOM.
When it comes across Images/CSS/JS/Object tags it checks cache and if not in cache it makes network requests...
...
M=2, N=7, K=8
Fill N (0,7)
Take out M and throw away (0,5)
Take out M and throw away (0,3)
Take out M and throw away (0,1)
Move N to M (1,0)
Fill N (1, 7)
That is how you get 8.
To get 9 you fill up both N and M.
I thought you can not get 10 because you don't have bucket K to pour stuff into...
However the GCD people seem to make it seem like you can get the 10 because you can fill the K while solving the problem (just use the 2 sized bucket 5 time)...
If both parts have the same average and you add the 2 segments together the average is the same as the whole.
So do this:
1. Go over the array and get the length and sum, then divide them to get average. O(n)
2. Then use this O(n^2) algorithm to find a subset that has the same average.
public List foundSetWithAverage(int[] arr, float avg)
{
return foundSetWithAverageHelper(arr, avg, 0, 0, 0);
}
private List findSetWithAverageHelper(int[] arr, int pos, float avg, int sum, int len)
{
if (pos == arr.length)
{
return null;
}
List list = findSetWithAverageHelper(arr, pos + 1, avg, sum, len);
if (list != null)
{
return list;
}
sum = sum + arr[pos];
len = len + 1;
if (sum / len == avg)
{
list = new List();
list.add(pos);
return list;
}
list = findSetWithAverageHelper(arr, pos + 1, avg, sum, len);
if (list != null)
{
list.add(pos);
return list;
}
return null;
}
3. Then split the original one into 2 other ones O(n)
- Ninja Coder October 03, 2011This is my O(N^2) solution:
I didn't 100% understand the O(N+N) talk above...
public bool foundSumZero(int[] arr)
{
return findSubSumWithSkip(arr, 0, 0);
}
private bool findSubSumWithSkip(int []arr, int pos, int subSum)
{
if (pos == arr.length)
{
return false;
}
return findSubSumWithSkip(arr, pos + 1, subSum) ||
findSubSum(arr, pos, subSum);
}
private bool findSubSum(int []arr, int pos, int subSum)
{
if (pos == arr.length)
{
return false;
}
subSum = subSum - arr[pos];
if (subSum == 0)
{
return true;
}
return findSubSum(arr, pos + 1, subSum);
}
The one above works however its probably easy to combine the 2 while loops into one to be a little cleaner.
Also renaming tmp to "carryOverValue" or something would be good too...
"increment both by one until they meet" works.
- Ninja Coder October 04, 2011Slow pointer went this far:
X (distance between beginning of list and start of circle) + Y (distance between beginning of list and meeting point).
Fast pointer went this far:
X (distance between beginning of list and start of circle)
+ Y (distance between beginning of list and meeting point) + Z (distance between meeting point and start of circle) +
Y (distance between beginning of list and meeting point)
We also know that the fast one went twice as fast as the slow one.
So 2 * (X + Y) = X + Y + Z + Y
Simplified X = Z
That is why it works.
Math win :-)