june.pravin
BAN USERHi.. I have a doubt on this question.
By 'connect' do you mean that each node must store a reference to all nodes at the same level?
If yes, then this reference storage itself cannot be achieved in O(1) space because as the height of the tree increases, every node will have more number of peers.
It would be helpful to think about this problem if you can explain.
Thanks,
Pravin
To know if a given set of characters can form a palindrome string
1. Sort the characters.
2. In a palindrome string, every character will have at least one duplicate. A palindrome string can be of odd length which means that there can be one character without any duplicate.
3. Check if the input string satisfies point 2 (it becomes easy to check after sorting).
4. If yes, form a palindrome string. Repeat the process for all string in the array.
private static List<String> makePalindromeOfAll(List<String> strings) {
List<String> palindromeStrings = new ArrayList<String>();
for (String string : strings) {
if (string == null  string.isEmpty()) {
palindromeStrings.add(string);
continue;
} else {
if (makePalindrome(string) == null) {
return null;
} else {
palindromeStrings.add(string);
}
}
}
return palindromeStrings;
}
public static String makePalindrome(String string) {
if(string == null  string.isEmpty()) {
return string;
}
if(string.length() == 1) {
return string;
}
char[] characters = string.toCharArray();
Arrays.sort(characters);
int uniqueCharacterCount = 0;
int oddCharacterIndex = 0;
if(characters.length % 2 == 0) {
for(int i = 0; i < characters.length; i+=2) {
if(characters[i] != characters[i+1]) {
return null; // not a palindrome
}
}
} else {
for(int i = 0; i < characters.length; i+=2) {
if(characters[i] != characters[i+1] && uniqueCharacterCount < 1) {
if(characters.length >= i+2 && characters[i+1] == characters[i+2]) {
oddCharacterIndex = i;
} else {
oddCharacterIndex = i+1;
}
i;
uniqueCharacterCount++;
}
if(uniqueCharacterCount > 1) {
return null;
}
}
}
//now, make a palindrome string
StringBuilder sb = new StringBuilder(String.copyValueOf(characters));
if(characters.length % 2 == 0) {
return sb.replace(sb.length()/2, sb.length(), new StringBuilder(sb.substring(sb.length()/2)).reverse().toString()).toString();
} else {
char oddCharacter = sb.charAt(oddCharacterIndex);
sb.deleteCharAt(oddCharacterIndex);
sb.replace(sb.length()/2, sb.length(), new StringBuilder(sb.substring(sb.length()/2)).reverse().toString());
sb.insert(sb.length()/2, oddCharacter);
return sb.toString();
}
}

june.pravin
September 14, 2015 Hi.. Thanks for your inputs. For 'bcccf', it outputs 'bc'.
 june.pravin September 12, 2015I optimized this solution so that it becomes O(n). Though the solution has nested for loops, I'm using a variable called 'currentPosition' which makes the input string traversal almost linear.
Your inputs are welcome :)
private static String findUniqueSubstring(String string) {
List<Character> uniqueCharacters = new ArrayList<Character>();
StringBuilder uniqueString = new StringBuilder();
String bestUniqueStringSoFar = "";
int currentPosition = 0;
for(int i = currentPosition; i < string.length(); i++) {
uniqueCharacters.clear();
uniqueString.delete(0, uniqueString.length());
for(int j = i; j < string.length(); j++) {
if(!uniqueCharacters.contains(string.charAt(j))) {
uniqueCharacters.add(string.charAt(j));
uniqueString.append(string.charAt(j));
} else {
currentPosition = j;
break;
}
}
if(uniqueString.length() > bestUniqueStringSoFar.length()) {
bestUniqueStringSoFar = uniqueString.toString();
}
}
return bestUniqueStringSoFar;
}

