joe kidd
BAN USER 1of 1 vote
AnswersYou are given an array, that is sorted, however was rotated to the right by a certain distance. The array may contain duplicated values. Find the index of a given element in the array.
 joe kidd in India
Example: {3, 9, 9, 9, 8, 10, 12, 13, 1, 2, 3}, element = 3, returns, any of indexes that 3 is present. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm
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.
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.
 joe kidd August 03, 2014You 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).
 joe kidd August 01, 2014Suffix 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.
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.
 joe kidd November 15, 2013If 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.
 joe kidd November 15, 2013The 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.
 joe kidd November 09, 2013The 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).
 joe kidd November 04, 2013Ok, 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.
 joe kidd October 24, 2013What 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.
 joe kidd October 24, 2013
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[i1][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
};

joe kidd
October 16, 2013 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;
}

joe kidd
October 09, 2013 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);

joe kidd
September 23, 2013 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.
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[h1], (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[l1] == input[h  1])
answers[l][h] = answers[l+1][h1];
else
answers[l][h] = 1 + min(answers[l+1][h], answers[l][h1]);
}
}
return answers[1][N] <= k;
}

joe kidd
August 28, 2013 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?
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.
So you have N on two positions. You calculate the distance  1, you get it.
 joe kidd August 04, 2014