Google Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
3
of 3 vote

One more thing that came to my mind ...

#1: We know the first few solutions (for n=1 through n=9).

#2: We know what the k-cycles do (they multiply number of A's by (k-2).

#3: 10-cycle would multiply by 8 but 2 5-cycles would multiply by 3*3=9. Similarly for any k > 10. So we don't have to consider any cycle for k bigger than 10.

#4: 1-cycle, 2-cycle don't make sense, 3-cycle gets us to where we were 3 strokes ago. So these can be ignored.

#5: 4-cycle doubles NumAs so it can be included, but it won't be used because it's inefficient.

#6: Now we can use DP to find the optimum solution for n using the following function:

``````f(n) = max (
2*f(n-4),
3*f(n-5),
4*f(n-6),
5*f(n-7),
6*f(n-8),
7*f(n-9)
)``````

So here we go, a DP solution at last :-)

It should give the same answers as my non-DP solution above. Why?

Because:

``````3*3 > 4*2    5-cycle + 5-cycle gives more A's than 6-cycle + 4-cycle
4*4 > 5*3    6-cycle + 6-cycle gives more A's than 7-cycle + 5-cycle
5*4 > 6*3    7-cycle + 6-cycle gives more A's than 8-cycle + 5-cycle
6*4 > 7*3    8-cycle + 6-cycle gives more A's than 9-cycle + 5-cycle``````

Comment hidden because of low score. Click to expand.
0

The 8-cycle mentioned multiples x by 6 times, consider this 8-cycle
C-A, C-C, C-V, C-A, C-C, C-V, C-V, C-V Multiples by 8.

??

Comment hidden because of low score. Click to expand.
1
of 1 vote

To the anonymous user above: Your sequence only multiplies x by 3 times.
To czpete: I think your idea is not only correct but also simpler to implement than mine.
My idea is:
(1) You can only type 'A' as first step.
(2) In the following steps you have two choices:
(2-a) type 'Ctrl-V' (or 'A' in the beginning steps) to increment 'count' by 'countCV'
(2-b) type 'Ctrl-A','Ctrl-C','Ctrl-V' to set 'countCV' as 'count'

I implemented my idea in 'G107' and yours in 'G108',
both of them got same answers till n = 180,
where the answer is approaching Long.MAX_VALUE so I stop.
i = 171; answer = 219902325555200000
i = 172; answer = 288230376151711744
i = 173; answer = 360287970189639680
i = 174; answer = 450359962737049600
i = 175; answer = 562949953421312000
i = 176; answer = 703687441776640000
i = 177; answer = 879609302220800000
i = 178; answer = 1152921504606846976
i = 179; answer = 1441151880758558720
i = 180; answer = 1801439850948198400

My idea:

``````import java.util.*;

class G107
{
public static void main(String[] args)
{
for (int i = 1; i <= 180; i++)
{
System.out.println("i = " + i + "; answer = " + best(i));
}
}

public static long best(int N)
{
return best(N - 1, 1, 1, new HashMap<String, Long>(), new HashMap<Integer, HashMap<Long, Long>>());
}

private static long best(int N, long count, long countCV, HashMap<String, Long> map, HashMap<Integer, HashMap<Long, Long>> shortcuts)
{
if (N <= 0) {return count;}

String key = "";
{
StringBuffer sb = new StringBuffer();
sb.append(N + ",");
sb.append(count + ",");
sb.append(countCV);
key = sb.toString();
}
if (map.containsKey(key)) {return map.get(key);}

// The "shortcut" code below doesn't effect the answer, but improve the efficiency.
// Begin of "shortcut"
HashMap<Long, Long> shortcut = shortcuts.get(N);
HashMap<Long, Long> next = new HashMap<Long, Long>();
if (null != shortcut) for (Long shortCount : shortcut.keySet())
{
Long shortCountCV = shortcut.get(shortCount);
if (shortCount >= count && shortCountCV >= countCV)
{
map.put(key, (long)0); return 0;
}
if (shortCount > count || shortCountCV > countCV)
{
next.put(shortCount, shortCountCV);
}
}
next.put(count, countCV);
shortcuts.put(N, next);
// End of "shortcut"

long result = best(N - 1, count + countCV, countCV, map, shortcuts);
result = Math.max(result, best(N - 3, count, count, map, shortcuts));

map.put(key, result); return result;
}
}``````

