The Hercules
BAN USER- 0of 0 votes
AnswerWhat is "group by"?
- The Hercules| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Database - 0of 0 votes
AnswerDiscussion on virtual inheritance
- The Hercules| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer C - 0of 0 votes
AnswersDifferent ways to pass parameters to a function (by value, by reference, by pointer). for the following cases.
- The Hercules
6.1 Basic data type (int, char etc)
6.2 Array of integers
6.3 an object of Structure
6.4 an object of a class
Discussed about possiblities of passing constant argument values (by reference, by pointer etc) & their syntax| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Java - 0of 0 votes
AnswersTelephonic Interview 2)
- The Hercules
1) Design a Hotel reservation system which will support the following functions.
a) User will get a list of all different types of rooms.
b) User selects a room type & check the room availabilty between the specified dates.
c) User Makes Reservation.
[Discussed about "locking" the room availbilty or not in case if user wants to proceed with reservation]| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Ideas System Design - 0of 0 votes
AnswersOnsite interview 1)
- The Hercules
1) Represent a Tic Tac Toe game class.
2) Now write a function IsWinner which takes a player as input and returns whether the player has won or not.
3) Now write a funtion Play which plays the game| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer C Coding - 0of 0 votes
AnswersConsider a TCP/IP server that passively waits for client connections. Once a client connects the server reads data from the client one character at a time. If the server receives character 'Q' it sends it back to the client the number of client currently connected(as a string). If the character is 'T', the server should send back the local timee, as a string in HHMMSS format. Characters '\r' and '\n' are ignored, all other characters result in the server returning the string BADREQUEST. The server is, or should be, able to handle multiple concurrent clients
- The Hercules| Report Duplicate | Flag | PURGE
Automated Traders Desk Software Engineer / Developer Networking / Web / Internet - 0of 0 votes
AnswersOnsite Interview (coding test) --
- The Hercules
Q3) Now write a derived class Undo_Buffer that derives from Buffer. It will provide the ability to undo the last change to the buffer. It should have a member variable, last_buffer, which is a copy of the internal unsigned char array from the last change to the buffer. For example, if the buffer has "0123456" and undo_buffer[3] = 'z' is called, then the Undo_Buffer class holds the new change value of "012z456".
Undo_Buffer should provide a method undo() which will revert the buffer to the last saved buffer. There does not need to be any access to the last_buffer, except to provide the functionality of undo.| Report Duplicate | Flag | PURGE
Automated Traders Desk Software Engineer / Developer C Coding - 2of 0 votes
AnswersOnsite Interview --
- The Hercules
Directions
1) Write compiling (& working) code on linux
2) 2 hours.
3) Total questions 6. Mandatory 4 (but 3 acceptable)
Q1) Write a recursive funciton "sum" that computes the sum of all integers between 0 & n. For example, presented the number 10, it would return -15. Next, write a "main" that will drive the function by calling it for each "valid" argument in the program's argument list. If an argument is not an integer then print out an error message, wiht the double quotation marks.For example calling the program with
a.out 23 -12 foo 7
should result in output like
Sum of all integers between 0 & 23 is 276
Sum of all integers between 0 & -12 is -78
"foo" is not a number
Sum of all integers between 0 & 7 is 28| Report Duplicate | Flag | PURGE
Automated Traders Desk Software Engineer / Developer C Coding
I was asked the same question for developing a system for users to login. I said Hash the password & save the hashed value for that userid.
She asked how do you use the value when someone logs in.I said retrieve the hashed value from the database(by userid etc) & compute the hash of the entered password during login. If the hashed value matches the hased value from Database then perform a successful login.
NOTE - you do have to worry about collisions etc. But she wasn't interested to discuss about collisions. So this answer was satisfactory to my interviewer
Apply dynamic programming to compute Max length for row & columns
1) Initialize
maxRowLen[ k ] [ n-1 ] = (arr[ k ][ n -1 ] == 0 ?1:0)
maxColLen[ n-1 ] [ k ] = (arr[ n-1 ][ k ] == 0 ?1:0)
For each element in arr[k][j] (k = n-2 to 0) (j = n-2 to 0)
2) if arr[ k ] [ j ] == 1
maxRowLen[ k ] [ j ] = 0
3) else // i.e arr[ k ] [ j ] == 0
maxRowLen[ k ][ j ] = maxRowLen[k][j+1] + 1
Compute Max length for Column
4) if arr[ k ] [ j ] == 1
maxLen[ k ][ j ] = 0
5) else // i.e arr[j] == 0
maxColLen[ k ][ j ] = maxColLen[k+1][j] + 1
6) maxSqLen = 0
Now iterate either of max length row or max length col & for each (either of) maxRowLen or maxColLen ---
Lets take maxRowLen
7) lenOfSquare = Minimum( maxRowLen[k][j], maxColLen[k][j] )
8) if lenOfSquare > maxSqLen
9) Now, check if a square is formed
if( maxColLen[ k ][ j+ lenOfSquare ] == lenOfSquare &&
maxRowLen[ k + lenOfSquare ][ j ] == lenOfSquare )
{
maxSqRowStart = k;
maxSqColStart = j;
maxSqLen = lenOfSquare ;
}
Space - 2 dimension array for maxRolLen & maxColLen i.e O(2 * N square )
Time - O( 2 * N square )
1) Compute maxRowLen & maxColLen for each element of arr[n * n] +
2) Compute if square with max len is formed for each element (either of) maxRowElem or maxColLen
@ khexa
If my interpretation is not wrong, you recommended using only a Heap. Heap is definitely required here but its not the only data structure you will use. The key for maintaining Max Heap is count i.e. the frequency. But how do you index or increment the count every time you read a word from the file?
For example
Hello Bonjour Hi Hey Namaste Bonjour Bonjour Hey
If you insert these words in the Max Heap/PQ then the heap property is built based on the content of the word & not the count. So your Heap will look like this :-
Namaste
Hi Hey
Hey Hello Bonjour Bonjour
NOTE - This is not the exact output of Heap but a rough sketch of the way heap data will be organized i.e based on content of the word & not the frequency of the word
You ALSO need a complete binary tree. Apart from left & right pointers your Binary node should have 2 metadata
1) char *pWord i.e the content to the word. This will be used as the key for the binary tree insertion & search
2) int frequency
Every time you read a word from the file do these
1) Search for a Binary Node for this word.
2) If Binary Node is found increment its frequency.
3) Else create a binary node & insert at the proper place in the tree. (with frequency=1)
4) Now, try to push this binary node in a Heap of constant size 10. The key for Push or Pop operation of Heap is frequency.
Finally, you can choose to keep an array of size 10 & push or overwrite. But a heap will be faster because everytime you read word you have to push it inside the Array. Heap will be efficient because it will minimize the data movement during Heapify i.e Bottom-Up as compared to an array.
if want more optimization during Push operation for data move (“ShiftUp” for pointers implement the Heap as a double link list so that its Bottom-Up is only a changing of the links.
1) ++a means increment & use. a++ means use & increment. i.e use the same value and then increment. This means a temporary is created to hold & use the same value. While a is incremented. So, ++a is faster & it is always better practice to use ++a
2) A constructor a) with one parameter or b) which has at least one default parameter can do implicit conversions
A) MyClass1( int num );
B) MyClass1( const MyClass1 &irOther);
MyClass1 ob1 = 15; // convert 15 to an instance of MyClass1 using 1st then call copy constructor i.e 2nd one to make this call succeed.
C) MyComplexNumber( double iReal, double iImaginary = 0);
D) MyComplexNumber( MyComplexNumber );
double realval = 15;
MyComplexNumber obj2 = realval; // we do not specify any impaginary here. Compiler converts realval to an object of type MyComplexNumber using C). Then calls D) to create obj2
Its a good practice to use the keyword 'explicit' with your constructors so that such implicity conversions can be checked.
A) explicit MyClass1( int num );
C) explicit MyComplexNumber( double iReal, double iImaginary = 0);
3) String::copy works on only string types. For memcopy the underlying type is irrelevant. It is a binary copy of the data.
4) Global & static variables
5) F2() has to assume that x has been newed i.e F1() has been called. This results in dependency of F2() on F1(). The design is flawed. If F1 throws an exception, F2 may not be called & memory for x cannot be reclaimed as long as the program is running.
6) Copy by value. There is no alternative
A) i + j;
B) k = i + j;
This calls operator + (a, b). You do not want to use the value of i as the final result. i should remain as it is !!
You have to create a temporary object from i (or j) using copy constructor. Add the data member values of j to the data member of temp. Return temp.
Note- It is always a better practiceto implement non-member function operator + (a,b) in terms of class member function operator += (b) for localiziing the core logic.
by the way what you proposed to store in an array[10] is perfectly feasible solution. The only perfomance issue is moving N [10 in ur specific case] elements at max. This data movement can be very frequent since the file is huge. But if the file is any particular order i.e biased then your solution does not has performance penatly due to data movements
- The Hercules February 06, 2008Hello JJ, following is the summary of your question/requirement specs
1) You have a huge file - Means your data structure cannot keep growing. Its size should be fixed to 10 or N for generic implementation.
2) 10 or any N 'LARGEST' number - you need a 'MAX priority queue'. [Uusually min or max priorit queues are resizeable. But since the file is HUGE the priority queue cannot be resized therefore, its size is fixed to 10 or N]
3) Since the largest 10 or N numbers can come in any order. You can come across the largest number at a time when the queue is already full. In this case, you have to find the right position for insert, remove the least element & shift all the elements to its right. To summarize "unlike" the normal priority queue you have to also support a Remove function.
Since the data movement from left to right using an array will be highest. It can be O(N) movements "everytime" you find a new integer such that 'new integer found' > pq[1] > pq[2].... > pq[10]
Use a doubly linked list to impelement Max PQ. Remove operation will be O(1). Insert will be O(N) similar to Array version of Max PQ
This is the basic algo which can be refined for all boundary conditions
int FindShortestDistance( const char *ipWord1, const char* ipWord2)
{
ifstream reader; // properly initialized with file name & stream opened
char wordRead[100]; // Handle the size more carefully.
char whiteSpace = ' '; // whitespace value
bool isFirstPatternFound = FALSE;
int shortestDistance = 0;
int currentCount = 0;
// Start reading the file
while( ! reader.eof() )
{ // Get function takes a delimiter with default delimiter value as --> \n so
// change the delimiter to ' ' i.e whitespace
reader.get( wordRead, whiteSpace );
if( 0 == strcmp( ipWord1, wordRead) )
{ // 1st pattern found
if( isFirstPatternFound == FALSE )
{
isFirstPatternFound = TRUE;
}
// reset count everytime you find 1st pattern because only resetting
// gives shortest distance
currentCount = 0;
}
// check if 2nd pattern is found
else if( 0 == strcmp(pWord2, wordRead) )
{
if( isFirstPatternFound == FALSE )
{ // starting word not yet found
continue;
}
// 1st & 2nd both pattern found
if( currentCount < shortestDistance || 0 == shortestDistance )
{
shortestDistance = currentCount;
}
// 1st pattern & 2nd pattern both found at least once.
// But, 1st pattern can occurs 2nd,3rd.. nth time
// So reset for onward scanning
isFirstPatternFound = FALSE;
}
else if( TRUE == isFirstPatternFound )
{ // increment only when 1st pattern is found & 2nd pattern not found
++currentCount;
}
}
return shortestDistance;
}
I guess the interviewer meant O(n). I don't think it can be done in O(1).
Secondly, i do not understand why people want to find the most complex solution to a question. We do not need the hi-fi technicalities of hash, sorted list & merge.
This can be solved in O(n) time with only 3 variables --> one boolean & 2 int variables for maintaining count.
If you do not agree with me, read the question carefully for "large" text file & "space" complexity i.e memory. With the approach of Hash & merge of a clearly defined "large" file you are going to have a LARGE hashtable & again for merge !!i.e huge memory consumption. So, this solution does not even address the specs.
Following is the algo for O(1) i.e constant memory & O(n) computations
I totally agree with weicool's solution. This is a neat solution as per the specs of the question.
Most of the times the solution to complex problems do not have to be complex it simply requires lateral thinking.
likexx, I agree with your logic. If your file has 1000 lines & you have to print last 10 [or 100] lines then this solution uses less memory, but reads only last N lines twice. Considering the fact You never know the total number of lines in the file beforehand this code will be much slow in the following boundary condition ->
Print last 10 [or 500] lines of a file. So, if your file has exactly only 10 [or 500] lines your logic ends up reading the file TWICE !! File reading operation is expensive.
If we continue on my logic, then the lines will be read only once. It may look obvious that my solution uses more memory since your logic only keep int[] while i keep string [] or char**. But, if we analuse my logic then at ANY time it keep only string[N] or char[N][] memory. As per your logic, at step 3) you will again end up using memory for string[N] or char[N][].
But I think a lil more brainstorming can result a solution which will be a balance between both approaches.
Basically at any time you need to store data for 10 years only i.e 10 years * 365 days = 3650 blocks of memory. So the 1st level of data structure used will be an array. [No problem of sparse, collision etc]
Each index of the array will correspond to 1 particular date in the last 10 years. While inserting a record in the array convert date to a integer value. If system starts from 1st Jan 2000 & you want to add entry for 13th Dec 2007 then the index where you want to add = (365 * 7) + (7 * 31) [months with 31 days] + (4 * 30) [months with 30 days] + 28 [for Feb] + 13 [days of december] = 2933
This array is encapsulated in a class StockTickerCache. The Cache stands in between the actual files & provides in-memory retrieval of the records. Basically, all client application/code 'can' deal only with Cache. The Cache will maintain a Balanced Binary Search Tree for every date. So each index of the array will have a pointer to the root of the binary search tree.
Lets introduce a struct StockTicker. StockTicker contains the name & its price [which can ne null]. Each instance of StockTicker pointer is encapsulated inside the Binary Search Tree for that particular day.
We can 2 have approach to implement StockTickerCache.
Strategy 1 - StockTickerCache maintains a Balanced Binary Tree for 'only' those StockTicker which have a closing price. If the company does not support any functionality for StockTicker without a closing price then then why waste memory by maintaining extra nodes.
Strategy 2 - StockTickerCache maintains
1) Pointer to the root of a Balanced binary tree for 'ALL' StockTicker irrespective whether they have closing price information or not. The only concern is this approach will use more memory. It will also use more processing time for B) & C) because you have to visit more nodes. Advantage of this approach is future enhancements for StockTicker without any closing prince will be more easily accomplished.
Time to find array index is constant - O(1)
Time to find StockTicker in Balanced Binary Search Tree - O(logn)
In order iteration of Balanced Binary Search Tree - O(n)
Time complexity of
A) O(1) + O(logn)
B) O(1) + O(n)
C) O(n-1) * O(logn)
This involves converting the given date to array index. Iterate all array elements from i = given date to 0 [before you get a successful search]. For each array index i.e StockTickerCache pointer, get the root of the tree & iterate the tree. An unsuccessful search will mean the given StockTicker does not has any closing price for that day. Else if the search finds it then return the closing price information.
Finally, the most IMPORTANT point --> You can implement the solution using Strategy patterns to vary your algorithm either for "only" those StockTicker which have closing price or "ALL" stocktickers irrespective of the closing price. You can also configure your system to use either of the strategy based on some configuration file & factories. This way you have the benefit of 'relatively' better performance [strategy 1] as well as easy future enhancements [strategy 2] based on your settings/configuration.
It can be easily done by using a 1 dimensional array & complete binary search tree. So, your outermost data structure is 1 dimension array.
In the nutshell, each index of an array denotes entry for the File corresponding to that day. Now instead of creating links to the file, or directly accessing the file read the necessary details of the file in a Balanced Binary Tree. So, each index of the array will contain a pointer to the Balanced binary search tree for that particular day.
ydxr's approach is good but requires O(n) memory. If you are short on memory [interviewers usually ask the classic trade-off alternative i.e. performance/extra computation over memory]
Assuming the size of list is not maintained in the list data structure.
1) Traverse the first list & determine its size lets say szList1.
2) Traverse the 2nd list & determine its size lets say szList2.
3) Find the difference in the size of the list. difference = szList1 - szList2;
4) Once you have the difference, iterate the 1st list or 2nd list for 'difference' number of nodes [if difference < 0, iterate list2 else iterate list1].Intersection will start only after the 'difference' number of nodes. Say if difference = 3, intersection can be at 4th node,..... to Nth node.
5) Once you reach difference number of nodes, break out of the loop.
6) Now both lists have same number of elements to be iterated. In another loop iterate both lists and compare their nodes. You can get the intersection.
Running time = O(n) + O(m) + O( greaterof(n,m))
Worst case = Last element of both lists are same i.e
2O(n) + O(m) if n > m else
2O(m) + O(n) if m > n
Memory = O(1)
I can give more insight on this. Let say you have this special singleton class, StackAdapter with Push, Pop, Remove operations derived from the interface of Stack.
If we focus only on 3 stack problem, all we need to do is -
1) maintain 2 data memebers which represents the max size of 2 instances of Stack. [ maximum size of 3rd instance of stack can be computed because we know the size of Array]
2) Maintain 3 data members which represents 3 the used size of all 3 instances.
3) You already have the pointer to the block of memory [I assume the block of memory is initialized with some default value of -1 or say null etc.]
4) Basically, 1st 2nd & 3rd instances of Stack will have some predefined max length. But this maximum length is not constant. They will change based on the usage.
5) Instance 1 of Stack class memory range is 0th index of array to maxLen1. Instance 2 of stack class memory range = maxLen1 +1 to maxLen2 & 3rd instance memory range = maxLen2 + to Size of array.
6)StackAdapter has a method GetNewStack/CreateNewStack. The class contains a static data member which knows how many instances of stack has been used. If instanceCount < 3 it will return the client code a stack instance. Note - We will always give the 2nd instance [ i.e memory pointing from maxLen1 + 1 to maxLen2 ] as the last instance.
7) Client1 calls StackAdapter.GetNewStack & starts pushing the values.
8) Instance 1 of Stack starts from 0 to maxSize1 [ i.e left to right ] so on every push operation we increment the count usedLen1++. if usedLen1 == maxLen1 this is the boundary condition. So we check that memory maxLen+1 still has the default value with which it was initialized. If yes, readjust the length of stack 1 & stack 2 instances i.e we decrement the maxLen2 for instance 2 & increment maxLen1 for Stack1. [ Note - you can impelement some Strategies pattern as how much offset you want when stack size grows beyond its max size]
9) To remove any item from instance 1 of stack class, simply decrement the count usedLen-- & set the memory to some default null or -1 values.
10) Another thread or client code calls StackAdapter.GetNewStack(). Your adapter returns the 3rd instance [ & NOT the 2nd instance ] of stack. The 3rd instance of stack moves right to left. So on ever push operation usedLen3 decreases. Your boundary condition is if( usedLen3 == 0 or in other words usedLen3 = maxLen2] check array[maxLen2] still holds the default value with which it was set. If yes, this means instance 2 of stack class has not been used. Then again readjust the size of instance 2 & instance 3 as per step 8) & continue push operation.
11) The remove for instance 3 is same as remove for instance 1 except usedLen3 will be incremented.
12) Only when the client application/code calls your StackAdapter 3rd time you return the 2nd instance of stack i.e memory from maxLen1+ 1 to maxLen2. Since, at step 8) & step 10) if usedLen > maxLen we do check whether 2nd instance of stack is in use or not, we know the ingetrity of memory range for 2nd instance is good.
This is the basic rough solution good enough from the interview perspective. But its implementation has to consider a lot of boundary condition such as what if stack 2 is getting used more than stack 3 or stack 1. This means we have to decrement max length for instance 1 or instance 3 depending upon whether stack 2 is moving left to right or right to left.
So i see a lot of starategies [boundary if else condition] & we can put it in an Strategy abstraction pattern. On similar view our stack class actually has to share memory between 3 instances [ or some maxNumOfStack instances]. So we need to adapt Stack interface to provide this functionality
Most importantly, everyone here uses the memory in 3 equal parts. This is completly wrong. Perhaps instance 2 of stack class is being used in the context where application is reading all values from a file etc & pushing it in the Stack. But instance 1 of stack class can push things only when certain condition/attributes on some computation is true. i.e instance 2 is using more memory than instance 1. So we cannot partition the memory in 3 equal parts.
- The Hercules November 19, 2007If i understand Khoa's solution of using linked list correctly, it uses extra memory. When we already have an array, then each array index will be encapsulated in linked list node. Besides the node has a pointer to the next node. His solution would work when you have to design a stack class from stratch where you are not given an array, rather the stack class manages its memory internally.
An efficient solution is to adjust the length of the individual stack objects. Basically, you have a continuous block of memory & they want to see how efficiently you can use it. This block of memory i.e. the array needs be "adapted" like a Stack class. "Adapt" because usually one instance of a regular Stack class will use the entire block of memmory. but here the same block of memory has to be shared by 3 instances of your special Stack class
Basically, this
void SortZeroOnes( int *pArr, int len )
{
int i = 0;
int oneIdx = -1;
int toSwap = 0;
while( i < len )
{
if( pArr[i] == 1 )
{
if( toSwap == 0 )
{
oneIdx = i;
toSwap = 1;
}
}
else // pArr[i] == 0
{
if( toSwap == 1 )
{
int temp = pArr[ i ];
pArr[i] = pArr[oneIdx];
pArr[oneIdx] = temp;
oneIdx++;
}
}
i++;
}
for(int i = 0; i < len; i++ )
{
cout<<pArr[i]<<" ";
}
}
Wow the formatting sucks !! Trying to paste it again. lets see !!
template <class TYPE>
struct BNode
{
public:
TYPE _data;
BNode *_pLeft;
BNode *_pRight;
BNode(const TYPE &iNum):_data(iNum),_pLeft(NULL),_pRight(NULL)
{
}
BNode();
};
int GetTreeDepth()
{
if( NULL == _pRoot )
{
return 0;
}
queue< BNode<TYPE>* > queueOfNodes;
BNode<TYPE>* pCurrent = _pRoot;
queueOfNodes.push( pCurrent );
BNode<TYPE>* pNextLevel = NULL;
if( NULL != pCurrent->_pLeft )
{
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight )
{
pNextLevel = pCurrent->_pRight;
}
else
{ // both left & right child are NULL i.e only 1 node i.e
// root exists in the tree
return 0;
}
int depth = 0;
while( 0 != queueOfNodes.size() )
{
// Get the next entry from the queue
pCurrent = (BNode<TYPE>*)queueOfNodes.front();
queueOfNodes.pop();
// Check if current node from queue starts a new
// depth level of the treee
if( pNextLevel == pCurrent )
{
pNextLevel = NULL;
depth++;
}
// Insert left child node in the queue
if( NULL != pCurrent->_pLeft )
{
queueOfNodes.push( pCurrent->_pLeft );
}
// Insert right child node in the queue
if( NULL != pCurrent->_pRight )
{
queueOfNodes.push( pCurrent->_pRight );
}
// Check if next level is to be set or not.
if( NULL == pNextLevel )
{// Next level = NULL means pCurrent happens to be
// the 1st node visited at a particular depth
if( NULL != pCurrent->_pLeft )
{
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight )
{
pNextLevel = pCurrent->_pRight;
}
}
}
return depth;
}
I am not sure the logic above for checking NULL will help determine when to increment the count !! It seems weird to me.
What you need to do is maintain a pointer for the Next Lvel at any particular depth. During iteration you check whether the current node is same as Next Level, if they are then increment the depth. Here is the code sample
template <class TYPE>
struct BNode
{
public:
TYPE _data;
BNode *_pLeft;
BNode *_pRight;
BNode(const TYPE &iNum):_data(iNum),_pLeft(NULL),_pRight(NULL)
{
}
BNode();
};
int GetTreeDepth()
{
if( NULL == _pRoot )
{
return 0;
}
queue< BNode<TYPE>* > queueOfNodes;
BNode<TYPE>* pCurrent = _pRoot;
queueOfNodes.push( pCurrent );
BNode<TYPE>* pNextLevel = NULL;
if( NULL != pCurrent->_pLeft ){
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight ){
pNextLevel = pCurrent->_pRight;
}
else{ // both left & right child are NULL i.e only 1 node i.e root
// exists in the tree
return 0;
}
int depth = 0;
while( 0 != queueOfNodes.size() ){
// Get the next entry from the queue
pCurrent = (BNode<TYPE>*)queueOfNodes.front();
queueOfNodes.pop();
// Check if current node from queue starts a new depth level of the treee
if( pNextLevel == pCurrent ){
pNextLevel = NULL;
depth++;
}
// Insert left child node in the queue
if( NULL != pCurrent->_pLeft ){
queueOfNodes.push( pCurrent->_pLeft );
}
// Insert right child node in the queue
if( NULL != pCurrent->_pRight ){
queueOfNodes.push( pCurrent->_pRight );
}
// Check if next level is to be set or not.
if( NULL == pNextLevel )
{// Next level = NULL means pCurrent happens to be the 1st
// node visited at a particular depth
if( NULL != pCurrent->_pLeft ){
pNextLevel = pCurrent->_pLeft;
}
else if( NULL != pCurrent->_pRight ){
pNextLevel = pCurrent->_pRight;
}
}
}
return depth;
}
Actually i can write the rough implementation. You can do all the necessary boundary condition check for getLine etc & conversion from char [] to string etc.
PrintLastNLines( int iNumOfLines, const char *ipFullName )
{
int count = 1;
string arrLines [ iNumOfLines ];
ifstream reader( ipFullName ); // Open the file & do all necessry checks
while( !EOF )
{
char thisLine[500];
reader.getLine(thisLine) // Read line with ifstream function
if( count == iNumOfLines )
{
count = 1;
}
arrLines[ count - 1 ] = thisLine;
count++;
}
int startPrintFrom = count;
for( int printCount = 0; printCount< numOfLines; printCount++ )
{
if( printCount == startPrintFrom )
{
count = 0;
}
cout<<arrLines[ count ]; // dont use [count -1] here bcoz while
// loop above has already incremented count
count++;
}
}
A better solution is to maintain a [int] count of the number of lines read & an array with size equal to the number of lines to display. Here is the basic algorithm,
PrintLastNLine( int numOfLines )
1) Declare an array --> string arrLines[ numOfLines ];
2) int count = 1;
3) while ( !EOF ) read current line
4) check if count == numOfLines. If true, set count = 1;
5) arrLines[ count -1 ] = current line read from ifstream;
6) count++;
It is important to understand step 4). Array holds only those lines that are to be printed. But we don't know when line Nth from last is reached.
Let's say our file has 50 lines and you have to print last 20 lines. So, line 1 to line 20 has been stored in the array. But EOF is not yet reached & count = 20. So reset the count to 1 & dump the next lines in array again. When ifstream reaches line 21 to line 40,
count = 20 again &
arrLines[0-19] = entries from line 21 to 40.[Note lines 21-30 not needed but lines 31-40 reqd]
Now set count = 1 again.
start reading from line 41 & save in array from count = 1 to 10. [ at 10 EOF is reached]
arrLines[0-9] = line 41 to line 50
arrLines[10-19] = line 31 to line 40
At the end of the loop varialbe count indicates the index in the array from where you can start printing the lines.
int startPrintFrom = count;
for( int printCount = 0; printCount< numOfLines; printCount++ )
{
if( printCount == startPrintFrom )
{
count = 0;
}
cout<<arrLines[ count ]; // dont use [count -1] here bcoz while
// loop above has already incremented count
count++;
}
Going backwards while reading the file is not a good solution. You can of course usek seekg etc from C++ ifstream objects but an file operation is expensive. This approach means you read the same line twice.
- The Hercules November 06, 2007
I was under the impression that the question states find the minimum distance between words ipWord1 & ipWord2 "starting" from ipWord1.
- The Hercules May 26, 2008If however anyone of them can be the 1st word & distance has to be computed from either the same "algorithm or logic" can be extended to handle this case.
I gave the basic sketch of the logic & not a compilable, running, exception proof code. Just extend the idea to handle the cases accordingly if you end up writing this functionality for an application to be used in production