Tulley
BAN USERHi Kishore,
Suppose we got k words in step 2. The time complexity is k*O(m) = O(m), where m is the length of the given word.
About your post:
I didn't understand it. You have divided a given word in two parts and got 2 words word1 and word2.
Now where do u search these words??? Obviously u'll search word1 and word2 in given dictionary. How'll u perform this search?? What'll be the complexity of this search?
I think trie is the best. But not in its original form. Rather we can use different variation which is memory efficient. e.g.
1. Burts Trie (goanna. cs. rmit. edu. au /~jz /fulltext /acmtois02. pdf)
2. Directed acyclic word graph (en.wikipedia.org /wiki / Acyclic_deterministic_finite_automaton)
How to check??
1. Pre-process the dictionary in to Burst Trie.
2. Start looking for a given word in Burst Trie. If you encounter a leaf or word completion delimiter at any node, you note down that word.
3. For all word obtained in 2, start a new search with remaining letters in the given word. If match found then print these two words.
1. Sort in lexicographically decreasing . Using radix sort base 10. With constraint if number is having only one digit then if second digit of first element of corresponding sorted list is less than the current number then append that number at first position and after that this number of this array wont take part in sorting.
2. Now concatenate all starting from 9.
It can be represented by an acyclic graph where nodes are project and edges are the dependencies between them. and visiting a node means building that project.
e.g. if project P1 depends upon the P2 P3 P4 then there will be an edge from P1->P2, P1->P3, P1->P4.
1. After constructing the graph chose a node having maximum out-degree as source.
2. Start a DFS from this source and note down the out-visit time of that node.
3. After DFS finishes we have the answer. We'll build the projects as per their out-visit time obtained in 2.
1. Sort numbers on each machine.
2. Make a mean heap of N elements by taking 1st element from each machine along with the information to which machine number belongs.
3. Now remove the minimum element (top of heap), and add the number from the same machine as removed element. Again min heapify.
4. Repeat 3 for (N*One million)/2 + 1 times. Min element of the heap is required median.
Total complexity.
Let M = 1 Million.
1. Sorting M elements on N machines. N*Mlog(M).
2. For step 2,3,4 ((N*M)/2 + 1)log (N).
3. So Time complexity is O(N*Mlog(M))
1. Do external sort using key as first node_id of each entry.
2. Search for a given node_id in the file for which sub graph needs to be made.
3. node_id.level = 0. Enque node_id.
4. Repeat 5-8 if Queue is not empty else end.
5. node_id = Dequeue()
6. Read all the entries for second node_id corresponding to node_id (dequeued).
7. For each entries
node_id_xx.level = node_id.level + 1
Enque node_id_xx and at the same time delete it from file (so that if cycle exist we wont enque again).
8. Go to 5.
I think in this particular case we can get a unique tree, but I m not sure.
1. root=NULL;
call MakeTree (&root, root, str, 0)
node* MakeTree (node** root, node* tempRoot, char* str, int* index)
{
if (str[*index])
{
tempRoot = makeNewNode ();/*some function which creates new
node and initialises node to 0*/
if (str [*index] == 'N')
{
if (*index == 0)
{
*root = tempRoot;
}
tempRoot->left = MakeTree (root, tempRoot->left, str, &((*index) ++));
tempRoot->right = MakeTree (root, tempRoot->right, str, &((*index) ++));
}
else
{
return tempRoot;
}
}
}
int* ArrayColSum (int*pAray, int numRow, int size)
{
int numOfCol = size/numRow;
int* pColSum = (int*)malloc (numOfCol * sizeof (int));
int i = 0;
int j = 0;
int count = 0;
memset (pColSum, 0x00, numOfCol);
while (j < numOfCol)
{
while (i < size)
{
pColSum [j] += pAray [i];
i = i + numOfCol;
}
j++;
i = j;
}
return pColSum;
}
complexity = (size/numOfCol)*numOfCol = size
O(size)
Find the min and find the max then min-max is -ve and it would be the minimum difference. Does the question say "minimum positive difference" or phrase it another way, "the distance between two numbers should be minimum when plotted on number line"??
If it is minimum positive difference then I don't think it can be done in O(n). Please correct me if I am wrong.
<pre lang="c" line="1" title="CodeMonkey39225" class="run-this">#include <stdio.h>
void strCompress (char* pInputStr)
{
int i=0, k=1;
int count = 0;
char charCh = pInputStr [i];
while (pInputStr [i] != '\0')
{
if (charCh == pInputStr [i])
{
count ++;
}
else
{
pInputStr [k-1] = charCh;
charCh = pInputStr [i];
pInputStr [k] = count + '0';
k = k + 2;
count = 1;
}
i ++;
}
pInputStr [k-1] = charCh;
charCh = pInputStr [i];
pInputStr [k] = count + '0';
pInputStr [k +1] = '\0';
}
int main ()
{
char str [100];
memset (str, 0x00, 100);
gets (str);
printf ("Before: %s\n", str);
strCompress (str);
printf ("After: %s\n", str);
return 0;
}
</pre>
Use autometa. N =Input String Length, Time O(N), Space O(1)
/*Assuming that input pointers are valid*/
int patternMatch (char* pInputStr, char* pPattern)
{
int inputLen = strlen (pInputStr);
int patternLen = strlen (pPattern);
int indexInPattern = patternLen - 1;
int indexInInput = inputLen - 1;
int returnIndex = -1;
while (indexInPattern >= 0)
{
if (pInputStr [indexInInput] == pPattern [indexInPattern])
{
indexInPattern --;
}
else
{
indexInPattern = patternLen - 1;
}
if (indexInPattern == -1)
{
returnIndex = indexInInput;
break;
}
indexInInput --;
}
return returnIndex;
}
Use autometa. N =Input String Length, Time O(N), Space O(1)
/*Assuming that input pointers are valid*/
int patternMatch (char* pInputStr, char* pPattern)
{
int inputLen = strlen (pInputStr);
int patternLen = strlen (pPattern);
int indexInPattern = patternLen - 1;
int indexInInput = inputLen - 1;
int returnIndex = -1;
while (indexInPattern >= 0)
{
if (pInputStr [indexInInput] == pPattern [indexInPattern])
{
indexInPattern --;
}
else
{
indexInPattern = patternLen - 1;
}
if (indexInPattern == -1)
{
returnIndex = indexInInput;
break;
}
indexInInput --;
}
return returnIndex;
}
1. Matrix is A[M][N], each row and column is sorted in ascending order.
2. For i=0 to M-1
---->if (i < N)
------> if (A[i][i] < Key)i++;
3. i--;
4. Do binary search in A[0][i] and A[i][0]
5. Do binary search in A[0][i+1] and A[i+1][0]
Time Complexity O(M)+O(log(M))+O(log(N)) == O(M)
At first I thought its an infinite loop. But when I ran this I came to know that this prog will stop. These are the last two values of F1 and F2.
- Tulley February 19, 2011F1=16777216.000000, F2=16777215.000000
F1=16777216.000000, F2=16777216.000000
Can anybody explain y F1 didn't increase after 16777216.000000 ?