vicky17D
BAN USERThat will works only if the array can be converted to an integer. If the length of array is longer than the value an int/Integer can hold, that won't work.
For ex. {1,2,3,4,5,6,7,8,9,10,11,12,12,13,14,15,16,17,1,8} + {1,2,3} won't work
But yes, for the examples in the problem statement, it will work.
public class ArraySumElementWiseDemo {
static int[] addArraysElementWise(int[] array1, int[] array2) {
int auxResultArrayLength;
int[] smallerArray;
int[] biggerArray;
int[] emptyArray = {};
if(array1.length == 0 && array2.length == 0) return emptyArray;
if(array1.length == 0) return array2;
if(array2.length == 0) return array1;
if (array1.length >= array2.length) {
auxResultArrayLength = array1.length + 1; //+1 to store the carry over
biggerArray = array1;
smallerArray = array2; //to traverse only until the smaller array
} else {
auxResultArrayLength = array2.length + 1; //+1 to store the carry over in case needed
biggerArray = array2;
smallerArray = array1;
}
int[] auxResultArray = new int[auxResultArrayLength];
int carryOver = 0;
int tempSum = 0; //to store temporary sum
for (int i = smallerArray.length -1, j = biggerArray.length -1 ;i > -1; i--, j--) {
tempSum = smallerArray[i] + biggerArray[j] + carryOver;
if (tempSum < 10) {
auxResultArray[j+1] = tempSum;
carryOver = 0;
} else {
carryOver = 1;
auxResultArray[j+1] = tempSum - 10;
}
}
//Now add carry on to the bigger array and keep on copying the bigger array + carryOver to the auxResultArray
for (int j = biggerArray.length - smallerArray.length - 1; j > -1; j--) {
tempSum = biggerArray[j] + carryOver;
if (tempSum < 10) {
auxResultArray[j+1] = tempSum;
carryOver = 0;
} else {
carryOver = 1;
auxResultArray[j+1] = tempSum - 10;
}
}
//Add the carry over to the first element of auxResultArray
auxResultArray[0] = carryOver;
return auxResultArray;
}
public static void main(String[] args) {
int[] array1 = {1,2,3};
int[] array2 = {2,3,4} ;
System.out.println(Arrays.toString(addArraysElementWise(array1, array2)));
}
}
Only minor differnece is that if there is no carry over, this algorithm still appends 0 in the beginning.
- vicky17D November 26, 2015Take the input as Integer Array.
Store the position where the first greater than or less than occurs (keep skipping if the elements are equal). Store the comparison value i.e. 1 or -1 in first
From that point on, find the next less than, greater than (next in this case) and compare it the last stored i.e first in this case.
At then end, the number of less thans and greater thans are found. Return result+!
public class ZigZagArrayMaxDemo {
public static int maxZigZagLength(Integer[] input) {
if(input.length ==0 ) throw new IllegalArgumentException("array length is 0");
int result = 0;
int first = 0;
int startIndex = 0;
for(int i = 0; i < input.length - 1; i++) {
first = input[i].compareTo(input[i+1]);
if(first !=0) {
startIndex = i+1;
result = 1;
break;
}
}
if(first == 0) return 0;
int next;
for (int i = startIndex; i < input.length - 1; i++) {
next = input[i].compareTo(input[i+1]);
if(next == 0) continue;
if((next != first)) {
result++;
first = next;
}
}
return result+1;
}
public static void main(String[] args) {
Integer[] inputArray = {1,42,54,20,1 };
System.out.println(maxZigZagLength(inputArray));
}
}
This solution does not have any additional memory requirements. No heap, array needed.
Space complexity = 1
Time complexity = nk or more specifically n*(k^2) where k is number of streams (small number) and n is number of elements in a stream (worst case - number of elements in the longest stream.
1. K streams; read the first element of the first non-empty stream
2. Compare it with the first element of all streams. Find the smallest. Store the pointer to the stream to which the smallest number belongs to
3. Pop out the first element from the stream to which pointer points to.
4. Keep on doing until all streams are empty.
public class MergeSortedStreamsDemo {
static ArrayList<Integer> mergeStreams(ArrayList<ArrayList<Integer>> streams) {
ArrayList<Integer> resultStream = new ArrayList<>();
int streamPointer = 0;
int numberOfStreams = streams.size();
int emptyStreams = 0;
int numberToBeKickedOut = Integer.MAX_VALUE;
while (emptyStreams != numberOfStreams) {
emptyStreams = 0; //set empty stream to 0 everytime
//Get the first element of first non-empty stream
for(int i = 0; i < numberOfStreams; i++) {
if(streams.get(i).size() != 0) {
numberToBeKickedOut = streams.get(i).get(0); //Just peek the value
streamPointer = i; //stream number needs to be remembered, for the pop operation later
break;
} else {
emptyStreams += 1;
if(emptyStreams == numberOfStreams) return resultStream;
}
}
for (int i = 0; i < numberOfStreams; i++) {
ArrayList<Integer> stream = streams.get(i);
if (stream.size() != 0) {
if (numberToBeKickedOut > stream.get(0)) {
numberToBeKickedOut = stream.get(0); //peek the value
streamPointer = i; //stream number to for pop operation later
}
}
}
resultStream.add(streams.get(streamPointer).remove(0)); //Pop the value and put it in the result stream
// streamPointer = 0;
}
return resultStream;
}
public static void main(String[] args) {
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
ArrayList<Integer> list3 = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> inputStreams = new ArrayList<>();
list1.add(1);
list1.add(2);
list1.add(3);
list2.add(4);
list2.add(5);
list2.add(6);
inputStreams.add(list1);
inputStreams.add(list2);
inputStreams.add(list3);
System.out.println(mergeStreams(inputStreams));
}
}
1. Take another array of length K, 'kLengthArray'
2. Add K elements to this array and sout(sum/k)
3. Now set a pointer at 0 index of this new array
4. If there are more elements coming from the stream, replace the element at pointer index with the new element. Increment the pointer. If pointer == K i.e. the length of the array, set it to 0 again.
public class MovingAverageDemo {
static void movingAverage(float[] dataStream, int K) {
float[] kLengthArray = new float[K];
int i;
for(i = 0; i< dataStream.length && i < K; i++) {
kLengthArray[i] = dataStream[i];
}
System.out.println(sumOfArray(kLengthArray)/ i);
if(dataStream.length > K ) {
int pointer = 0;
for(int z = i ; z < dataStream.length; z++) {
kLengthArray[pointer] = dataStream[z];
pointer++;
if(pointer == K) {
pointer = 0;
}
System.out.println(sumOfArray(kLengthArray)/K);
}
}
}
static float sumOfArray(float[] data) {
float sum = 0;
for(int i = 0; i< data.length ; i++) {
sum = sum + data[i];
}
return sum;
}
public static void main(String[] args) {
float[] dataStream = {1,2,3,4,5,6,7,8,9,10,11,12};
movingAverage(dataStream, 3);
}
}
Space Complexity = K
Time complexity is K*n.
K is supposed to be a small number. If K is in millions, then the average won't change much anyways by the next number coming.
All suggestions/improvements welcome. Thanks
Steps:
1. Split the String by " "
2. Go through the array and keep adding the elements to a new String until the length is less than charLimit
import java.util.ArrayList;
public class SplitTextDemo {
static ArrayList<String> splitText(String message, int charLimit) {
return splitTextAuxUsingSplit(message, charLimit);
}
static ArrayList<String> splitTextAuxUsingSplit(String message, int charLimitOriginal) {
//Decrease the char limit to accomodate chunk number at the end i.e. (1/3). For now assuming, the message chunks won't be more than 9
int charLimit = charLimitOriginal - 5;
//New arraylist to store message chunks
ArrayList<String> result = new ArrayList<String>();
String[] splitted = message.split(" ");
String temp;
for (int i = 0; i < splitted.length - 1; i++) {
temp = splitted[i];
//while length of temp and the next element combined is less than charLimit, temp = temp + next element
//Last element to be taken care of after this loop
while ((temp + 1 + splitted[i + 1]).length() <= charLimit && i + 1 < splitted.length - 1) { //+1 for space
temp = temp + " " + splitted[i + 1];
i++;
}
result.add(temp);
}
//Take care of the last element
//Add the last element from splitted to the last element of result if their combined length is less than charLimit
String lastElement = result.get(result.size() - 1);
if (lastElement.length() + 1 + splitted[splitted.length - 1].length() < charLimit) { //+1 for space
result.set(result.size() - 1, lastElement + " " + splitted[splitted.length - 1]);
} else {
result.add(splitted[splitted.length - 1]);
}
//append message chunk number for ex (1/3)
int resultSize = result.size();
for(int i = 0; i < resultSize; i++) {
result.set(i, result.get(i) +"("+ (i+1) + "/" + resultSize + ")" );
}
return result;
}
public static void main(String[] args) {
String message;
int charLmit;
message = "Hi Sivasrinivas, your Uber is arriving now! And this is a bigger text";
charLmit = 25;
ArrayList<String> result = splitText(message, charLmit);
for(String item : result) {
System.out.println("Length = " + item.length() + " : " +item );
}
System.out.println(result.toString());
}
}
1. Take a HashSet
2. Keep putting the value until you find a value that already exists.
3. Will be done in one scan only
- vicky17D November 29, 2015