CareerCup

8 & 7 = 15 not 0

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 6n-1. 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

6n-1 = 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

6n-1 = 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.

The 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.

it look he changed the name to Guy.

No srini, they are both linear time solutions. In solution 1 you, you first find median in O(n) and then rearrange the elements in O(n), so it's 2 *O(n) , which is O(n) asymptotically, not O(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

Here is the C++ code for solution 2:

void rearrange(std::vector<int> &A) {
    for (int i = 0; i < A.size(); ++i) {
        if (((i & 1) == 0 && A[i] > A[i +1]) || (i & 1) && A[i] < A[A+1])) {
            std::swap(A[i], A[i + 1])
        }
    }
}

or swap A[i] and A[i+1], when i is odd and A[i] > A[i + 1].

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;
}

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 key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time 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).

Stop spamming with the same questions.

for(i = 0; i < 32; i++)
{
	dec = dec * 2 + (bin[i] == '1' ? 1 : 0);
}

Are you seriously asking how to convert from binary to decimal here?!

+1 from me, for just mentioning trie :)

This is O(N log N) time solution due to sorting at step 1. The other steps are linear time.

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, breadth-first-search is more suitable finding the shortest path. Another good algorithm is A* algorithm. A* achieves better time performance by using heuristics.

@eugene.yarovoi +1 great analysis. What about using Fibonacci sequence?
1 forward
2 backward
3 forward
5 backward
8 forward
...

Here is a really good answer from stackoverflow:

1. Use the log-function 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 log-function 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/diameter-of-a-binary-tree/" 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.

Yes, for the first method, you create 2 arrays, but the second method creates only 1 array and it has a linear time solution.

+1 EOF. This is not the same problem. This is partitioning the subarrays not subsets and there is a really easy solution that works in O(n) time and O(1) time that I've described above.

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)

@Up The original problem was subset sum and now they added "continuous" part! I've seen this a lot of times, where people keep changing the problem statement after posting.

1. First pass, find the sum S of all the numbers in the array
2. Second pass, keep a running sum RS and check if RS == (S - RS), return true
3. Return false at the end

This is the classic subset sum problem, which is asked here many many many times before and is NP-complete problem. You can check out en.wikipedia.org/wiki/Subset_sum_problem for more info.

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)

This will work, but it's very inefficient. Imagine a tree that goes left->left->left->...->left or right->right->right->...->right, then your array will have a lot of sparse elements.

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.

If you do level order traversal and only mark the beginning of the levels, that won't tell you if the node is a left or right node. This will only work for a perfectly balanced tree.

Alright point taken!

If the numbers are repeated more than once, then you need to use a hashtable with elements being the key and the element count is the value. Only add the elements to the list, if the element exists in the hash table AND the count is 1.

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 post-order
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

Good explanation for all the options I can think of. +1. Why is the worst case of hash set solution is O(m+n+R) though? Isn't it O(max(m,n))? Can you explain?

Nice and clean. +1.

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.

how exactly?

@ Chih.Chiu.19
Why is my solution O(n^2)?
This is a linear algorithm, note that there is only one loop.

I second @Chih.Chiu.19, this is a good solution and it's well written. +1 my friend.

@Chih.Chiu.19
I wish I could claim credit lol, but no it's not mine and it's been around for quiet some time.

If I ever invent one though, I wouldn't call it "Saddleback", maybe "Oz Sort" :))

Like @Apostle's solution below, I was thinking of using min-heap of size 5, but this solution is better. Good job! +1 from me.

@ashot madatyan I'd agree with you, if the problem didn't say that there are only 100 numbers. Again, if you normalize the upper and lower bounds, the sum will always be 5050, so you can even define this as a constant.

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.

Sorry, I've just realized that you've changed the question, after I submit the answer. I said this algorithm is O(n) for square matrix because O(2n) = O(n), but i general case it runs O(n+m) as you mentioned.

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 top-right M[0][n-1]
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][j-1])

Or you can start from bottom left M[n-1][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[i-1][j])

Total running time is O(n)

what is the time complexity of this solution?

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.