|
Given a very big file of words, a word in each line, sort the words....
Microsoft Interview Questions and Answers
(Continued from previous question...)
65. Given a very big file of words, a word in each line, sort the words....
Question:
Given a very big file of words, a word in each line, sort the words
maybe an answer1:
One example of external sorting is the external merge sort algorithm, which sorts chunks that each fit in RAM, then merges the sorted chunks together. For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:
1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
2. Write the sorted data to disk.
3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
4. Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
5. Perform a 9-way merge and store the result in the output buffer. If the output buffer is full, write it to the final sorted file, and empty it. If any of the 9 input buffers gets empty, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available.
maybe an answer2:
int count=0;
BNode sMax;
public BNode secondMax()
{
secondMax(root);
return sMax;
}
private void secondMax(BNode root)
{
if(root == null)
return;
else
{
secondMax(root.right);
count++;
if(count==2)
{
sMax = root;
return;
}
secondMax(root.left);
}
}
to use,
1. place code into your BinaryTree class.
2. in the main() method, call the class by calling secondMax().
i.e. BNode node = secondMax();
maybe an answer2:
int secondMaxInBST(node* root)
{
int max=0, secondMax=0;
getSecondMaxInBST(root,max,secondMax);
return secondMax;
}
void getSecondMaxInBST(node* root, int& max, int& secondMax)
{
if(root)
{
getSecondMaxInBST(root->left, max, secondMax);
secondMax=max;
max=root->data;
getSecondMaxInBST(root->right, max, secondMax);
}
}
(Continued on next question...)
Other Interview Questions
| 