``````class G108
{
public static void main(String[] args)
{
for (int i = 10; i <= 180; i++)
{
System.out.println("i = " + i + "; answer = " + answer[i]);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

@czpete: awesome solution!

Comment hidden because of low score. Click to expand.
0

nice idea, I just lack option f(n)=f(n-1) +1 when pressing "A" only.

Comment hidden because of low score. Click to expand.
2
of 2 vote

A(n) = max ( A(i) * A(j) ) such that i+2+j=n starting from i=2 till i<=j.

The problem we are trying to solve is very similar to the following problem:

if we currently have X no. of characters in our clipboard then what is the maximum number of characters that we can print using n clicks. So for 1 click we can print X characters using one Ctrl-V, similarly 2*X for 2 clicks.

Let A(k) denote what multiple of X characters can we print using k no. of clicks.

These clicks will be Ctrl-V's separated by pairs of Ctrl-A,Ctrl-C. So in the optimal solution if one such CA,CC pair occurs at ith and (i+1)th click and i+2+j=n, then :

-> after first i clicks we had printed X*A(i) no of characters,

-> then using Ctrl-A,Ctrl-C pair the no. of characters in clipboard becomes X*A(i),

-> using the next j clicks we can print A(j) multiple of what we have in clipboard now ie X*A (i)*A(j) characters.

So we have A(n) = A(i)*A(j). All we need to do is check for all possible i,j pairs, for which we can easily use DP.

Now to map the given problem to the above problem all we need to assume is that the character that is to be printed is in our clipboard at the beginning (ie before the first click). So for our problem X = 1. To state it the other way, the first few Ctrl-V clicks in the solution of the above problem (ie those before the occurence of the first Ctrl-A,Ctrl-C pair) is to be replaced by equal no the clicks of the character that is to be printed.

Comment hidden because of low score. Click to expand.
0

I forgot to mention the base cases which will be : For n = 1 to 7, A(n) = n

Comment hidden because of low score. Click to expand.
1
of 1 vote

A(n) = max ( A(i) * A(j) ) such that i+2+j=n starting from i=2 till i<=j.

The problem we are trying to solve is very similar to the following problem:

if we currently have X no. of characters in our clipboard then what is the maximum number of characters that we can print using n clicks. So for 1 click we can print X characters using one Ctrl-V, similarly 2*X for 2 clicks.

Let A(k) denote what multiple of X characters can we print using k no. of clicks.

These clicks will be Ctrl-V's separated by pairs of Ctrl-A,Ctrl-C. So in the optimal solution if one such CA,CC pair occurs at ith and (i+1)th click and i+2+j=n, then :

-> after first i clicks we had printed X*A(i) no of characters,

-> then using Ctrl-A,Ctrl-C pair the no. of characters in clipboard becomes X*A(i),

-> using the next j clicks we can print A(j) multiple of what we have in clipboard now ie X*A (i)*A(j) characters.

So we have A(n) = A(i)*A(j). All we need to do is check for all possible i,j pairs, for which we can easily use DP.

Now to map the given problem to the above problem all we need to assume is that the character that is to be printed is in our clipboard at the beginning (ie before the first click). So for our problem X = 1. To state it the other way, the first few Ctrl-V clicks in the solution of the above problem (ie those before the occurence of the first Ctrl-A,Ctrl-C pair) is to be replaced by equal no the clicks of the character that is to be printed.

Comment hidden because of low score. Click to expand.
0

I forgot to mention the base cases which will be : For n = 1 to 7, A(n) = n

Comment hidden because of low score. Click to expand.
0
of 0 vote

use dynamic programming

``````public static int maxNumAs(int n){
int a[] = new int[n+1];
for(int i = 1; i <= n; i++){
if((i-3)*2 > i)
a[i] = a[i-3]*2;
else
a[i] = i;
}
return a[n];
}``````

Comment hidden because of low score. Click to expand.
0

im not sure a[i]= i....

the way i see it..the substructure is as follows

A[0] = 0;

A[n] = max(A[n-1]+1, 2*A[n-3]);

so the program is...

``````int A[n+1];
A[0] = 0;

for(int i=1;i<=n;i++)
{
A[i] = max(A[i-1]+1, 2*A[i-3]);
}

return A[n];``````

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

@anonymous, the solution does not work with N=7. Your code will return 8 but actually the max As is 7.

Comment hidden because of low score. Click to expand.
0

@above... no the solution for N=7 is 8... 4 As and CtrlA+C+V will double it..so 8

Comment hidden because of low score. Click to expand.
0

@Anonymous
The code will not work for a[8]

i :: (i-3)*2 > i :: a[i]
-----------------------------
1 :: False :: 1
2 :: False :: 2
3 :: False :: 3
4 :: False :: 4
5 :: False :: 5
6 :: False :: 6
7 :: True :: 8
8 :: True :: 1o

According to your code a[8] = 10
but I think it should be 9.

Comment hidden because of low score. Click to expand.
0

@Anonymous and v:
Both the code works fine if we assume that we can use Ctrl+V with combination of Ctrl+A and Ctrl+C

If Ctrl+V may print multiple times as in the editors, then the code may fail.

Comment hidden because of low score. Click to expand.
0

@v, CTRL a c v will not double. CTRL a c v v will double.

Comment hidden because of low score. Click to expand.
0

Yes, the issue is that we can use ctrl+v multiple times as in the editors.

And Ctrl+A, Ctrl+C, Ctrl+v will not double, Ctrl+A, Ctrl+C, Ctrl+v, Ctrl+v will double.

Comment hidden because of low score. Click to expand.
0

``````public static void main(String[] args)
{
int n=8;
int gain=0, nextGain;
for(int i=1; i<= n; i++)
{
gain = (n-3-i)*i + i;
nextGain = (n-3-(i+1))*(i+1) + (i+1);
if(nextGain < gain)
{
break;
}
}
System.out.println(Math.max(gain,n));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let step1,2,3,4 is assumed as a cycle.
G(n)= number of A's generated after n cycles
And formula for G(n)=(1+G(n-1))*2
Now n=N/4
Maintain an array.Loop from 0 to n-1.Update arr[n] according to the given formula.
And at last if N/4=1 then final_result=arr[n-1]+1
else final_result=arr[n-1];

Comment hidden because of low score. Click to expand.
0
of 0 vote

@above:
Keys are pressed randomly.Not in a fixed,sequential manner.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Max (N%4 == 0? 4*2^(N/4-1) : (N%4)*2^((N- N%4)/4), N)

Comment hidden because of low score. Click to expand.
0
of 0 vote

@all above

try running your logics against N=12. actual outcome should be 36.
1,1,1,1,0,0,4,4,0,0,12,12

Comment hidden because of low score. Click to expand.
0
of 0 vote

int ReturnMaxA(int N)
{
int count = 0;
int temp;

if((N-4) < 3)
return N;
else
{
N -= 4;
count += 4;

printf("a,a,a,a,");

while(N > 3)
{
temp = count;
count *=2;
N -=3;
printf("Ctrl+a, Ctrl+c, Ctrl+v,");
}

count += temp*N;

while(N)
{
printf("Ctrl+v,");
N--;
}
return count;
}
}

Comment hidden because of low score. Click to expand.
0

Ok, there is one error in the program. For N =7, before the while loop, one more conditional is required

if(N == 3)
{
printf("Ctrl+a, Ctrl+c, Ctrl+v,");
return count*=2;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="java" line="1" title="CodeMonkey21631" class="run-this">use dynamic programming

f(n) = maximum A s that can be produced after n keys
c(n) = clipboard count at f(n)

f(0) = 0
c(0) = 0

f(n) = max of the following:
f(n-1) + 1 in which case c(n) = c(n-1)
f(n-1) + c(n-1) in which case c(n) = c(n-1)
f(n-3) * 2 in which case c(n) = f(n-3)</pre><pre title="CodeMonkey21631" input="yes">
</pre>

Comment hidden because of low score. Click to expand.
0

Keeping track of what's in the clipboard is definitely useful. But how do you use that for DP? What function do you maximize? Just f(n) is not enough!!!

Unfortunately, the sequence of strokes to get the most A's for N-1 could be completely different from the sequence of strokes for N. For example, to get the best for 7, you do "a,a,a,a,a,a,a", but the best for 8 is "a,a,a,C-A,C-C,C-V,C-V,C-V". Notice that for N=7, I only had 6 a's written in the above sequence. Your formula would not work for this case.

What I am trying to say is that DP is the most promising algorithm to use but it won't be completely straightforward to write it, and you'd need to keep track of several pairs (NumAs,ClipboardLenght) or in your case (f(n),c(n)) for each n.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int f( int n )
{
int DP[n+1];

DP[1]=1;
DP[2]=2;
DP[3]=3;

int copied=0,i,val;

for( i=4;i<=n;i++ )
{
val= max( DP[i-3]*2 , DP[i-1]+1 );

if( copied > 0 )
val=max( val , DP[i-1] + copied );

if( val == DP[i-3]*2 )
copied=max( copied , DP[i-3] );

DP[i]=val ;

}

return DP[n] ;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class ATest {

StringBuilder stringProduced = new StringBuilder();
String clipBoardString = "";
static int keyStrokesConsumed = 0;
static int n = 26;

public static void main(String[] args){
ATest aTest = new ATest();
while(keyStrokesConsumed<n){
if(keyStrokesConsumed<3){
aTest.pressA();
}else{
if(aTest.clipBoardString.length()==0){
aTest.log("Clipboard length is zero");
if(keyStrokesConsumed+4<=n){
aTest.pressCtrlA();
}else{
if(n<=6){
aTest.pressA();
}else{
aTest.pressCtrlV();
}
}
}else{
if(aTest.stringProduced.length()+aTest.clipBoardString.length()> aTest.stringProduced.length()*2){
aTest.pressCtrlV();
}else{
if(keyStrokesConsumed+4<=n){
aTest.pressCtrlA();
}else{
aTest.pressCtrlV();
}
}
}
}
}
System.out.println("keyStrokesConsumed = "+ keyStrokesConsumed+", length = "+aTest.stringProduced.length());

}

void pressA(){
keyStrokesConsumed = keyStrokesConsumed+1;
stringProduced.append("a");
log("pressed A \t" + stringProduced);
log("remaining keyStrokes = "+ (n-keyStrokesConsumed));
}

void pressCtrlA(){
log("pressed Ctrl+A");
keyStrokesConsumed = keyStrokesConsumed+1;
pressCtrlC();
}

void pressCtrlC(){
keyStrokesConsumed = keyStrokesConsumed+1;
clipBoardString = stringProduced.toString();
log("pressed Ctrl+C");
pressCtrlV();
pressCtrlV(); //this stroke will actually double the length.. just type some aaaa in notepad and try CrtlA,C,V,V
}

void pressCtrlV(){
keyStrokesConsumed = keyStrokesConsumed+1;
stringProduced.append(clipBoardString.toString());
log("Pressed Ctrl+V \t" + stringProduced);
log("remaining keyStrokes = "+ (n-keyStrokesConsumed));
}

void log(String message){
System.out.println(message);
}
}``````

Comment hidden because of low score. Click to expand.
0

Can you explain what your code does? Or at least add sample output for some interesting values (like 8 and 9)?

I don't know if it's arrogance or incompetence, but I see so many people on this site just writing code with no explanation what so ever. This kind of approach won't land you the job you want!!! If you've spent the time to write the code, please make everyone else's life a bit easier and tell us how your solution works, why it works, and especially why it's better than anything posted so far.

Thanks :-)

Comment hidden because of low score. Click to expand.
0
of 2 vote

I think the one mistake in most of the posts above (with very few exceptions) is trying to double the number of A's using "C-A,C-C,C-V,C-V" repeatedly. But that's not the fastest way to grow! In fact, the fastest way to grow (for large N) is using "C-A,C-C,C-V,C-V,C-V" repeatedly! In 6 strokes, you multiply the number of A's by 4!

OK, when I started the post, I did not think I had the solution, but now I think I do ...

Point #1:
If N is large, the middle of the stroke sequence should be the 6-cycle from above, repeated many times. So it now depends on the specific N what will be at the beginning and what will be at the end ...

Point #2:
You can assume that somehow at stroke -2 you pressed "A", then at stroke -1, you pressed "Ctrl-A", at 0 "Ctrl-C". Then pressing "A" at stroke 1 would be the same as pressing "Ctrl-V" at stroke 1. This not really needed but it will make things more clear.

Point #3:
We know that all the way till N=7, it's better to just push "A" (or Ctrl-V with assuming #2 above). But for N=8, we are starting a new 6-cycle at stroke #4.

Solution:

``````Define
5-cycle: "C-A,C-C,C-V,C-V,C-V".                 Multiplies NumAs by 3
6-cycle: "C-A,C-C,C-V,C-V,C-V,C-V".             Mutliplies NumAs by 4
7-cycle: "C-A,C-C,C-V,C-V,C-V,C-V,C-V".         Mutliplies NumAs by 5
8-cycle: "C-A,C-C,C-V,C-V,C-V,C-V,C-V,C-V".     Mutliplies NumAs by 6
9-cycle: "C-A,C-C,C-V,C-V,C-V,C-V,C-V,C-V,C-V". Mutliplies NumAs by 7

N=1: NumAs=1, "A"
N=2: NumAs=2, "A,A"
N=3: NumAs=3, "A,A,A"                 This is really a 5-cycle starting at -1 (using #2 above)
N=4: NumAs=4, "A,A,A,A"               Really a 6-cycle (starting at -1)
N=5: NumAs=5, "A,A,A,A,A"             Really a 7-cycle
N=6: NumAs=6, "A,A,A,A,A,A"           Really an 8-cycle
N=7: NumAs=7, "A,A,A,A,A,A,A"         Really a 9-cycle
N=8: NumAs=3*3=9,   "A,A,A"+5-cycle     5-cycle + 5-cycle (starting at -1)
N=9: NumAs=4*3=12,  "A,A,A,A"+5-cycle   6-cycle + 5-cycle
N=10: NumAs=4*4=15, "A,A,A,A"+6-cycle   6-cycle + 6-cycle
N=11: NumAs=4*5=18, "A,A,A,A"+7-cycle   6-cycle + 7-cycle
N=12: NumAs=4*6=21, "A,A,A,A"+8-cycle   6+8
N=13: NumAs=4*7=21, "A,A,A,A"+9-cycle   6+9
N=14: NumAs=3*4*3=36,  "A,A,A"+6-cycle+5-cycle     5+6+5
N=15: NumAs=4*4*3=48,  "A,A,A,A"+6-cycle+5-cycle   5+6+5
N=16: NumAs=4*4*4=64,  "A,A,A,A"+6-cycle+6-cycle   6+6+6
N=17: NumAs=4*4*5=80,  "A,A,A,A"+6-cycle+7-cycle   6+6+7
N=18: NumAs=4*4*6=96,  "A,A,A,A"+6-cycle+8-cycle   6+6+8
N=19: NumAs=4*4*7=112, "A,A,A,A"+6-cycle+9-cycle   6+6+9

And so on ...``````

The pattern changes with multiples of 6. The order of the cycles does not really matter, so 6+6+9 could be also written as 9+6+6, i.e. a 9-cycle + 6-cycle + 6-cycle, which is 7 A's followed by 2 6-cycles.

Now you can easily write a generic formula/function to output the best sequence for any n.

Comment hidden because of low score. Click to expand.
0

ur code is wrong ....
till n=9 correct ....after that wrong ...
in n=10 ............
1.A
2.A
3.A
4.A
5.cntl+a
6.cntl+c
7.cntl+v : total count : 4
8.cntl+v : : 8
9.cntl+v : 12
10.cntl+v : : 16
so total count is 16............. not 15

Comment hidden because of low score. Click to expand.
0
of 0 vote

@czpete solutions is correct , but I would like to say my approach (not the code)..

I used DP here.

for a given value of N , I would allocate an array a[N][3]. And every entry in this array stores two values : 1) count : Number of A's Stored till now. 2) cache : Value in clipboard at current step.

for every step i, we have three options :
1) Press A
2) Press Ctrl V with value in the clipboard from previous step i-1;
3) Press Ctrl V with value just copied from Ctrl A from step i-4; // this one doubles the value

for(int i=1;i<=4;i++)
{
a[i][0].count = a[i-1][0]+1;
a[i][0].cache = 0;

a[i][1].count = a[i-1][1]+1;
a[i][1].cache = 0;

a[i][2].count = a[i-1][2]+1;
a[i][2].cache = 0;
}

for(;i<=N;i++)
{

a[i][0].count = max { a[i-1][0].count,a[i-1][1].count,a[i-1][2].count ) + 1;
a[i][0].cache = // cache value from the element selected from previous step.

a[i][1].count = max { a[i-1][0].count + a[i-1][0].cache ,a[i-1][1].count+a[i-1][1].cache,a[i-1][2].count + a[i-1][2].cache );
a[i][1].cache = // cache value from the element selected from previous step.

a[i][2].count = max(a[i-4][0].count*2 , a[i-4][1].count*2,a[i-4][2].count*2};
a[i][2].cache = // cache value from the element selected from previous step.

}

The sol is big.. But Tell me if my approach is correct ?

Also one another approach is :

A every step we can have four possibilities :

1) Press A,
2) Press Ctrl A,
3) Press Ctrl C,
4) Press Ctrl V

