R.Kozikowski
BAN USERfree is used to dealocated objects allocated by malloc and it shouldn't be used to dealotace objects created by new. Also free doesn't call destructors.
- R.Kozikowski January 26, 2011I got the same question on my interview. First answer is that malloc is allocation method from C and new is allocation method from C++. There is no object-oriented programming in C, and therefore malloc don't know about constructors. So the basic answer is that new allocates memory and calls the constructor, where malloc only allocates memory and return pointer on the void* without any values initalized (we have to memset them to 0). I also mentioned that malloc and new use different allocation techniques so we shouldn't use malloc with delete and new with free.
- R.Kozikowski January 26, 2011It's common dynamic programming problem. It can be solved in O(n) time and O(1) memory. Let's call the cost on i-th day as c_i. You have the best solution from the previous day assuming that You have a stock (let's call it x_i) and You sold the stock (y_i). Then you have to actualize the solution:
x_{i+1} = max ( x_{i} (hold), y_{i} - c_{i} (buy));
y_{i+1} = max ( y_{i} (do nothing, I am not sure if You are allowed to do that based on problem description), x_{i} + c{i} (sell) )
I would also add here that boost::shared_ptr<T> is much better for this purpose.
- R.Kozikowski January 26, 2011I wrote easy C++ program (I have redundant code etc. because I didn't care about a style here) to show how I understand a transpose vs rotate:
#include <iostream>
#include <vector>
using namespace std;
vector<int> rotate(const vector<int>& v, int rows, int columns) {
if(rows*columns > v.size())
throw new vector<int>(v);
vector<int> solution(rows*columns);
for(int i=0; i<rows; i++)
for(int j=0; j<columns; j++)
solution[j*rows + (rows - i - 1)] = v[i*columns + j];
return solution;
}
vector<int> transpose(const vector<int>& v, int rows, int columns) {
if(rows*columns > v.size())
throw new vector<int>(v);
vector<int> solution(rows*columns);
for(int i=0; i<rows; i++)
for(int j=0; j<columns; j++)
solution[j*rows + i] = v[i*columns + j];
return solution;
}
void write(const vector<int>& v, int row, int col) {
for(int i=0; i<row; i++) {
for(int j=0; j<col; j++)
cout << v[i*col + j] << ' ';
cout << '\n';
}
cout << '\n';
}
int main() {
vector<int> v;
int row = 3;
int col = 4;
v.resize(row*col);
for(int i=0; i<row; i++)
for(int j=0; j<col; j++)
v[i*col + j] = (i*col + j);
write(v, row, col);
cout << "Rotated:\n";
vector<int> v2 = rotate(v, row, col);
write(v2, col, row);
cout << "Transposed:\n";
vector<int> v3 = transpose(v, row, col);
write(v3, col, row);
return 0;
}
Output of this program:
0 1 2 3
4 5 6 7
8 9 10 11
Rotated:
8 4 0
9 5 1
10 6 2
11 7 3
Transposed:
0 4 8
1 5 9
2 6 10
3 7 11
I agree about the idea that suffix tree is not required here. Also I think it would use too much excesive memory. I know that it uses O(n) memory, but that O(n) have an assumption that we store edge as a two indexes from the original word, so here we should store words somewhere or store edges as a string, what would result in O(n^2) memory. Anyway PATRICIA trees would be much better choice than TRIE, since it compresses edges. Tree aproach is not perfect, since they doesn't utilize the property of languages that many deal of words end with the same suffix. We can on example make additional tree for ends of a nouns/werbs, and if we are on the end of the noun we go to the noun tree.
The optimal solution would be using Directed Acyclic Word Graph (DAWG). More about it here: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph . The image on the right shows good comparision of space efficency of DAWG and TRIE.
I belive that question 3 was in other words question if the class with 1 object have automatically overloaded operator < based on this single element. Turns out it doesn't, example code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class my_class{
public:
int x;
};
bool operator<(const my_class& a, const my_class& b) {
return a.x < b.x;
}
vector<my_class> v;
int main() {
sort(v.begin(), v.end());
}
Try to compile this code without the line:
bool operator<(const my_class& a, const my_class& b);
And see how it fails.
- R.Kozikowski January 18, 2011
((x^3)*2 + (x^2)*3 + x) / 6 gives the sum of squares 1^2 + 2^2 + ... + x^2
- R.Kozikowski January 26, 2011