arun_lisieux
BAN USERI'm a guy who plays a role similar to SDET and tries to improve my skills in problem solving and Data Structures.
- 1of 1 vote
AnswersGiven a string, find the longest possible even palindrome (length of palindrome is even) from it.
- arun_lisieux in India
Eg:
Input: abcicbbcdefggfed
Output: defggfed (length is 8)
Available palindromes are
1) bcicb - has odd length
2) cbbc - even length
3) defggfed - longest palindrome with even length
This question was asked in a telephonic interview for my friend. I will be posting his solution in a day.| Report Duplicate | Flag | PURGE
Groupon Software Engineer / Developer Algorithm Arrays Coding String Manipulation
@coding.arya
Complexities should be as follows
Space: O(m), where m is the number of unique elements from the given input of n
Time: O(n)
@Ganesh
Sorting takes O(n log n).
Can you elaborate on a bit on how to get the number of events?
Heap returns the min or max in O(1) time. Also, one problem I see is removal of elements from the heap when the time window slides.
@anonymous - The interviewer was ok with this parameter?
- arun_lisieux June 14, 2013Will monitioring the number of clicks from an IP be feasible? It might be more of analytics rather than run time check.
- arun_lisieux June 14, 2013Correct me if I'm wrong, I think this would not work for the below case. The correct approach to this problem is the one posted by vgeek.
---------------------------5
-------------3 10
--------------------------11
PS: Forgive me for the poor tree structure.
Basically 5 is root of the with 3 as left child (3 has 11 as right child) and 10 as right child.
@JSDUDE
I'm aware of an O(m+n) approach which works if the arrays are sorted. If your approach works on un-sorted lists as well, please post it.
@cdonthini: As long as the information is shared with only one person (instead of everyone). This solution should work.
- arun_lisieux June 13, 2013This can be done in a single pass without the need for counting. Please see my post above for the algorithm.
- arun_lisieux June 13, 2013@aka
We would need some kind of variable (flag or boolean or integer) to keep track of alternate elements, right? I'm not aware of a method without this. If you know of a method, kindly post it.
This method traverses the string twice. The extra traversal can be avoided. While reversing the whole string, maintain a flag isNormal and flip it at every word. If it is true, push the characters into a stack and pop them. This prints the words in normal order and reduces the time complexity (of course, extra space of largest word is needed).
- arun_lisieux June 09, 2013@prashanthreddy.mtech
Start from index 0
3-2 = 1
move 1 index in the array
3-1 = 2
move 2 indexes in the array
3-1 = 2
move 2 indexes in the array
3-3 = 0
Element found!!!
@Anonymous
In case of even sized matrix, (fwd==bkw) might not work.
I think It should be changed to (fwd < bkw)
Shouldn't this be O(m+n) rather than O(m*n)???
You are just iterating through the whole matrix once in this approach...
@oOZz: Using a stack to compare the elements will work. This might work faster as you can store the nodes in the stack as you slide the slow runner. You dont need the extra traversals reverse the list and revert it back. But this uses n/2 extra space. Decent solution if extra space is not a concern.
- arun_lisieux June 01, 2013Oops. My bad. Sorry.
- arun_lisieux May 31, 2013Heap is a good choice. If the mapping has to be stored as well, Priority queue can be used.
- arun_lisieux May 31, 20131) Use the two pointer method till first points to middle and second points to end (both even and odd lists should be handled)
2) Reverse the list from head till middle
3) Compare both the lists and report true or false
4) Reverse the first half again and revert the list to its original form
Consider this scenario.
1->2->1
Moving the 2nd pointer by 3 might not work in this case.
It seems to work in a list larger than 3, like the ones below.
1->3->5->2->4->2....
1->3->5->2->4->5...
Please let me know if I missed something.
@Anonymous
It would be nice if you can comment on algorithm/code rather than my display name.
PS: The very reason I have posted the algorithm before code is because the code is too long.
Algorithm:
1) Have a method to print the diagonal, given the top and bottom pointers
2) Start from top left (initially both pointers point to (0,0)) and iterate the pointers along the perimeter till top and bottom pointers hit the top right(0,n) and bottom left (m,o) corners
3) In each iteration, print the diagonal using the method defined in step 1
4) Now iterate the top and bottom pointers from the their corresponding positions to bottom right corner of the matrix (m,n)
5) In each iteration, print the diagonal using the method defined in step 1
Below is a solution given in Java. Let me know if something is wrong or can be improved.
public class Coordinate {
int rowPosition;
int columnPosition;
//Default Constructor
public Coordinate(){
}
//Parametrized Constructor
public Coordinate(int x, int y){
rowPosition = x;
columnPosition = y;
}
}
private void printDiagonal (int[][] input, int count, Coordinate top, Coordinate bottom) {
/*Checking if coordinates of the top parameter are within the boundaries*/
if ((top.rowPosition > count)
|| (top.rowPosition < 0)
|| (top.columnPosition > count)
|| (top.columnPosition < 0)){
return;
}
/*Checking if coordinates of the bottom parameter are within the boundaries*/
if ((bottom.rowPosition > count)
|| (bottom.rowPosition < 0)
|| (bottom.columnPosition > count)
|| (bottom.columnPosition < 0)){
return;
}
/*Printing the values of the diagonal from top to bottom*/
while ((top.rowPosition != bottom.rowPosition) && (top.columnPosition != bottom.columnPosition)){
system.out.println (input[top.rowPosition][top.columnPosition]);
top.rowPosition++;
top.columnPosition--;
}
system.out.println (input[bottom.rowPosition][bottom.columnPosition]);
}
public void printDiagonalsInMatrix (int[][] input){
Coordinate top = new Coordinate(0,0);
Coordinate bottom = new Coordinate(0,0);
int count = input.length;
/*Iterating till top reaches top right and bottom reaches bottom left*/
while ((top.columnPosition < count) && (bottom.rowPosition < count)){
printDiagonal(input, count, top, bottom);
top.columnPosition++;
bottom.rowPosition++;
}
/*Iterating till top and bottom reaches bottom right*/
while ((top.rowPosition < count) && (bottom.columnPosition < count)){
printDiagonal(input, count, top, bottom);
top.rowPosition++;
bottom.columnPosition++;
}
}
If extra space is not a problem, the below approach should work.
1) Compute two integers by parsing the first two lists (assuming the numbers stored in the list are within integer's size. If not, any of the recursive solutions in this thread should be fine).
2) Add both the integers and store it in a resultant variable
3) Break down the digits in the resultant variable and store it in the third list
@ao
True, initial solution will not work.
How about doing this recursively for each node, storing the sum of depths of left and right subtree along with the node and then searching for the node with highest value.
@asenthilkumargce
My algorithm will actually remove all elements to the left element 4. The result will be sorted. But as you pointed it's not the largest possible sorted sub sequence. Thanks for pointing it out.
@ EK MACHCHAR
Assuming the definition of words likely to be swapped to be words with maximum of one letter difference, I give the below algorithm. Let me know if I have missed anything.
1) Define a method isSwappable, which accepts two words, counts the number of letters in both the words and returns true if both of the words have a maximum of one letter
This can be done by maintaining a hash (array of size 26) to keep track of the count of each letter in the word.
2) Make the calls to the isSwappable method from inside of a nested loop
This compares the current word from the list to rest of the list
3) Maintain a pointer currentInsertion (by default, this points to currentPosition + 1). If two words are swappable, swap the jth element with currentInsertion and increment currentInsertion. Continue next iteration where i equals currentInsertion with rest of the list.
for (int i = 0; i < list.length; i = currentInsertion){
for (int j = i+1; j < list.length; j++) {
if (isSwappable(list[i], list[j]) {
temp = list[j];
list[j] = list[currentInsertion];
list[currentInsertion] = temp;
currentInsertion++;
}
}
}
4) While grouping swappable elements, keep track of the following
a) count of elements in current swappable group
b) count of elements in max swappable group and
c) starting index of swappable group with largest count.
If current count is greater than max count, replace max count with current count and assign starting index of current group to corresponding pointer.
5) Print count of elements in largest swappable group from its starting index
@dn
This algorithm will not work. The problem is to find existing palindromes from the input string. Not form palindromes from available characters?
Input: abab
should return null, but your code will return abba
Assuming that the coins mentioned above are the only allowed coins.
1) Positive case for each of the product when exact amount of coins are supplied.
2) Positive case for products other than tea in multiples of lower value coins (various possible denominations).
3) When excess amount is entered and change has to be returned after dispensing product.
4) Product is unavailable
5) How should the system behave when it doesn't have enough change to return in case of excess amount (should the order be rejected?)
6) Product unavailable + excess amount given
7) Insufficient amount supplied for the product
These are what comes to my mind immediately. Others can post more cases which I might have missed.
@Dilbert Einstein
I understand heap has better time complexity, just wanted to understand the space complexity. I'm not very familiar with heaps.
@Dilbert Einstein
Won't heaps use O(n) extra space? Or is it possible to create max and min heap using the same input array?
If heaps require extra space, won't O(n) be a large number for extra space?
@eugene.yarovoi
Left and Right are merely pointers which point initially to the last and last but one position of the array and we iterate till they reach 1st and 2nd position.
Can you please post the dataset for which this algorithm might fail? Will help in altering the algo...
@alex
Can you please explain your algorithm?
Below is the algorithm given by my friend.
Complexity: Time - O(n2), Space - O(1)
1) Have counters i and j point to first and second elements and mark them left and right of current largest palindrome.
2) Decrement left and increment right until left>0 and right<length of array and array[left]=array[right]
3) Store the longest palindrome and its count
4) Repeat the process by incrementing i and j till i points to length-1 and j points to length
Find the deepest node on each side of the root. That should be the longest possible path between two nodes. Please let me know if im missing something.
- arun_lisieux May 11, 2013@aka
Just a slight variant of Dutch National flag problem.
@EK MACHCHAR
Isnt the input array supposed to be sorted?
Pseudocode:
1) Find the point from start of array where zeros end
2) Find the point from end of array where ones end
3) Swap the two points
4) Increment zeros pointer by one and decrement ones pointer by one
5) Repeat steps 1-4 while (ones-zeros) > 1
public void sortArray (int[] input) {
int zeros = 0, ones = input.length, current = 0;
while ((ones-zeros) > 1){
while ((zeros < ones) && (zeros < input.length)){
if (array[zeros]==0){
zeros++;
} else {
break;
}
}
if (zeros < input.length){
while ((ones > zeros) && (ones > 0)) {
if (array[ones]==1){
ones--;
} else {
break;
}
}
}
array[zeros]=1;
array[ones]=1;
zeros++;
ones--;
}
}
Approach 2: (Time Complexity: O(n), Space Complexity: O(1))
Note: This approach works ONLY when the last element of the array is the largest element.
1) Start from the tail of the array and iterate till start
2) if array[left] > array[right], remove the current element from maximum subsequence
Eg:
Input array: 20 24 28 49 5 50 51 62 4 70
Indices where array[left] > array[right]: 8, 4
When we remove these indices, we get the largest possible sorted sub sequence.
Approach 1: (Time Complexity: O(n2), Space complexity: O(n))
1) Do a linear traversal and store the indices of the array where array[current] > array[next] in a new array
2) In the array of indices, Loop from first index and check if array[currentIndex] < array[currentIndex+2]
3) If yes, remove currentIndex+1 and currentLongest sub sequence is from left till nextIndex (after removing currentIndex+1)
4) Repeat the steps 2,3 till all combinations are covered (like a nested for loop)
CurrentLength is compared with maximumLength at the end of each inner loop and store the indexes to be removed if current > maximum
Eg:
Input array: 20 24 28 49 5 50 51 62 4 70
Array of indices where array[current] > array[next]: 3, 7
Iteration 1:
if array[3] < array[5] => 49 < 50 = yes
currentLength = current(0) + length ((3-0)+1)+((7-5)+1)=7 (subtracting each set of indices and adding one to it)
if array[7] < array[9] => 62 < 70 = yes
currentLength = current(7) + length ((array.length-9)+1)=8 (subtracting each set of indices and adding one to it)
Repeat such iterations starting from each element in the indices array.
I think your code returns the longest sub array instead of sub sequence.
Consider the following input.
Input: 20 24 28 49 5 50 51 62
Expected output: 20 24 28 49 50 51 62
Your code will return 20 24 28 49.
Providing code for the above approach
int prev = Integer.MIN_VALUE;
int current = 0;
boolean isValid = true;
public boolean validateBST (Node root){
isValidBST (root);
return isValid;
}
private boolean isValidBST (Node root) {
if (root == null) {return;}
isValidBST (root->left);
if (isValid){
current = root->value;
if (current > prev) {
prev = current;
}else{
isValid = false;
}
}
isValidBST (root->right);
}
Nisk, in this dataset if you are searching for
1) 0 - You will get this in the 1st iteration (Difference = 0)
2) 1 - You will get this in the 2nd iteration (Difference = 1)
3) 2 - You will get this in 8th iteration (Difference = 2,2,2,2,2,2,2)
Even in the worst case of this algorithm, we are not visiting all the elements in the array. Hence, this is better than a linear search.
Correct me if Im wrong.
My bad. Didn't look in to the recursive call thoroughly.
It would be printTraversal (9, false, false) and printTraversal (6, true, false).
Up voting the solution.
@amazon engineer
Consider the following tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / / \
8 9 10 11 12
\
13
For the above input, if I'm not mistaken,
1) node 9 would be printed since it satisfies the condition
if (isRight && !isLeft && (node.left != null || node.right != null)
printTraversal (9, false, true).
2) Node 6 would be printed since it satisfies the condition
if(isLeft || (node.left == null && node.right == null))
printTraversal (6, true, false).
Correct me if I'm wrong.
Alex, I calculate the absolute difference ignoring the sign. I believe case you mentioned should be handled. Can you please provide a sample data for the case you mentioned?
- arun_lisieux May 07, 2013Pseudocode:
1) Instantiate current pointer to first position in array
2) Calculate absolute difference between current value and expected value
3) If difference is 0, return current value, else, increment current pointer by the difference
4) Repeat steps 2-4 until difference is not zero and current pointer is less than length of array
public int findElementInArray (int[] input, int expected){
current = 0;
difference = abs(input[current]-expected);
while (difference != 0 && current < input.length){
difference = abs(input[current]-expected);
current += difference;
}
if (difference == 0){
return current;
}
return -1;
}
Will this approach handle multiple palindromes in a given string?
- arun_lisieux June 25, 2013