Comment hidden because of low score. Click to expand.
0

This should work too (the first part). It would be a bit messy to code but the idea is correct.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution (my code is horrendous so I'm just gonna describe it).

* Use a doubly-linked list of keys.
* Treat CTRL+A, CTRL+C, CTRL+V, CTRL+V as a single key called "double".
* "A" and "paste" have a weight of 1, "double" has a weight of "4". This is the number of keystrokes represented by the key.

1. Initialize the linked list with N number of "A"s. (N being the input).
3. print the list, return the total (M)

- append the new key to the list.
- find the rightmost sublist with weight equaling the original list (which is N). If that sublist doesn't exist, append "paste" until the weights match.
- calculate the total As of the old list and new list.
- if the total of the new list >= the old list's total, then dequeue the list down to weight N. (do this even if the totals are equal, on the basis that appending another "paste" or "double" is never worse and potentially better for any subsequent keys). return true.
- if the old total is greater, then remove the keys from the right and return false.

Comment hidden because of low score. Click to expand.
0

Also, I believe this is wrong:

N=12: NumAs=4*6=21, "A,A,A,A"+8-cycle 6+8

I calculate this as

A A A A A double paste paste paste

which is 25 A's, not 24.

Comment hidden because of low score. Click to expand.
0

Just realized my solution is rubbish

Comment hidden because of low score. Click to expand.
0
of 0 vote

observations :
- A prints a single A, other keys don't print anything unless in a sequence
- a sequence of Ctrl^A, Ctrl^C, Ctrl+V costs 3 keystrokes, but allows to multiply current amount of A by a factor of 2.

For less or equal to 6, typing only As is the bese solution, thus we return n.
Starting from 7, typing four A then a "copy sequence" allows to make 8 A.

we have to maximize the amount of sequences, and make sure we type at least one A.

``````public class CopyPaste {

public static void main(String[] args){
System.out.println(copyPaste(Integer.parseInt(args[0])));
}

private static final int SEQ_LEN = 3;

private static int copyPaste(int n){
int nbSeq = n/SEQ_LEN-1;
if( nbSeq < 0 ){
nbSeq = 0;
}
int nbLeft = n - (SEQ_LEN*nbSeq);

int result = nbLeft;
for(int i=0;i<nbSeq;i++){
result = 2 * result;
}
return result;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

the optimal pattern:
1. n A's
2. several A's + ctrlA + ctrlC + several ctrlV's
3. several A's + ctrlA + ctrlC + several ctrlV's + repeated(ctrlA + ctrlC + ctrlV)
In other words, f(n) = max(n, ((n-2)/2)*((n-1)/2), f(n-3))
(notice in pattern 2, we obtain the maximum when the number of A's and the number of ctrlV's plus 1 are the same.)

proof:
first, the last symbol cannot be ctrlA or ctrlC, otherwise we can replace it by A.
next, observe A's cannot appear after ctrl symbols, otherwise we can move them forward.
so the pattern must be: several A's + repeated(ctrlA + ctrlC + several ctrlV's).
finally, to obtain pattern 3, we repeatedly replace all the subsequence: ctrlV + ctrlA + ctrlC + ctrlV + ctrlV by the subsequence: ctrlV + ctrlV + ctrlA + ctrlC + ctrlV.
The sequence after the transformation is at least as good as the old one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumption (Ctrl + a is one key press)
use the following formula: n% 4 = 0
then max # of keys press = 2(pow(2,t-1) -1) where int t = n/4
else if n%4 != 0 then of keys press = 2(pow(2,t-1) -1) +1 where int t = n/4

Comment hidden because of low score. Click to expand.
0
of 0 vote

Formula is this
N=0, M=0
N=1, M=1
N=2, M=2
N=3, M=3

For N>3
M=(3+ (N-3) mod 3) * 2 ^ floor((N-3)/3)

N=4, M=4
N=5, M=5
N=6, M=6
N=7, M=8 a,a,a,a,C+A,C+C,C+V
N=8, M=10
N=9, M=12 a,a,a,C+A,C+C,C+V,C+A,C+C,C+V

etc.

Comment hidden because of low score. Click to expand.
0

Your solution is close but not completely correct. C + A needs two key presses, not one.

So, you should use 6's instead od 3's in your equation and your formula should start at 12, not 3.

Comment hidden because of low score. Click to expand.
0
of 0 vote

AAAA <= 4 press
AAAAAAAA <=7 + A, C, V
AAAAAAAAAAAA <= 8, V
AAAAAAAAAAAAAAAA <=9, V

16A's ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

1:1
2:2
3:3
4:4
5:5
6:6
7:7
8:9
9:12
10:16
11:20
12:25
13:30
14:36
15:48
16:64
17:80
18:100
19:125
20:150
21:192
22:256
23:320
24:400
25:500
26:625
27:768
28:1024
29:1280
30:1600

Comment hidden because of low score. Click to expand.
0

I think, u r correct dude

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since M[x]=MAX(M[x-1]+1, M[x-5]*2);
you need to five more keystroke to double the size and one more keystroke to increase by one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

till 7 : ans : same number
e.g :
n=1 : ans :1
--------------------------
n=8:9
add 3 to previous ans --------------
n=9:12
add 4 to previous ans ---------------
n=10:16
n=11:20
add 5 to previous ans ---------------
n=12: 25
add 5 to previous ans --------------
n=13:30
add 6 to previous ans --------------
n=14:36

so on and so forth .............

here we can use recursive algorithm

Comment hidden because of low score. Click to expand.
0
of 2 vote

using DP. When calculating the S[i], it may be got by three ways:
1. just input "A". So S[i] = S[i - 1] + 1
2. just "Ctrl-V", and the content in the buffer will be added to S[i - 1]
3. from i - 3, we will do "Ctrl-A" + "Ctrl-C" + "Ctrl-V", So the S[i] = S[i - 3] * 2, and the length of content in buffer will be S[i - 3].

Here is the code in C++;

``````#include <iostream>
using namespace std;

int maxlength(int n)
{
int s[1000];
int buff[1000];
s[0] = buff [0] = buff[1] = buff[2] = 0;
s[1] = 1;
s[2] = 2;
for (int i = 3; i <= n; ++i)
{
buff[i] = buff[i - 1];
s[i] = s[i - 1] + 1;
if (s[i - 1] + buff[i - 1] > s[i])
{
s[i] = s[i - 1] + buff[i - 1];
buff[i] = buff[i  - 1];
}
if (s[i - 3] * 2 > s[i])
{
s[i] = s[i - 3] * 2;
buff[i] = s[i - 3];
}
cout << buff[i] << " " << s[i] << endl;
}
return s[n];
}

int main()
{
int n;
cin >> n;
int result = maxlength(n);
cout << result << endl;
return 0;
}``````

The first 10 result should be:
1:1
2:2
3:3
4:4
5:5
6:6
7:8
8:12
9:16
10:20

Comment hidden because of low score. Click to expand.
0

I am afraid this is not right.
7 should be 9
AAA CA CC CV CV

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int fun(int n, int tot, int clip, boolean selected) {
if (n<0) return -1;
if (n<2) return (tot+n);
if (selected) return Math.max(
fun(n-1,1,clip,false),fun(n-1,tot,tot,true));
int tmp = Math.max(fun(n-2,tot+clip,clip,false),fun(n-2,tot,clip,true));
return Math.max(tmp, fun(n-1, tot+1, clip,false));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int fun(int n, int tot, int clip, boolean selected) {
if (n<0) return -1;
if (n<2) return (tot+n);
if (selected) return Math.max(
fun(n-1,1,clip,false),fun(n-1,tot,tot,true));
int tmp = Math.max(fun(n-2,tot+clip,clip,false),fun(n-2,tot,clip,true));
return Math.max(tmp, fun(n-1, tot+1, clip,false));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the below recurrence

``F(N) = Max (F(N-1)+1, 2 * F(N-3))``

The base cases are: F(1)=1, F(2)=2, F(3)=3

Comment hidden because of low score. Click to expand.
0
of 0 vote

So for, the post on leetcode (ctrla-ctrlc-ctrlv.html) is the best solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

danidevi11

Comment hidden because of low score. Click to expand.
-1
of 1 vote

total number of A's = ((N-4)%3+4)*pow(2,(floor((N-4)/3))
//press A initially 4 times, for N=4 that's the max num of A's we get

``````//Example: N=11
Total Number of A's from the equation on top = ((11-4)%3+4)*pow(2,((11-4)/3))
= 5*(2^2) => 20``````

``````pressA_init = 4; //press A initially 4 times
keysPerSeq  = 3; //number of keys per sequence, here sequence is {Ctrl+A: Ctrl+C: Ctrl+V}
max_nSeqs   = floor((N-pressA_init)/3);
pressA_init += (N-pressA_init)%3;
total_nAs = 0;
while(pressA_init>0){
//press A .
--pressA_init; ++total_nAs;
}
while(max_nSeqs>0){
// press the sequence of keys
total_nAs=total_nAs*2; //the sequence doubles number of A's
--max_nSeqs;
}``````

Comment hidden because of low score. Click to expand.
0

``````#include <iostream>
using std::cout;using std::endl;
int main(){
int keysPerSeq ,max_nSeqs,pressA_init;
int N = 20,total_nAs = 0;
while(N>0){ //for each value on N
pressA_init = (N>4)?4:N; //press A initially 4 times
keysPerSeq  = 3; //number of keys per sequence, here sequence is {Ctrl+A: Ctrl+C: Ctrl+V}
max_nSeqs   = ((N-pressA_init)/3);
pressA_init += (N-pressA_init)%3;
total_nAs = 0;
while(pressA_init>0){
//press A .
--pressA_init; ++total_nAs;
}
while(max_nSeqs>0){
// press the sequence of keys
total_nAs=total_nAs*2; //the sequence doubles number of A's
--max_nSeqs;
}
cout<<"total A's using "<<N<<" keys :"<<total_nAs<<endl;
--N;
}
}``````

Comment hidden because of low score. Click to expand.
0

I don't think you understood the actions :)
a, ctrl+a, ctrl+c, crtl+v => a
a, ctrl+a, ctrl+c, crtl+v => aa
a, ctrl+a, ctrl+c, crtl+v => aaa
a, ctrl+a, ctrl+c, crtl+v => aaaa
...
this happens because you paste the same content over the content (ctrl + a).
so, if n = 4k, m = k
if n = 4k+1, m = k+1 (writes a new a)
if n = 4k+2, m = k+1 (just selects)
if n = 4k+3, m = k+1 (copies k+1 a's)
if n = 4k+4 (is the first case), m = k+1 (paste k+1 a's).

the algorithm is simple. O(1).

Comment hidden because of low score. Click to expand.
0

The question is "write a program to produce maximum number of A's", there's no order for the sequence of keys.
example for N =20, wat is the max num of A's u can generate?

Comment hidden because of low score. Click to expand.
0

I think, for N=11, number of A's will be 17 not 20.

Comment hidden because of low score. Click to expand.
0

ya..this is a wrong solution

Comment hidden because of low score. Click to expand.
0

FOR N = 11,
A A A A A
CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V, CTRL+V,
total = 20 A's

Comment hidden because of low score. Click to expand.
0

N=11
1) A 1
2) A 2
3) A 3
4) Ctr-A
5) Ctr-C
6) Ctr-V 6
7) Ctr-V 9
8) Ctr-A
9) Ctr-C
10)Ctr-V 18
11)Ctr-V 27

