petrov4feedly
BAN USER@ChrisK, your solution is not working for input containing all negatives, e.g. [-1,-2,-3]. Also, there is no need in dp list.
Here is my solution with O(n) time / O(1) memory. I hope it covers all corner cases :)
class Main {
public static void main(String[] args) {
System.out.println(solve(new int[] {0,1,-2,3})); // -> 1+3 = 4
System.out.println(solve(new int[] {8,1,-1,2,2,10})); // -> 8+2+10 = 20
System.out.println(solve(new int[] {10,0,0,0,20})); // -> 10+20 = 30
System.out.println(solve(new int[] {-1,-2,-3})); // -> all negatives -> 0
}
private static int solve(int[] boxes) {
if (boxes.length == 0) return 0;
if (boxes.length == 1) return max(0, boxes[0]);
int box2 = boxes[0];
int box1 = boxes[1];
for (int i = 2; i < boxes.length; i++) {
int curr = box2 + boxes[i];
box2 = max(box2, box1);
box1 = max(box1, curr);
}
return max(box1, max(box2, 0));
}
}
class Main {
public static void main(String[] args) {
BigInteger num = new BigInteger("9620680364645634331845386726262609206982068206820281340810801411111793759");
String s = num.toString(2);
System.out.println(s);
for (int i = 2; i <= 999; i++) {
String str1 = num.mod(new BigInteger(Integer.toString(i))).toString();
String str2 = "" + mod(s, i);
if (!str1.equals(str2)) {
System.out.println(i + ":\t" + str1 + "\t" + str2);
}
}
}
private static int mod(String num, int k) {
final long maxValModK = (1L<<62) % k;
int times = 0;
int pos = num.length()-1;
int res = 0;
while (pos >= 0) {
long factor = 1;
long x = 0;
while (pos >= 0 && factor != 1L<<62) {
if (num.charAt(pos--) == '1') {
x |= factor;
}
factor <<= 1;
}
x %= k;
for (int i = 0; i < times; i++) {
x = (x * maxValModK) % k;
}
res += x;
res %= k;
times++;
}
return res;
}
}
A strange question, actually.
- petrov4feedly May 22, 2017The default implementation of indexOf(String) is O(len1 x len2), however...
There are intrinsics for all major platforms. These implementations are far more effective, ~O(len1 + len2).
So, I wonder what the interviewer wanted to hear...