https://leetcode.com/discuss/interview-question/5846629/SquarePoint-OA-Desk-Quant/
Any ideas how to solve this problem ? some of my observations: (i) all k's are independent to each other (ii) looking for corners ?? Thanks in advance
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
https://leetcode.com/discuss/interview-question/5846629/SquarePoint-OA-Desk-Quant/
Any ideas how to solve this problem ? some of my observations: (i) all k's are independent to each other (ii) looking for corners ?? Thanks in advance
Given a undirected graph(Total No of Nodes is 1e5) .each node has its beauty .each edge has its own time travel cost .U have some finite time say m(<=100).U are at root node of graph.U have to travel those nodes and return to root .find the maximum beauty that u can collect. Idea is by knapsack .But I am facing difficulty in calculating dp states.Please confirm if it is Np-hard problem (As i correctly remember this was asked in coding test )
Thanks
Given a sequence of integers ,find a subsequence of largest length such that in the subsequence adjacent elements are not equal at most k times. n<=1e3,k<=n<=1e3 .. Any Hints or ideas?
upd: Thank You everyone. Final solution:
suppose u are at index i.say p denotes index of prev elements.say given array is a ; dp[x][y]=max length when u have explored only till x index and atmost y non equla adjacent pairs.
brute force dp(O(n3)):- for(int p=0;p<i;p++) { for(int j=0;j<k;j++) {int a=-1,b=-1; if(a[i]==a[p]) a=dp[p][j]+1; else if(j>=1) b=dp[p][j-1]+1;
dp[i][j]=max{dp[i][j],a,b} }
}
Very easy to optimise: we want just max out of dp[0 ....... i-1][j] and max out of dp[0...... i-1][j-1] using map[value][j].I have tried to be accurate .Still U find some thing to be correct pls inform.
Name |
---|