micvog
BAN USERPassionate about software development, large-scale processing, now involved in a tech start-up. Always keen to minimize technical debt, so why not drop me a tweet? @mvogiatzis
Use two Suffix Trees, one for the normal word and one for the reverse string. Then return the occurrences of the substrings by calling SuffixTree#search(substring).
String search in O(m) complexity, where m is the length of the sub-string (but with initial O(n) time required to build the suffix tree for the string)
Link: en.wikipedia.org/wiki/Suffix_tree
Starting from the last element of b and going towards the first, we apply a merge similar to the merge step of mergeSort.
If B has moved completely and A still has elements, move the remaining elements of A to B.
Otherwise, no need to move anything. B elements are already there!
public void mergeSorted(int[] a, int[] b){
//start from the end of b
//kind of merge sort step of mergeSort algorithm
int current = b.length-1;
int helperA = a.length-1;
int helperB = b.length/2-1;
while (helperA>=0 && helperB>=0){
if (arr[helperA]>=arr[helperB])
{
b[current] = arr[helperA];
helperA--;
}
else{
b[current] = arr[helperB];
helperB--;
}
current--;
}
if (helperA>0)
{
while(helperA>=0)
b[current--] = arr[helperA--];
}
//else do nothing, b elements are already there
}
You should find the longest partial sequence that sums to the bigger number
//PseudoCode
//if next is positive add it to part sum
//if partSum > maxSum make part the max, adjust indeces.
//else if negative
//if (maxSum+value)>0
//if yes, we need it. Add it to the part sum.
//else reset the index to this element+1 and make partsum =0;
public class MaxPartSum {
public PartSum findPartMaxSum(int[] arr){
int partSum =0;
int maxSum = 0;
int startIndex=0;
int endIndex =0;
int i=0;
while (i<arr.length){
if (arr[i]>0) //num is positive
{
partSum += arr[i]; //increase partSum
if (partSum>maxSum){
maxSum = partSum;
endIndex = i;
}
}
else{ //num is negative or zero
if (maxSum+arr[i] > 0)
partSum+=arr[i];
else //the element doesn't help at all
{
partSum=0;
startIndex = i+1;
}
}
i++;
}
System.out.println("Max Sum: " + maxSum);
System.out.println("Index " + startIndex + " to " + endIndex);
PartSum p = new PartSum(maxSum, startIndex, endIndex);
return p;
}
class PartSum{
int maxSum;
int startIndex;
int endIndex;
public PartSum(int maxSum, int startIndex, int endIndex){
this.maxSum = maxSum;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
}
public static void main (String[] args){
MaxPartSum m = new MaxPartSum();
int[] arr = {-1, -2, 5, -2, -3};
m.findPartMaxSum(arr);
}
}
1)Have an abstraction layer that shows the 2 arrays as logically one.
2) Perform merge sort on the logical array.
3) Find median
Code:
public int median2Arrays(int[] arr1, int[] arr2){
CombinedArray arr = new CombinedArray(arr1, arr2);
mergeSort(arr);
return arr.getMedian();
}
public class CombinedArray{
private int[] arr1;
private int[] arr2;
private length=0;
public CombinedArray(int[] arr1, int[] arr2){
this.arr1=arr1;
this.arr2=arr2;
length = arr1.length + arr2.length;
}
public int getLength(){
return length;
}
public int get(int index){
if (index>=length)
throw new Exception("Array index out of bound");
if (index>=arr1.length)
return arr2[arr1.length-index];
return arr1[index];
}
public void set(int index, int value){
if (index>=length)
throw new ArrayIndexOutOfBound("Arr out of bound");
if (index>=arr1.length)
arr2[arr1.length-index] = value;
else
arr1[index] = value;
}
public int getMedian(){
if (length%2==1)
{
return get(length/2 + 1);
}
return (get(length/2) + get(length/2 + 1)) / 2
}
}
public void mergeSort(CombinedArray array){
int[] helper = new helper[array.getLength()-1];
mergeSort(array, helper, 0, array.getLength()-1);
}
public void mergeSort(CombinedArray array, int[] helper, int left, int right){
if (left<right){
int mid = (left+right)/2;
mergeSort(array, helper, left, mid);//sort left
mergeSort(array, helper, mid+1, right);//sort right
merge(array, helper, left, mid, right);
}
}
public void merge(CombinedArray array, int[] helper, int left, int mid, int right){
//use helper array to copy everything
for (int i=0; i<array.getLength(); i++){
helper[i] = array.get(i);
}
int helperLeft = left;
int helperRight = mid+1;
int current = left;
while (helperLeft<=mid && helperRight<=right){
if (helper[helperLeft]<=helper[helperRight])
{
array.set(current, helper[helperLeft]);
helperLeft++;
}
else
{
array.set(current, helper[helperRight]);
helperRight++;
}
current++;
}
//copy the rest of the helper left array to target array
while(helperLeft<=mid)
array.set(current++, helper[helperLeft++]);
}
Solution (considers duplicates as well):
One half of the array is normally ordered. It's either the left or the right. Find the normally ordered half and perform binary search on that if X is inside it. Otherwise, search the other half.
Complexity: O(logN) without duplicates, O(n) with all elements duplicates (because we need to search both halves)
CODE:
public int search(int[] array, int n){
return search(array, n, 0, array[array.length-1]);
}
private int search(int[] array, int n, int left, int right){
if (left>right)
return -1;
int mid = (left+right) / 2;
if (array[mid] == n)
return mid;
//find the normally ordered array and search in it
if (array[left] < array[mid])
{
//left is normally ordered
if (array[left]<=n && n<=array[mid])
return search(array, n, left, mid-1); //search left
else
return search(array, n, mid+1, right); //search right
}
else if (array[mid]<array[right]){
//right is normally ordered
if (array[mid] <= n && n <= array[right])
return search(array, n, mid+1, right);
else
return search (array, n, left, mid-1);
}
else if (array[left]==array[mid]){ //there are duplicates
if (array[mid]!=array[right])
return search(array, n, mid+1, right);
else
{
int l = search(array, n, left, mid-1);
if (l==-1)
return search(array, n, mid+1, right);
return l;
}
}
return -1;
}
It seems to me like that giving the full concatenated String is not necessary. What is needed is to answer if a chain is possible given a list of Strings.
Methodology:
Iterate over words and store the first and the last chars in two maps Map<Character, Integer>
If the two maps have the same first and last chars count then they can match.
Note that we can tolerate up to 1 difference. (The first/last char of the final String is not connected with any).
Code:
public boolean concatAll (String[] words){
Map<Character, Integer> firstsMap = new HashMap<Character, Integer>();
Map<Character, Integer> endingMap = new HashMap<Character, Integer>();
//populate maps
for (String s : words)
{
//assume that empty characters are always attachable
if (s.equals(""))
continue;
char beginChar = s.charAt(0);
addToMap(firstsMap, beginChar);
char lastChar = s.charAt(s.length()-1);
addToMap(endingMap, lastChar);
}
int notMatching=0;
for (Entry<Character, Integer> e : firstsMap.entrySet()){
Integer firstCount = e.getValue();
if (notMatching>1)
return false;
Integer endingCount = endingMap.get(e.getKey());
if (endingCount!=null){
if (!(firstCount == endingCount))
notMatching+=Math.abs(endingCount-firstCount);
}
else
{
notMatching+=firstCount;
}
}
if (notMatching>1)
return false;
return true;
}
private void addToMap(Map<Character, Integer> map, char c){
Integer i = map.get(c);
if (i==null)
i=0;
map.put(c, i+1);
}
EDIT: Time Complexity O(n) where n the number of words in the array.
- micvog October 03, 2013
Looks like the n*logn brute-force is equivalent to this one. Your while loop adds an additional logn complexity no?
- micvog October 26, 2013