flyingpig
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I could only come up a Time O(m+N), space O(m) solution, wish there is a better solution.
Go through the pointer array, store all nodes pointed into a hashset.
Go through the double-linked list, at each node, check prev and next of it, if(prev not included in set but next included), this node is the beginning of a group, so sum++.
return sum.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Hinted from "Source"'s recursive solution, this is my DP solution. Time complexity is O(n^(1.5)), space complexity is O(n)
int total(int n){
if(n<2) return n;
vector<int> dp(n+1, 0);
dp[1] = 1;
for(int i=2; i<=n; ++i){
int minv = INT_MAX;
for(int j=1; j<=sqrt(i); ++j){
minv = min(minv, 1+dp[i-j*j]);
}
dp[i] = minv;
}
return dp[n];
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
"initialize A array of integers in sequence from 0 to end" takes gigabytes. I guess the guys asked this questions was looking for less space solution.
- flyingpig February 06, 2015