-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathquestions
78 lines (61 loc) · 3.84 KB
/
questions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Search in Rotated Sorted Array
Key: one half of the array (either the left or the right) will always be sorted. If the target value lies within its start-end range, then search only in that half.
Else, search in the other half.
--------------------------------------------------------------------------------------------------------------------------------
//string number addition
handle same size cases
handle different size cases
do not forget to insert carry left over at the end
--------------------------------------------------------------------------------------------------------------------------------
//string number multiplication
get smaller element in b
do not forget to add zeroes in rows aptly
--------------------------------------------------------------------------------------------------------------------------------
//maximum contiguous subarray
maxending = (maxending+a[j]>a[j])?maxending+a[j]:a[j];
maxsumtillnow=(maxsumtillnow>maxending)? maxsumtillnow:maxending;
--------------------------------------------------------------------------------------------------------------------------------
//coin change problem - different ways to make change
initialize dp with 0; first column with 1;
row:
if(i%coins[0]==0)
a[0][i]=1;
for each cell:
long long int v=0;
v+=(j-coins[i]>=0)?a[i][j-coins[i]]:0;
v+=a[i-1][j];
--------------------------------------------------------------------------------------------------------------------------------
//Minimum candies: children seated in a row; min 1; If two children sit next to each other, then the one with the higher rating must get more candies
if 1 child, 1 candy
if same ratings, the latter one gets 1 candy
if ratings dip, the latter one gets 1 candy
increase/decrease candies accordingly.
if(decreased to 0 at any stage)
set it as one. traverse back...and increment the candies
break if a child has a smaller or equal rating
break if candy number differs by more than one.
--------------------------------------------------------------------------------------------------------------------------------
//buy max one share per day, sell any number you own, or make no transaction at all
back-traverse:
if(a[i]<maxv)
profit+=(maxv-a[i]);
maxv=max(maxv,a[i]);
--------------------------------------------------------------------------------------------------------------------------------
//arrange 1x4 and 4x1 bricks in Nx4 wall
f(i)=f(i-1)+f(i-4);
--------------------------------------------------------------------------------------------------------------------------------
//pick 1,2 or 3 coins from top of stack
//set basecases till n=1,2,3
maxscore[i] // maximum score obtainable if a player starts here
second[i] //score obtainable by other player
maxscore[i]= for moves j: 1 to 3 => max(pick j coins +second[j+1])
second[i]=maxscore[j+1] for j giving best maxscore;
Hint: if player1 picks till i+2th coin, player2 gets maxscore[i+3] and player1 gets sum till i+2 and second[i+3];
--------------------------------------------------------------------------------------------------------------------------------
//given coins, find the largest sum possible, lesser than or equal to K;
//coins can be used multiple times
do DP for exact sum till K; check columnwise backwards to locate the first possible answer. //OR maintain a maxsum variable
--------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------