june.pravin
September 12, 2015 Here's my O(n^2) solution. But I think this problem can be solved in O(n).
private static String findUniqueSubstring(String string) {
List<Character> uniqueCharacters = new ArrayList<Character>();
StringBuilder uniqueString = new StringBuilder();
String bestUniqueStringSoFar = "";
for(int i = 0; i < string.length(); i++) {
uniqueCharacters.clear();
uniqueString.delete(0, uniqueString.length());
for(int j = i; j < string.length(); j++) {
if(!uniqueCharacters.contains(string.charAt(j))) {
uniqueCharacters.add(string.charAt(j));
uniqueString.append(string.charAt(j));
} else {
break;
}
}
if(uniqueString.length() > bestUniqueStringSoFar.length()) {
bestUniqueStringSoFar = uniqueString.toString();
}
}
return bestUniqueStringSoFar;
}

june.pravin
September 12, 2015 Dude.. Your code won't work for
e cBAd LkmY
because you are not sorting.
 june.pravin September 11, 2015Mediator
 june.pravin September 11, 20151. Sort the characters
2. Remove duplicates
public static String removeDupAndOrder(String string) {
if(string == null  string.isEmpty()) {
return string;
}
char[] charArray = string.toCharArray();
Arrays.sort(charArray);
StringBuilder sb = new StringBuilder(String.valueOf(charArray));
char currentChar = '\0';
for(int i = 0; i < sb.length(); i++) {
if(currentChar != sb.charAt(i)) {
currentChar = sb.charAt(i);
} else {
sb.deleteCharAt(i);
i;
}
}
return sb.toString();
}

june.pravin
September 11, 2015 B and R string algorithm:
1. Sort the strings in descending order of length in such a way that those starting and ending with B and B are first, followed by those with B and R, then R and B and finally R and R.
2. Let strings starting and ending with B and B be called BxxB. Similarly, BxxR, RxxB, RxxR
3. Now there are 16 possible cases:
a. N = 0 (no strings given)
Output is 0
b. Only strings starting and ending with B and B (BxxB)
Output is length of all strings summed up.
c. Only strings starting with B and ending with R (BxxR)
Output is length of the longest string
d. Only strings starting with R and ending with B (RxxB)
Output is length of the longest string
e. Only strings starting and ending with R and R (RxxR)
Output is length of all strings summed up
f. Only two types of strings: BxxB, BxxR
Output is total length of all BxxB + Length of longest string of type BxxR
g. Only two types of strings: BxxB and RxxB
Output is length of RxxB + Total Length of all BxxB
h. Only two types of strings: BxxB and RxxR
Output is max(total length of BxxB, total length of RxxR)
i. Only two types of strings: RxxB and BxxR
Output is RxxB1 + BxxR1 + RxxB2 + BxxR2 + ….
j. Only two types of strings:
Only three types of strings: BxxB, BxxR, RxxB
k. Output is total length of all BxxB + (BxxR1 + RxxB1 + BxxR2 + RxxB2 + .. till either is exhausted)
Only three types of strings: BxxR, ….. and so on

