Miguel Oliveira
BAN USERI enjoy algorithms, puzzles and programming competitions :)
- 1 Answer Interview "red flags"
Hi,
- Miguel Oliveira September 09, 2013
In the beginning of CtCI book, Gayle talks about the case of a student which she referred but had too many "red flags".
Could you elaborate more on the "red flags"? Maybe with a few more examples of these kind of mistakes that we should avoid in an interview?| Flag | PURGE
You only save space if the value of the numbers is quite small, in the order of N, N being the number of elements in the list.
Suppose the value of the numbers in the list can be as high as 10000000000000000000000. The bit vector need to have that many bits, while the hash table continues to have size O(N)
The compiler doesn't know the address of p, but that is true for both cases. It does not make a difference.
- Miguel Oliveira September 12, 2013that's still O(log n) == number of bits of n. you can do better than that with some pre-computation (assuming there are many queries, the pre-computation cost will be worth it)
- Miguel Oliveira September 12, 2013in an interview setting, there not much value in using language features like those to answer these types of questions
- Miguel Oliveira September 12, 2013If you want just one query, just use a breadth first search from the first node until the second node is found.
- Miguel Oliveira September 12, 2013right, it is O(n^2)
- Miguel Oliveira September 12, 2013hash table operations run in amortized constant time. wikipedia.org / wiki/Amortized_analysis
for more details i suggest you consult a book like Introduction to Algorithms
Come on, how do you possibly think you can go through N elements in constant time?
The constant time part is about using a hash table to check if a number was already seen in the list. And also insert numbers in the hash table in constant time.
Constant time is usually a tip for "use a hash table" and this is a good example for that.
- Miguel Oliveira September 11, 2013read the question till the end "3)(i,j)th entry of the matrix can be either 0 or 1"
- Miguel Oliveira September 11, 2013There are n*n elements, so you can't possible have a O(n) solution, but O(n*n).
// prints all valid positions in O(n*n) with extra O(n) space.
// If the interviewer just wants a boolean Possible/Impossible, just return true/false
void FindOut(int matrix[1000][1000], int n) {
int row_zeros[n], col_ones[n], i, j;
for (i = 0 ; i < n ; i++) {
row_zeros[i] = col_ones[i] = 0;
for (j = 0 ; j < n ; j++) {
row_zeros[i] += matrix[i][j] == 0;
col_ones[i] += matrix[j][i] == 1;
}
}
for (i = 0 ; i < n ; i++)
for (j = 0; j < n ; j++)
if (matrix[i][j] == 1) {
if (row_zeros[i] == n-1 && col_ones[j] == n)
printf("position (%d, %d)\n", i, j);
} else {
if (row_zeros[i] == n && col_ones[j] == n-1)
printf("position (%d, %d)\n", i, j);
}
}
it is quite similar to the knapsack problem. if you reach the solution yourself, you will learn much more
- Miguel Oliveira September 11, 2013When an array is declared in the stack or heap, those 2 statements are equivalent since the compiler translates p[2] in *(p + 2 * sizeof(char)) = *(p + 2 * 1) = *(p+2) since 2 and 1 are constants.
String literals are usually stored in read-only segments of memory. So the compiler might know the value of p during compile time. This still does not make a difference in efficiency between the 2.
"where as p[2] move one by one" why do you say this? i've never seen such argument before. that's not how it works in arrays
- Miguel Oliveira September 10, 2013i++ increments the variable but returns its value before the increment.
++i increments the variable and returns a reference to the variable.
the = operator needs a L-value on the left side to be able to assign the value of a to i. the first statement does not return an L-value, while the second statement does (return variable i).
That would be my approach as well. We can't have a better time complexity because there are n*m numbers in the matrix and we need (at least) to read them all.
~
The space complexity is also O(n*m) - store the matrix. I think we can't avoid it because we need the whole matrix to resolve collisions. The hash table needs an extra O(n) space which is ignored in big-O notation.
If you read the beginning of the explanation, this approach is assuming that there are no duplicate values. Hence, <= or < does not matter since the values can't be equal.
Same thing as the <= at "array[i] <= array[i-1]" in the first approach
In your example it seems you're not finding the leftmost element greater than number i, but the number at index j closest to i.
In this case, I know how to do it in O(log n) for each i, giving a total of O(n log n). Are you sure it's possible to do it in O(n)? It seems unlikely to me.
I think the 2 most common definitions of balanced I've seen are
1) The height difference between any two leaves is at most 1
2) The height of the tree is at most 2 * log(N), where N is the number of elements in the tree.
In either case, we can use a Breadth First Search and record the heights of the nodes in the tree. For case 1 we want the minimum and maximum heights of the tree and for case 2 we only want the maximum.
You can use bitwise operations to simplify the code. Here's my implementation:
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
public class SubsetSum {
// Array size should not exceed 40
public static void solve(int[] v) {
int i, sum, N = v.length;
for (i = sum = 0; i < N ; i++)
sum += v[i];
if (N % 2 == 1 || sum % 2 == 1) {
System.out.println("Impossible");
return;
}
int halfLength = N / 2, halfSum = sum / 2;
ArrayList<HashMap<Integer,Integer>> hash = new ArrayList<HashMap<Integer,Integer>>();
for (i = 0 ; i <= halfLength; i++)
hash.add(new HashMap<Integer,Integer>());
int mask, numSubSets = 1 << halfLength;
// process all subsets using the first half of the array. Use bitmasks to do it.
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0, subsetSum = 0;
for (i = 0 ; i < halfLength; i++)
if ((mask & (1 << i)) > 0) {
// mask has bit i set to 1
subsetSum += v[i];
subsetSize++;
}
hash.get(subsetSize).put(subsetSum, mask);
}
// process the other half and check the hashmaps
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0, subsetSum = 0;
for (i = 0 ; i < halfLength; i++)
if ((mask & (1 << i)) > 0) {
// mask has bit i set to 1. Note that we're using the other half.
subsetSum += v[i + halfLength];
subsetSize++;
}
int remSize = halfLength - subsetSize, remSum = halfSum - subsetSum;
if (hash.get(remSize).containsKey(remSum)) {
printSolution(v, hash.get(remSize).get(remSum), mask);
return;
}
}
System.out.println("No solution");
}
static void printSolution(int[] v, int leftMask, int rightMask) {
int i, indexA=0, indexB=0, halfLength = v.length / 2;
int[] a = new int[halfLength];
int[] b = new int[halfLength];
for (i = 0 ; i < halfLength; i++) {
if ((leftMask & (1 << i)) > 0)
a[indexA++] = v[i];
else
b[indexB++] = v[i];
if ((rightMask & (1 << i)) > 0)
a[indexA++] = v[i + halfLength];
else
b[indexB++] = v[i + halfLength];
}
System.out.print("Array A: ");
for (i = 0; i < halfLength; i++)
System.out.print(a[i] + " ");
System.out.print("\nArray B: ");
for (i = 0; i < halfLength; i++)
System.out.print(b[i] + " ");
System.out.println("");
}
public static void main(String[] args) {
final int input[] = {1, 20, 20, 20, 29, 30};
solve(input);
}
}
So we need to go through n walkways using either the left or right one, correct?
The way you described it is solvable in O(n) using dynamic programming.
it means that there is a positive weight cycle. hence, there is no limit to the weight of paths using this cycle repeated times.
- Miguel Oliveira September 05, 2013it means that there is a positive weight cycle. hence, there is no limit to the weight of paths using this cycle repeated times
- Miguel Oliveira September 05, 2013this is incorrect as explained in other posts in this thread
- Miguel Oliveira September 05, 2013this is incorrect as explained in other posts in this thread
- Miguel Oliveira September 05, 2013subArray does not run in O(1) but O(N).
anyway this recursive approach runs in exponential time
that approach is much slower
- Miguel Oliveira September 04, 2013it seems you copy pasted this from somewhere else. It's not properly formatted and it's not clear what the question is about.
Try to be a bit more clear about the objective and give one or 2 examples of input and output
no interviewer wants you to use standard library functions on these types of questions
- Miguel Oliveira September 02, 2013Jie, there can be O(N^2) such subsequences, how do you print them all in O(N)? :)
- Miguel Oliveira September 01, 2013The question does not make sense if the point is to have "abc" and "ABC" mapped to different hash values. It already does that by default.
If the point was to consider "abc" and "ABC" as the same key, we would have to override the hashCode() and equal() of the type we're putting in the HashMap.
This would make more sense as an interview question.
The only difference in your algorithm is that you take numbers in decreasing order. It's wrong by the same reason. It works for that example, but fails with examples like
{ 1, 20, 20, 20, 29, 30 } answer is {1, 29, 30} , {20,20,20} but your algorithm gives {30, 20, 1} and {29, 20, 20 }
and negative numbers { -87, -30, -30, -30, -2 , -1 } you get 6. -1 -2 -30 -30 -30 -87 | <empty array>
both arrays must have the same amount of numbers, so it does here.
- Miguel Oliveira August 30, 2013The approach I mentioned does not assume that.
For the 0-1 knapsack approaches to work with negative numbers, you just need to add an offset to the numbers, so that all numbers become positive.
(offset = - smallest_negative_number)
this kind of approach gives wrong answers. check the other posts
- Miguel Oliveira August 30, 2013check the other posts with this kind of approach. it is wrong
- Miguel Oliveira August 30, 2013Like I said in the post, we're making the string and its reverse equal. They have both N characters so if we remove K characters, we need to insert K as well to get to size N.
- Miguel Oliveira August 30, 2013@Parin, it's O(N^2) which is too slow
- Miguel Oliveira August 30, 2013This code does not work. Counter-example: "axxbababa", k = 2. Answer is True, but your code gives False
- Miguel Oliveira August 29, 2013that does not work as was already mentioned in this thread
- Miguel Oliveira August 29, 2013@anotherguy, i think you misunderstood his post. he's not recursively spliting the parts of the array.
This solution will work in a pseudo-polynomial time (depends on the size of the integers to have a feasible space complexity) but it is a bit tricky because you must be sure to be using only N/2 numbers to achieve T/2.
The subset sum problem is NP Complete. If that worked, there would be a polynomial time algorithm for this problem and P = NP.
Find a counter-example for that code, it will help you understand how that can't work.
You can't use a greedy approach. See the example I gave earlier:
{1, 2, 30, 30, 30, 87}
array1 = {1, 30, 30} , array2 = {2, 30, 87}
However there is a solution {1,2,87} and {30,30,30}
Let S = Sum(all numbers) / 2, the sum of the elements each array shall have. I suppose N is reasonably small, like N <= 40. One approach would be
Work with 2 halves A and B of the array independently: A from indices [0, N/2-1] and B from [N/2, N-1].
Generate all possible sums of elements in array A. Use N/2 hash tables, one for each number of elements of the subsets, and put the sum of a subset in the corresponding hash table. There are 2^(N/2) subsets of A, this takes O(N/2 * 2^(N/2)) time.
Then generate all possible sums of B. For each subset of B, with X elements and sum Z, check if there is a subset of A in the hash table for sizes N/2-X with sum S-Z. There are also 2^(N/2) subsets and each lookup in a hash table takes O(1).
So this takes total time O(N/2 * 2^(N/2)) and O(2^(N/2)) space. For N=40, N/2 = 20 and 2^20 is ~1 million which is usually ok.
You can't solve these kind of subset problems with greedy solutions. Simple counter example: {1, 2, 30, 30, 30, 87}
var1 = 1 + 30 + 30 = 61 , var2 = 2 + 30 + 87 = 119
However there is a solution {1,2,87} and {30,30,30}
That kind of approach can take N choose N/2 time instead of (N/2)!
- Miguel Oliveira August 29, 2013sort of, but I love these kind of questions/problems :)
- Miguel Oliveira August 29, 2013@joe for the purpose of this problem, the simple LCS approach works. It would not work if we wanted to find out the palindromic string instead of just its length. Check the page wcipeg . com / Longest_palindromic_subsequence
The longest palindromic subsequence is one of the LCSes but it's not guaranteed that every LCS is palindrome.
"afala" and "alafa" are LCSes of "alfalfa" and its reverse, yet neither is palindromic.
right, it's not necessarily a palindrome. there are ways to make a LCS based approach work though (just found on the web but can't link it here due to this site restrictions).
anyway, i've given an efficient solution to this problem based on edit-distance
yes it is, but the nodes usually have a pointer to its parent. you can use that.
- Miguel Oliveira September 12, 2013this pointer is used for situations like deleting elements of the tree and is also useful here