C++ Coding Practice #1
Today's coding practice was motivated by a C++ interview challenge question on toptal.com involving arrays:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Implement a void function F that takes pointers to two arrays of integers (A and B) and a size N as parameters. It then populates B where B[i] is the product of all A[j] where j != i. | |
| For example: If A = {2, 1, 5, 9}, then B would be {45, 90, 18, 10}. |
The Code
Here's the implementation I whipped out in under 5 minutes:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| void F(int* A, int* B, int N) { | |
| // B[i] = product of... | |
| for (int i=0; i<N; ++i) { | |
| int product = 1; | |
| // ...all A[j], j!= i | |
| for (int j=0; j<N; ++j) { | |
| if (j == i) continue; | |
| else { | |
| product *= A[j]; | |
| } | |
| } | |
| B[i] = product; | |
| } | |
| } | |
| int main() { | |
| const unsigned int N = 4; | |
| int A[N] = {2, 1, 5, 9}; | |
| int* B = new int[N]; | |
| F(A, B, N); | |
| // Output the results of array B | |
| for (int i=0; i<N; ++i) { | |
| std::cout << "B[" << i << "]=" << B[i] << std::endl; | |
| } | |
| return 0; | |
| } |
You can compile and run this code with the following commandline:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| $ g++ test.cpp && ./a.out | |
| B[0]=45 | |
| B[1]=90 | |
| B[2]=18 | |
| B[3]=10 |
Dev Notes
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //-------------------------------------------------------------------------- | |
| // Runtime | |
| //-------------------------------------------------------------------------- | |
| // My quick implementation of the F() function runs in O(N^2) (i.e. quadratic) | |
| // time because it uses a double nested loop: | |
| void F(int* A, int* B, int N) | |
| for (int i=0; i<N; ++i) | |
| for (int j=0; j<N; ++j) | |
| // To achieve O(N) (i.e. linear) run time, we could use two single loops | |
| // in serial: | |
| // | |
| // Loop #1: Iterate n=0; n < i; ++n | |
| // Loop #2: Iterate n=i; i < N; ++n | |
| // | |
| // In other words, iterate above and below i. | |
| //-------------------------------------------------------------------------- | |
| // Type choice | |
| //-------------------------------------------------------------------------- | |
| // I used an unsigned int just to convey the intent of N, i.e. always a positive | |
| // number. However, it's a const so this doens't really matter. Just a spur of | |
| // the moment decision. | |
| const unsigned int N = 4; |
