aalimian
BAN USERAre you sure this implementation will work and you will not miss the true median ? I have been asked once to find the first 4 largest elements in the array and I provided an O(4n) solution. Find first maximum then take it out, the 2nd maximum, etc. In the case of a median this will be O(n-square).
- aalimian April 11, 2013First you need to reverse the two linked lists, unless the heads that are given point to least significant bits of both numbers. Most likely that is not the case.
After the two linked lists are reversed, we scan both of the heads forward and sum them. We can either get 0 or 1. If it's a 1, it gets carried over, if not you just move forward. If either of the heads becomes null, we stop its traversal and keep traversing the head that is not null. Once we reach the end and we still have a carry-over bit 1, we need to prepend a new head with value 1. Reverse the resulted linked list and return its head.
Looks like a graph, with each letter being a node. And we need to find the path from one node to the other using breadth first search and the nodes being the subsequent letters. Meaning if have a word "hello", we need to find the following paths:
1. "h" to "e"
2. "e" to "l"
3. "l" to "o"
Each node may have up to 4 children.
Insertion sort is what needs to be used here. Even though with insertion sort we will have O(n-square) complexity. Here is how I see the implementation:
1. Create a new empty list
2. Traverse the original list node by node and insert the new node in the newly created list but in the right order. Meaning, we need to have another function ReturnIndex(Node head, int number), which well return the index where the new number needs to be inserted in the linked list with head "head".
3. Once we get that index, we insert it right there.
Very elegant implementation of insertion sort can be found on Wikipedia.
This one works. A bit longer and requires an extra data structure. But a clean implementation:
public class Range
{
public int start, end, sum;
}
public static List<int> BiggestSumSet(List<int> numbers)
{
List<Range> ranges = new List<Range>();
Range r = new Range();
int i = 0;
while (i < numbers.Count)
{
r.start = i;
while (i < numbers.Count && numbers[i] >= 0)
{
r.sum += numbers[i];
r.end = i++;
}
ranges.Add(r);
r = new Range();
r.start = i;
while ( i < numbers.Count && numbers[i] < 0)
{
r.sum += numbers[i];
r.end = i++;
}
ranges.Add(r);
r = new Range();
r.start = i;
}
i = 0;
int maxIndex = i;
for (i = 1; i < ranges.Count; i++)
{
if (ranges[i].sum > ranges[maxIndex].sum)
maxIndex = i;
}
i = maxIndex+1;
int totalSum = ranges[maxIndex].sum;
while(i < ranges.Count)
{
totalSum += ranges[i].sum;
if (totalSum > ranges[maxIndex].sum)
{
ranges[maxIndex].end = ranges[i].end;
}
i++;
}
if (totalSum < ranges[maxIndex].sum)
{
totalSum = ranges[maxIndex].sum;
}
i = maxIndex-1;
while (i >= 0)
{
totalSum += ranges[i].sum;
if (totalSum > ranges[maxIndex].sum)
{
ranges[maxIndex].start = ranges[i].start;
}
i--;
}
return numbers.GetRange(ranges[maxIndex].start, ranges[maxIndex].end - ranges[maxIndex].start + 1);
}
Table look-up, if space is not an issue. If space is an issue then even bit vector implementation won't work because it says you can have repeating elements.
- aalimian April 12, 2013