Skip to content

/ C-Plus-Plus

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Added Sparse Table for range query #812

Open
wants to merge 10 commits into
base: master
from
Open

Added Sparse Table for range query #812

wants to merge 10 commits into from

Conversation

@arpanmukherjee
Copy link

arpanmukherjee commented Jun 1, 2020

No description provided.

@arpanmukherjee
Added Sparse Table RMQ
Loading status checks…
ad7c062
@arpanmukherjee
Added Sparse Table for range query
Loading status checks…
e53d77e
@arpanmukherjee
Added Sparse Table for range query
Loading status checks…
65855f6
@poyea
Copy link
Member

poyea commented Jun 2, 2020

Hi @arpanmukherjee, thanks for the code! Please fix the cpplint failure according to

range_queries/SparseTable.cpp:9:  Do not use namespace using-directives.  Use using-declarations instead.  [build/namespaces] [5]
Done processing range_queries/SparseTable.cpp
Total errors found: 13
range_queries/SparseTable.cpp:20:  { should almost always be at the end of the previous line  [whitespace/braces] [4]
range_queries/SparseTable.cpp:22:  Missing space before ( in for(  [whitespace/parens] [5]
range_queries/SparseTable.cpp:27:  { should almost always be at the end of the previous line  [whitespace/braces] [4]
range_queries/SparseTable.cpp:29:  Missing space before ( in for(  [whitespace/parens] [5]
range_queries/SparseTable.cpp:30:  { should almost always be at the end of the previous line  [whitespace/braces] [4]
range_queries/SparseTable.cpp:31:  Missing spaces around <<  [whitespace/operators] [3]
range_queries/SparseTable.cpp:32:  Missing space before ( in for(  [whitespace/parens] [5]
range_queries/SparseTable.cpp:33:  { should almost always be at the end of the previous line  [whitespace/braces] [4]
range_queries/SparseTable.cpp:34:  Missing space before ( in if(  [whitespace/parens] [5]
range_queries/SparseTable.cpp:43:  { should almost always be at the end of the previous line  [whitespace/braces] [4]
range_queries/SparseTable.cpp:51:  { should almost always be at the end of the previous line  [whitespace/braces] [4]
range_queries/SparseTable.cpp:56:  Missing space before ( in for(  [whitespace/parens] [5]
@arpanmukherjee
Fixed cpplint failure
Loading status checks…
23b7627
@arpanmukherjee
Fixed cpplint failure
Loading status checks…
81a3f46
@arpanmukherjee
Removed namespace using-directives
Loading status checks…
e0fb76a
@kvedala
kvedala reviewed Jun 2, 2020
View changes
range_queries/SparseTable.cpp Outdated
@@ -30,21 +29,19 @@ void buildTable(int n) {
if (curLen == 1)
table[i][j] = A[j];
else
table[i][j] = min(table[i-1][j], table[i-1][j + curLen/2]);
table[i][j] = std::min(table[i-1][j], table[i-1][j + curLen/2]);

This comment has been minimized.

Sign in to view
Copy link
@kvedala

kvedala Jun 2, 2020

Contributor

std::min and std::max require #include <algorithm>

This comment has been minimized.

Sign in to view
Copy link
@arpanmukherjee

arpanmukherjee Jun 2, 2020

Author

It is compiling without any errors/warnings. Should I still include #include<algorithm>?

This comment has been minimized.

Sign in to view
Copy link
@kvedala

kvedala Jun 2, 2020

Contributor

yes please. it may compile on some platforms but not on others. if you can confirm it compiles on linux, Mac, Win using GCC, Clang and MS Visual C++ compilers in its current format, then I am ok :)

This comment has been minimized.

Sign in to view
Copy link
@kvedala

kvedala Jun 2, 2020

Contributor

you can check by creating a pull request here which will compile on all these platforms for you and confirm

This comment has been minimized.

Sign in to view
Copy link
@arpanmukherjee

arpanmukherjee Jun 2, 2020

Author

Added and pushed final commit.
@arpanmukherjee
Renamed for cpplint
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
5af4c62
@arpanmukherjee
Removed uppercase from filename.
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
9397c12
@arpanmukherjee
Included algorithm library header file
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
79f69cf
@arpanmukherjee
Removed duplicate data structure.
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
6064c74
@poyea
Copy link
Member

poyea commented Jun 3, 2020

I think the code fails for some of my test cases. What is the expected output for the array, being queried for [3, 9]? Also, I suggest not to remove other files in this PR.

6 5 1 3 2 0 4 5 6 7 8 9
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@kvedala kvedala

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Linked issues

Successfully merging this pull request may close these issues.

None yet

3 participants
@arpanmukherjee @poyea @kvedala
You can’t perform that action at this time.