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();
}
}
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;
}
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;
}
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();
}
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
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);
}
}
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^(n-1) + 3! x m^(n-2) + ... n! x m^(1)
Part one: m^n
Part two: m^n + m^(n-1) + m^(n-2) + ... m^(n-n) .... (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 */
}
RepAvikaEthan, Data Engineer at Adjetter Media Network Pvt Ltd.
Avika Ethan has five years of experience collecting physical and biological data in California streams and rivers. In the field ...
rhombus - all four sides congruent but diagonals are not.
- june.pravin September 14, 2015parallelogram - opposite sides congruent but diagonals are not.