Adnan Ahmad
BAN USER
Find anagrams using prime hash
private int primes[] = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
public Collection<String> findAnagrams(String haystack, String needle){
int hashNeedle = hash(needle);
Collection<String> anagrams = new ArrayList<>();
Map<Integer, Integer> hashes = new HashMap<>();
int index = 0, hashHayStack = 1;
for(char ch : haystack.toLowerCase().toCharArray()){
hashHayStack *= primes[ch - 'a'];
if(hashHayStack%hashNeedle == 0
&& hashes.containsKey(hashHayStack/hashNeedle)){
int startIndex = hashes.get(hashHayStack/hashNeedle) + 1;
anagrams.add(haystack.substring(startIndex, startIndex + needle.length()));
}
hashes.put(hashHayStack, index++);
}
return anagrams;
}
private int hash(String word){
int hash = 1;
word = word.toLowerCase();
for(int i = 0; i< word.length(); i++){
int index = word.charAt(i) - 'a';
hash *= primes[index];
}
return hash;
}
private List<String> pathList;
public List<String> getPaths(int destX, int destY){
pathList = new ArrayList<String>();
getPaths(0,0, destX, destY, "");
return pathList;
}
private void getPaths(int currX, int currY, int destX, int destY, String path){
path += String.format(" (%d,%d)", currX , currY);
if( currX == destX && currY == destY){ //reach the (destX,destY) point
pathList.add(path);
}else if( currX > destX || currY > destY){//wrong way
return;
}else {
getPaths(currX + 1, currY, destX, destY, path);//down
getPaths(currX , currY + 1, destX, destY, path);//right
}
}
public static Set<String> decode(String code){
return decode("", code);
}
private static Set<String> decode(String prefix, String code) {
Set<String> set = new HashSet<String>();
if (code.length() == 0) {
set.add(prefix);
return set;
}
if (code.charAt(0) == '0'){
return set;
}
set.addAll(decode(prefix + (char) (code.charAt(0) - '1' + 'a'), code.substring(1)));
if (code.length() >= 2 && code.charAt(0) == '1') {
set.addAll(decode(prefix + (char) (10 + code.charAt(1) - '1' + 'a'), code.substring(2)));
}
if (code.length() >= 2 && code.charAt(0) == '2' && code.charAt(1) <= '6') {
set.addAll(decode(prefix + (char) (20 + code.charAt(1) - '1' + 'a'), code.substring(2)));
}
return set;
}
Same as
question?id=19300678
Java implementation of above idea...
public static List<Set<Integer>> readBook(Map<Integer, Integer> pagesPerChapter, int totalDays){
// Store pages count in the array {like 10, 20, 50, 90, 100}
int pages[] = new int[pagesPerChapter.size()];
pages[0] = pagesPerChapter.get(1);
for(int index = 1; index < pages.length; index++){
pages[index] = pages[index - 1] + pagesPerChapter.get(index+1);
}
int averagePages = pages[pages.length-1]/totalDays;
List<Set<Integer>> chaptersPerDay = new ArrayList<>();
int index = 0, product = 1;
while(index < pages.length){
int closest = getClosestToValueIndex(pages, index, averagePages*product++);
Set<Integer> chapters = new HashSet<>();
for(int value = index; value <= closest; value++){
chapters.add(value+1);
}
index = closest+1;
chaptersPerDay.add(chapters);
}
return chaptersPerDay;
}
private static int getClosestToValueIndex(int[] data, int low, int key) {
int high = data.length - 1;
while (low < high) {
int mid = (low + high) / 2;
if(data[mid] == key){
return mid;
} else {
int d1 = Math.abs(data[mid] - key);
int d2 = Math.abs(data[mid+1] - key);
if (d2 <= d1) {
low = mid+1;
} else {
high = mid;
}
}
}
return high;
}
public static boolean canBePalidrome(String str){
int[] charCount = new int[Character.MAX_VALUE];
for(char ch : str.toCharArray()) {
charCount[ch]++;
}
if(str.length()%2 == 0){
for(int count : charCount){
if(count % 2 == 1){
return false;
}
}
} else {
int oddCount = 0;
for(int count : charCount){
if(count % 2 == 1){
if(oddCount > 1){
return false;
} else {
oddCount++;
}
}
}
}
return true;
}
Time Complexity: O(nlogk); Space Complexity: O(k)
public class FindNClosestPoints {
private class Point implements Comparable<Point>{
int value1;
int value2;
double distance;
Point(int value1, int value2) {
super();
this.value1 = value1;
this.value2 = value2;
}
@Override
public int compareTo(Point that) {
if(that.distance > this.distance){
return 1;
} else if(that.distance < this.distance){
return -1;
}
return 0;
}
}
public Point[] findNClosePoint(Point points[], Point from, int k){
Queue<Point> maxHeap = new PriorityQueue<Point>(k);
int index = 0;
for(; index < k; index++){
points[index].distance = euclideanDistance(points[index], from);
maxHeap.offer(points[index]);
}
for(; index < points.length; index++){
points[index].distance = euclideanDistance(points[index], from);
if(maxHeap.peek().distance > points[index].distance){
maxHeap.poll();
maxHeap.offer(points[index]);
}
}
return maxHeap.toArray(new Point[k]);
}
private double euclideanDistance(Point point1, Point point2){
return Math.sqrt(Math.pow(point2.value1 - point1.value1, 2) + Math.pow(point2.value2 - point1.value2, 2));
}
}
public class CheckPalindrome {
private static boolean isLetterOrDigit(char ch){
return Character.isAlphabetic(ch) || Character.isDigit(ch);
}
public static boolean isPalindrome(String str){
if(str == null){
throw new IllegalArgumentException("String must be not null");
} else if(str.length() == 0 || str.length() == 1 ){
return true;
} else {
int left = 0, right = str.length() - 1;
while(left < right){
if(!isLetterOrDigit(str.charAt(left))){
left++;
} else if(!isLetterOrDigit(str.charAt(right))){
right--;
} else {
if(Character.toLowerCase(str.charAt(left)) == Character.toLowerCase(str.charAt(right))){
left++;
right--;
} else {
return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("ABA"));
System.out.println(isPalindrome("A!#A"));
System.out.println(isPalindrome("A!AB#A"));
System.out.println(isPalindrome("A man, a plan, a canal, Panama!"));
}
}
- Adnan Ahmad March 16, 2015@ Anonymous
Character Class
- static char[] toChars(int codePoint)
- Converts the specified character (Unicode code point) to its UTF-16 representation stored in a char array.
You can also use
result = (char)(index+65) + result;
instead of
result = Character.toChars(index + 65)[0] + result;
Java implementation
public class MergeIntervals {
class Interval{
double start;
double end;
public Interval(double start, double end) {
this.start = start;
this.end = end;
}
}
public List<Interval> mergeIntervals(List<Interval> nonOverlapInt, Interval another){
List<Interval> merge = new ArrayList<Interval>();
for(Interval current : nonOverlapInt){
if(current.end <= another.start || another.end <= current.start){
merge.add(current);
} else{
another.start = (current.start < another.start) ? current.start : another.start;
another.end = (current.end > another.end) ? current.end : another.end;
}
}
merge.add(another);
return merge;
}
}
Java Implementation using hashMap in time complexity O(n)...
//Time Complexity: O(n)
public static int[] longestConsecutiveSequence(int[] data){
int first = Integer.MAX_VALUE; // the first number of the maximum consecutive sequence
int length = 0; // the length of the maximum consecutive sequence
Map<Integer, Integer> table = new Hashtable<Integer, Integer>();
for(int value: data) {
if(!table.containsKey(value)) {
int start = value;
int end = value;
if(table.containsKey(value + 1) && table.get(value + 1) >= value + 1) {
end = table.get(value + 1);
table.remove(value + 1);
table.remove(end);
}
if(table.containsKey(value - 1) && table.get(value - 1) <= value - 1) {
start = table.get(value - 1);
table.remove(value - 1);
table.remove(start);
}
table.put(start, end);
table.put(end, start);
if(end - start + 1 > length) {
first = start;
length = end - start + 1;
}
}
}
int[] seq = new int[length];
for(int i = 0; i < length; i++){
seq[i] = first + i;
}
return seq;
}
/**
Tree1: 90
/ \
70 110
Tree2: 60
/ \
5 800
Balanced Tree3:
70
/ \
5 110
\ / \
60 90 800
*/
Java language solution of this problem is given below:
/**
* Solution:
* 1. Covert the BSTs to sorted linked list (using inorder traversal, Time O(m+n))
* 2. Merge this two sorted linked lists to a single list (same as merge portion of merge sort, Time O(m+n))
* 3. Convert sorted linked list to balanced BST (this can be done in place with O(m+n) time)
*/
import java.util.ArrayList;
import java.util.List;
public class MergeTwoBST {
class TreeNode {
private int value;
private TreeNode leftNode;
private TreeNode rightNode;
public TreeNode(int value) {
super();
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public TreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
}
public static TreeNode mergeBSTToFormBalancedTree(TreeNode tree1, TreeNode tree2){
if(tree1 != null && tree2 != null){
List<Integer> sortedList1 = new ArrayList<Integer>();
List<Integer> sortedList2 = new ArrayList<Integer>();
getSortedList(tree1, sortedList1);
getSortedList(tree2, sortedList2);
List<Integer> sortedList3 = merge(sortedList1, sortedList2);
return createTree(sortedList3, 0, sortedList3.size() - 1);
}
else if(tree1 != null){
return tree1;
}
else if(tree2 != null){
return tree2;
}
return null;
}
// left, root, right( INORDER TRAVERSAL GIVES SORTED ORDER)
private static void getSortedList(TreeNode node, List<Integer> sortedList){
if(node != null){
getSortedList(node.getLeftNode(), sortedList);
sortedList.add(node.getValue());
getSortedList(node.getRightNode(), sortedList);
}
}
private static List<Integer> merge(List<Integer> sortedList1, List<Integer> sortedList2){
List<Integer> mergeList = new ArrayList<Integer>(sortedList1.size() + sortedList2.size());
int index1 = 0, index2 = 0;
while(index1 < sortedList1.size() && index2 < sortedList2.size()){
if(sortedList1.get(index1) <= sortedList2.get(index2)){
mergeList.add(sortedList1.get(index1));
index1++;
} else {
mergeList.add(sortedList2.get(index2));
index2++;
}
}
while(index1 < sortedList1.size()){
mergeList.add(sortedList1.get(index1));
index1++;
}
while(index2 < sortedList2.size()){
mergeList.add(sortedList2.get(index2));
index2++;
}
return mergeList;
}
// Create Tree using array
private static TreeNode createTree(List<Integer> data, int begin, int end) {
if (begin > end) {
return null;
}
if (begin == end) {
return new TreeNode(data.get(begin));
}
int size = end - begin + 1;
int lSize = (size - 1) >> 1;
TreeNode parent = new TreeNode(data.get(begin + lSize));
parent.setLeftNode(createTree(data, begin, begin + lSize - 1));
parent.setRightNode(createTree(data, begin + lSize + 1, end));
return parent;
}
public static void printLevelWiseTree(List<TreeNode> nodes) {
if(nodes == null || nodes.isEmpty()){
return;
}
else{
List<TreeNode> next = new ArrayList<TreeNode>();
for(TreeNode node : nodes) {
System.out.print(node.getValue()+" ");
if(node.getLeftNode() != null){
next.add(node.getLeftNode());
}
if(node.getRightNode() != null){
next.add(node.getRightNode());
}
}
System.out.println();
printLevelWiseTree(next);
}
}
public static void main(String[] args) {
TreeNode tree1 = new TreeNode(90);
tree1.setLeftNode(new TreeNode(70));
tree1.setRightNode(new TreeNode(110));
TreeNode tree2 = new TreeNode(60);
tree2.setLeftNode(new TreeNode(5));
tree2.setRightNode(new TreeNode(800));
TreeNode balancedTree = mergeBSTToFormBalancedTree(tree1, tree2);
List<TreeNode> list = new ArrayList<TreeNode>();
list.add(balancedTree);
printLevelWiseTree(list);
}
}
Java Implementation of DominoChecker....
public class DominoChecker {
class Domino {
int first;
int second;
Domino(int first, int second){
this.first = first;
this.second = second;
}
public boolean equals(Object obj){
if(!(obj instanceof Domino)){
return false;
} else{
Domino that = (Domino) obj;
return (this.first == that.first && this.second == that.second);
}
}
public int hashCode(){
return (this.first+this.second)*31;
}
}
class DominoComparator implements Comparator<Domino>{
public int compare(Domino dom1, Domino dom2) {
if(dom1.first < dom2.first){
return -1;
} else if(dom1.first > dom2.first){
return 1;
} else{
if(dom1.second < dom2.second){
return -1;
}
if(dom1.second > dom2.second){
return 1;
}else{
return 0;
}
}
}
}
Set<Long> boxes = null;
public DominoChecker(){
boxes = new HashSet<Long>();
}
public boolean addBox(int[] box) {
Domino[] dominos = new Domino[box.length>>1];
for(int index = 0; index < 5; index++) {
Domino domino = new Domino(box[2*index], box[2*index+1]);
if(domino.first > domino.second){
swapDominoPair(domino);
}
dominos[index] = domino;
}
Arrays.sort(dominos, new DominoComparator());
long hashValue = 0;
for(int index = 0; index < 5; index++) {
hashValue = hashValue * 100 + dominos[index].first*10 + dominos[index].second;
}
if(!boxes.contains(hashValue)){
boxes.add(hashValue);
} else {
return false;
}
return true;
}
private void swapDominoPair(Domino domino){
int temp = domino.first;
domino.first = domino.second;
domino.second = temp;
}
public static void main(String[] args) {
DominoChecker checker = new DominoChecker();
int[] box1 = {0,2,9,1,3,3,7,4,5,6};
int[] box2 = {0,2,3,3,5,6,7,4,9,1};
System.out.println(checker.addBox(box1));
System.out.println(checker.addBox(box2));
int[] box3 = {0,1,3,2,5,6,7,4,9,1};
System.out.println(checker.addBox(box3));
int[] box4 = {3,3,3,1,1,1,7,3,3,1};
int[] box5 = {7,3,1,1,1,3,3,1,3,3};
System.out.println(checker.addBox(box4));
System.out.println(checker.addBox(box5));
}
}
@Avinash
Sight modification is your code to avoid findPoistion of zero in each iteration. Correct me if I am wrong...
public class RearrangeArray {
public static void rearrange(int []source, int []target) {
int srcIndex = -1, srcZeroIndex = -1;
srcZeroIndex = findPosition(source, 0);
for (int index = 0; index < source.length; index++) {
if (target[index] != 0 && source[index] != target[index]){
swapInSource(source, srcZeroIndex, index);
srcZeroIndex = index;
srcIndex = findPosition(source, target[index]);
swapInSource(source, index, srcIndex);
srcZeroIndex = srcIndex;
}
}
}
private static int findPosition(int[] array, int key){
for (int i = 0; i < array.length; i++){
if (array[i] == key){
return i;
}
}
return -1;
}
private static void swapInSource(int source[], int index1, int index2){
int temp = source[index1];
source[index1] = source[index2];
source[index2] = temp;
}
public static void main(String[] args){
int[] source = { 1, 0, 2, 3, 7, 4, 8, 9 };
int[] target = { 0, 2, 8, 3, 1, 9, 4, 7 };
rearrange(source, target);
System.out.println("Source: "+ Arrays.toString(source));
}
}
Java Implementation of remove word using dynamic programming...
public class RemoveWord {
Map<String, Boolean> memorize;
public RemoveWord() {
super();
memorize = new HashMap<String, Boolean>();
}
public boolean remove(String word, Set<String> dictionary) {
if (word == null){
return false;
}
else if (word.length() == 1){
return true;
}
else if (!dictionary.contains(word)){
return false;
}
else {
if(memorize.containsKey(word)){
return memorize.get(word);
}
else{
boolean isValid = false;
for ( int index = 0; index < word.length(); index++) {
isValid = isValid || removeWord(word.substring(0, index)+ word.substring(index+1), dictionary);
}
memorize.put(word, isValid);
return isValid;
}
}
}
public static void main(String[] args) {
Set<String> dictionary = new HashSet<String>();
dictionary.add("restated");
dictionary.add("restate");
dictionary.add("estate");
dictionary.add("state");
dictionary.add("stat");
dictionary.add("sat");
dictionary.add("at");
RemoveWord obj = new RemoveWord();
System.out.println(obj.remove("restated", dictionary));
}
}
Java Implementation of string matcher using dynamic programming...
public class StringMatcher {
static class Pairs{
int mIndex, pIndex;
Pairs(int mIndex, int pIndex){
this.mIndex = mIndex;
this.pIndex = pIndex;
}
public boolean equals(Object obj) {
if (!(obj instanceof Pairs)) {
return false;
} else {
Pairs that = (Pairs)obj;
return this.mIndex == that.mIndex && this.pIndex == that.pIndex;
}
}
public int hashCode() {
return (mIndex + pIndex)* 31;
}
}
Map<Pairs, Boolean> matchMemorize = null;
String matcher = null;
String pattern = null;
public void initializer(String matcher, String pattern){
this.matchMemorize = new HashMap<Pairs, Boolean>();
this.matcher = matcher;
this.pattern = pattern;
}
public boolean isStringMatches(int mIndex, int pIndex){
if(mIndex == matcher.length() && pIndex == pattern.length()){
return true;
}
else if(mIndex == matcher.length() || pIndex == pattern.length()){
return false;
}
else{
Pairs pairs = new Pairs(mIndex, pIndex);
if(matchMemorize.containsKey(pairs)){
return matchMemorize.get(pairs);
}
else {
boolean result = false;
if(pattern.charAt(pIndex) != '*' && pattern.charAt(pIndex) != '?'){
if(matcher.charAt(mIndex) == pattern.charAt(pIndex)){
result = isStringMatches(mIndex+1, pIndex+1);
}
}
else if(pattern.charAt(pIndex) == '*'){
result = isStringMatches(mIndex+1, pIndex) || isStringMatches(mIndex, pIndex+1) || isStringMatches(mIndex+1, pIndex+1);
}
else { // for ? case
result = isStringMatches(mIndex+1, pIndex+1);
}
Pairs newPair = new Pairs(mIndex, pIndex);
matchMemorize.put(newPair, result);
return result;
}
}
}
public static void main(String[] args) {
StringMatcherUsingDP matcher = new StringMatcherUsingDP();
matcher.initializer("ababab","ab*b");
System.out.println(matcher.isStringMatches(0, 0));
matcher.initializer("abab","abab");
System.out.println(matcher.isStringMatches(0, 0));
matcher.initializer("ababab","a**b");
System.out.println(matcher.isStringMatches(0, 0));
matcher.initializer("","*");
System.out.println(matcher.isStringMatches(0, 0));
matcher.initializer("aaaaaab","*?*b");
System.out.println(matcher.isStringMatches(0, 0));
}
}
Modification of Knuth-Morris-Pratt String matching algorithm.
Time Complexity = O(m+n) where m is the string length and n is the pattern length
public class StringMatchingWithRegexPattern {
/**
* The prefix function π for a pattern encapsulates knowledge about how the pattern matches against shifts of itself.
*/
public static int[] preProcessing(String pattern) {
int index = 0, shift = -1;
int[] prefix = new int[pattern.length() + 1];
prefix[0] = -1;
while (index < pattern.length()) {
if(pattern.charAt(index) == '?' || pattern.charAt(index) == '*'){
if(index == pattern.length() - 1){ // handles the last 'abc*' or 'c?' cases
prefix[index] = ++shift;
break;
}
index++;
}
/**
* String: b a c b a b a b a a b c b a b
* Pattern: a b a b a c a (mismatch between a and c)
* Pattern: a b a b a c Then shift 2 character right
*/
while (shift >= 0 && pattern.charAt(index) != pattern.charAt(shift)) { // if there is mismatch consider next widest border
shift = prefix[shift];
}
index++;
shift++;
prefix[index] = shift;
}
return prefix;
}
public static boolean matching(String text, String pattern) {
// Generate prefix for pattern
int[] prefix = preProcessing(pattern);
int index = 0, charMatched = 0;
while (index < text.length()) {
while(pattern.charAt(charMatched) == '*' || pattern.charAt(charMatched) == '?'){ // while loop for handles **b / ?*b cases
if(pattern.charAt(charMatched)== '*'){
index = text.length() - (pattern.length() - charMatched);
}
index++; // increment for both cases * and ?
charMatched++;
if (charMatched == pattern.length()) {// if their is "*"
return true;
}
}
while (index < text.length() && charMatched >= 0 && text.charAt(index) != pattern.charAt(charMatched)) {
charMatched = prefix[charMatched];
}
index++;
charMatched++;
if (charMatched == pattern.length()) {
return true;
}
}
if(text.length() == 0 && pattern.length() == 1 && pattern.charAt(0) == '*' || pattern.charAt(charMatched) == '?'){ // str:'' ptrn:'*'
return true;
}
return false;
}
public static void main(String[] args) {
System.out.println(matching("ababab","ab*b"));
System.out.println(matching("abab","abab"));
System.out.println(matching("ababab","a**b"));
System.out.println(matching("","*"));
System.out.println(matching("aaaaaab","*?*b"));
}
}
Java Implementation of tree diameter
/**
6
/ \
2 7
/ \ \
1 4 9
/ \ /
3 5 8
*/
public class TreeDiameter {
static class CustomInteger{
int value;
CustomInteger(int value){
this.value = value;
}
}
public static int treeDiameter(TreeNode root, CustomInteger height){
CustomInteger leftHeight = new CustomInteger(0), rightHeight = new CustomInteger(0);
if(root == null){
height.value = 0;
return 0;
}
/* Get the heights of left and right subtrees in lh and rh
and store the returned values in ldiameter and ldiameter */
int ldiameter = treeDiameter(root.getLeftNode(), leftHeight);
int rdiameter = treeDiameter(root.getRightNode(), rightHeight);
/* Height of current node is max of heights of left and right subtrees plus 1*/
height.value = Math.max(leftHeight.value, rightHeight.value) + 1;
return Math.max(leftHeight.value + rightHeight.value + 1, Math.max(ldiameter, rdiameter));
}
public static void main(String[] args) {
TreeNode root = new TreeNode(6);
root.setLeftNode(new TreeNode(2));
root.setRightNode(new TreeNode(7));
root.getLeftNode().setLeftNode(new TreeNode(1));
root.getLeftNode().setRightNode(new TreeNode(4));
root.getLeftNode().getRightNode().setLeftNode(new TreeNode(3));
root.getLeftNode().getRightNode().setRightNode(new TreeNode(5));
root.getRightNode().setRightNode(new TreeNode(9));
root.getRightNode().getRightNode().setLeftNode(new TreeNode(8));
CustomInteger hgt = new CustomInteger(0);
System.out.println(treeDiameter(root, hgt));
}
}
/**
6
/ | \
2 10 7
/ \ \
1 4 9
/ \ / / | \
3 5 8 12 13 14
*/
public class PrintTreeInLevelWiseFormat {
static class Node {
int value;
Node children[];
public Node(int value, Node[] children) {
super();
this.value = value;
this.children = children;
}
}
public static void printLevelWiseTree(List<Node> nodes) {
if(nodes == null || nodes.isEmpty()){
return;
}
else{
List<Node> next = new ArrayList<Node>();
for(Node node : nodes) {
System.out.print(node.value+" ");
if(node.children != null){
for(Node child : node.children){
next.add(child);
}
}
}
System.out.println();
printLevelWiseTree(next);
}
}
public static void main(String[] args) {
Node node14 = new Node(14, null);
Node node13 = new Node(13, null);
Node node12 = new Node(12, null);
Node children9[] = {node12, node13, node14};
Node node9 = new Node(9, children9);
Node node8 = new Node(8, null);
Node children4[] = {node8};
Node node4 = new Node(4, children4);
Node node5 = new Node(5, null);
Node node3 = new Node(3, null);
Node children1[] = {node3, node5};
Node node1 = new Node(1, children1);
Node children7[] = {node9};
Node node7 = new Node(7, children7);
Node children2[] = {node1, node4};
Node node2 = new Node(2, children2);
Node node10 = new Node(10, null);
Node children6[] = {node2, node10, node7};
Node root1 = new Node(6, children6);
List<Node> rootList = new ArrayList<Node>();
rootList.add(root1);
printLevelWiseTree(rootList);
}
}
Question is find longest palindrome with ignoring white space in the text.
For this, I modify the Manacher's algorithm for ignoring the white space.
For example:
This is the book koob eh te is had
Output:
the book koob eh t
public class LongestPalindromeFromFile {
public String findLongestPalindrome(String filePath) {
String data = null;
// Read data from file
try {
data = readDataFromFile(filePath);
if(data == null){
System.out.println("Unable to get file contents");
return null;
}
} catch (Exception e) {
return null;
}
// Transform file data
char []transformData = transformData(data);
int center = 0, right = 0, mirror = 0;
int []lengthPal = new int[transformData.length];
for(int index = 1; index < transformData.length - 1; index++){
mirror = (2*center) - index;
if(right > index){
lengthPal[index] = Math.min(right - index, lengthPal[mirror]);
}
// Ignore white spaces on right and left sides
int leftSpaces = 0, rightSpaces = 0;
int leftIndex = index - (1 + lengthPal[index]);
int rightIndex = index + (1+lengthPal[index]);
while(leftIndex >=0 && rightIndex < transformData.length){
if (transformData[leftIndex] == ' '){
leftSpaces++;
leftIndex = index - (2 + lengthPal[index]);
}
else if (transformData[rightIndex] == ' '){
rightSpaces++;
rightIndex = index + (2 + lengthPal[index]);
}
else if (transformData[leftIndex] == transformData[rightIndex]){
lengthPal[index]++;
leftIndex = index - (1 + lengthPal[index]);
rightIndex = index + (1 + lengthPal[index]);
}
else{
break;
}
}
lengthPal[index] += leftSpaces + rightSpaces;
if((index+lengthPal[index])> right){
center = index + (rightSpaces - leftSpaces);
right = center + lengthPal[index];
}
}
return printPalindrome(data, lengthPal);
}
private String readDataFromFile(String filePath) throws FileNotFoundException, IOException{
try{
BufferedReader reader = new BufferedReader(new FileReader(filePath));
StringBuilder builder = new StringBuilder();
String line;
while((line = reader.readLine()) !=null){
builder.append(line);
}
return builder.toString();
}
catch(FileNotFoundException ex){
throw ex;
}
catch (IOException e) {
throw e;
}
}
private char[] transformData(String data){
char[] transformData = new char[2*data.length() + 3];
transformData[0] = '$';
transformData[2*data.length() + 2] = '$';
transformData[2*data.length() + 1] = '#';
for(int index = 0; index < data.length(); index++){
transformData[2 * index + 1] = '#';
transformData[2 * index + 2] = data.charAt(index);
}
return transformData;
}
private String printPalindrome(String data, int[]lengthPal){
int center = 0, length = 0;
for(int index = 1; index < lengthPal.length - 1; index++){
if(lengthPal[index] > length){
length = lengthPal[index];
center = index;
}
}
int leftSpaces = 0, rightSpaces = 0;
String leftSide = data.substring((center - 1 - length) >> 1, center >> 1);
String rightSide = data.substring((center + 1) >> 1, (center - 1 + length) >> 1);
for(char ch : leftSide.toCharArray()){
if(ch == ' '){
leftSpaces++;
}
}
for(char ch : rightSide.toCharArray()){
if(ch == ' '){
rightSpaces++;
}
}
center += (leftSpaces - rightSpaces);
return data.substring((center - 1 - length) >> 1, (center - 1 + length) >> 1);
}
}
Java Implementation:
public class ReplaceNumberWithExcelLabel {
public static String convertToExcelLabel (int n) {
String result = "";
int index = 0;
while (n > 0) {
index = (n - 1) % 26;
result = Character.toChars(index + 65)[0] + result;
n = (n - 1) / 26;
}
return result;
}
public static void main(String[] args) {
System.out.println(convertToExcelLabel(1));
System.out.println(convertToExcelLabel(55));
}
}
public class FindMeetingPoint {
static class Point{
double x, y;
Point(double x, double y){
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}
}
public static double findPoint(Point points[]){
// Calculate the average point
double avgX = 0.0;
double avgY = 0.0;
for (int index = 0; index < points.length; index++) {
avgX += points[index].x;
avgY += points[index].y;
}
avgX = avgX/points.length;
avgY = avgY/points.length;
// Calculate the distance average point to particular point
int avgPoint = 0;
double pointsdiff = Math.sqrt(Math.pow(avgX - points[0].x, 2) + Math.pow(avgY - points[0].y, 2));
for (int index = 1; index < points.length; index++) {
double tempdiff = Math.sqrt(Math.pow(avgX - points[index].x, 2) + Math.pow(avgY - points[index].y, 2));
if (pointsdiff > tempdiff) {
pointsdiff = tempdiff;
avgPoint = index;
}
}
System.out.println("Meeting point is: "+ points[avgPoint]);
double totalDistance = 0;
for (int index = 0; index < points.length; index++) {
double sumx = Math.abs(points[index].x - points[avgPoint].x);
double sumy = Math.abs(points[index].y - points[avgPoint].y);
totalDistance += Math.max(sumx, sumy);
}
return totalDistance;
}
public static void main(String[] args) {
Point points[] = new Point[6];
points[0] = new Point(0, 0);
points[1] = new Point(4, 1);
points[2] = new Point(2, 0);
points[3] = new Point(1, 5);
points[4] = new Point(3, 2);
points[5] = new Point(2, 4);
System.out.println(findPoint(points));
}
}
//Time Complexity: O(n)
public static int[] longestConsecutiveSequence(int[] data){
int first = Integer.MAX_VALUE; // the first number of the maximum consecutive sequence
int length = 0; // the length of the maximum consecutive sequence
Map<Integer, Integer> table = new Hashtable<Integer, Integer>();
for(int value: data) {
if(!table.containsKey(value)) {
int start = value;
int end = value;
if(table.containsKey(value + 1) && table.get(value + 1) >= value + 1) {
end = table.get(value + 1);
table.remove(value + 1);
table.remove(end);
}
if(table.containsKey(value - 1) && table.get(value - 1) <= value - 1) {
start = table.get(value - 1);
table.remove(value - 1);
table.remove(start);
}
table.put(start, end);
table.put(end, start);
if(end - start + 1 > length) {
first = start;
length = end - start + 1;
}
}
}
int[] seq = new int[length];
for(int i = 0; i < length; i++){
seq[i] = first + i;
}
return seq;
}
public static List<String> getSubStrings(String word) {
List<String> allSubStrings = new ArrayList<String>();
int max = 1 << word.length();
for (int index = 1; index < max; index++) {
StringBuffer subString = new StringBuffer();
int bits = index;
int _index = 0;
while (bits > 0) {
if ((bits & 1) > 0) {
subString.append(word.charAt(_index));
}
bits >>= 1;
_index++;
}
allSubStrings.add(subString.toString());
}
return allSubStrings;
}
public static void main(String[] args) {
String word = "abc";
System.out.println(getSubStrings(word));
String word1 = "abababab";
System.out.println(getSubStrings(word1));
}
public static List<String> getSubStrings(String word) {
List<String> allSubStrings = new ArrayList<String>();
int max = 1 << word.length();
for (int index = 1; index < max; index++) {
StringBuffer subString = new StringBuffer();
int bits = index;
int _index = 0;
while (bits > 0) {
if ((bits & 1) > 0) {
subString.append(word.charAt(_index));
}
bits >>= 1;
_index++;
}
allSubStrings.add(subString.toString());
}
return allSubStrings;
}
public static void main(String[] args) {
String word = "abc";
System.out.println(getSubStrings(word));
}
public static void partitionNegArray(int data[]){
int minElement = 0;
for(int index = 0; index < data.length; index++){
if(minElement > data[index]){
minElement = data[index];
}
}
int copyData[] = new int[data.length];
minElement = Math.abs(minElement);
for(int index = 0; index < data.length; index++){
copyData[index] = data[index] + minElement;
}
partitionArray(copyData);
}
public static void partitionArray(int data[]){
// Find Sum
int sum = 0, maxSubSetSize = data.length>>1;
for(int value : data){
sum += value;
}
int halfSum = sum>>1;
int subsetSum[][] = new int[maxSubSetSize +1][halfSum + 1];
subsetSum[0][0] = 1;
for(int i = 0; i < data.length; i++){ //consider taking i-th item
for(int k = maxSubSetSize - 1; k >= 0; k--){ //each item must be taken once, hence loop backwards
for(int j = 0; j <= halfSum - data[i]; j++){
if (subsetSum[k][j] == 1 && (data[i] + j <= halfSum)){
subsetSum[k+1][j+data[i]] = 1;
}
}
}
}
for(int j = halfSum; j >= 1; j--){
if(subsetSum[maxSubSetSize][j] == 1){
System.out.println("Difference between sum: "+ ((sum - j) - j));
break;
}
}
}
Java Implementation....
public static void findMaxNumberInSlidingWindow(int[] numbers, int k) {
Queue<Integer> numberQueue = new LinkedList<Integer>();
for (int i = 0; i < numbers.length; i++) {
Queue<Integer> tmpQueue = new LinkedList<Integer>();
while (!numberQueue.isEmpty()) {
int index = numberQueue.remove();
if(index > i - k && numbers[index] > numbers[i]){
tmpQueue.add(index);
}
}
tmpQueue.add(i);
numberQueue = tmpQueue;
if (i >= k-1){
System.out.println(numbers[numberQueue.peek()]);
}
}
}
public static void concateMaxValue(int[] data, int left, int right) {
if(left < right) {
int part = partition(data,left,right);
concateMaxValue(data, left, part);
concateMaxValue(data, part + 1, right);
}
}
private static int partition(int[] data, int left, int right) {
int mid = (left+right)>>1;
int i = left;
int j = right;
String value1, value2;
while (true) {
while (i < right){
value1 = Integer.toString(data[mid])+Integer.toString(data[i]);
value2 = Integer.toString(data[i])+Integer.toString(data[mid]);
if (Integer.valueOf(value1)< Integer.valueOf(value2)){
i++;
} else {
break;
}
}
while (j > left) {
value1 = Integer.toString(data[mid])+Integer.toString(data[j]);
value2 = Integer.toString(data[j])+Integer.toString(data[mid]);
if (Integer.valueOf(value1)> Integer.valueOf(value2)){
j--;
} else {
break;
}
}
if (i < j){
swap(data, i, j);
i++;
j--;
}
else {
return j;
}
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
@above algorithm fails, if input array contains zero value
- Adnan Ahmad September 23, 2013public static void insertionOfTwoArrays(int data1[], int data2[]){
int i = 0, j = 0;
int prev = data1[0] < data2[0] ? data1[0] - 1 : data2[0] - 1;
while (i < data1.length && j < data2.length) {
if (data1[i] == data2[j] && prev != data1[i]){
System.out.print(data1[i]+ " ");
prev = data1[i];
i++;
j++;
}
else if(data1[i] < data2[j]){
i++;
}else {
j++;
}
}
}
Above Solution is wrong,
public static void sortZeroOne(int[] data) {
if (data == null || data.length==1){
return;
}
int left = 0;
int right = data.length-1;
while (left<right) {
while (data[left]==0){
left++;
}
while (data[right]==1){
right--;
}
if (left < right) {
data[left]=0;
data[right]=1;
left++;
right--;
}
}
}
reheapify of min heap takes O(nlogn) time complexity.
- Adnan Ahmad September 22, 2013/*
* Slight modification of KMP string searching algorithm
* Time complexity is O(m+n)
* This algorithm takes atmost 2n comparisons
*/
public int[ ] preProcessPattern(char[ ] ptrn) {
int i = 0, j = -1;
int ptrnLen = ptrn.length;
int[] b = new int[ptrnLen + 1];
b[i] = j;
while (i < ptrnLen) {
if(ptrn[i] == '\\' ){ // Ignore \d+ or \d*
i += 3;
}
while (j >= 0 && ptrn[i] != ptrn[j]) {
// if there is mismatch consider next widest border
j = b[j];
}
i++;
j++;
b[i] = j;
}
return b;
}
public boolean searchSubString(char[ ] text, char[ ] ptrn) {
int i = 0, j = 0;
// pattern and text lengths
int ptrnLen = ptrn.length;
int txtLen = text.length;
// initialize new array and preprocess the pattern
int[ ] b = preProcessPattern(ptrn);
while (i < txtLen) {
if(Character.isDigit(text[i])){
if(isMultipleDigit(ptrn, j)){
j+=3;
while(i < txtLen && Character.isDigit(text[i])){
i++;
}
}
if(isSingleDigit(ptrn, j)){
j+=3;
i++;
}
}
while (j >= 0 && text[i] != ptrn[j]) {
j = b[j];
}
i++;
j++;
// a match is found
if (j == ptrnLen) {
return true;
}
}
return false;
}
public boolean isMultipleDigit(char [ ]ptrn, int index){
boolean isMultipleDigit = false;
if(ptrn[index]== '\\' && ptrn[index+1]== 'd' && ptrn[index+2]== '*'){
isMultipleDigit = true;
}
return isMultipleDigit;
}
public boolean isSingleDigit(char [ ]ptrn, int index){
boolean isSingleDigit = false;
if(ptrn[index]== '\\' && ptrn[index+1]== 'd' && ptrn[index+2]== '+'){
isSingleDigit = true;
}
return isSingleDigit;
}
public static void main(String[] args) {
StringSearchingHavingRegexPattern stm = new StringSearchingHavingRegexPattern();
System.out.println(stm.searchSubString("abcd123456abcd".toCharArray(), "abcd\\d*abcd".toCharArray()));
System.out.println(stm.searchSubString("abcd12abcd".toCharArray(), "abc,d\\d*abcd".toCharArray()));
System.out.println(stm.searchSubString("abcd1abcd".toCharArray(), "abcd\\d*abcd".toCharArray()));
System.out.println(stm.searchSubString("abcd123456bcd".toCharArray(), "abcd\\d*abcd".toCharArray()));
System.out.println(stm.searchSubString("abcd1abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));
System.out.println(stm.searchSubString("abcd2abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));
System.out.println(stm.searchSubString("abcd7abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));
System.out.println(stm.searchSubString("abcd123456abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));
}
public static void printMultipleBrackets(int openParen, int closeParen, int openBracket, int closeBracket, int openCBracket, int closeCBracket, char[] str, int count) {
if (openParen < 0 || closeParen < openParen) {
return; // invalid state
}
if (openParen == 0 && closeParen == 0 && openBracket == 0 && closeBracket == 0 && openCBracket == 0 && closeCBracket == 0) {
System.out.println(str); // found one, so print it
}
else {
if (openParen > 0) { // try a left parenthesis, if there are some available
str[count] = '(';
printMultipleBrackets(openParen - 1, closeParen, openBracket, closeBracket, openCBracket, closeCBracket, str, count + 1);
}
if (openBracket > 0) { // try a left bracket, if there are some available
str[count] = '[';
printMultipleBrackets(openParen, closeParen, openBracket - 1, closeBracket, openCBracket, closeCBracket, str, count + 1);
}
if (openCBracket > 0) { // try a left curly bracket, if there are some available
str[count] = '{';
printMultipleBrackets(openParen, closeParen, openBracket, closeBracket, openCBracket - 1, closeCBracket, str, count + 1);
}
if (closeCBracket > openCBracket) { // try a right curly bracket, if there’s a matching left
str[count] = '}';
printMultipleBrackets(openParen, closeParen, openBracket, closeBracket, openCBracket, closeCBracket - 1, str, count + 1);
}
if (closeBracket > openBracket) { // try a right bracket, if there’s a matching left
str[count] = ']';
printMultipleBrackets(openParen, closeParen, openBracket, closeBracket - 1, openCBracket, closeCBracket, str, count + 1);
}
if (closeParen > openParen) { // try a right parenthesis, if there’s a matching left
str[count] = ')';
printMultipleBrackets(openParen, closeParen - 1, openBracket, closeBracket, openCBracket, closeCBracket, str, count + 1);
}
}
}
public static void printMultipleBrackets(int count) {
char[] str = new char[count*6];
printMultipleBrackets(count, count, count, count, count, count, str, 0);
}
public static void main(String[] args) {
printMultipleBrackets(1);
}
Repmarkhmitchell6, Analyst at ASAPInfosystemsPvtLtd
At first, tattooing was a hobby kind of thing for me. I didn’t spend too much time in tattoo ...
Repjesselblagg9, Cloud Support Associate at 247quickbookshelp
Hello, I am Jesse and I live in Springfield, USA. I am working in a company as an engineering technician ...
Reppaulinedsisk, Testing / Quality Assurance at Cloudmere, Inc.
I want to become a successful professional in a highly competitive technological world where performance is rewarded with exciting new ...
Reptaylorjose221, Production Engineer at BT
Graphic designer with a strong background in marketing design.Having a day off during the week to do whatever I ...
Repileenjconnelly, Cloud Support Associate at Absolute Softech Ltd
I have extensive experience in providing breaking news and giving precise details to the viewers. Interested in leading/working with ...
Repdorarwoods, Kuwait airways reservations at Aspire Systems
I am an Application engineer in the network chef company. In my free time, I enjoy reading programming and technology ...
RepHi, I am Anne from Portsmouth, USA. I have been working as a freelance digital illustrator specialized in 3D character ...
Repshinchunigo, Benefits clerk at Good Times
Votaw, Top Duties and Qualifications Benefits clerk . It is responsible for performing administrative tasks to support daily business operations. My ...
Repeffiefranke, Mail clerk at Envirotecture Design
Hello, I am Effie Mail clerk . I sort mail by department and category, utilizing sorting machines and similar administrative technology ...
Repgoamgivheler, Accountant at Lava
I am working as a nurse in Bali Boer Cafarius. I enjoy relationships with patients and their families. It has ...
RepArnoldTate, Title searcher at Keeney's
I am a Title searcher with 8+ years of experience . In real estate business and law, a title search or ...
Repmarkemorgan007, Applications Developer at Big Fish
I am Mark From Fresno city in USA.I working as a tour guide and also help for make a ...
Time Complexity: O(n), Space Complexity: O(n)
Store maximum indexes of left sub array and right sub array for each index and multiply them.
- Adnan Ahmad January 28, 2017