Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
Store N lines in a vector. When N lines have been read, start adding to the beginning again and increment a counter by 1 % size of the array for each element read.
readNLines() {
int counter = 0;
while(file NOT empty) {
if(vector.size() < n)
vector.push_back(file.line)
else {
vector[(counter+1)%n] = file.line
counter = (counter+1)%n
}
}
for(int i = 1; (counter+i)%n != counter; ++i) {
output vector[i-1]
}
}
#include <iostream>
#include <queue>
#include <fstream>
using namespace std;
void printLastNLines(const std::string& fname, int n);
int main()
{
std::string fname = "myfile.txt";
int n=10;
printLastNLines(fname, n);
return 0;
}
void printLastNLines(const std::string& fname, int n)
{
ifstream infile(fname.c_str());
if (!infile.is_open())
{
cout<<"File opening error."<<endl;
return;
}
std::queue<std::string> lines;
std::string line;
while (std::getline(infile, line))
{
if (lines.size() >= n)
{
lines.pop();
}
lines.push(line);
}
infile.close();
while(!lines.empty())
{
cout<<"line = "<<lines.front()<<endl;
lines.pop();
}
}
Go through all the lines one by one and put each line in a node of a single linked list.
Then, take two pointers, one starting at head, and other starting at a distance of n from head
At the end of one traversal of the linked list, you have the first pointer at a distance of n from the end and second pointer at the end.
Just print the lines
Use fseek to find the size of file and then read backwards from the end until n line breaks are read and then print the result.
- Anand Barnwal June 08, 2015Another solution can be like this:
Take a buffer for n lines and keep updating the buffer while reading from the files. So that at last the buffer contains the last n lines.