Comment hidden because of low score. Click to expand.
0

You are wrong at step 6 and again at 10. They key sequence Ctrl+A, Ctrl+C and Ctrl+V overwrites the selected text, try it yourself in any editor. The correct value for 11 is indeed 20.
1) A 1
2) A 2
3) A 3
4) A 4
5) Ctrl+A
6) Ctrl+C
7) Ctrl+V (Still 4 A's as it will overwrite selected text)
8) Ctrl+V 8
9) Ctrl+V 12
10) Ctrl+V 16
11) Ctrl+V 20

There is a dynamic programming solution to this problem.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

for N = 7, the maximum number of A is 9. key in 3 times A, then do a Ctrl + A, Ctrl + C, Ctrl + V, then Ctrl + V

Comment hidden because of low score. Click to expand.
0

That's not correct. Since Ctrl + A, Ctrl + C, Ctrl + V will not double. Only Ctrl + A, Ctrl + C, Ctrl + V, Ctrl + V will double. That is to say, according to your key sequence, the maximum As is 6. While, the actual maximum As should be 7.

Comment hidden because of low score. Click to expand.
0

agree with amklo.

here is a way to calculate:
------------------
#include <iostream>
#include <math.h>
using namespace std;

int GetMaxCount(int N)
{
if (N<=0)
{
return 0;
}

if (N<=4)
{
return N;
}

int reminder=(N-4)%4;

int power=(N-4)/4;
int result=4;
if (power>0)
{
result+=pow(4.0,power);
result*=(1+reminder);
}
else
{
result+=reminder;
}

return result;
}