june.pravin
September 10, 2015 B and R string algorithm:
Sort the strings in descending order of length in such a way that those starting and ending with B and B are first, followed by those with B and R, then R and B and finally R and R.
Let strings starting and ending with B and B be called BxxB. Similarly, BxxR, RxxB, RxxR
Now there are 16 possible cases:
N = 0 (no strings given)
Output is 0
Only strings starting and ending with B and B (BxxB)
Output is length of all strings summed up.
Only strings starting with B and ending with R (BxxR)
Output is length of the longest string
Only strings starting with R and ending with B (RxxB)
Output is length of the longest string
Only strings starting and ending with R and R (RxxR)
Output is length of all strings summed up
Only two types of strings: BxxB, BxxR
Output is total length of all BxxB + Length of longest string of type BxxR
Only two types of strings: BxxB and RxxB
Output is length of RxxB + Total Length of all BxxB
Only two types of strings: BxxB and RxxR
Output is max(total length of BxxB, total length of RxxR)
Only two types of strings: RxxB and BxxR
Output is RxxB1 + BxxR1 + RxxB2 + BxxR2 + ….
Only two types of strings:
Only three types of strings: BxxB, BxxR, RxxB
Output is total length of all BxxB + (BxxR1 + RxxB1 + BxxR2 + RxxB2 + .. till either is exhausted)
Only three types of strings: BxxR, ….. and so on
1. Check length, if difference greater than 1, return false.
2. Initialize variables differenceCount = 0, shouldInsert = false, forLoopIterationCount = 0;
3. If strings are of different length, identify which is longer. Also, differenceCount++, shouldInsert = true, forLoopIterationCount = longer.length()  1
4. If strings are of equal length take any as longer string. shouldInsert = false, forLoopIterationCount = longer.length()
5. Iterate over the longer string till differenceCount < 2. On first mismatch, insert the mismatching character in the shorter string if shouldInsert is true (Use StringBuilder). On further mismatches, differenceCount++
6. After for loop, if differenceCount < 2, return true. Else return false.
public class Main {
public static void computeSumAtHeights(BinaryNode tree, int currentHeight, List<Integer> sums) {
if(sums.size() <= currentHeight) {
sums.add(currentHeight, new Integer(tree.getValue()));
} else {
sums.set(currentHeight, sums.get(currentHeight) + tree.getValue());
}
if(tree.getLeft() != null) {
computeSumAtHeights(tree.getLeft(), currentHeight + 1, sums);
}
if(tree.getRight() != null) {
computeSumAtHeights(tree.getRight(), currentHeight + 1, sums);
}
}
public static void main(String... args) {
BinaryNode level2Left1 = new BinaryNode(null, null,4);
BinaryNode level2Right1 = new BinaryNode(null, null,5);
BinaryNode level1Left = new BinaryNode(level2Left1, level2Right1, 2);
BinaryNode level2Left2 = new BinaryNode(null, null,1);
BinaryNode level2Right2 = new BinaryNode(null, null,2);
BinaryNode level1Right = new BinaryNode(level2Left2, level2Right2, 3);
BinaryNode root = new BinaryNode(level1Left, level1Right,1);
List<Integer> sums = new ArrayList<Integer>(0);
computeSumAtHeights(root, 0, sums);
System.out.println(sums);
}
}

june.pravin
August 31, 2015 1) Let P1,P2,P3,P4 be the points
2) Find all possible distances between them. There will be six.
3) Sort these distances. Let them be D1,D2,D3,D4,D5,D6
4) If the first 4 and last 2 are equal, its a square
5) If the first 2, second 2 and last 2 are equal, its a rectangle
6) If not, its neither
This is what I thought initially too. But I think this doesn't handle paths like this:
Consider 5 levels and 3 nodes per level (i.e. n = 5 and m = 3)
start > Choose one node from level 1 > choose one node from level 4 > sink
Can you check my answer and tell me I got it right? Thanks! :)
Correcting this slightly
Part one: m^n
Part two: m^n + 2! x m^(n1) + 3! x m^(n2) + ... n! x m^(1)
Part one: m^n
Part two: m^n + m^(n1) + m^(n2) + ... m^(nn) .... (Mathematical induction)
subString() method of the String class always generates a new String object.
 june.pravin September 04, 2013I could not retrieve much information from the question:
1) Is the object at an integral number position on the line or can it be at any position?
2) We can go forward and backward one step. But how big can the step be?
3) The other answers here suggest the use of exponentiation and prime numbers. How are we sure that the object is to be found at an exponential position, etc ?
Kindly explain as it would help me understand what you all are thinking.
/**
* Returns a Set of customers who have visited the website on exactly given days and should have visited at least given distinct pages altogether.
* @param days the number of days a customer visits
* @param distinctWebPageVisitCount the minimum number of distinct web pages visited by the customer.
*/
Set<Customer> getCustomers(int days, int distinctWebPageVisitCount) {
/** First find all customers who have exactly 'days' entries in the mapping class's set. Then from this set, return only those instances who's webPage count is >= 'distinctWebPageVisitCount' */
}
/** Many to Many mapping between customers and webpages. Each mapping denotes a customer's visit to a webpage on a particular date. The tuple (customer, webPage, date) is unique */
class CustomerWebPageMapping {
id;
Customer c;
WebPage webPage;
Date date;
/** other details */
}
class Customer {
id;
/** other details */
}
class WebPage {
id;
/** other details */
}

june.pravin
September 04, 2013 Open Chat in New Window
rhombus  all four sides congruent but diagonals are not.
 june.pravin September 14, 2015parallelogram  opposite sides congruent but diagonals are not.