Grr1967
BAN USER- 1of 1 vote
AnswersGiven a seria of points (Xi, Yi), find the line containing the highest number of points from the list.
- Grr1967
Per my question he mentioned that I can assume that there is a given function that receives two points and returns the a and b of the line euqation (aX+b)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures
Previous answer is O(n^2). This one is O(n*logn), assuming that find a number in a set takes logN.
void findPair(list<int> aList, int sum)
{
set<int> aSet;
for each (auto item in aList)
{
if (aSet.find(sum - item) != aSet.end())
{
cout << item << " " << (sum - item) << endl;
}
aSet.insert(item);
}
}
If the dictionary contains many words and it is extenssively searched, a tria based solution may be the most efficient solution.
The search function should get a tria node and a set of possible letters ("act"). It should check if there is a sub node for "a", "c" and "t". Suppose we found a sub node for "c", then the sub node should be searched for the ramaining letters "at".
The efficiency of such implementation depends only on the number of letters and does not depend on the number of words in the dictionary.
Here is a sample main:
TriaNode tree;
tree.addWord("cat");
tree.addWord("act");
tree.addWord("ac");
tree.addWord("stop");
tree.addWord("cac");
tree.findScribble((string)"act", (string)"");
And the implementation:
#define NUM_LETTERS 256
class TriaNode
{
public:
TriaNode();
void addWord(string word);
void findScribble(string possibleLetters, string wordSoFar);
protected:
// a pointer to the sub node of each letter
TriaNode *m_pLet[NUM_LETTERS];
// indication if this node terminates an existing word in the dictionary
bool m_isTerminating;
};
void TriaNode::findScribble(string possibleLetters, string wordSoFar)
{
if (m_isTerminating)
{
cout << wordSoFar << endl;
return;
}
for (size_t i=0; i<possibleLetters.size(); i++)
{
char curLetter = possibleLetters[i];
if (m_pLet[curLetter])
{
string remainingLetters = "";
if (i > 0)
remainingLetters = letters.substr(0, i);
if (i < letters.size()-1)
remainingLetters += letters.substr(i+1);
m_pLet[curLetter]->findScribble(remainingLetters, wordSoFar + (char)curLetter);
}
}
}
O(logn) solution. Returns -1 in case original vector is empty or if no number is missing
int find_missing(vector<int> &vec, int from, int size)
{
if (size == 0)
return -1;
if (size == 1)
return (vec[from] == from + vec[0] ? -1 : from + vec[0]);
int half1_size = size / 2;
int half1_start = from;
int half1_end = from + half1_size - 1;
int half2_size = size - half1_size;
int half2_start = half1_end + 1;
if (vec[half1_start] == half1_start + vec[0]
&&
vec[half1_end] == half1_end + vec[0])
return find_missing(vec, half2_start, half2_size);
else
return find_missing(vec, half1_start, half1_size);
}
- Grr1967 December 10, 2012If possible to allocate another array.
Initialize the additional array (call it B) with zeros.
Traverse the original array A, element by element, with index i=1..N
if B[ A[i] ] != 0
found duplicate number
else
B[A[i]] = 1
In-place algorithm
for (i=1..N)
{
idx = abs(A[i])
if (A[idx] < 0)
the duplicate number is idx
else
A[idx] *= -1
}
Example:
A={5,4,2,3,2}
i=1, a[5] = -2
i=2, a[4] = -3
i=3, a[2] = -4
i=4, a[3] = -2
at this stage array looks like this:
A= {5,-4,-2,-3, 2}
Now i=5
idx = abs(A[5]) = 2
Checking if a[idx] is negative => A[2] is indeed negative, 2 is the duplicate number.
I believe that if the array is already sorted, finding the first missing number should be in O(n) and not in O(nlogn)
Algorithm would be
nextExpected = array[0]
for (i=1; i<array.size(); i++)
{
nextExpected++;
if (array[i] != nextExpected)
First missing number is the value of nextExpected
}
This approach involves one pass on the array, i.e. O(n).
Is there something I'm missing in the understanding of the question?
My suggestion was to create a map with key pair<a, b> and value - number of points contained in line aX+b.
Then traverse each pair of points (Xi, Yi) (Xj Yj), send to the given function to receive a, b of the line connecting those two points
And update the map by adding 1 to the key <a,b> (creating it with value of 1 if not yet in the map).
In addition keeping aside the <a, b> for which the number of points is the highest.
Order of this solution is O(N^2)
I was wondering if there is a solution with better performance.
C++ solution. This one also uses a stack, similar to previous answers
I omitted some code which is not relevant to the question itself, as well as some "friend" commands to make it more readable.
NestedNode contains a value and two pointers: to the nested element and to the next element.
NestedList is a simple list containing head and tail pointers:
Here is the iterator.
And a sample "main"
- Grr1967 January 14, 2014