oOZz
BAN USERGoogle+ ozslatersd
Preprocessing step:
Calculate squares of numbers from 1 to 100 (Note that we'll query the numbers that are less than 10000) and put the number and the square to a hashmap/hashtable value = the numbers from 1 to 100 and the keys are the corresponding square of that number, e.g.,
<1, 1>
<4, 2>
<9, 3>
...
<10000, 100>
Time complexity of the preprocess = TO(N), but since N is constant which is equal to 100, then time complexity is constant time  O(1)
Query Step:
Once the hashtable is created in the preprocessing step, all the queries can be done in in O(1) time. Of course, assuming that the hashmap/hashtable used has O(1) for get, put, containsKey operations.
Time complexity of the queries: O(1)
@Up
Easy tiger :) that's what i meant, sorry for the bad wording, but it's clear from the example that I gave, isn't it?
The point is this method is not accurate. This 6n+/1 formula is like saying "pick an odd number", because all the primes are odd, but in fact not all the odd number are primes.
Not all primes are in the form of 6n+1 and 6n1. This holds true up to a certain digits, but definitely not 10 digits:
1,000,000,000 / 6 = 166,666,666 (integer division)
166,666,666 * 6 = 999,999,996
999,999,996 + 6 = 1,000,000,002
when n = 166,666,667
6n1 = 1,000,000,001
6n+1 = 1,000,000,003
Both 1,000,000,001 and 1,000,000,003 are not prime:
1,000,000,001 = 1,001×999,001
However when when n = 166,666,668
6n1 = 1,000,000,007
6n+1 = 1,000,000,009
Which are both prime.
In conclusion, this method of generating primes holds true for most integer "n", but not always.
 oOZz July 29, 2014The problem statement says " NxN matrix which contains all distinct 1 to n^2 numbers" and this is an elegant solution. It's probably the answer the interviewer expecting too. +1.
@Eugene says it's linear time, but it's actually O(N^2) time and space, because input size is N^2.
Sorry the above code needs a few changes, because I typed too fast:
void rearrange(std::vector<int> &A) {
for (int i = 0; i < A.size() 1; i++) {
if ( ((i & 1) == 0 && A[i] < A[i +1])  ((i & 1) && A[i] > A[i+1]) ) {
std::swap(A[i], A[i + 1]);
}
}
}
@pratik Here are the trace output after each swap for your counter example:
Start:
2 3 0 1
3 2 0 1
3 0 2 1
End: 3 0 2 1
@srini
Start:
8 9 6 7
9 8 6 7
9 6 8 7
End:9 6 8 7
There are two O(n) solutions for this problem that does not require ordering.
1. You can find the median in O(n) and then rearrange the elements around the median
2. (Better Solution) If you notice the desired ordering, the even numbered elements are bigger (or equal) than the next element, and the odd numbered elements are less than (or equal) than the next element, of course I am assuming the array is 0 offset.
So, you can iterate the array and swap the elements that doesn't match this arrangements,e.g., swap A[i] and A[i+1], when i is even and A[i] < A[i + 1].
That's what I thought at first, because the problem definition didn't mention it otherwise. However, if the content of array A is modifiable then there is a O(n) solution:
int* permutation_sort(int *X, int* A, size_t size) {
for (int i=0; i < size; i++) {
// Note that values in A have offset 1, not 0
int index = A[i]  1;
A[i] = X[temp];
}
return A;
}

