CareerCup

#,#,#,#,#....,#,*,#
0,-1,-2,-3,....,-N,-N+1,-N,

So you have -N on two positions. You calculate the distance - 1, you get it.

Yes, indeed. This the solution I provided:
- find the pivot place O(N) = log N
- run two binary searches O(N) = log N

*scan from left to right.

Sure. Imagine you have a hash table, that is empty at the moment. You also have the maximum distance max_dist = -1. Scan the result array ([1 0 -1 0 -1 -2 -3 -2 -1]) from left to one.
1) if 0, then max_dist = i
2) else
---- if(hash_map.contains(arr[i]) then max_dist = max(max_dist, i - hash_map.get(arr[i] - 1)
--- else hash_map.set(arr[i], i)

So the hash map is used to store, minimum index, that a value arr[i] was met and is then used to calculate maximum distance. 0 is considered in a special way, as it stands for: equal amount from the beginining.

Consider * and # as 1 and -1. Then calculate the sum starting from left, and store it in the array.
Example: *##*###** becomes 1 -1 -1 1 -1 -1 -1 1 1 and the sums = [1 0 -1 0 -1 -2 -3 -2 -1].
As you can see the places where 0 appearance says that there is an equal amount of zeros and one,
starting from the beginning of the array. In the places where the number matches, let's say at
index i and j, the sum between i + 1, and j was equal 0.

In the second step you need to find the maximum distance. Consider using hash_map for storing
the first occurence of every number. Calculate the size.

Yeah, remove 8. My bad.

It is. Originally you have an array {1,2,3,3,9,9,9,8,10,12,13}, and it's then rotated right by 9, so it becomes {3, 9, 9, 9, 8, 10, 12, 13, 1, 2, 3} (the first element from the original array, is moved to index 9, generally new_index = (original_index + 9) % array_size.

You start a DFS/BFS everytime you meet a cell with 1 and assign it the current value of the counter and all the cells with value 1 you meet while DFS/BFS. The counter should be incremented everytime DFS/BFS is done. Consider cells with value smaller than counter, but greater than 1 as visited. I suggest to start with the value counter 2, as it allows to skip the special case, when the label should be equal 1. (It's not said that the first label has to be equal 1).

Suffix tree is a great thing and would work however I think you should notice two things:
- it's quite complex to implement it within interview time
- there is a number k given.
It should lead you to other solution - why just not to browse the sequences of size k from left to right? I.e having a->b->c->d, and k = 3 we got a->b->c, then remove first element, and add the next from the sequence to the end what results in b->c->d. This has a linear time. Moreover, we maintain a map (hash table) that matches the sequence with the counter. This leads to O(n log n) (c++ map), or O(n) solution (c++ unordered_map).

What about using a queue to generate a breadth first search through the tree and when it is done then:
1. take three first elements from the queue A, B, C and then: B->right = A, B->left = C,
2. assign curRight = C
3. while(queue is not empty)
- take two elements A B from the queue
- A->right = curRight, A->left = B
- curRight = A
4. set root = curRight

Handle the edge cases.

I am glad I am not the only one who shares this point of view :)

Isn't it the memory/complexity tradeoff problem? Can't see how can it be done meeting the requirements.

1. Create the hash map of the characters of s1
2. Initialize the counter to 0
3. Iterate over S2 in the way:
- if current character in HashMap then counter++
- otherwise counter = 0
4. Stop when counter == HashMap.size()

I dont think you can write this length code within an interview....

Yeah, the subarray is subarray :) Vote up for you.

Imagine you sort the list of N strings, and from the sorting you create a long new string by concatenating the elements of the list. Now the requirement of the task is met. But if you have a concatenation of prefixes abcd and ecd that is abcdecd you may simplify it as abecd - both prefixes appears here as subsequences. This step might be done while concatenation. If we have string L and R, and we need to concatenate them, and R contains a substring of L, then we can remove it from L.

I think in this case it's about a sub-array that doesn't have to be contingous.

If the subarray is contingous then you can go for Kadan's algorithm suggested by mindless monk. If you need to consider subsequence then dynamic programming approach, as the optimal substructure property is met: you may process the task from left to right, as if A is a solution of size N, and A is optimal it has to be also a part of a solution of B, of size N + 1.

So you should build a helper array M, where

for each i < N
 for each j < i
   if a[i] > a[j] && b[i] + M[j] > M[i] then
    M[i] = b[i] + M[j]

And then for the maximum value of M reconstruct the solution.

The remove operation from LinkedList is O(n). As it's in the loop then the complexity is O(|string1| * |string2|). But as he suggests to use the doubly linked list we can keep in the hash table directly the nodes of it. So then the remove would be O(1) what gives linear complexity.

Topological sort.

The solution to this problem may base on the dynamic programming approach to palindrom finding (google it, as there is plenty of implementation). Then when we have a table P[i][j] and it's value is greater than zero, we know the value between i and j in the original string is a palindrom, so we may print it. The solution would be O(n^2).

Ok, maybe I don't understand the question: we have an array, of size K, where every element is a string of size N? So in this case we have K=4, N=3?

Player1 is liked by {1,2 }
Player2 is liked by {3, 4 }
Player3 is liked by {1,4}

Fans = {1,2,3,4}

Choose player1: Remainig Fans: {3,4}, Remaining players: Player2 = {3,4}, Player3 {4}
Choose player2: Remainig Fans {}

When we remove a player, we remove a fan related to that player, but also the players that are liked by this fan.

Why? Every players is liked by two fans. So if we choose a random player, we remove it and its fans, we have 2 players and 1 fan remaining. So now choose again a random player, and we remove the last fan. Fan set is empty. Answer=2. Please tell me if I am wrong as I had a tough day and may have some problems with thinking.

What about a greedy approach? We have a set of fans and an array of players, sorted according to numbers of fans they have. Till the set is not empty, we choose a player that is liked by the biggest amount of fans (first in the sorted array). Now we remove those fans from the set, update the table (if fan F was removed, then decrease the counter of fans number, for a player, that had F as a fan) and resort. Repeat. The number of iterations, would be the searched minimum. I dind't look for a counter example, but still can't prove it works.

It's a mask having all bits at even positions set.

Yeah, I agree that you should rabin-karp, but instead of one hash, you should have also the second one, counted for a word that was reversed, and match against those two hashes instead of one.

Yeah you are right. Minus the solution please.

Yeah, I added an example.

-----------------------------------------------------------------------
The solution below fails for the case when the number is 12. Please take a look at Zoro post, as you get a correct solution there!!!
-----------------------------------------------------------------------

Take a look at the bit represantation of number that is power of 4 you get:

1 = 000000001
4 = 000000100
16 = 000010000
64 = 001000000
256 = 100000000
...
So the sum off all above gives us a mask
mask = (...)101010100 = 0x55554

So now we can write a function

bool isPowerOf4(int n)
{
int mask = 0x55554;
return !(n & ((n & mask) - 1));
}

Why does it work? Check what happens if n is a power of four:

for n = 16
n = 10000, mask = 10100
n & mask = 10000
(n & mask) - 1 = 01111
!(10000 & 01111) = !(0) == true

for n = 8
n = 01000, mask = 10100
n & mask = 00000
(n & mask) - 1 = 11111
!(01000 & 11111) = !(01000) = false

for n = 20
n = 10100, mask = 10100
n & mask = 10100
(n & mask) - 1 = 10111
!(10100 & 10111) = !(1000) == false


Regards Joe

Generally the DP approach, except finding the solution step, contain also a step of building a structure of optimal solution, that is skipped sometimes.

The matrix filling in this case looks like:

M[i][j] = if Weight[i] <= W then M[i - 1][W - Weight[i]] else M[i-1][j]

So you choose or the solution (i - 1), with the value K - (current value), or you choose the previous solution. You need to remember which way you choose. Then when finding the solution you need to iterate back using previously stored steps to rebuild the structure of solution.

I propose instead of having array of int, let's say

int M[N][K];

An array of structure (or pairs)

struct Cell{
int value;
struct Cell * prevCell; // or coordinates of the previous cell in the array
};

I would treat it as a knapsack problem, where every number of the array is a weight and the limitation is the sum, then every time we get the sum we print the output. Using dynamic programming the solution could be n^2.

I propose a recursive solution using memoization. You start DFS from the source, visiting all the nodes till you meet destination. If you can reach a destination from a given node, then you add it to the sum, otherwise you don't. Please see the following pseudo code.

int findAllNodes(Node * curNode)
{
	// don't consider already visited nodes
	if(curNode.pathSize)
		return pathSize;
	// if node is a destination, return that your reached destination
	if(curNode == destination)
		return 1;
	int sum = 0;
	// consider all the neigbours of a given node and count different nodes
	for(int i = 0; i < curNode.neighours.size(); i++)
		sum += findAllNodes(curNode.neighbours[i]);
	curNode->pathSize = sum ? sum + 1 : 0;
	return curNode->pathSize;
}

Hi,

obviously you can use BST and then you may try to find floor/ceil (google it for BST) of the given value and choose what is closer to the given value.

Check Reservoir Sampling on wiki please. In this case k = 1.

I would like to extend the solution of amber by providing comparator function, that compares sorted strings, something like:

bool cmp(string & one, string & two)
{
	string oneSorted = sort(one.begin(), one.end());
	string twoSorted = sort(two.begin(), two.end());
	
	return oneSorted.compare(twoSorted) < 0;
}

Then you may just apply this comparator to sort i.e a vector of strings:

sort(v_string.begin(), v_string.end(), cmp);

A Pythagorean triple consists of three positive integers a, b, and c, such that a^2 + b^2 = c^2:)

