Kishore
BAN USERYes, start and end are indexes in the array. I think i know why you got confused. I made a mistake while calculating range. Instead of using array[start], i used start. Here is the fixed version.
bool FoundInArray(array, start, end, x)
{
bool found = false;
if(end == start)
if(array[start] == x)
return true;
int lowrange = array[start] - (end-start);
int uprange = array[start] + (end-start);
if(lowrange <= x && uprange >= x)
{
//Divide into two
found = FoundInArray(array, start, (end-start)/2, x);
if(!found)
found = FoundInArray(array, (end-start)/2, end, x);
}
else
return false;
return found;
}
I think everyone knows that brute force gives O(n) solution where we look at all numbers.
So to do better we have to divide and conquer.
Since every consecutive number is +/- 1, if there are n numbers, and start number is s, then range of values would be in (s+n, s-n).
So given a number x, we can divide the array into two halves and if our target number x falls within the range, then subdivide the array and repeat the process. If it is not in range, simply ignore that part of array.
bool FoundInArray(array, start, end, x)
{
bool found = false;
if(end == start)
if(array[start] == x)
return true;
int lowrange = start - (end-start);
int uprange = start + (end-start);
if(lowrange <= x && uprange >= x)
{
//Divide into two
found = FoundInArray(array, start, (end-start)/2, x);
if(!found)
found = FoundInArray(array, (end-start)/2, end, x);
}
else
return false;
return found;
}
Henry, I guess you are checking to see if both the left and right subtrees are BST to determine if root is BST. But I guess you can have case where LEFT child is BST and right child is BST but they cannot be part of BST because MAX of left subtree could be more than RIGHT subtree.
E.g.
[32]
[30] [35]
[22] [38]
As you can see 30 as a tree is BST, 35 is another BST and 32 as a root is between 30 and 35. However the above is not BST as there is 38 that is greater than 35.
I guess we might have to add a condition that MAX of left BST child should be less than MIN of right BST child.
Thoughts?
Since we know we will have two children or none, can we do this recursively
Node ConstructTree(ref string s)
{
Node node = null;
if(s != null && s.length > 0)
{
char curNodeChar = s[0];
s = s.substr(1, s.length);
if(curNodeChar == 'L')
{
node = new Node('L');
s = subStr;
}
else
{
node = new Node('N');
node->left = ConstructTree(s);
node->right = ConstructTree(s);
}
}
return node;
}
Looks like the line did not wrap. So copying again.
1. if current letter is b or d, change to a or c respectively and break (nothing else to do).
2. If current letter is a or c change to b or d respectively and
instead of breaking you need scan the next character to your left. Go to (1) for the next left character.
Start from the right most position and move towards left doing this:
1. if current letter is b or d, change to a or c respectively and break (nothing else to do).
2. If current letter is a or c change to b or d respectively and instead of breaking you need scan the next character to your left. Go to (1) for the next left character.
E.g. if your current sequence is cdca, then start from right: change a to b and go to next left. change c to d and move left, change d to c and break (as per point 1). So your sequence is ccdb
Idea is that when you zoom, your first character keeps rotating between a and b, once done it starts repeating your next character to left (aa ab ba bb) so on. So traverse back to get your left sequence for a given sequence.
With extra space we can do this in O(n).
First do a pass and get min/max.
Create an array of bits with length equal to (max-min).
Go through the array again, now setting the bit to 1 for every number u encounter. So if you encounter 5 you will set the bitarray[5]=1
To get the kth largest number, assign tmp=0
Start from the end of the array, everytime you hit a 1 do tmp++. When tmp==k, you have your result.
I know that is true for 2 numbers. But not sure if that is right for array at same time.
For e.g. take numbers: 2,4,6 : LCM is 12 and GCD is 2.
Ofcourse, even with your solution, you have to give answer to find GCD.
I think for this, we first sort the given numbers ascending.
Idea is to divide the whole series by 2 or 3 iteratively till we convert the first number into a prime number.
Ofcourse when we divide, if a number is not divisible by 2, then leave as it is and proceed to next number which is divisible by 2(with remainder 0). Remember number of 2's and 3's we used to divide. Example below:
So if input is 10,9,15.
Sort it 9,10,15
Divide by 2: 9,5,15 (Only 10 was divisible)
No more evens, so done with 2.
Divide by 3: 3,5,5
Divide by 3: 1,5,5
First number is prime (cannot be divided by 2 or 3). So stop. LCM is 2 * 3 * 3 * 5 * 5 = 450
This can be done in O(n). Just simply go through each element. Maintain two indexes. One for next positive and another one for next negative number.
Go through the array and any time we need a different sign number, get it from the indexes and swap. Trick is to make sure that the pointers always start from the index we are scanning. Pos and Neg index go linearly and so in worst case it is O(n) [for scan] + O(n) [for pos index scan] + O(n) [for neg index scan] ~ O(n)
int negPos=1, posPos = 1, curVal = 0;
bool found = true;
for(int index=0; index < count ; index++)
{
int swappos = 0;
if(index%2 == 0) //We need a negative number
{
if(arr[index] > 0) //This is positive number. Get a negative and swap.
{
if(negPos < index)
negPos = index+1;
while(arr[negPos] < 0)
{
negPos++;
if(negPos > count)
found = false;
else
swappos = negPos;
}
}
}
else //Need a positive number here.
{
if(arr[index] > 0) //This is positive number. Get a negative and swap.
{
if(posPos < index)
posPos = index+1;
while(arr[posPos] < 0)
{
posPos++;
if(posPos > count)
found = false;
else
swappos = negPos;
}
}
}
if(found == false)
break;
swapvalues(index, swappos);
}
Hi Tulley,
As per the question, new word is made out of two words always.
The idea behind the splitting of words is that you will always find a full word in one of the half, if you split the string into two halves.
I was assuming that the dictionary given is a dictionary where i can search in O(1). If it is not, i can still add all dictionary words in a Hashtable or Dictionary.
@Plymouth,
At the 6th try, you actually got news,paper and you would stop there. Why were you trying the other cases?
Also a dictionary lookup is O(1), so worst case is O(n) and not O(n^2).
Also the split is not WIERD. You just didn't get it. The question says that the word given is a combination of two words. So the logic is that if you divide into two halves, you are guaranteed that a full word will be in one of the two halves.
@Guess Who: If i understood your nomenclature you are denoting Bi at 0,1 nodes as (1,6) and Ci which is on edge between 0 & 1 and there could be only one value, which one is it, 2 OR 3?
All the condition means is that if you accumulated enough from all previous nodes that is greater than cost to travel an edge, then you can make a trip and this is true for all nodes you already travelled.
One more initialization i forgot is:
//Check if the arr[i] is greater than maxValTillNow and if maxCount < maxCountTillNow.
//If so we can actually resume our previous sequence
if((maxCountTillNow > maxCount) && (arr[i] > maxValTillNow))
{
//we can start resuming our prev sequence. Just note which indexes to add to final array.
indexesTillNow.Add(i);
indexes.clear();
maxCountTillNow ++;
maxCount = maxCountTillNow;
maxValue = arr[i];
}
I think this can be done in O(n). (Similar to max sub array in given array but with twist)
maxCountTillNow = maxCount = 0;
maxValTillNow = maxVal = 0;
maxVal = maxValTillNow = curVal = arr[i];
maxCountTillNow = maxCount = 1;
List<int> indexes = new List<int>(), indexesTillNow = new List<>();
indexes.Add(0); //Add the first one.
for(int i=1; i< n; i++)
{
if(arr[i] > curVal)
{
maxVal = arr[i];
maxCount++;
indexes.Add(i);
//Check if the arr[i] is greater than maxValTillNow and if maxCount < maxCountTillNow.
//If so we can actually resume our previous sequence
if((maxCountTillNow > maxCount) && (arr[i] > maxValTillNow))
{
//we can start resuming our prev sequence. Just note which indexes to add to final array.
indexesTillNow.Add(i);
indexes.clear();
}
}
else
{
//Break in sequence
//Save maxCount if greater than maxCountTillNow
if(maxCountTillNow < maxCount)
{
maxCountTillNow = maxCount;
maxValTillNow = maxVal;
indexesTillNow = indexes;
}
maxVal = curVal;
maxCount = 1;
}
}
Review and let me know if you see issue.
- Kishore February 25, 2011Similar to scheduler algorithms.
1. First make sure you don't have a cycle, if not you will never complete.
2. Create a graph, with each node denoting how many projects its depending on and dependent-count?
3. For all nodes, with 0 dependent-count, build them in parallel.
4. Once done, update the dependent projects and remove their dependency. So dependent-count will be decreased.
5. Repeat step 3 until there are no more projects to be built.
Actually this is simplified version of 'Exon Chaining algorithm'.
In first pass : Create nodes for all the times (start and end time separately) and add it to a hash such that given a time, we can retrieve all the nodes associated.
Also get the smallest and largest times. THis can be done in O(n).
In second pass:
Go through all the times (we can just go through intervals if this is calendar appt). For each interval, get the node (if available) at that time.
If this is start node, simply add it to a stack (stack of all open nodes)
else
If this is close node, then go through the stack of all open nodes till you hit the open node for the current close node. Mark all these node's conflict = true. Remove current node with closed node and retain the other open nodes in the stack (as they might have conflict with other nodes).
This is a line sweep algorithm.
@blueskin:
I did not write the code to execute and give you an answer.
You can do it yourself as all u need is a 10 line quicksort program.
If you find an error in my logic, you can dispute it by giving an example. To dispute a logic you just need 2-3 input numbers.
Please don't get me wrong as i don't want to take the pain of writing code.
I think by brute force you can do this in O(n) where you go find the first word by adding character by character and if found check if remaining is another valid word.
I think we can do better because given a word, you can cut it into halves. Use that divide-position and see if that gives you two known words.
If you don't then recursively, go through both the chunks and divide them equally again to see if that gives you two known words. Remember that when you divide at a position, you will always analyze the left and right of the 'FULL' string at that position.
Logic is similar to quicksort. (divide and conquer)
Best case is lg(n) but worst cast when there is no match will be O(n).
In our example "newspaper", it goes this way:
1st cut:
newsp | aper (position at 9/2 = 5, if i take 4 i would get answer in first cut ;))
STRINGS at this divide-position (newsp, aper)Found = false; Analyze 'newsp' and 'aper' separately.
Analyze newsp
2nd cut:
new | sp (remember even if the word newsp is cut, we have to take the FULL word)
STRINGS at this divide-position (new, spaper), Found = false;
Analyze new and sp
Analyze sp:
s | p
STRINGS at this divide-position(news and paper), Found = true;
Hi,
I posted the answer below. I guess it works for all cases and is simple. Can you check and let me know if you see issues.
I am copying it again here:
++++++++++++++++++++++++++++++++++++++++
quick sort the input BUT
while comparing two inputs A and B
instead of doing the regular A > B, DO THIS
if(ToInt('AB') > ToInt('BA')) return 1
Example:
The idea is why would you chose '9' over '94'. All I have to check is whether '994' is greater than '949'. I hope that is clear. Once you sort them by this fashion, you have the sorted list. Just concatenate to get the answer.
+++++++++++++++++++++++++++++++++++++++
else -1;
Ignore earlier comment. Misread question.
- Kishore April 03, 2011