i059069
BAN USERcan't see if the solution will work, " if the current sum > target, right pointer --; " array is not sorted , how will this work ?
the real N^2 involves an extra data structure (bring N^3 down to N^2 in trade of space)-
use a HashTable to store a Key Value Pair, where the key is the square of the value and the value is the index.
Iterate from the beginning of the array using 2 pointers, calculate P1^2 + P2^2 and check if it matches any value in the hash table.
The iteration costs N^2 .
solution takes O(N^2) but very straight foreword -
/// <summary>
/// builds the word link by connecting the head and end of each of the word in the list.
/// </summary>
/// <param name="leadingChar">expected Head Char for the string at the top of the returning list. </param>
/// <param name="candidateList">the list of the strings</param>
/// <returns>sorted string list, null if such list can't be built</returns>
public static List<string> BuildWordLink(char leadingChar, List<string> candidateList)
{
for (int i = 0; i < candidateList.Count; i++)
{
var currentelement = candidateList[i];
if (leadingChar == ' ' || currentelement[0] == leadingChar)
{
// currentelement is the only element left, we should return here.
if (candidateList.Count == 1)
{
var returnList = new List<string>();
returnList.Add(currentelement);
return returnList;
}
// remove the currentelement from the candidatelist, build a new wordlink using the remaining words that can link to the end character of the current element
candidateList.RemoveAt(i);
var result = BuildWordLink(currentelement[currentelement.Length - 1], candidateList);
if (result != null)
{
result.Insert(0, currentelement);
return result;
}
candidateList.Insert(i,currentelement);
}
}
return null;
}
To test -
var test = new List<string> {"luis", "hector", "selena", "emmanuel", "amish", "anna", "andrea", "rawle"};
var result = BuildWordLink(' ', test);
O(n) solution,
Basically keep a track of (Value - Index) of all the element you walked thru, if you happen to see one that the result of (index - value) is logged previously you got the pair .
private static bool ContainElementsWithValueSumEqualsToIndexSum(int[] array)
{
var hash = new HashSet<int>();
int idx;
for(idx = 0; idx < array.Length; idx++)
{
if(hash.Contains(- (array[idx] - idx)))
return true;
else
hash.Add(array[idx] - idx);
}
return false;
}
this is just a extended version of "sort a queue with the help of an other queue."
First give the solution of "sort a queue with the help of an other queue", the idea here is if the item at the head of the target queue (first queue) is smaller than the item has been dequeued and pushed to the temp queue (second queue) , we dequeue the item from target queue and push it to the temp queue, otherwise dequeue it from target and enqueue it back to the target, process until we have worked thru all the elements, if all the elements are in the tmp queue (second queue) means the sort is done, otherwise redo the process until the sort is done .
Code as below -
/// <summary>
/// function to sort a queue using an extra queue.
/// </summary>
/// <param name="target">the target queue that contains all the unsorted elements</param>
private static void SortQueueUsingExtraQueue(Queue<int> target)
{
if (target == null || target.Count < 2) return;
var tmpQueue = new Queue<int>(); // the second Queue, this queue contains the sorted part of the target queue.
var queueLength = target.Count; // length of the target queue.
var lastInput = target.Peek(); // element at the top of the "sorted" queue.
var processedCount = 0; // currently processed item count.
bool sorted = false;
while (!sorted)
{
// if the element element is lesser than the item on the top of the sorted queue, we move it from the target queue and push it into the sorted queue.
if (lastInput >= target.Peek())
{
lastInput = target.Dequeue();
tmpQueue.Enqueue(lastInput);
}
// the poping element is bigger than the top element on the sorted queue, we put it back to the bottom of the queue and will process it later.
else
{
target.Enqueue(target.Dequeue());
}
// continue if we still have item to process.
if (++processedCount != queueLength) continue;
// once all item are processed, we check the length of the sorted queue, if the # of item equals the length of the orignal queue, means the sort is done.
if (tmpQueue.Count == queueLength)
{
sorted = true;
}
// we dump all the elements to the target queue, if the sort is done, target queue ends up with all the element sorted, if not, target queue ends with element that is parcially sorted.
// We will process on until all the elements are sorted.
while (tmpQueue.Count > 0)
{
target.Enqueue(tmpQueue.Dequeue());
lastInput = target.Peek(); // don't forget to reset lastInput.
}
processedCount = 0;
}
}
To extend the solution to two queues and both with elements to be sorted, simply dump all the elements from queue 2 to queue 1, use the second queue and the tempQueue to process elements for Queue1, once all Queue 1 elements processed, use queue1 as the temp queue to process all elements in queue 2. Until all the elements in both queues sorted.
- i059069 January 15, 2014
directly walk thru the whole BST is not ideal.
One possible solution is this -
1. you check the given target node, and see if the node has a right child, if it has the successor is the most left element in the right child tree (let me know if you can't understand this part.)
2. if the given target node doesn't have a right child, means you need to figure out the element that is just bigger than the target, because the target has no right child, it can tell that by itself, so what to do next is to utilize and walk thru the BST , keep a track of the most recent element that is bigger than the target element until we find the element.
Return Null if such element doesn't exist.
- i059069 January 24, 2014