oOZz
BAN USERGoogle+ ozslatersd
@mayur The data structure is called hashtable, so I didn't mean java.util.Hashtable. In Java though, both java.util.Hashtable and java.util.HashMap have (amortized) constant time put, get, delete operations. The only difference between them is java.util.Hashtable is synchronized, but java.util.HashMap is not.
- oOZz June 15, 20131. Put each letter tiles to the hashtable. Characters are keys and the character counts are values.
2. for each word in the dictionary dictionary
2.a. for each character in the word
check if the character is in the hashtable as well as how many times it is used
if it doesn't next word
print the word if all the characters of the word exist in the dictionary
Sorting seems too obvious. If this is a legit Google interview question, I'd suspect there must be a better solution than O(n log n).
I can think of a linear solution, but it has a lot of assumptions; if the numbers are small positive numbers, let's say [0,31), then you can use a 32 bit integer and set the bits with the corresponding number in the int array. e.g., S = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11, 3} becomes binary digit:
00000000 00010000 00001111 00111110
Then you can check the longest contiguous set bit sequence. This is linear time, but the worst case is the length of the bit vector, not the array length. Similarly, you can use 64 bit number for [0,64), for bigger numbers, you'll have to use a bit vector or a bit set.
Note that this solution will only make sense, if the numbers are positive, small, and/or there are a lot of repetitions.
@Dumbo you can get the connected components in liner time. However, how will you create a graph with edges that differ in value by 1? Doesn't that require you to search the graph every time you try to insert a node/vertex and add the edge? That'll be a quadratic operation.
- oOZz June 14, 2013@arun_lisieux it works buddy, but don't take my word for it, here is a unit test, go ahead and test it yourself.
@Test
public void testIsBST() {
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(10);
root.left.right = new Node(11);
boolean bst = isBST(root);
assertEquals(false, bst);
}
The solutions described here is O(n log n) due to sorting. There is an O(n) solution using a hashtable, therefore, this is an O(n) space solution:
1. Put numbers in the hashtable (this in O(n))
2. Iterate the array and subtract each element from sum and check if the result is in the hashtable.
2.a. if it's in the hashtable, print the two numbers
2.b. if it's not then continue
There is a special case though, when the array contains duplicates. In that case, you will also need to save the count of the number and process accordingly. e.g., if the array is [2,3,5,10] and sum = 6, 6-3=3 and 3 is in the hashtable, so you need to check if the count of the 3 in the hashtable is >=2.
You need to use the definition of BST, i.e., the left node is smaller and the right node is bigger than the parent node, and traverse the tree to check if that condition satisfies.
public boolean isBSTMain(Node root) {
return (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
private boolean isBST(Node node, int min, int max) {
if (node == null) return true;
if (node.data < min || node.data > max) return false;
// left should be in range min...node.data
boolean leftOk = isBST(node.left, min, node.data);
if (!leftOk) return false;
// right should be in range node.data..max
return isBST(node.right, node.data, max);
}
This solution is O(n)
- oOZz June 14, 2013You can use a hashtable and insert the arrays to the hashtable.
For union, after insertion the hashtable will have all unique keys (aka, union) of two arrays, so return the keys in the hashtable.
For intersection, insert both arrays to the hashtable, before inserting each element though check if it's there (containsKey in Java), if it's not there then insert set the count 1, if it's there, then increment count. Then iterate the items on the hashtable and print keys, that has count >=2, which are the elements of the intersection.
O(m+n) time, and O(m+n) space.
You can use a bitvector or a bitset instead of a hashtable and save space with the same approach.
@Anonymous. Respect my friend! The code mostly works (see below), but it's still impressive to come up with a DP solution in 1 hour during lunch. (+1) I also agree with you that the DP problems are hard to solve in 45 mins without a compiler and therefore, they're better suited for coding competitions than job interviews.
Your code for input [-1,-2,-3] fails. It outputs 1, but neither 4 nor 6. I've asked the same question to @LAP for clarification whether the empty set is a valid subarray and its sum is 0, but he/she didn't answer. I'd assume that it is. Then IMO, [-1,-2,-3] should return (0 - (-1,-2,-3)) = 6 and [4,-1,7] should return ((4,-1,7) - 0) = 10.
I've also just made a small change to the code that I posted above. It works with the empty set assumption. Though it's a O(N) time and O(1) space and only 20 lines, no one seems to not like it LOL Happy coding!
This is a variation of max continues sum problem. There is O(n) running time and O(1) space solution.
1. Find the max continues sum
2. Find the continues min sum
3. return 1-2
public static int findMaxDiff(int[] a) {
int maxsum = 0;
int maxEndingHere = 0;
boolean wholeArray = true;
for (int i = 0; i < a.length; i++) {
maxEndingHere = Math.max(maxEndingHere + a[i], 0);
if (maxEndingHere == 0) wholeArray = false;
maxsum = Math.max(maxsum, maxEndingHere);
}
if (wholeArray && maxsum > 0) return maxsum;
int minsum = 0;
int minEndingHere = 0;
for (int i = 0; i < a.length; i++) {
minEndingHere = Math.min(minEndingHere + a[i], 0);
minsum = Math.min(minsum, minEndingHere);
}
return maxsum - minsum;
}
Running time is O(n). Space O(1)
- oOZz June 10, 20131. Find the max continues sum
2. Find the continues min sum
3. return 1-2
public static int findMaxDiff(int[] a) {
int maxsum = 0;
int maxEndingHere = 0;
boolean wholeArray = true;
for (int i = 0; i < a.length; i++) {
maxEndingHere = Math.max(maxEndingHere + a[i], 0);
if (maxEndingHere == 0) wholeArray = false;
maxsum = Math.max(maxsum, maxEndingHere);
}
if (wholeArray) return maxsum;
int minsum = 0;
int minEndingHere = 0;
for (int i = 0; i < a.length; i++) {
minEndingHere = Math.min(minEndingHere + a[i], 0);
minsum = Math.min(minsum, minEndingHere);
}
return maxsum - minsum;
}
Running time is O(n).
- oOZz June 10, 20131. Create a matrix from the characters from the input file. For example your example will generate this 3x3 matrix below. Each row is a line and each character will be in different columns including the spaces, so the number of columns will be the maximum line length.
| a b c |
| d e f | = matrix[3][3]
| g h |
2. Transpose the matrix:
public static char[][] transpose(char[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for(int j =0; j < matrix[0].length; j++) {
if (i > j) {
// swap the characters in diagonal
char temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
return matrix;
}
3. Then print the matrix.
- oOZz June 10, 2013Example for Alphabet C, A, B:
Imagine this is your dictionary below.
1. C
2. CAC
3. CB
4. BCC
5. BA
These are the steps based on the example above.
1. Compare line 1 and line 2. Create vertices C and A
2. Compare line 2 and 3. Create vertex B. Create Edge E = A->B, meaning A comes before B
3. Compare line 3 and 4. Add edge C->B meaning C comes before B
4. Compare line 4 and line 5: Add edge C->A
This yields to a DAG below.
C->B
C->A
A->B
C->A->B
| ^
|---------|
and the topological sort will give you:
C,B,A
As you can see, you cannot determine the correct order of the alphabet, if there is a directed cycle in the graph. So the dictionary given must generate a DAG to find a solution.
You can create a directed graph where vertices represent the characters in the language and the edges represent the order relationship, i.e., if there is an edge Eij, then character Vi comes before character Vj in the alphabet.
You need to process two consecutive words in the dictionary at a time to determine the precedence relationship of the characters, so it will take O(N * M) time to create the graph, where N is the number of words and M is the length of the words.
Then use topological sorting to get characters in the correct order in O(|V| + |E|) time
You can simplify this by
1. Find the mid point by using the slow and fast runners and then push the first half to the list to a stack from the slow runner. Note that, at this point slow runner is pointing the middle of the linked list and the elements in the stack are in the reverse order.
2. Iterate from the middle to the end of the list with slow pointer and compare the top of the the stack at each iteration. If they don't match return false.
If you can't use extra storage, then you can solve this recursively:
bool isPalindrome(Node** left, Node* right) {
if (!right) return true;
bool ispal = isPalindrome(left, right->next);
if (ispal == false) return false;
// check if the values are the same
ispal = (right->data == (*left)->data);
// go to next
*left = (*left)->next;
return ispal;
}
Call this function like:
bool isp = isPalindrome(&head, head);
Note what the Floyd algorithm says a fast runner (hare) and a slow runner (tortoise), it doesn't say how fast they should be. For any step size >1 the algorithm will work to find the cycle/loop. It may take more or less steps to finish, depending on the loop size, the collision point, and the step size.
Firstly, step size of 2 is practical when iterating the linked list. Secondly and more importantly, step size of 2 is needed to calculate the collision point and/or the length of the loop.
Here is the explanation from Wikipedia:
The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0, xi = xi + kλ, where λ is the length of the loop to be found. In particular, whenever i = kλ ≥ μ, it follows that xi = x2i. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence than the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value xμ in the sequence, using the fact that λ divides ν and therefore that xμ = xν + μ. Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which xμ + λ = xμ.
The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at xi, and the other (the hare) at x2i. At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of i > 0 for which the tortoise and hare point to equal values is the desired value ν.
The solution your looking for is a "distributed counter". You can search about this topic, because I cannot include links here. A good approach to solve the scalability design problems is that starting with a small scale version of the solution and then extend your solution for a large scale version.
- oOZz May 29, 2013
This won't work, because you're not checking the case, where let's say, the sum is 20; 20-10=10 and 10 exists in the hashtable, but you're currently processing 10. You need to check if there are two or more 10s in this example.
- oOZz June 15, 2013