oOZz
April 21, 2014 unordered_map is the new data structure added to C++ STL as part of C++11 version (in <unordered_map> library).
Here is the direct quote from cppreference.com:
"Unordered map is an associative container that contains keyvalue pairs with unique keys. Search, insertion, and removal of elements have average constanttime complexity.
Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once hash is computed, it refers to the exact bucket the element is placed into."
Original map (<map>) implementation was done using a balanced tree implementation and therefore having the O(log N) time complexity to get/put/delete elements. However, <ordered_map> library is implemented differently as described above and have _amortized_ O(1) time complexity for get/put/delete operations.
Note that, if you go to actual manual page at cppreference.com, you can see the time complexities for each operations and you will see that worst case analysis in certain cases may vary from O(1) to (N), but if I were the interviewer I'd be OK with O(1).
This question doesn't sound right. Were you asked the contiguous subarray?
If the question is what's asked here then,
0. Initialize index_z = 0, index_p = N
1. Sort the array.
2. Set the index of first zero (index_z) and the first positive number (index_p)
3. If index_z is nonzero,
3.a if index_z = 0, then PN = 1
3.b. else if the index_z is odd, then calculate the product PN = [0, index_z).
Note that, index starts from zero, so odd index means even number of elements, and vice versa.
3.c. else (if index_z is even) calculate product PN = (0, index_z), i.e., both index 0 and index_z are exclusive.
4. Calculate the product PP = (index_p, n)
5. Return (PP * PN)
There is one edge case where all the numbers can be zero, so initialize index_p to N initially before step 2.
There are a number of maze solving algorithms. It's not clear from the question, but considering that this is from a programming/coding interview, by "suitable", I am assuming you're looking for the shortest path.
If there are multiple path solutions, breadthfirstsearch is more suitable finding the shortest path. Another good algorithm is A* algorithm. A* achieves better time performance by using heuristics.
Here is a really good answer from stackoverflow:
1. Use the logfunction to find out the magnitude m of your number. If the magnitude is negative print "0." and an appropriate amount of zeros.
2. Consecutively divide by 10^m and cast the result to int to get the decimal digits. m for the next digit.
3. If you came accross m==0, don't forget to print the decimal point ".".
4. Break off after a couple of digits. If m>0 when you break of, don't forget to print "E" and itoa(m). (Here I meant your own implementation of itoa, which is easy to implement)
Instead of the logfunction you can also directly extract the exponent by bitshifting and correcting for the exponent's offset (see IEEE 754, where 1st bit is sign, next 8 bits is exponent and next 23 bits significand). For instance, Java has a floatToLongBits etc. functions to get the binary representation and than you can create the string using bit manipulation.
Check out "w w w.geeksforgeeks.org/diameterofabinarytree/" for explanation and the solution for this problem.
Note that there is a very good O(n) solution provided, but it doesn't use parent pointers. I am very interested to see, if there is a better solution using the parent pointers though.
You can accomplish O(1) time complexity, by using extra space to keep track of the minimum, during push and pop operations.
Method 1:
Push the minimum so far and the new element in the stack as a pair, when you add the element to the stack. This will require double the space size of the stack, because for each element, you also save the minimum. Therefore, the space complexity is Big_Theta(n)
Method 2:
Keep another stack and push the min values along with the count of the min as a pair to the let's say, min_stack. For instance, when you push the element to the stack, if it's the new minimum, then push it to the min stack and set the count 1, if the new element is equal to the min value at the top of the min_stack, then increment the count.
In the second method, the implementation is a little bit more complex compared to the 1st method because of the cases when you do push and pop on the main stack. Heuristically, the additional space will be reduced compared to method 1, but in the worst case, where each element pushed is less then the previous element, it is still Big_Theta(n)
I think you're almost there. What about concatenating the the array with same array minus the last element?
1, 2, 3, 0, 6 becomes 1,2,3,0,6,1,2,3,0 and LIS is 4 (0,1,2,3)
5, 4, 3, 2, 1 becomes 5,4,3,2,1,5,4,3,2 and LIS is 2 (1,5) or 2(4,5)
5, 6, 7, 1, 2, 3 becomes 5,6,7,1,2,3,5,6,7,1,2 and LIS is 6(1,2,3,5,6,7)
For the unbalanced tree, you can't reconstruct the tree from it's inorder, preorder, post order, or level order traversals, because these traversals alone don't have enough information for you to figure out the shape of the tree.There are two methods you can use to reconstruct a tree from its serialized array.
Method 1
Use inorder+preorder lists or inorder+postorder lists. By using inorder along with postorder or preorder traversals will help you to build the tree, because postorder and preorder will tell you the root node and using the root on inorder will tell you the left and right subtrees. If you observe these lists closely you'll see a recursive pattern.
Method 2
Use the preorder or postorder traversals and save null values as keys when you visit a null left or right node. Null nodes will work as a markers to help you reconstruct the tree in the right form. Again postorder's last node is the root, and preorder's first node is he root node; you can go from the leaf nodes and up and reconstruct the tree.
Traverse the binary tree whichever way you want (preorder, postorder, inorder, level order, etc.). When you visit the node, check if the node exists in the hash set (or hash table), if it does then add it to the list, otherwise add the node to the hash set.
O(n) time and O(n) space
The solution provided here assume that there is a parent pointer, but it's a working solution. +1
If there are no parent pointers;
LCA(A, B)
1. Get inorder list from (A, B).
1.2. If there are no elements between inorder (A, B), then return the latter
1.3 else
1.3.a. Check the order of each element in (A,B) in postorder
1.3.b. Return the highest order element in postorder, which is the LCA
e.g., LCA(10, 40)
inorder : 10 20 30 40 80
postorder : 10 30 20 80 40
then LCA(10, 40) = 20
O(n) time, O(n) space
Can you explain a little bit more, maybe with an example?
What is the expected space complexity, because you said the solution has to be in place and then you're asking, if it can be done with one stack? I think you're confusing the problem with the spiral traversal order of a binary tree, which is done with 2 stacks, but this question is the other way around.
1. Get a tiny domain name like bit.ly, goo.gl, or is.gd
2. Create a URI to shorten the website with the actual URL, e.g., h t t p: / / w w w.myverylongwebsitename.com/blab/blah/blah/ becomes h t t p : / / goo.gl/mVLwsnWx. You can do this by using a good hash function that generates a unique and short string for the website.
3. Implement h t t p: / / goo.gl/mVLwsnWx as a HTTP redirect to the actual website.This can be implemented as a RESTful service, so when you do HTTP.GET h t t p : / / goo.gl/mVLwsnWx, the service redirects you to the actual website.
Short answer "Saddleback Search"
This is a sorted matrix, i.e., the rows and columns are sorted, so you can take advantage of that.
You can either start from the topright M[0][n1]
While until key found in M
Let M[i][j] be the current element
if M[i][j] < key, go down (M[i+1][j])
else if M[i][j] > key, go to left (M[i][j1])
Or you can start from bottom left M[n1][0]
While until key found in M
Let M[i][j] be the current element
if M[i][j] < key, go to right (M[i][j+1])
else if M[i][j] > key, go up (M[i1][j])
Total running time is O(n)
Thank you, @Miguel Oliveira. Good point, but that's subject to interpretation, isn't it? If you have all negatives, then empty set is 0 and that's the largest element.
If the question suggests that the sub array can't be empty, then you're right, you must return the greatest negative.
8 & 7 = 15 not 0
 oOZz April 19, 2015