Is it going to work, when the diagonals create not a valid X? Like in the example in the question, when there is an intersection, but X is not valid because the intersection point is wrapped by some other 1s?

To my mind you should add a checking after all if the found intersection is valid or not.

Make a list of squares {1,9,16,25,....} and every square add to a hash table. Then take every two squared elements from a list from previous step and check if their sum is in a hash table. Complexity O(n^2).

Thanks, the page seems to be very cool not only for this particular case.

It looks like. The reversal is maxlayalam, so the longest common subsequence is: malayalam, the lenght difference 1, so it works.

I think that the LCS approach should work fine. The longest subset in this case would be a base of a palindrom, as we are comparing the same set, just in a different order. Please give a real counter example.

Hi, it has been some time already, but you may find exactly the same problem in the Cormen's famous book, where he simplifies the problem to finding maximum sum, by converting the stock values to it's day to to day changes.

There are two approaches you may apply. The first one is to reverse the input string and find the LCS of the input string, and it's reversal. This gives you the lenght of the longest palindrom. Now you substract the LCS value from the lenght of the string and you get the k - so just check if it matches.

The second approach just looks for a palindrom. Let's say p[n] is a palindrom with lenght n. Let l will be begining, end e the end of a palindrom. Then we can see that:
1) p[l] == p[h], then we need to check p[l+1] == p[h - 1], i.e abcba, where p[l] == a == p[h]
2a) p[l] != p[h], then we need to check p[l+1],p[h] (we removed p[l])
2b) p[l] != p[h], then we need to check p[l], p[h-1], (we removed p[h])