void main()
{
for (int i=0;i<30;i++)
{
cout<<GetMaxCount(i)<<endl;
}

getchar();
}
------------------
and we have results for N=0,1,...,30:
you can plot the curve in excel to verify:
0
1
2
3
4
5
6
7
8
16
24
32
20
40
60
80
68
136
204
272
260
520
780
1040
1028
2056
3084
4112
4100
8200

Comment hidden because of low score. Click to expand.
0

#include <iostream>
#include <math.h>
using namespace std;

int GetOldest(int i,int N)
{
int temp=i-N+1;
if (temp>=0)
{
return temp;
}
else
{
return temp+N;
}

}
int GetMaxCount(int N)
{
if (N<=0)
{
return 0;
}

if (N<=4)
{
return N;
}

int incremental=1;
int array[4]={1,2,3,4};

int pLatest=3;

for (int i=4;i<N;i++)
{
int pOldest=GetOldest(pLatest,4);

int doubleV=array[pOldest]*2;
int incrementalV=array[pLatest]+incremental;

//cout<<doubleV<<"\t"<<incrementalV<<endl;

if (doubleV>=incrementalV)
{
incremental=array[pOldest];
array[pOldest]=doubleV;
}
else
{
array[pOldest]=incrementalV;
}
pLatest=pOldest;
}

return array[pLatest];
}

