[algogeeks] Re: Google Interview Question: find shortest summary containing all key words
You'd better wite a program. On 11 окт, 10:42, Vaibhav Jain [EMAIL PROTECTED] wrote: Algo: 1. initialize final_result array with whole sequence and count number of keywords in no_of_keys and initialize counter array for keywords with value zero. 2. if sequence_ptr is not null then start scanning the sequence if keyword_matches() in sequence put into temp_array and update pointer to read next character and repeat it till keyword unmatches. 3. put the value of temp_array into result_array and make temp_array null. then if strlen(result_array) no_of_keys then go to step 2 with updated pointer to read remaining sequence. 4. else check each character of temp_array and if keyword_matches() in temp_array then increment counter in counter array at corresponding keyword place in counter array. 5. check counter array if all places in array contain non-zero values, then compare if strlen(result_array)strlen(final_result) array then final_result=result_array. 6. else (if some places still have zero in counter array) then make zero in each place of counter array and make result array null and go to step 2 with updated pointer to read remaining sequence. 7. else (if sequence_ptr is null) then print final result. Assume keyword_matches() is checking characters of given sequence/pattern in hash table(hash table stores all the keywords), so it is giving O(1) complexity. This will give O(N) time complexity where N is total no of characters in sequence(If no_of keywords kN). Please correct me if i have done any mistake. On 9/25/07, Sticker [EMAIL PROTECTED] wrote: Declare: this question is originally from Google. The original form is: given a document, how to find a shortest summary containing all the key words. After translated, it will be: given a sequence, how to find a shortest substring that contains all the items required. Example: a sequence abaccdefgacel and a set of key words a, c, d and e. The shortest substring contianing all of the key words is accde. Find one of such shortest substrings. In the original question, there is time complexity boundary O(N), where N is the length of the sequence. To me, this problem is rather questionable. So far my solution requires a hash table that gives no conflict and can locate a key word in O(1) time. Otherwise the time complexity will definitely be related to the number of key words. Does anyone have idea for a O(N) algorithm to solve this problem? -- Vaibhav Jain --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: NxN matrix of positive and negetive integers?
The explanation above is correct ... O(n^3) is enough. If you're able to solve the one dimensional array in O(n), then you can solve the 2D case in O(n^3). For each row-range [a..b], we'll compute the maximum contiguous subarray with the O(n) above. To achieve O(n^3), this means that for each column c, we need to have the sum of arr[a][c], arr[a+1][c], ... arr[b-1][c] handy ( i.e. in O(1) algo). But that's fine, we can precalc them using prefix-sum (O(n^2)). Look at my post in www.algorithmist.com ... search for UVa problem 108 - Maximum Sum. Good luck. On 10/12/07, Andrey [EMAIL PROTECTED] wrote: Does anyone knew more effective solution then DP? On Oct 12, 3:46 pm, Andrey [EMAIL PROTECTED] wrote: I doubt It will be O(n^3).. Dynamic programming algorithm, by size of submatrix, will give at least O(N ^ 4), won't it? -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Google Interview Question: find shortest summary containing all key words
You'd better write a program. On Oct 11, 10:42 am, Vaibhav Jain [EMAIL PROTECTED] wrote: Algo: 1. initialize final_result array with whole sequence and count number of keywords in no_of_keys and initialize counter array for keywords with value zero. 2. if sequence_ptr is not null then start scanning the sequence if keyword_matches() in sequence put into temp_array and update pointer to read next character and repeat it till keyword unmatches. 3. put the value of temp_array into result_array and make temp_array null. then if strlen(result_array) no_of_keys then go to step 2 with updated pointer to read remaining sequence. 4. else check each character of temp_array and if keyword_matches() in temp_array then increment counter in counter array at corresponding keyword place in counter array. 5. check counter array if all places in array contain non-zero values, then compare if strlen(result_array)strlen(final_result) array then final_result=result_array. 6. else (if some places still have zero in counter array) then make zero in each place of counter array and make result array null and go to step 2 with updated pointer to read remaining sequence. 7. else (if sequence_ptr is null) then print final result. Assume keyword_matches() is checking characters of given sequence/pattern in hash table(hash table stores all the keywords), so it is giving O(1) complexity. This will give O(N) time complexity where N is total no of characters in sequence(If no_of keywords kN). Please correct me if i have done any mistake. On 9/25/07, Sticker [EMAIL PROTECTED] wrote: Declare: this question is originally from Google. The original form is: given a document, how to find a shortest summary containing all the key words. After translated, it will be: given a sequence, how to find a shortest substring that contains all the items required. Example: a sequence abaccdefgacel and a set of key words a, c, d and e. The shortest substring contianing all of the key words is accde. Find one of such shortest substrings. In the original question, there is time complexity boundary O(N), where N is the length of the sequence. To me, this problem is rather questionable. So far my solution requires a hash table that gives no conflict and can locate a key word in O(1) time. Otherwise the time complexity will definitely be related to the number of key words. Does anyone have idea for a O(N) algorithm to solve this problem? -- Vaibhav Jain --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: NxN matrix of positive and negetive integers?
I doubt It will be O(n^3).. Dynamic programming algorithm, by size of submatrix, will give at least O(N ^ 4), won't it? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: NxN matrix of positive and negetive integers?
Does anyone knew more effective solution then DP? On Oct 12, 3:46 pm, Andrey [EMAIL PROTECTED] wrote: I doubt It will be O(n^3).. Dynamic programming algorithm, by size of submatrix, will give at least O(N ^ 4), won't it? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: NxN matrix of positive and negetive integers?
I've found task 108 [ http://acm.uva.es/p/v1/108.html ] but there is
nothing except task statement.
I have written a program that solves this problem (see listing below)
but It has complexity = O(N^4).
Please look at my program it's quite simple to understand and prints
debug output
(see at the bottom of this post). It also counts number of iterations
performed.
For 4x4 matrix, from task sample input, it performs 100 iterations.
It's very likely that my algorithm differs from your (that works for
O(n^3) ).
Is it required for your algorithm that matrix is square? My algorithm
works for any matrix N x M,
can it make the difference?
Listing: ---
#include string
#include vector
#include iostream
#include algorithm
#include exception
#include stdexcept
using namespace std;
class Range {
public:
int x0, y0, x1, y1;
int width () const { return y1 - y0; }
int height() const { return x1 - x0; }
explicit Range(int px0=0, int py0=0, int px1=0, int py1=0)
: x0(px0), y0(py0), x1(px1), y1(py1) {}
friend ostream operator (ostream out, const Range range) {
return out[range.x0, range.y0; range.x1,
range.y1];
}
};
/**
* Splits range on smaller pices, if possible, or returns it self.
*/
vectorRange split(const Range r) {
vectorRange result;
result.reserve(4);
if (r.width() == 1 r.height() == 1) {
result.push_back(r);
} else if (r.width() 1 r.height() == 1) {
result.push_back(Range(r.x0, r.y0, r.x0 + 1, r.y0 + r.width() -
1));
result.push_back(Range(r.x0, r.y0 + r.width() - 1, r.x0 + 1,
r.y0 +
r.width()));
} else if (r.height() 1 r.width() == 1) {
result.push_back(Range(r.x0, r.y0, r.x0 + r.height() - 1, r.y0 +
1));
result.push_back(Range(r.x0 + r.height() - 1, r.y0, r.x0 +
r.height(), r.y0 + 1));
} else {
result.push_back(Range(r.x0, r.y0, r.x0 + r.height() - 1, r.y0 +
r.width() - 1));
result.push_back(Range(r.x0 + r.height() - 1, r.y0, r.x0 +
r.height(), r.y0 + r.width() - 1));
result.push_back(Range(r.x0, r.y0 + r.width() - 1, r.x0 +
r.height()
- 1, r.y0 + r.width()));
result.push_back(Range(r.x0 + r.height() - 1, r.y0 + r.width()
- 1,
r.x0 + r.height(), r.y0 + r.width()));
}
return result;
}
template class Value_
class Matrix {
public:
int getN() const { return _n; }
int getM() const { return _m; }
vectorValue_ operator[] (int index) {
return _rows[index];
}
const vectorValue_ operator[] (int index) const {
return _rows[index];
}
Matrix subMatrix(const Range r) {
Matrix result(r.height(), r.width());
for (int i = 0; i result.getN(); i++ ) {
for (int j = 0; j result.getM(); j++ ) {
result[i][j] = _rows[r.x0 + i][r.y0 + j];
}
}
return result;
}
/*
* Create matrix with n rows and m columns
*/
explicit Matrix(int n=0, int m=0) : _n(n), _m(m), _rows(n) {
for (int i = 0; i n; i++ ) {
_rows[i] = vectorValue_(m);
}
}
/*
* Create matrix with n rows and m columns filled by value defValue
*/
Matrix(int n, int m, const Value_ defValue) : _n(n), _m(m),
_rows(n) {
for (int i = 0; i n; i++ ) {
_rows[i].reserve(m);
fill_n(back_inserter(_rows[i]), m, defValue);
}
}
friend ostream operator (ostream out, const Matrix m) {
outm.getN() m.getM()endl;
for (int i = 0; i m.getN(); i++ ) {
for (int j = 0; j m.getM(); j++ ) {
outm[i][j] ;
}
out\n;
}
return out;
}
private:
int _n, _m;
vectorvectorValue_ _rows;
};
/*
* Implements dynamic programming approach.
*/
class DPSolver {
public:
void solve(Range result, int max) {
max = numeric_limitsint::min();
for (int h = 1; h = height(); h++ ) {
for (int w = 1; w = width(); w++ ) { // Start with
width = 2
cout-debug- Checking matrices:
hxwendl;
for (int y0 = 0; y0 = width() - w; y0++ ) {
for (int x0 = 0; x0 = height() - h;
x0++ ) {
Range r(x0, y0, x0 + h, y0 + w);
vectorRange sr = split(r);
