Solution
1. In the first three lines, determine the common line.
2. If possible, determine the unique lndex and line
3. Early terminate the loop for the rest if unique line is found
// FindUniqueLine.cpp : Defines the entry point for the console application.
//
#include <string>
#include <vector>
#include <iostream>
#include <cstdlib>
#include <iterator>
using namespace std;
int FindUniqeLine(vector<string>& file, string &line)
{
if(file.size() < 3){
cout << "File lines is less than 3" << endl;
return -1;
}
string firstLine[3];
string commonLine;
for(int i = 0; i < 3; i++){
firstLine[i] = file.at(i);
}
commonLine = firstLine[0];
if(commonLine != firstLine[1]){
if(commonLine == firstLine[2]){
line = firstLine[1];
return 1;
}
else{
line = firstLine[0];
return 0;
}
}
if(firstLine[2] != commonLine){
line = firstLine[2];
return 2;
}
for(int i = 3; i < file.size(); ++i){
if(file.at(i) != commonLine){
line = file.at(i);
return i;
}
}
}
void GeneratePseudoFile(vector<string>& file, int fileSize)
{
string uniqueLine = "unique";
string commonLine = "common";
for(int i = 0; i < fileSize; ++i){
file.push_back(commonLine);
}
int uniqueLineNum = rand() % fileSize;
file.at(uniqueLineNum) = uniqueLine;
}
void DisplayPseudoFile(vector<string> &file)
{
copy(file.begin(), file.end(), ostream_iterator<string>(cout, " "));
cout << endl;
}
int main(int argc, char* argv[])
{
int fileSize = 15;
srand(1);
for(int i = 0; i < fileSize; ++i)
{
cout.width(8);
cout << left << i;
}
cout << endl;
for(int i = 0; i < 20; ++i)
{
vector<string> pseudoFile;
string line;
GeneratePseudoFile(pseudoFile, fileSize);
DisplayPseudoFile(pseudoFile);
int index = FindUniqeLine(pseudoFile, line);
if(index != -1){
cout << "The unique line is at " << index << " " << line << endl;
}
cout << endl << endl;
}
return 0;
}
Output
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
common common common common common common common common common common common unique common common common
The unique line is at 11 unique
common common unique common common common common common common common common common common common common
The unique line is at 2 unique
common common common common unique common common common common common common common common common common
The unique line is at 4 unique
common common common common common common common common common common unique common common common common
The unique line is at 10 unique
common common common common common common common common common common common common common common unique
The unique line is at 14 unique
common common common common unique common common common common common common common common common common
The unique line is at 4 unique
common common common unique common common common common common common common common common common common
The unique line is at 3 unique
common common common unique common common common common common common common common common common common
The unique line is at 3 unique
common common common common common common common unique common common common common common common common
The unique line is at 7 unique
common common common common common common common common common common common common common common unique
The unique line is at 14 unique
common common common common common unique common common common common common common common common common
The unique line is at 5 unique
common common common common common unique common common common common common common common common common
The unique line is at 5 unique
common unique common common common common common common common common common common common common common
The unique line is at 1 unique
common common common common common common common common common common common common unique common common
The unique line is at 12 unique
common unique common common common common common common common common common common common common common
The unique line is at 1 unique
common common common common common common common common common common common unique common common common
The unique line is at 11 unique
common common common common common common common common common common unique common common common common
The unique line is at 10 unique
common common unique common common common common common common common common common common common common
The unique line is at 2 unique
common common common common common common common common common common common common unique common common
The unique line is at 12 unique
common common common common common common unique common common common common common common common common
The unique line is at 6 unique
Press any key to continue . . .
Problem
Given a file of n lines, where n-1 lines are identical and 1 line is different. Find the unique line in not more than one scan of the file (Amzon)