void main()
{
for (int i=1;i<=30;i++)
{
cout<<GetMaxCount(i)<<","<<endl;
}

getchar();
}

------------------
and we have results for N=1,...,30:
you can plot the curve in excel to verify:
1
2
3
4
5
6
7
8
12
16
20
24
28
32
48
64
80
96
112
128
192
256
320
384
448
512
768
1024
1280
1536

Comment hidden because of low score. Click to expand.
0

algo is not optimal. eg for N=8, max A is 9 not 8.

A, A, A, Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V, Ctrl+V, Ctrl+V Gives 9 As.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Python Code: Assuming that ctrl+A , ctrl+C, ctrl+V over writes the original string.

``````#!/usr/bin/env python

def length(N):
sos = 0 #Current length of string
cp = 0 #Length on clipboard

curr = 0
while curr < N:
next = cp if cp > 1 else 1
#    print 'curr:', curr, 'sos:', sos,'next:', next
if curr + 4 > N:
sos += (N-curr)*next
curr = N
else:
if sos + 4*next > 2*sos:
sos += 4*next
else:
cp = sos
sos = 2*sos
curr += 4
return sos

for i in range(1,41):
print i,':',length(i)``````

output:

``````1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 6
7 : 7
8 : 8
9 : 12
10 : 16
11 : 20
12 : 24
13 : 28
14 : 32
15 : 36
16 : 48
17 : 72
18 : 96
19 : 120
20 : 144
21 : 168
22 : 192
23 : 216
24 : 288
25 : 432
26 : 576
27 : 720
28 : 864
29 : 1008
30 : 1152
31 : 1296
32 : 1728
33 : 2592
34 : 3456
35 : 4320
36 : 5184
37 : 6048
38 : 6912
39 : 7776
40 : 10368``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.