ravio
BAN USERpublic class Test {
public static int reverse(int num){
int result = 0;
while(num != 0){
result = result * 10 + num % 10;
num /= 10;
}
return result;
}
public static void main(String[] args){
System.out.println(reverse(-12345));
System.out.println(reverse(12345));
}
}
Apparently, we have to ask the interviewer what should we do if the number will overflow after reversing.
- ravio September 23, 2014This is a 2 dimensional dynamic programming question. Here is the solution:
dp[i][j] =
Min{
dp[i + 1][j - 1] + 1, if str1[i] = str2[j] && str1[j] = str2[i]
dp[i + 2][j] + 1, if str1[i] = str2[i + 1] && str1[i + 1] = str2[i]
dp[i][j - 2] + 1, if str1[j] = str2[j - 1] && str1[j - 1] = str2[j]
}
In short, it's
dp[i][j] = Min(dp[i + 1][j - 1], dp[i + 2][j], dp[i][j - 2]) + 1.
Here dp[i][j] means the number of minimum swaps needs to swap str1[i, j] to str2[i, j]. Here str1[i, j] means the substring of str1 starting from pos i to pos j :)
Here is an example like the one in the quesition,
str1 = "aab",
str2 = "baa"
dp[1][1] = 0 since str1[1] == str2[1];
dp[0][2] = str1[0 + 1][2 - 1] + 1 since str1[0] = str2[2] && str1[2] = str2[0].
This is just a simple example, you are sure to be able to solve more complicates ones.
And I think if you understand the equation above, you are sure to implement it into code which is pretty a two for loop :)
Thanks for the question. We can solve it as the following:
Assume the following matrix:
1, 1, D, D, D, D
1, 1, D, D, D, D
1, 1, 1, D, D, D
1, 1, 1, 1, 1, D
1, 1, 1, 1, 1, D
1, 1, 1, 1, 1, 1
If you look at this matrix, you will see the tric here, for each row, we just need to check from the end position of '1' in the previous row.
Here in this example,
the end position of each row is 1, 1, 2, 4, 4, 5.
the end position is a non-decreasing sequence. So we end up checking from 1 - n. Then the runtime is O(n).
Sounds like 3-dimensional dynamic programming. The dp function is as follows:
dp[i][j][k] = ((dp[i + 1][j][!k] + num[i]) + (dp[i][j - 1][!k] + num[j] )) / 2;
Here I will explain the function I wrote. It is 3 dimensional dynamic programming.
Let's say we have an array called num[N] which contains the importance levels.
Then [i - j] is the sub region of array num , e.g 0 - 4, 2-3 and so on. k can only be 0 or 1 representing player 1 or player 2. And dp array stores the average importance.
dp[i][j][k] = ((dp[i + 1][j][!k] + num[i] ) + (dp[i][j - 1][!k] + num[j])) / 2;
This function means that when player k moves and the sub region is from i to j, we can get the answer from its sub problems which are dp[i + 1][j][!k] and dp[i][j - 1][!k].
Let's see an example, dp[3][9][0] can be constructed from d[4][9][1] and dp[3][8][1] since we can only shoot from the edge.
This idea can be easily implemented using 3 loops which I believe any of you can do:)
Here I just provide my implementation
public class Test{
public static float getSum(float[] tempSum, int start, int end){
if(start == 0){
return tempSum[end];
}else{
return tempSum[end] - tempSum[start - 1];
}
}
public static void main(String[] args){
float[] num = new float[]{10, 20};
float[][][] dp = new float[num.length][num.length][2];
float[] tempNum = new float[num.length];
System.arraycopy(num, 0, tempNum, 0, num.length);
for(int i = 1; i < num.length; ++i){
tempNum[i] += tempNum[i - 1];
}
for(int i = 1; i <= num.length; ++i){
for(int j = 0; j <= num.length - i; ++j){
for(int k = 0; k <= 1; ++k){
if(i == 1){
dp[j][j][k] = num[j];
}else{
float total1 = getSum(tempNum, j, j + i - 2);
float total2 = getSum(tempNum, j + 1, j + i - 1);
dp[j][j + i - 1][k] = ((total1 - dp[j][j + i - 2][1 - k] + num[j + i - 1]) + (total2 - dp[j + 1][j + i - 1][1 - k] + num[j])) / 2;
}
}
}
}
System.out.println(dp[0][num.length - 1][0]);
}
}
There is the same problem in Leetcode called same tree.
Just do a level order traversal.
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue<TreeNode> firstQueue = new LinkedList<TreeNode>();
Queue<TreeNode> secondQueue = new LinkedList<TreeNode>();
firstQueue.add(p);
secondQueue.add(q);
while(!firstQueue.isEmpty() && !secondQueue.isEmpty()){
TreeNode first = firstQueue.poll();
TreeNode second = secondQueue.poll();
if(first == null && second == null){
continue;
}else
if(first == null || second == null){
return false;
}
else{
if(first.val != second.val){
return false;
}
firstQueue.add(first.left);
firstQueue.add(first.right);
secondQueue.add(second.left);
secondQueue.add(second.right);
}
}
return true;
}
}
The answer is to check if all these rows are unique. If they are unique, just return true. If they are not, just return false. Because if two of the rows are the same, no matter how many columns you remove, they are still the same. If they are originally unique, no matter how many columns you remove, they are still unique.
- ravio September 07, 2014I think this solution is correct. If you think a,b,c as three points on the number line, then it make sense.
The only problem is that, if the minimum number are all from one array, then it will move to the end of the array. So we have to deal with this special case.
We can turn one operand into binary format and calculating using shift like following:
public class Main{
public static int findMinimumAddition(int first,int second){
if(second == 0){
return 0;
}
if(second % 2 == 1){
return findMinimumAddition(first << 1, second / 2) + first;
}else{
return findMinimumAddition(first << 1, second / 2);
}
}
public static void main(String[] args){
System.out.println(findMinimumAddition(9, 9));
System.out.println(findMinimumAddition(6, 3));
}
}
It works only works with positive numbers. If we have negative numbers included, just do a preprocessing like setting an indicator to indicate if the result will be negative. And then deal with postive numbers first and come back to the indicator.
- ravio September 07, 2014Why don't we just do a binary search. The time complexity is just O(log(N)).
public class Main{
public static int getN(long number){
int left = 0;
int right = 31;
while(left <= right){
int middle = left + (right - left) / 2;
long value = 1L << middle;
if(value == number){
return middle;
}else
if(value < number){
left = middle + 1;
}
else{
right = middle - 1;
}
}
return -1;
}
public static void main(String[] args){
System.out.println(getN(1L << 31));
System.out.println(getN(1L << 15));
System.out.println(getN(1L << 1));
}
}
Hi, ChristmasDonkey,
I agree with you that it's a definitely dynamic programming question. And the dp function should be:
dp[i][j] = Math.max(dp[p][q]), if (i - j) * (p - q) > 0, here no lead change
Math.max(dp[p][q]) + 1, if(i - j) * (p - q) < 0, here lead changes
where p < i and p < j;
Your code is not correct. Your code will return true in the following case.
TreeNode<Integer> root = new TreeNode<Integer>(4);
root.left = new TreeNode<Integer>(2);
root.left.left = new TreeNode<Integer>(1);
root.left.right = new TreeNode<Integer>(0);
root.right = new TreeNode<Integer>(6);
root.right.left = new TreeNode<Integer>(1);
root.right.right = new TreeNode<Integer>(7);
boolean sorted = isSorted(root);
Or you could do a inorder traversal, if all the nodes are in ascending order, then it is sorted. Here prev is used to record the node visited previously.
private TreeNode prev = null;
public boolean isSorted(TreeNode head){
if(head == null){
return true;
}
if(!isSorted(head)){
return false;
}
if(prev == null){
prev = head;
}else{
if(head.val < prev.val){
return false;
}
prev = head;
}
if(!isSorted(head)){
return false;
}
return true;
}
The basic idea is to use a map to count the number of characters in string1, and then use another map to track the number of occurances in string2. And use count to check if we have satisfied the conclusion.
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class Solution{
public List<Integer> findIndex(String s1, String s2){
Map<Character, Integer> map = new HashMap<Character, Integer>();
List<Integer> resultList = new LinkedList<Integer>();
//put all characters in a map
for(int i = 0; i < s1.length(); ++i){
char c = s1.charAt(i);
if(!map.containsKey(c)){
map.put(c, 1);
}else{
map.put(c, map.get(c) + 1);
}
}
int count = 0;
Map<Character, Integer> tempMap = new HashMap<Character, Integer>();
for(int i = 0; i < s2.length(); ++i){
char c = s2.charAt(i);
if(!map.containsKey(c)){
count = 0;
tempMap.clear();
}else{
//for cases like s1 = "abcd", "abcda"
if(count == s1.length()){
char cc = s2.charAt(i - s1.length());
tempMap.put(cc, tempMap.get(cc) - 1);
--count;
}
if(!tempMap.containsKey(c)){
tempMap.put(c, 1);
}else{
tempMap.put(c, tempMap.get(c) + 1);
}
if(tempMap.get(c) <= map.get(c)){
++count;
if(count == s1.length()){
resultList.add(i - s1.length() + 1);
}
}else{
count = 0;
tempMap.clear();
}
}
}
return resultList;
}
public static void main(String[] args){
Solution s = new Solution();
System.out.println(s.findIndex("aa", "abcdefcdbacd"));
}
}
I think it just aims to check if we know how a number is stored in big endian and little endian machine or system. As you know that almost all of our personal computers are using little endian and the internet protocol is using big endian. So the network adaptor has to do this conversion for us. Anyway, I just treat it as a chance to review endianness.
- ravio June 07, 2014What I am writing here is how the number is stored in memory. The compiler can do that conversion for us automatically, so we don't need to care about if the machine is using big endian or small endian when we are programming. For example, if you use GDB to debug c or c++ programs, gdb will do that conversion for you.
- ravio June 07, 2014It's a dynamic programming question. And the solution format is just like the fabocci sequence. For example, if w = 1, then the answer is 1, if w = 2, the answer is 2, if w = 3, the answer is 1 + 2 = 3, if w = 4, the answer is 2 + 3 = 5. And the dynamic equation is
dp[n] = dp[n - 1] + dp[n - 2]. Here is the code:
public class Solution{
public int dp(int w){
if(w == 1){
return 1;
}
if(w == 2){
return 2;
}
int prev1 = 1;
int prev2 = 2;
int current = 0;
for(int i = 3; i <= w; ++i){
current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
return current;
}
public static void main(String[] args){
int w = 4;
Solution solution = new Solution();
System.out.println(solution.dp(w));
}
}
Let's take 13 as an example, its binary format is:
00000000, 00000000, 00000000, 00001101, this is also the representation of little endian. The big endian format is 00001101, 00000000, 00000000, 00000000. You have to reverse the bytes, not the bits.
public class Solution{
public int convertToBigEndian(int num){
//we assume that it is a 32-bit number
byte[] bytes = new byte[4];
for(int i = 0; i < 4; ++i){
bytes[i] = (byte)(num % 256);
num = num>> 8;
}
int result = 0;
for(int i = 0; i < 4; ++i){
result = result << 8;
result += bytes[i];
}
return result;
}
public String convertToBinary(int input, boolean littleEndian){
if(!littleEndian){
input = convertToBigEndian(input);
}
StringBuilder sb = new StringBuilder();
while(input > 0){
sb.insert(0, String.valueOf(input % 2));
input /= 2;
}
if(littleEndian){
while(sb.length() < 32){
sb.insert(0, "0");
}
}
return sb.toString();
}
public static void main(String[] args){
Solution solution = new Solution();
System.out.println(solution.convertToBinary(13, false));
}
}
You answer is wrong because you miss understood the concept of little endian and big endian. Let's take 13 as an example, its binary format is:
00000000, 00000000, 00000000, 00001101, this is also the representation of little endian. The big endian format is 00001101, 00000000, 00000000, 00000000. You have to reverse the bytes, not the bits. That's where you got the answer wrong. Please refer to my code for the corrent answer.
I jus want to give a brief explanation about this question since all the others just posted their code. The basic idea is to do search at each possible possition. In this example, we want to find "SNAKE", then the possible start positions are the positions where the character is "S", then you keep a visited array to avoid going back to the same position. The visited array is a little bit tricky. For example, if the matrix is :
S N B S N
B A K E A
B K B B K
S E B S E
Then you go from (0, 0) to (1, 0), to (2, 0), you visited array in these three positions are set as true, but when you discovered that (2, 0) is not a possible answer, you should reset the visited array at position (2, 0) to false immediately since you may go to it later.
It is a good idea to do it like binary search. Here is the code and I have tested it.
public class Solution{
public int findTransitionPoints(String s, int start, int end){
if(start > end){
return 0;
}
if(s.charAt(start) == s.charAt(end)){
return 1;
}
int mid = start + (end - start) / 2;
int left = findTransitionPoints(s, start, mid);
int right = findTransitionPoints(s, mid + 1, end);
//if mid + 1 > end , it means that start = end;
if(mid + 1 <= end){
if(s.charAt(mid) == s.charAt(mid + 1)){
return left + right - 1;
}
}
return left + right;
}
public static void main(String[] args){
String inputString = "0000011112222222222";
System.out.println(new Solution().findTransitionPoints(inputString, 0, inputString.length() - 1));
}
}
There are two problems with this solution.
1.It's not a random number generator. It means that the number you generated is not random. It depends on the time.
2. The reason why you always get 0 firstly is that any positive mod 1 is 0. In your case, you have the first number mod i where i is always 1 initially.
The corrent way to generate a ranom number is to use Linear congruential. You can check that out.
Just do binary search and use a variable to track the most recent value that can have the equation less than k. Here is the java code for this.
import java.util.Scanner;
public class Solution{
public long getValue(long a, long b, long c, long d, long n){
return a * n * n * n + b * n * n + c * n + d;
}
public long findT(long a, long b, long c, long d, long k){
long result = 1;
long right = 1000000;
long left = 1;
long mid = left;
long shouldReturn = 1;
while(left < right){
mid = left + (right - left) / 2;
result = getValue(a ,b, c , d, mid);
if(result == k){
break;
}
if(result < k){
shouldReturn = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return shouldReturn;
}
public static void main(String[] args){
Solution s = new Solution();
int T, K, a, b, c, d;
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int i = 0; i < T; ++i){
a = scanner.nextInt();
b = scanner.nextInt();
c = scanner.nextInt();
d = scanner.nextInt();
K = scanner.nextInt();
System.out.println(s.findT(a, b, c, d, K));
}
}
}
Yes, you can access them since they are all in memory. One of the format could be:
- ravio September 24, 2014---header---content-----tail---, the pointer to the start of the content is what you get through malloc, you can definitely access the header or tail through some pointer arithmetic.