Now simply use this in your dynamic programming aproach. If you have a problem with that, I am more than glad to help you more.

As I was bored, I typed the code for the second solution:)

bool isKPalindrom(string input, int k)
{
        int answers[input.size() + 1][input.size() + 1];
        int N = input.size();
        for(int i = 0; i <= N; i++)
                for(int j = 0; j <= N; j++)
                        answers[i][j] = 0;


        for(int gap = 1; gap <= N; gap++)
        {
                int l = 1;
                int h = l + gap;
                for(; h <= N; l++, h++)
                {
                        if(input[l-1] == input[h - 1])
                                answers[l][h] = answers[l+1][h-1];
                        else
                                answers[l][h] = 1 + min(answers[l+1][h], answers[l][h-1]);
                }
        }

        return answers[1][N] <= k;
}

I thought rather bout a single variable.

Nice one!

The inplace quicksort doesn't remain the order.

-1 1 3 -2 2 and pivot 0 it would give -1 -2 3 1 2 instead of -1 -2 1 3 2

The n^2 solution would be:

Keep trace of a first met positive number = P. If you find a negative number = N, and P is set, then store P into T, insert value of N into positon P, shift the table right from P to N positon, insert T into P+1.

Can we really do it in O(n) without extra space?

Yeah, you are right:) My bad:(

Hi,

For me it sounds like a greedy approach:

Firstly sort all the works according to it's start time in an increasing order, then according to the finish time in an decreasing one. So what you do now: take the first event that appears, let's name the start time S(i) and finish time E(i). Now take the first event that S(i+1) > E(i). If there are several events starting at the same time take the one that E(i+1) has the largest value (because we are trying to find the longest time). Proceed till the end.

Ah yeah, sorry it was arround 2 am when I took a look at this: then it's absolutely correct :) The problem now is that you make some extra work analysing the same node several times instead of just once. But the correctness of solution is preserved.