gigi84
BAN USER- 3of 3 votes
AnswersThis question was asked in the chat, just adding here with the solution. I don't know for which company it is.
Replace wild cards with all possible combinations of zeros and ones using recursion.Input String: 0?1? Output: 0010, 0011, 0110, 0111
This is my solution using recursion:
- gigi84import java.util.*; public class ReplaceWildcardsRec { public static List<String> expandString(String s, int i) { List<String> l = new ArrayList<String>(); if(i>s.length()-1) { l.add(""); return l; } for(String expanded: expandString(s,i+1)) { if(s.charAt(i)=='?') { l.add('0'+expanded); l.add('1'+expanded); } else { l.add(s.charAt(i)+expanded); } } return l; } public static void main(String[] args) { List<String> l = new ArrayList<String>(); String s = "1111?"; l = expandString(s,0); System.out.println(l); } }
| Report Duplicate | Flag | PURGE
String Manipulation
O(n) algorithm:
the idea is to increment the possible pattern length by 1 and check if you can arrive to the end of the string using that pattern, otherwise you increment patternlength by 1 until patternlength<=s.length/2
- Use two pointers i and j
- Initialize i=0, PatternLength=1, j=i+PatternLength
while PatternLength<=s.length/2 && j<s.length
if(s.charAt(i)==s.charAt(j))
increment i to i=(i+1)%s.length and j to j++
else
increment patternlength
start checking from patternlength+1
then count the number of repetitions of the pattern in the string by doing j/patternlength,
if patternrepetitions*patternlength==s.length the string is following the pattern.
here is a step by step description of the algorithm for the string "xyzxyzxyz"
Strng s = "xyzxyzxyz";
Step 1:
i=0 j=1
s[i]=x,s[j]=y
PatternLength: 1 PatternRepetitions: 0
Step 2:
i=0 j=2
s[i]=x,s[j]=z
PatternLength: 2 PatternRepetitions: 0
Step 3:
i=0 j=3
s[i]=x,s[j]=x
PatternLength: 3 PatternRepetitions: 0
Step 4:
i=1 j=4
s[i]=y,s[j]=y
PatternLength: 3 PatternRepetitions: 1
Step 5:
i=2 j=5
s[i]=z,s[j]=z
PatternLength: 3 PatternRepetitions: 1
Step 6:
i=0 j=6
s[i]=x,s[j]=x
PatternLength: 3 PatternRepetitions: 2
Step 7:
i=1 j=7
s[i]=y,s[j]=y
PatternLength: 3 PatternRepetitions: 2
Step 8:
i=2 j=8
s[i]=z,s[j]=z
PatternLength: 3 PatternRepetitions: 2
Final Step:
String: xyzxyzxyz
Pattern: xyz
PatternLength: 3 PatternRepetitions: 3
9 steps to check for a string of length 9
This is the code in java to implement this algorithm:
public static boolean followPattern(String s) {
if(s==null || s.length()==0) return false;
int i = 0;
int j = 1;
int patternlength = 1;
int repetitions = 0;
int steps = 1;
while(patternlength<=s.length()/2 && j<s.length()) {
if(s.charAt(i)==s.charAt(j)) {
j++;
i=(i+1)%patternlength;
repetitions=j/patternlength;
}
else {
i=0;
patternlength++;
j=i+patternlength;
repetitions=0;
}
steps++;
}
if(patternlength*repetitions==s.length()) {
//System.out.println("String: "+s+"\nPattern: "+s.substring(0,patternlength)+"\nPatternLength: "+patternlength+"\nRepetitions: "+repetitions);
return true;
}
else {
return false;
}
}
Sure, that is a good analysis, always good to think about extreme cases. In a real problem we can think of k much smaller than n (millions of people -> a lot of repetitions in ages). The largest is the array and the more repetitions we will have, the more the performance will improve with respect to n;
Another improvement we could make is:
before starting the binary search for each element, compare the element at startindex to the last element of the array, if they are equal we have already finished, just return array.length-startindex to get the number of people with that age. This will speed up the algorithm when we have cases like:
[13,13,13,13,13,13,13,13,13,13,13,13,13]
or
[1,4,6,15,37,37,37,37,37,37,37,37,37,37]
with lot of repetitions in the last part of the array, or array with all the same values.
- gigi84 December 31, 2014it is O(n) in your example ([8,9,11,12,15,16,18,20]), check the first control if in the binSearchEnd method, it immediately returns the lastindex if the next element is different (so lastindex will be equal to firstindex for that age) -> if there is just one element for that age, it won't perform binary search. O(n) is the best you can do in the example you provide, because we need to retrieve all the ages present in the input array, so if there is just one person for each age, we will have to retrieve n elements
- gigi84 December 31, 2014This problem can be solved in less than O(n) using a modified binary search.
For each element in the array ages[] (starting from 0) we record the first index i where this age is present, then we search using binary search the last index where this age is present.
The number of people with the same age will be given by lastindex-firstindex for this age.
Then we retake the search from lastindex+1 for the next age.
1+(lastindex-startindex) to get the number of people with the same age for each key in the map.
public static Map<Integer,Integer> countAges(int[] ages) {
if(ages==null || ages.length==0) {
return new HashMap<Integer,Integer>();
}
int i = 0;
int end = 0;
Map<Integer,Integer> count = new HashMap<Integer,Integer>();
int from = 0;
int to = 0;
while(i<ages.length) {
from = i;
end=binSearchEnd(ages,i,ages.length);
to = end;
count.put(ages[i], 1+to-from);
i=end+1;
}
return count;
}
and this is the method to search for the last index of an age in the array of ages using binary search:
public static int binSearchEnd(int[] ages, int start, int end) {
if(start+1>ages.length-1 || ages[start]!=ages[start+1]) return start;
if(ages[start]==ages[ages.length-1]) return ages.length-1;
int i = start+1;
int k = ages[start];
while(start<i && i+1<ages.length) {
//System.out.println("i: "+i);
if(ages[i]==k && ages[i+1]!=k) return i;
else if(ages[i]>k) {
end=i;
i=(start+i)/2;
}
else { //ages[i]==k && ages[i+1]==k
start=i;
i=(i+end)/2;
}
if(i>=ages.length-1) return i;
}
return i;
}
And Here is the complete code to test the algorithm, you can use
int[] genAgesArray(int n)
to generate a sorted array of ages and:
void printArray(int[] a)
to print the array
here is the full code for testing:
import java.util.*;
public class CountAgesSortedArray {
public static Map<Integer,Integer> countAges(int[] ages) {
if(ages==null || ages.length==0) {
return new HashMap<Integer,Integer>();
}
int i = 0;
int end = 0;
Map<Integer,Integer> count = new HashMap<Integer,Integer>();
int from = 0;
int to = 0;
while(i<ages.length) {
from = i;
end=binSearchEnd(ages,i,ages.length);
to = end;
count.put(ages[i], 1+to-from);
i=end+1;
}
return count;
}
public static int binSearchEnd(int[] ages, int start, int end) {
if(start+1>ages.length-1 || ages[start]!=ages[start+1]) return start;
if(ages[start]==ages[ages.length-1]) return ages.length-1;
int i = start+1;
int k = ages[start];
while(start<i && i+1<ages.length) {
//System.out.println("i: "+i);
if(ages[i]==k && ages[i+1]!=k) return i;
else if(ages[i]>k) {
end=i;
i=(start+i)/2;
}
else { //ages[i]==k && ages[i+1]==k
start=i;
i=(i+end)/2;
}
if(i>=ages.length-1) return i;
}
return i;
}
public static int[] genAgesArray(int n) {
if(n<1) {
System.out.println("ERROR Generating Ages: N must be > 0");
return null;
}
Random r = new Random();
int[] ages = new int[n];
ages[0] = r.nextInt(2);
for(int i=1;i<n;i++) {
ages[i]=ages[i-1]+r.nextInt(r.nextInt(5)+1);
}
return ages;
}
public static void printArray(int[] a) {
if(a==null || a.length==0) {
System.out.println("ERROR Printing Array: Empty Array");
return;
}
for(int i=0;i<a.length-1;i++) {
System.out.print(a[i]+",");
}
System.out.println(a[a.length-1]);
}
public static void main(String[] args) {
int[] ages = genAgesArray(10);
//int[] ages = {0,1,1,1,1,1,1,1,1,1};
printArray(ages);
System.out.println(countAges(ages));
}
}
If you have the pairs:
(1,2)(1,3)(1,4)(1,7)
you can retrieve them as:
(1,(2,3,4,7))
and you won't loss any information;
with my algorithm for each i you should go down the BST built with the elements of B[] with index j > i, and associate that i with the sublist of the elements already present in the BST that are smaller of A[i].
so:
for each i from A.length-1 to 0; O(n)
- add the element B[i+1] (if exists) to the BST; O(logn)
- go down the BST (that holds the elements of B[] with index j>i) and find which should be the position of A[i] in the BST O(logn)
- associate i with the sublist of smaller elements.
MaxLR[] = maximum subarray sum at each position of the input array going left to right. O(n)
MinLR[] = minimum subarray sum at each position of the input array going left to right. O(n)
MaxRL[] = maximum subarray sum at each position of the input array going right to left. O(n)
MinRL[] = minimum subarray sum at each position of the input array going right to left. O(n)
Then for each position i, get the currentMaxdifference by getting the greatest difference between the maximum left-to-right at pos i and the minimum right-to-left at position i+1 (MaxLR[i]-MinRL[i+1]), and the minimum left-to-right at pos i and the maximum right-to-left at pos i+1 (MaxRL[i+1]-MinLR[i]). If the current max diff is greater than the general MaxDiff change maxDiff to currentMaxDiff.
Here is the code that implement this solution, you can use genArray to generate a random array and printArray to print it.
public class DisjointSubarraysDifference {
public static int maxDiffSubArrays(int[] a) {
// Compute max left -> right
int[] maxlr = new int[a.length];
maxlr[0] = a[0];
for(int i=1;i<a.length;i++) {
maxlr[i] = (maxlr[i-1]+a[i]>a[i])?maxlr[i-1]+a[i]:a[i];
}
// Compute min left -> right
int[] minlr = new int[a.length];
minlr[0] = a[0];
for(int i=1;i<a.length;i++) {
minlr[i] = (minlr[i-1]+a[i]<a[i])?minlr[i-1]+a[i]:a[i];
}
// Compute max right -> left
int[] maxrl = new int[a.length];
maxrl[a.length-1] = a[a.length-1];
for(int i=a.length-2;i>=0;i--) {
maxrl[i] = (maxrl[i+1]+a[i]>a[i])?maxrl[i+1]+a[i]:a[i];
}
// Compute min right -> left
int[] minrl = new int[a.length];
minrl[a.length-1] = a[a.length-1];
for(int i = a.length-2;i>=0;i--) {
minrl[i] = (minrl[i+1]+a[i]<a[i])?minrl[i+1]+a[i]:a[i];
}
int maxDiff = 0;
int currDiff = 0;
for(int i=0;i<a.length-1;i++) {
currDiff = Math.max((maxlr[i]-minrl[i+1]),(maxrl[i+1]-minlr[i]));
if(currDiff>maxDiff) {
//System.out.println("New Breaking Point: "+i);
maxDiff=currDiff;
}
}
return maxDiff;
}
public static int[] genArray(int n) {
Random r = new Random();
int[] a = new int[n];
for(int i=0;i<n;i++) {
a[i] = r.nextInt(10)-4;
}
return a;
}
public static void printArray(int[] a) {
for(int i=0;i<a.length-1;i++) {
System.out.print(a[i]+",");
}
System.out.println(a[a.length-1]);
}
public static void main(String[] args) {
int[] a = genArray(10);
printArray(a);
int maxDiff = maxDiffSubArrays(a);
System.out.println("MaxDiff "+maxDiff);
}
}
Sorry, I still do not agree...to describe the complexity of an algorithm you can use both average and worst case complexity, both described by the Big O notation. Again take into account QuickSort that is a well known algorithm, and has an average case performance of O(nlogn) and a worst case performance of O(n^2). And it is always presented as one of the best perfoming sorting algorithms, often with better performance than MergeSort that has a complexity of O(nlogn) in both average and worst case.
- gigi84 December 30, 2014Therefore you recognize that this has O(nlogn) complexity and a worst case of O(n^2), that is definitely better than an algorithm that has a complexity of O(n^2) in the average and worst case. Example given: the quick sort algorithm has an average compexity of O(nlogn) and a worst case of O(n^2), and is definitely better than bubble sort that is O(n^2) in both average and worst case...
- gigi84 December 30, 2014I'm pretty sure that adding an element to a BST is O(logn), such as searching for an element or deleting it. The cost of those operations on a BST is proportional to the height of the BST. The height of a BST is log(n). The worst case is present only if the height of the BST is n, that is a completely unbalanced tree. But in this case the tree behave like a linked list, and is called a degenerate tree.
- gigi84 December 29, 2014In order to find the Longest Palindromic Substring in O(n) we need to apply the Manacher's Algorithm. It works like this:
Let's say that we have the input string S:
S = ccacaacaba
First Step: Preprocess input string by inserting special Character '#' between each char in the string:
T = ^#c#c#a#c#a#a#c#a#b#a#$
Characters ^ and $ are used just to avoid bounds checking. Let's call this preprocessed String T.
Then we need to create an Array (P) with the same size of the preprocessed String T. This array will have at each position i the size of the longest Palindrome centered in i.
T = ^ # c # c # a # c # a # a # c # a # b # a # $
P = 0 0 1 2 1 0 3 0 3 0 1 6 1 0 3 0 1 0 3 0 1 0
In order to compute all the value of P efficiently, we can use the simmetric property of P, for example if we take into account the palindrome centered at position i=11, T[11] ("acaaca"), we can see that the value of P at position i+1 is equal at the value of P at position i-1 (T[i-1]==T[i+1]) and T[i-2]==T[i+2], T[i-3]==T[i+3] ... T[i]==T[i_mirror].
The problem is that this property is not always valid. Let's take into account i+5 and i-5. Note T[i+5]==1 and T[i-5]==3. This happens because the Palindrome centered at i-5 expands beyond the left limit of the simmetric center that we took into account P[11], with palindromic length of 6. This means that the simmetric property is guaranteed only if P[i_mirror] <= R-i, where R is the Right limit of the Palindrome centered at the simmetric center C that we are taking into account (in this case P[11]). If R-i<P[i_mirror] then we only know that P[i]>=R-i. Thus we need to expand the palindrome size centered at i char by char:
while(T.charAt(i+1+P[i])==T.charAt(i-1-P[i]))
P[i]++;
the last step is to know when to move the simmetric center C and the right limit R to the right with i. This happens when i past the right limit R of C:
if(R<i+P[i]) {
C=i;
R=i+P[i];
}
Expanding a palindrome take at most O(n) and moving the center also at most O(n), therefore this algorithm performs with O(2n) complexity, thus this is a linear algorithm to find the longest Palindrome substring.
In my code you can use
String stringGenerator(int n)
to generate a random String from the alphabet (first var in the method) of length n;
the method
String manacherizeString(String s)
preprocess the input string by inserting special characters and the longest palindromic substring is retrieved by the method
String manacher(String s)
Here is the complete code implementing the Manacher Algorithm in java:
import java.util.Random;
public class LongestPalindromicSubstring {
public static String manacherizeString(String s) {
if(s.length()==0) return "^$";
String p = "^#";
for(int i=0;i<s.length();i++) {
p+=s.charAt(i)+"#";
}
p+="$";
return p;
}
public static String manacher(String s) {
String T = manacherizeString(s);
System.out.println(T);
int R = 0;
int C = 0;
int imirror;
int[] P = new int[T.length()];
for(int i=1;i<T.length()-1;i++) {
imirror = C-(i-C);
if(R>i) {
P[i] = Math.min(P[imirror],R-i);
}
else {
P[i] = 0;
}
while(T.charAt(i+1+P[i])==T.charAt(i-1-P[i]))
P[i]++;
if(R<i+P[i]) {
C=i;
R=i+P[i];
}
}
int maxLength = 0;
int maxCenter = 0;
for(int i=0;i<P.length-1;i++) {
System.out.print(P[i]+" ");
if(P[i]>maxLength) {
maxLength = P[i];
maxCenter = i;
}
}
System.out.println("\nMaxLength: "+maxLength+" MaxCenter: "+maxCenter);
return s.substring((maxCenter-1-maxLength)/2,((maxCenter-1-maxLength)/2)+maxLength);
}
public static String stringGenerator(int n) {
//String alphabet = "abcdefghiklmnopqrstuvxyz";
String alphabet = "abc";
String s = "";
Random r = new Random();
for(int i=0;i<n;i++) {
s+=alphabet.charAt(r.nextInt(alphabet.length()));
}
return s;
}
public static void main(String[] args) {
String s = stringGenerator(10);
System.out.println(s);
System.out.println("Longest Palindromic Substring:\n"+manacher(s));
}
}
I convert the input expression in a postfix expression, represented with a List<String>.
Then I push this postfix version into a Stack starting from the last element of the postfix expression.
To evaluate the postfix expression inserted into a stack I pop elements and push them into an helper stack until I find an operator. When I find an operator in the Stack of the postfix expression I pop 2 elements from the helper stack and apply the operator to thos two elements. then push back the result of this operation to the helper stack. Keep going until the stack with the postfix expression will be empty. At the end you will have the result in the helper stack.
Here is the code to implement this solution, the method
List<String> getExpressionTokens(String s)
convert the input expression string into single tokens and the method
List<String> toPostfix(String s)
convert an input infix expression String into a postfix expression.
Those two previous methods are used in the method
String eval(String s)
that evaluate an expression and retrieve the result in a String.
Here is the complete code for this solution:
import java.util.*;
public class EvaluateExpression {
public static List<String> toPostfix(String s) {
List<String> postfix = new ArrayList<String>();
Map<String,Integer> operators = new HashMap<String,Integer>();
operators.put("*", 1);
operators.put("/", 1);
operators.put("+", 2);
operators.put("-", 2);
List<String> tokens = getExpressionTokens(s);
Stack<String> stack = new Stack<String>();
for(String token: tokens) {
if(operators.containsKey(token)) {
if(stack.size()==0) {
stack.push(token);
}
else {
while(stack.size()>0 && operators.get(stack.peek())<=operators.get(token)) {
postfix.add(stack.pop());
}
stack.push(token);
}
}
else {
postfix.add(token);
}
}
while(stack.size()>0) {
postfix.add(stack.pop());
}
return postfix;
}
public static List<String> getExpressionTokens(String s) {
List<String> tokens = new ArrayList<String>();
String token = "";
Set<Character> operators = new HashSet<Character>();
operators.add('*');
operators.add('/');
operators.add('+');
operators.add('-');
for(int i=0;i<s.length();i++) {
if(!operators.contains(s.charAt(i))) {
token+=s.charAt(i);
}
else {
tokens.add(token);
tokens.add(String.valueOf(s.charAt(i)));
token = "";
}
}
if(token.length()>0) {
tokens.add(token);
}
return tokens;
}
public static String eval(String s) {
List<String> expr = toPostfix(s);
Set<String> operators = new HashSet<String>();
operators.add("*");
operators.add("/");
operators.add("+");
operators.add("-");
Stack<String> postfix = new Stack<String>();
Stack<String> helper = new Stack<String>();
for(int i=expr.size()-1;i>=0;i--) {
postfix.push(expr.get(i));
}
String token = "";
while(postfix.size()>0) {
token = postfix.pop();
if(operators.contains(token)) {
String el1 = helper.pop();
String el2 = helper.pop();
if(token.equals("*")) {
helper.push(String.valueOf(Double.valueOf(el2)*1.0*Double.valueOf(el1)));
}
if(token.equals("/")) {
helper.push(String.valueOf(Double.valueOf(el2)/1.0/Double.valueOf(el1)));
}
if(token.equals("+")) {
helper.push(String.valueOf(Double.valueOf(el2)+0.0+Double.valueOf(el1)));
}
if(token.equals("-")) {
helper.push(String.valueOf(Double.valueOf(el2)-0.0-Double.valueOf(el1)));
}
}
else {
helper.push(token);
}
}
if(helper.size()>0) {
return helper.pop();
}
else return "0";
}
public static void main(String[] args){
String expr = "12*3-4+2*8";
//System.out.println(expr);
//System.out.println(getExpressionTokens(expr));
//List<String> postfix = toPostfix(expr);
//System.out.println(postfix);
System.out.println(expr+" = "+eval(expr));
}
}
I think a suitable approach could be using a Binary Search Tree for the elements of B that have an index j>i.
We iterate from i=A.length-1 to 0 and keep updating the BST at each iteration by adding 1 element B[j] with j=i+1 (add an element to a BST costs O(logn)). Complexity O(nlogn)
If you have the pairs:
(1,2)(1,3)(1,4)(1,7)
you can retrieve them as:
(1,(2,3,4,7))
and you won't loss any information;
with my algorithm for each i you should go down the BST built with the elements of B[] with index j > i, and associate that i with the sublist of the elements already present in the BST that are smaller of A[i].
so:
Build a Binary Search Tree of the elements of the array B with index j>A.length.
for each i from A.length-1 to 0; O(n)
- add the element B[i+1] (if exists) to the BST; O(logn)
- go down the BST (that holds the elements of B[] with index j>i) and find which should be the position of A[i] in the BST O(logn)
- associate i with the sublist of smaller elements in the BST.
In order to compute the sum of all the elements within the area of rectangle in O(1) running time we can preprocess the Matrix to have in each element of the Matrix the sum of all the elements between (0,0) and the lowerRight corner. Then we can use this preprocessed Matrix to get the sum for all the elements between upperLeft and lowerRight by getting the sum at lower right, minus the sum at the element on the bottom left-1 of the rectangle (that will subtract all the elements on the left os the Rectangle), minus the sum at the element on the top-1 right (that will subtract all the elements above the rectangle, and then we have to readd the elements that are both on the left and above the reactangle, because we have subtracted them 2 times, so we add the sum at the top-1 left-1 corner. In this way we can compute the sum of all the elements in a rectangle inside a matrix we just 3 operations for any dimension.
So there are 2 steps:
1. Preprocess the matrix substituting the elements with the sum of all previous elements (like a running sum)
2. Get the sum in a rectangle by getting the sum at lowerRight minus the sum at position bottom left -1 (elements on the left), minus the sum at position top-1right, plus the sum at position top-1 left-1.
The complexity is O(n*m) to preprocess the matrix as we need to process each element (n and m are the dimensions of the matrix), and O(1) to get the sum after preprocessing.
Example 1:
Original Matrix:
1,2,8,1
7,4,6,1
4,7,7,8
Summed Matrix:
1,3,11,12
8,14,28,30
12,25,46,56
The sum in the rectangle betweeen
UpperLeft corner (0,1)
and
LowerRight corner (2,2)
is: 34
Example 2:
Original Matrix:
9,9,9,6
2,5,1,8
4,3,0,7
9,3,7,3
6,5,3,5
Summed Matrix:
9,18,27,33
11,25,35,49
15,32,42,63
24,44,61,85
30,55,75,104
The sum in the rectangle betweeen
UpperLeft corner (1,1)
and
LowerRight corner (2,3)
is: 24
This is the code for this solution, you can use:
int[][] genMatrix(int n, int m)
to generate a Matrix of size n,m with random integers, and:
void printMatrix(int[][] m)
to print the matrix. The method:
int[][] preprocessSumMatrix(int[][] m)
will preprocess the matrix with the running sum and the method:
int sum(int[][] m, Vertex upperLeft, Vertex lowerRight)
will compute the sum of all the elements in the Matrix included between upperLeft and lowerRight vertices.
Here is the complete code:
import java.util.*;
class Vertex {
int i;
int j;
public Vertex(int i, int j) {
this.i=i;
this.j=j;
}
public String toString() {
return "("+this.i+","+this.j+")";
}
}
public class SumElementsInRectangle {
public static int[][] preprocessSumMatrix(int[][] m) {
int[][] summedMatrix = new int[m.length][m[0].length];
for(int i=0;i<m.length;i++) {
for(int j=0;j<m[i].length;j++) {
summedMatrix[i][j] = m[i][j];
if(j-1>=0) {
summedMatrix[i][j] = summedMatrix[i][j] + summedMatrix[i][j-1];
}
if(i-1>=0) {
summedMatrix[i][j] = summedMatrix[i][j] + summedMatrix[i-1][j];
}
if(i-1>=0 && j-1>=0) {
summedMatrix[i][j] = summedMatrix[i][j] - summedMatrix[i-1][j-1];
}
}
}
return summedMatrix;
}
public static int sum(int[][] m, Vertex upperLeft, Vertex lowerRight) {
int sum = 0;
if(m==null) return sum;
if(upperLeft.i>lowerRight.i || upperLeft.j>lowerRight.j) {
System.out.println("ERROR: Input Vertices not Correct, check the coordinates.");
return sum;
}
if(upperLeft.i<0 || upperLeft.i>=m.length || upperLeft.j<0 || upperLeft.j>=m[0].length) {
System.out.println("ERROR: Input Vertex UpperLeft out of Bounds.");
return sum;
}
if(lowerRight.i<0 || lowerRight.i>=m.length || lowerRight.j<0 || lowerRight.j>=m[0].length) {
System.out.println("ERROR: Input Vertex LowerRight out of Bounds.");
return sum;
}
sum = m[lowerRight.i][lowerRight.j];
if(upperLeft.i-1>=0) {
sum = sum - m[upperLeft.i-1][lowerRight.j];
}
if(upperLeft.j-1>=0) {
sum = sum - m[lowerRight.i][upperLeft.j-1];
}
if(upperLeft.i-1>=0 && upperLeft.j-1>=0) {
sum = sum + m[upperLeft.i-1][upperLeft.j-1];
}
return sum;
}
public static int[][] genMatrix(int n, int m) {
if(n<=0 || m<=0) {
System.out.println("ERROR: Non-positive values to create Matrix");
return null;
}
Random r = new Random();
int[][] matrix = new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
matrix[i][j] = r.nextInt(10);
}
}
return matrix;
}
public static void printMatrix(int[][] m) {
if(m==null) {
System.out.println("ERROR: Null Matrix");
return;
}
for(int i=0;i<m.length;i++) {
for(int j=0;j<m[i].length-1;j++) {
System.out.print(m[i][j]+",");
}
System.out.println(m[i][m[i].length-1]);
}
}
public static void main(String[] args) {
int[][] matrix = genMatrix(3,4);
System.out.println("Original Matrix:");
printMatrix(matrix);
int[][] summedMatrix = preprocessSumMatrix(matrix);
System.out.println("Summed Matrix:");
printMatrix(summedMatrix);
Vertex upperLeft = new Vertex(0,1);
Vertex lowerRight = new Vertex(2,2);
int sum = sum(summedMatrix,upperLeft,lowerRight);
System.out.println("The sum in the rectangle betweeen\nUpperLeft corner "
+upperLeft+"\nand\nLowerRight corner "+lowerRight+"\nis: "+sum);
}
}
I would create an array of size 24 to represent the hours of the day;
then for each interval I would add the flow of the interval at the start hour of that interval in the array and subtract the flow of that interval at the end+1 hours of that interval.
After I have populated the array in this way I will find the maxFlow in the array just by scanning the array and keeping the running sum. The max value of the running sum is the MaxFlow.
O(n) time complexity, O(1) space complexity. We could use a sorted Collection to avoid all the empty values in the array but in this case we will lose time to keep the keys sorted, an insertion will take O(logn) and the final time complexity would be O(nlogn). As we are computing intervals just for 24 hours we can assume the cost of having some non used slots in an array of size 24.
Example:
0,10,100
10,15,300
16,20,400
5,15,200
the array would be populated with the following values:
[0]-> 100
[1]-> 0
[2]-> 0
[3]-> 0
[4]-> 0
[5]-> 200
[6]-> 0
[7]-> 0
[8]-> 0
[9]-> 0
[10]-> 300
[11]->-100
[12]-> 0
[13]-> 0
[14]-> 0
[15]-> 0
[16]->-100
[17]-> 0
[18]-> 0
[19]-> 0
[20]-> 0
[21]->-400
[22]-> 0
[23]-> 0
and the running sum will be:
100,100,100,100,100,300,300,300,300,300,600,500,500,500,500,500,400,400,400,400,400,0,0,0
just keep the max while computing the running sum.
This is the code for this solution:
import java.util.*;
class FlowInterval {
int start;
int end;
int flow;
public FlowInterval(int start, int end, int flow) {
this.start=start;
this.end=end;
this.flow=flow;
}
public String toString() {
return "("+this.start+","+this.end+"):"+this.flow;
}
}
public class MaxFlow {
public static int maxFlow(List<FlowInterval> intervals) {
int maxFlow = 0;
int currentFlow = 0;
int[] hours = new int[24];
for(FlowInterval flowint: intervals) {
hours[flowint.start]+=flowint.flow;
hours[flowint.end+1]-=flowint.flow;
}
for(int i=0;i<hours.length;i++) {
currentFlow = currentFlow+hours[i];
if(currentFlow>maxFlow) {
//System.out.println("Found new MaxFlow of "+currentFlow+" at "+String.format("%02d", i)+":00");
maxFlow=currentFlow;
}
}
return maxFlow;
}
public static void main(String[] args) {
FlowInterval f1 = new FlowInterval(0,10,100);
FlowInterval f2 = new FlowInterval(10,15,300);
FlowInterval f3 = new FlowInterval(16,20,400);
FlowInterval f4 = new FlowInterval(5,15,200);
List<FlowInterval> intervals = new ArrayList<FlowInterval>();
intervals.add(f1);
intervals.add(f2);
intervals.add(f3);
intervals.add(f4);
System.out.println(intervals);
System.out.println("MaxFlow: "+maxFlow(intervals));
}
}
We have to find the number of Clusters composed by elements of the input Matrix with value of 1. I understand that two elements with value of 1 belong to the same cluster if they are adjacent, in horizontal, vertical, or diagonal. E.g.:
1 0 1 0
0 0 0 1
0 1 0 0
Has 3 clusters of 1's, the first Cluster is composed by the single element at Position(0,0), the second cluster by two elements at Position(0,2) and Position(1,3), and the third cluster by the single element at Position(2,1);
Another example:
0 1 1 0
0 0 0 1
1 1 1 0
In this case the Matrix has just 1 cluster, because the two 1's in the first line and the three 1's in the third line are joined (in diagonal) by the 1 at the end of the second line.
To solve this problem I would iterate through the elements of the input Matrix, and every time I find an element with value of 1 in the matrix that has not already been visited, I increment the value of clusters found by 1, and I perform a Breadth First Search in the input Matrix from this element, moving through elements with value of 1 adjacent and marking them as visited.
In the following code you can use:
int[][] genBoard(int i, int j)
to generate a Matrix of 0's and 1's with size i, j, and:
void printBoard(int[][] board)
to print that matrix;
the method
int countClusters(int[][] board)
retrieves the number of clusters of 1's in the input matrix,
then the method:
void exploreCluster(int i,int j, int[][] board, int[][] visited)
performs the Breadth First Search starting from a specific position, and finally the method
List<Position> possMoves(Position pos, int[][] board, int[][] visited)
computes the possible moves from a given position in the Matrix to find adjacent 1's in the cluster; I use a class Position to hold the coordinates of a single position in the Matrix.
Complexity is O(n^2) as we need to visit each element of the Matrix to count how many clusters there are in the matrix.
Here is the complete code for this solution:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
class Position {
int i;
int j;
public Position(int i, int j) {
this.i=i;
this.j=j;
}
}
public class CountClusters {
public static int countClusters(int[][] board) {
int clusters = 0;
if(board==null || board.length==0) {
return clusters;
}
int[][] visited = new int[board.length][board[0].length];
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
if(visited[i][j]!=1 && board[i][j]==1) {
clusters++;
exploreCluster(i,j,board,visited);
}
}
}
return clusters;
}
public static void exploreCluster(int i,int j, int[][] board, int[][] visited) {
if(board==null || visited==null || i<0 || j<0 || i>board.length-1 || j>board[i].length-1) {
System.out.println("Bad Input in explore Cluster");
return;
}
List<Position> tovisit = new ArrayList<Position>();
Position start = new Position(i,j);
tovisit.add(start);
Position visiting;
while(tovisit.size()>0) {
visiting = tovisit.remove(0);
visited[visiting.i][visiting.j]=1;
List<Position> moves = possMoves(visiting,board,visited);
for(Position p: moves) {
tovisit.add(p);
}
}
}
public static List<Position> possMoves(Position pos, int[][] board, int[][] visited) {
List<Position> moves = new LinkedList<Position>();
if(board==null || visited==null || pos.i<0 || pos.j<0 || pos.i>board.length-1 || pos.j>board[pos.i].length-1) {
System.out.println("Bad Input in explore Cluster");
return moves;
}
int[] dx = {-1,0,1,-1,0,1,-1,0,1};
int[] dy = {-1,-1,-1,0,0,0,1,1,1};
int new_i, new_j;
for(int k=0;k<dx.length;k++) {
new_i=pos.i+dy[k];
new_j=pos.j+dx[k];
if(new_i>=0 && new_i<board.length && new_j>=0 && new_j<board[new_i].length) {
if(board[new_i][new_j]==1 && visited[new_i][new_j]!=1) {
moves.add(new Position(new_i,new_j));
}
}
}
return moves;
}
public static int[][] genBoard(int i, int j) {
if(i<=0 || j<=0) {
System.out.println("Error Generating Board, non positive input size.");
return null;
}
int[][] board = new int[i][j];
Random r = new Random();
for(int x=0;x<i;x++) {
for(int y=0;y<j;y++) {
board[x][y]=r.nextInt(2);
}
}
return board;
}
public static void printBoard(int[][] board) {
if(board==null || board.length==0 || board[0].length==0) {
System.out.println("Error Printing Board, null or non positive input size.");
return;
}
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] board = genBoard(3,4);
printBoard(board);
System.out.println("Number of clusters in Matrix: "+countClusters(board));
}
}
I have implemented the method to retrieve all the combinations of the given lower case String in both recursive and iterative way.
Iterative Algorithm:
- Keep a Set of String where you will have all the combinations
- Initially add the original String to the Set of combinations
- For each char from position 0 to position s.length-1 and for each String in the Set of combinations if this Char is a lowerCase Char add to the Set of combinations the String composed by replacing this lowerCase char with the correspondent upperCase Char. Add this new String to the Set of combinations.
public static Set<String> allCombs(String s) {
Set<String> combs = new HashSet<String>();
if(s==null || s.length()==0) {
return combs;
}
combs.add(s);
for(int i=0; i<s.length();i++) {
Set<String> newcombs = new HashSet<String>();
for(String comb: combs) {
if(Character.isLowerCase(comb.charAt(i))) {
newcombs.add(comb.substring(0,i)+Character.toUpperCase(comb.charAt(i))+comb.substring(i+1));
}
}
combs.addAll(newcombs);
}
return combs;
}
Recursive Algorithm:
- From pos 0 to s.length, if the current Char is lowerCase convert it to upperCase and attach it to all the combinations generated by the recursive call starting from pos+1; then also add the current Char (not converted) to all the combinations generated by the recursive call with pos+1; base case pos>=length, add the empty String to the Set.
public static List<String> allCombsRec(String s, int pos) {
List<String> combs = new ArrayList<String>();
if(s==null || s.length()==0) {
return combs;
}
if(pos>=s.length()) {
combs.add("");
return combs;
}
for(String srec: allCombsRec(s,pos+1)) {
if(Character.isLowerCase(s.charAt(pos))) {
combs.add(Character.toUpperCase(s.charAt(pos))+srec);
}
combs.add(s.charAt(pos)+srec);
}
return combs;
}
I used a recursion for this:
Start from the root:
while we can go down the tree:
- if the value of the current node is equal to n return current.value
- if it is smaller than n: if the difference with n is smaller than the closest difference update closest, then call recursion on right subtree
- if it is bigger than n, call recursion on left subtree
(closest is initialized to the MAX Integer)
Time complexity O(logn) where n is the number of nodes in the tree.
public static int greatestLessThanN(Node root, int n, int closest) {
if(root!=null) {
if(closest==Integer.MAX_VALUE) { //visiting the first node, update closest
closest=root.getValue();
}
if(root.getValue()==n) {
return root.getValue();
}
else if(root.getValue()<n) {
if((n-root.getValue())<=(n-closest)) {
closest=root.getValue();
}
return greatestLessThanN(root.getRightChild(), n, closest);
}
else {
return greatestLessThanN(root.getLeftChild(), n, closest);
}
}
else {
if(closest==Integer.MAX_VALUE) {
System.out.println("Error: No value smaller than "+n);
}
return closest;
}
}
call the previous method with:
greatestLessThanN(Node root, int n, Integer.MAX_VALUE)
Compute the distance from each Point in the input List of Points to the Point (5,5).
Then add each Point with its distance from (5,5) to an Heap that will always have the element with the minimum distance at the root of the Heap. Remove the root of the heap (for k times) and add it to the list of the closest Points.
You can use PriorityQueue structure as heap; you have to implement Comparable and define the compareTo method in the class Point in order to make the Points comparable by their distance from (5,5). Otherwise you can use an external Comparator. Time complexity is O(nlogn+klogk), that is: add n times (one for each Point in the input list) to the heap (O(logn) insertion complexity in the heap) plus O(klogk) to add the k elements closets to (5,5) to the final list of closest point, because you need to repeat k times the remove operation from the heap (remove the min element from the heap takes O(logk) as we need to rearrange the heap).
import java.util.*;
class Point implements Comparable<Point> {
int x;
int y;
double distance;
public Point(int x, int y) {
this.x=x;
this.y=y;
}
public int compareTo(Point p) {
if(this.distance>p.distance) {
return 1;
}
else if(this.distance<p.distance) {
return -1;
}
else {
return 0;
}
}
public String toString() {
return "("+this.x+","+this.y+"):"+this.distance;
}
}
public class KClosestPoints {
public static double computeDistance(Point p1, Point p2) {
return (Math.sqrt(Math.pow(p1.x-p2.x, 2)+Math.pow(p1.y-p2.y, 2)));
}
public static List<Point> kClosest(List<Point> l, int k) {
if(k<0) {
System.out.println("K must be a nonnegative number");
return null;
}
if(l.size()==0) {
System.out.println("Empty input list");
return new ArrayList<Point>();
}
Point p5 = new Point(5,5);
List<Point> closest = new ArrayList<Point>();
PriorityQueue<Point> heap = new PriorityQueue<Point>();
for(Point p: l) {
p.distance=computeDistance(p,p5);
heap.add(p);
}
for(int i=0;i<k;i++) {
closest.add(heap.remove());
}
return closest;
}
public static void main(String[] args) {
Point p1 = new Point(-2,4);
Point p2 = new Point(0,0);
Point p3 = new Point(10,15);
Point p4 = new Point(5,6);
Point p5 = new Point(7,8);
Point p6 = new Point(-10,30);
List<Point> input = new LinkedList<Point>();
input.add(p1);
input.add(p2);
input.add(p3);
input.add(p4);
input.add(p5);
input.add(p6);
//System.out.println(input);
List<Point> closest = kClosest(input,2);
System.out.println(closest);
}
}
while at least one of the lists has some elements, check if one of the lists is empty; is one list is empty add elements from the other list. Each time you add an element to the merged list remove it from the input list (by updating the head node to head.next). If both lists have elements check which element is smaller, and remove it from the head of the list by pointing the head of that list to the head.next element, and add it to the tail of the merged list (current.next. O(n) time complexity, space complexity I think it's O(1) as we don't need to create a new structure to hold the merged list, we just need to update the pointer to the next node in the input lists. Pros of this approach: O(1) space complexity as we don't have to create a new structure, cons: we are destroying the input lists; if we need to mantain the input lists as they are we should make a copy of them before start updating the links to the next nodes.
class ListNode {
int value;
ListNode next;
public ListNode(int value) {
this.value=value;
}
}
public class SortedListMerger {
public static ListNode merge(ListNode l1, ListNode l2) {
if(l1==null && l2==null) {
System.out.println("Null Lists");
return null;
}
else if(l1==null) {
return l2;
}
else if(l2==null) {
return l1;
}
ListNode head;
ListNode current;
if(l1.value<=l2.value) {
head = l1;
l1=l1.next;
}
else {
head = l2;
l2=l2.next;
}
current = head;
while(l1!=null || l2!=null) {
if(l1==null) {
current.next=l2;
l2=l2.next;
}
else if(l2==null) {
current.next=l1;
l1=l1.next;
}
else {
if(l1.value<=l2.value) {
current.next=l1;
l1=l1.next;
}
else {
current.next=l2;
l2=l2.next;
}
}
current=current.next;
}
return head;
}
public static void printList(ListNode l) {
ListNode nextNode=l;
while(nextNode!=null) {
System.out.print(nextNode.value);
if(nextNode.next!=null) System.out.print(" -> ");
nextNode=nextNode.next;
}
System.out.println();
}
public static void main(String[] args) {
ListNode l1 = new ListNode(2);
ListNode l2 = new ListNode(19);
ListNode l3 = new ListNode(33);
ListNode l4 = new ListNode(221);
l1.next=l2;
l2.next=l3;
l3.next=l4;
ListNode ll1 = new ListNode(1);
ListNode ll2 = new ListNode(7);
ListNode ll3 = new ListNode(33);
ListNode ll4 = new ListNode(61);
ListNode ll5 = new ListNode(66);
ll1.next=ll2;
ll2.next=ll3;
ll3.next=ll4;
ll4.next=ll5;
printList(l1);
printList(ll1);
printList(merge(l1,ll1));
}
}
First, I search the matrix for the starting letter of the given alphabet. Then starting from that Position, I perform a Depth First Search and store the maxDepth.
I use a class Position to hold the coordinates of the current Position; a Position holds the coordinates i,j in the board and also knows his depth in the current Path.
The method:
List<Position> possibleMoves(int i, int j, char[][] board, int depth)
retrieves the list of possible moves from the current Position. From a Position you can move to another Position in the board if it is an existing adjacent Position in the board and the Char in that Position is the Char following the Char in the current Position in the Alphabet. In my solution I define the First Char in the Alphabet as the Next of the Last Char in the Alphabet, in this way we can get Paths longer than the size of the Alphabet.
The method:
boolean isNextInAlphabet(char c1, char c2)
check if the char c2 is next of the char c1 in the Alphabet.
You can use genBoard(int n, int m) and printBoard() to generate and print a new board. The Alphabet used in the example is just 'a','b','c' but you can add more characters if you want to test it, just take into account that the longer the alphabet the harder to get a Path in a random generated board from the method genBoard. Here is my code for this solution:
import java.util.*;
class Position {
int i;
int j;
int depth;
public Position(int i,int j, int depth) {
this.i=i;
this.j=j;
this.depth = depth;
}
public String toString() {
return "("+this.i+","+this.j+")";
}
}
public class MaxAlphabetPathInMatrix {
//final static char[] ALPHA = {'a','b','c','d','e','f','g','h','i','l','m','n','o','p','q','r','s','t','u','v','z'};
final static char[] ALPHA = {'a','b','c'};
public static int maxAlphabetPath(char[][] board) {
if(board==null || board.length==0) {
return 0;
}
int maxDepth = 0;
int currDepth = 0;
int[][] visited = new int[board.length][board[0].length];
Stack<Position> tovisit;
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
if(board[i][j]=='a' && visited[i][j]!=1) {
tovisit = new Stack<Position>();
Position start = new Position(i,j,1);
tovisit.push(start);
Position visiting;
currDepth = 0;
while(!tovisit.empty()) {
visiting=tovisit.pop();
System.out.println("Popping "+visiting);
currDepth = visiting.depth;
System.out.println("board["+visiting.i+"]["+visiting.j+"]="+board[visiting.i][visiting.j]+":"+visiting.depth);
if(currDepth>maxDepth) {
maxDepth = currDepth;
}
if(visited[visiting.i][visiting.j]!=1) {
visited[visiting.i][visiting.j] = 1;
for(Position p: possibleMoves(visiting.i,visiting.j,board,currDepth+1)) {
System.out.println("Pushing "+p);
tovisit.push(p);
}
}
}
}
}
}
return maxDepth;
}
public static List<Position> possibleMoves(int i, int j, char[][] board, int depth) {
List<Position> moves = new ArrayList<Position>();
int[] dx = {-1,0,1,-1,0,1,-1,0,1};
int[] dy = {-1,-1,-1,0,0,0,1,1,1};
for(int k=0;k<dx.length;k++) {
if(i+dy[k]>=0 && i+dy[k]<board.length && j+dx[k]>=0 && j+dx[k]<board[i+dy[k]].length) {
if(isNextInAlphabet(board[i][j],board[i+dy[k]][j+dx[k]])) {
Position nextPos = new Position(i+dy[k],j+dx[k],depth);
moves.add(nextPos);
}
}
}
return moves;
}
public static boolean isNextInAlphabet(char c1, char c2) {
boolean isNext = false;
if(ALPHA[ALPHA.length-1]==c1 && ALPHA[0]==c2) {
isNext = true;
}
for(int i=0;i<ALPHA.length-1;i++) {
if(ALPHA[i]==c1 && ALPHA[i+1]==c2) {
isNext=true;
break;
}
}
return isNext;
}
public static char[][] genBoard(int n, int m) {
if(n<=0 || m<=0) {
System.out.println("Error: wrong size for generating board");
return null;
}
char[][] board = new char[n][m];
Random r = new Random();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
board[i][j] = ALPHA[r.nextInt(ALPHA.length)];
}
}
return board;
}
public static void printBoard(char[][] board) {
for(int i=0;i<board.length;i++) {
System.out.print("[");
for(int j=0;j<board[i].length-1;j++) {
System.out.print(board[i][j]+",");
}
System.out.print(board[i][board[i].length-1]);
System.out.println("]");
}
}
public static void main(String[] args) {
char[][] board = genBoard(3,4);
printBoard(board);
int maxPath = maxAlphabetPath(board);
System.out.println("Max Path: "+maxPath);
}
}
Hi,
for a date int the format MMDDYYYY to be palindrome, YYYY must be equal to DDMM. So get the start year STARTYYYY, and the end year ENDYYYY.
Then for each year in the range STARTYYYY -> ENDYYYY generate the date composed by the Strings rev(YYYY) and YYYY.
For each date generated in this way check for the month MM to be included in the interval [01,12]
(revYYYY.charAt(0)=='0' && revYYYY.charAt(1)!='0') || (revYYYY.charAt(0)=='1' && (revYYYY.charAt(1)=='2' || revYYYY.charAt(1)=='1' || revYYYY.charAt(1)=='0'))
and for the day DD to be included in the interval [01-31]
(revYYYY.charAt(2)=='0' || revYYYY.charAt(2)=='1' || revYYYY.charAt(2)=='2') || (revYYYY.charAt(2)=='3' && (revYYYY.charAt(3)=='0' || revYYYY.charAt(2)=='1'))
Example:
Start Date = 01012000
End Date = 31122100
Output = [10022001, 01022010, 11022011, 02022020, 12022021, 03022030, 04022040, 05022050, 06022060, 07022070, 08022080, 09022090]
This is the code that implement this solution:
import java.util.*;
public class PalindromeDatesInterval {
public static String rev(String s) {
String rev = "";
for(int i=s.length()-1;i>=0;i--) {
rev = rev+s.charAt(i);
}
return rev;
}
public static List<String> palindromeDates(String start, String end) {
List<String> dates = new ArrayList<String>();
//System.out.println(start+" "+end);
if(start.length()!=8 || end.length()!=8) {
System.out.println(start+" "+end);
System.out.println("Warning: Wrong Dates Format!");
return null;
}
String startYYYY = start.substring(4,8);
String endYYYY = end.substring(4,8);
for(int i=Integer.parseInt(startYYYY);i<=Integer.parseInt(endYYYY);i++) {
String revYYYY = rev(String.valueOf(i));
String YYYY = String.valueOf(i);
if(((revYYYY.charAt(0)=='0' && revYYYY.charAt(1)!='0') ||
(revYYYY.charAt(0)=='1' && (revYYYY.charAt(1)=='2' || revYYYY.charAt(1)=='1' || revYYYY.charAt(1)=='0')))
&&
((revYYYY.charAt(2)=='0' || revYYYY.charAt(2)=='1' || revYYYY.charAt(2)=='2')
||
(revYYYY.charAt(2)=='3' && (revYYYY.charAt(3)=='0' || revYYYY.charAt(2)=='1')))
) {
String pdate = revYYYY+YYYY;
dates.add(pdate);
}
}
return dates;
}
public static void main(String[] args) {
List<String> pdates = new ArrayList<String>();
String start = "01012000";
String end = "31122100";
pdates = palindromeDates(start,end);
System.out.println(pdates);
}
}
This is my solution, let me know test cases where this algorithm doesn't work:
I define a class Pet. Each Pet has a type(C or D) and a code (the sequential number 1 2 etc...). Each Pet knows the difference between positive and negative votes received, the number positive votes received, and the Pets that should be discarded if this Pet is chosen for the final solution.
After parsing the input into a List of Pets, I sort the list by the difference between positive and negative votes received.
Then starting with the Pet with the Highest tradeoff between positive and negative votes( the most popular pet ), I add the number of positive votes received by that pet to the solution, and then I flag all the pets that should be discarded according to the votes received by that pet, and I won't count these discarded pets in the final sum. Keep adding positive votes until the end of the list skipping Pets flagged as discarded. The total obtained in this way is the maximum number of satisfied votes.
Complexity O(v) to read the votes, where v is the number of votes; O(nlogn) to sort the list of Pets by the difference positive and negative votes (maybe this can be improved by adding the Pets directly in a TreeSet with and external Comparator; O(n) to count the final sum; n is the number of Pets;
In the code below the pets list is already sorted by the most popular pets:
public static int maxViewers(List<Pet> pets) {
int max = 0;
if(pets==null || pets.size()==0) return max;
Set<Pet> discarded = new HashSet<Pet>();
for(Pet p: pets) {
if(!discarded.contains(p)) {
for(Pet petout: p.getDiscards()) {
discarded.add(petout);
}
max+=p.getPositive();
}
}
return max;
}
Hi Zortlord,
why would you take into account for the solution just the most voted pet for the elimination?
It seems that your solution doesn't work for this kind of input:
C1 D1
C1 D1
C1 D2
C1 D2
D2 C1
D2 C1
D1 C1
with this input the output should be 4 (we can eliminate D1 and D2 and keep C1, and the first four lines will be satisfied).
instead your algorithm retrieves 3 (the last 3 lines)
An integer is composed by 32 bit, so the lowlevel representation of an integer will be 10011010100100100......11001010, thus I think you can use just one integer to represent up to 32 squares. I assumed that we had to represent final configurations of the game to check if there is the winner, then each square will be filled with X or O. we need just 2 values that means that each square can be represented with just 1 bit. If the integer has 32 bits you can represent each line with 1 integer
- gigi84 December 12, 2014I think you can store each line as an integer, that is composed by 32 bits. You can use each bit of the integer to represents a single square, if the bit is 0 then the square contains a O if it is 1 the square contains an X. In this case you would need 2^31 Integers to store the entire board. You can preprocess the board to store each configuration as "winning for X", "winning for O" or "Draw".
- gigi84 December 10, 2014In my solution I keep track of the last N node in a List, then I attach the last node to the N-1th node in the original list and read backwards the nodes on the List containing the last N nodes. Running time O(n) and you don't have to know the length of the list of nodes in advance.
import java.util.ArrayList;
import java.util.List;
class Lnode {
int value;
Lnode next;
public Lnode (int value) {
this.value = value;
this.next=null;
}
public Lnode(int value,Lnode next) {
this(value);
this.next = next;
}
public String toString() {
return this.value+" ";
}
}
public class ReverseNthNode {
public static void printLnode(Lnode head) {
while(head!=null) {
System.out.print(head.value);
if(head.next!=null) {
System.out.print(" -> ");
}
head=head.next;
}
System.out.println();
}
public static Lnode reverseLastN(Lnode head, int n) {
if(n<=0) return head;
List<Lnode> lasts = new ArrayList<Lnode>();
Lnode prev = null;
Lnode current = head;
while(current!=null) {
if(lasts.size()>=n) {
prev = lasts.remove(0);
}
lasts.add(current);
current=current.next;
}
for(int i=lasts.size()-1;i>0;i--) {
lasts.get(i).next = lasts.get(i-1);
}
if(prev != null) {
lasts.get(0).next=null;
prev.next=lasts.get(lasts.size()-1);
return head;
}
else {
lasts.get(0).next=null;
return lasts.get(lasts.size()-1);
}
}
public static void main(String[] args) {
Lnode l7 = new Lnode(7);
Lnode l6 = new Lnode(6,l7);
Lnode l5 = new Lnode(5,l6);
Lnode l4 = new Lnode(4,l5);
Lnode l3 = new Lnode(3,l4);
Lnode l2 = new Lnode(2,l3);
Lnode l1 = new Lnode(1,l2);
printLnode(l1);
printLnode(reverseLastN(l1,5));
}
}
Hi Loneranger!
I like your approach of using subsolutions and also limiting the number of solutions by taking into account that the range of the numbers is included between 0 and 100; anyway I still think that the solution to the problem is to "redistribute" the values of the array in order to have the difference between adjacent number less or equal to a target number, but also you need to keep the total sum of the array. If you check the example in the initial stating of the problem, they transform the array:
[1,4,2,3] and target=1
in the array
[2,3,2,3]
as you can see [1+4+2+3]=10 and [2+3+2+3]=10.
so you need to "redistribute" the values, not add nor subtract values from the total sum.
In your solution you solve the problem of having the adjacent number with a difference of 10 or less, but you are changing the total value of the array:
55+77+52+61+39+6+25+60+49+47=471
55+62+52+49+39+29+30+40+49+47=452
so I think this is not the complete solution to the problem
The problem is to redistribute the values in order to have adjacent values with difference less or equal to target N, but keeping the total sum of the array. In your solution you do not keep the total sum.
If you take the example:
1 3 1 with target difference of 1
one possible solution will be:
1 2 2
in this way you keep the total value of the array, 1+3+1=5, 1+2+2=5
So we need to redistribute the values of an array of integers
in order to obtain all the adjacent values with less than N difference.
If A is the input array and B the output array we need to minimize the
sum of the difference between the elements of the two arrays:
|A[i]-B[i]|
without changing the total sum of the elements in the array.
sum(A) == sum(B)
Example 1:
A[]: 55,77,52,61,39,6,25,60,49,47
A[] Tot: 471
Target Diff for Adjacent Numbers: 10
B[]: 57,56,55,46,45,38,37,46,44,47
B[] Tot: 471
SUM(A[i]-B[i]): 110
Example 2:
A[]: 94,35,29,55
A[] Tot: 213
Target Diff for Adjacent Numbers: 10
B[]: 58,49,51,55
B[] Tot: 213
SUM(A[i]-B[i]): 72
Example 3:
A[]: 97,73,56,56,93,55,29,47,90,36
A[] Tot: 632
Target Diff for Adjacent Numbers: 3
B[]: 72,70,69,66,64,61,60,58,57,55
B[] Tot: 632
SUM(A[i]-B[i]): 180
Lets say that the input array is A and the input target number is N.
To balance the array I use the following approach:
I analyze 3 elements adjacent elements at the same time (A[i-1], A[i], A[i+1]);
I use 3 elements because if I take just 2 elements, by balancing 2 of them (A[i-1] and A[i])
we could make the balancing between A[i] and A[i+1] worse.
For each triplet if it is not balanced, I take the Min and the Max of the triplet, and try to make
the smallest modification possible that brings the difference between the two number smaller or
equal to N. So we need to take off a quantity X from the max and add a quantity Y to the min of
the three elements such as the difference between Max and Min become equal to N (smallest modification).
To find X and Y we can solve the following system of equations:
(Max+X)-(Min+Y)=N
(Max+X)+(Min+Y)=TOT
Where Max and Min are the maximum and minimum elements in the triplet, N the target difference, TOT the
sum of Max+Min before the modification (that we don't want to change); using these two equations we can find
X and Y. I left the equation to find X and Y not simplified in the code for the sake of clarity.
So we keep balancing three numbers for each i between 1 and A.length-1, until we don't need to make any more
changes in the triplets. When there are no more modifications to do we return the modified array.
If the array are just two elements balance them doing the smallest modification to achieve a difference of N and again
not changing the total sum between the two elements.
The time complexity should be O(NlogK), where N is the number of elements in the array (inside for in the code), and K the range of the elements (as
we are balancing the values of the elements, external while in the code).
Here is the code to implement this solution, you can use "int[] genArray(int n, int range)" to generate a random
array of N integers between 0 and range, void printArray(int[] a) to print the input and output array,
int[] distribute(int[] a, int n) to generate the balanced array with a target difference of N:
import java.util.Random;
public class DistributeArray {
public static int tot(int[] a) {
int tot=0;
if(a!=null) {
for(int n: a) {
tot+=n;
}
}
return tot;
}
public static int[] genArray(int n, int range) {
int[] a = new int[n];
Random r = new Random();
for(int i=0;i<n;i++) {
a[i] = r.nextInt(range);
}
return a;
}
public static int[] distribute(int[] A, int n) {
int avg,tot,oldmax,oldmin;
int[] a= new int[A.length];
System.arraycopy( A, 0, a, 0, a.length );
boolean adj = false;
if(a==null) {
System.out.println("Null input array.");
return null;
}
if(n<=0) {
System.out.println("N must be a positive number.");
return a;
}
// Special case a.length<2
if(a.length<2) {
return a;
}
// Special case a.length==2
if(a.length==2) {
if(Math.abs(a[0]-a[1])>n) {
int sum = a[1]+a[0];
if(a[0]<a[1]) {
a[0]=((a[1]+a[0])/2)-(n/2);
a[1]=sum-a[0];
}
else {
a[1]=((a[1]+a[0])/2)-(n/2);
a[0]=sum-a[1];
}
}
return a;
}
while(!adj) {
adj=true;
//printArray(a);
for(int i=1;i<a.length-1;i++) {
if(Math.abs(a[i-1]-a[i])>n || Math.abs(a[i]-a[i+1])>n) {
tot = a[i-1]+a[i]+a[i+1];
//System.out.println(a[i-1]+","+a[i]+","+a[i+1]+" KO - TOT="+(a[i-1]+a[i]+a[i+1]));
int max, min, med;
if(a[i-1]>a[i] && a[i-1]>a[i+1]) {
max = i-1;
if(a[i+1]<a[i]) {
min = i+1;
med = i;
}
else {
min = i;
med = i+1;
}
}
else if(a[i]>a[i+1]){
max = i;
if(a[i+1]<a[i-1]) {
min = i+1;
med = i-1;
}
else {
min = i-1;
med = i+1;
}
}
else {
max = i+1;
if(a[i-1]<a[i]) {
min = i-1;
med = i;
}
else {
min = i;
med = i-1;
}
}
int tot2=a[max]+a[min];
oldmax = a[max];
oldmin = a[min];
a[max] = a[max]+(-a[max]-(n/2)+(tot2/2)+n);
a[min] = a[min]+(-a[min]-(n/2)+(tot2/2));
int diff = tot2-(a[max]+a[min]); //readd the rest to not change the sum
if(oldmin != a[min]+diff) {
a[min] = a[min]+diff;
}
else if(oldmax != a[max]+diff){
a[max] = a[max]+diff;
}
else {
a[med] = a[med]+diff;
}
//System.out.println(a[i-1]+","+a[i]+","+a[i+1]+" AFTER KO TOT="+(a[i-1]+a[i]+a[i+1]));
adj=false;
}
}
}
return a;
}
public static void printArray(int[] a) {
if(a!=null && a.length>0) {
for(int i=0;i<a.length-1;i++) {
System.out.print(a[i]+",");
}
System.out.println(a[a.length-1]);
}
}
public static void main(String[] args) {
int[] a = genArray(10,100);
//int[] a = new int[]{57,67,45,87};
System.out.print("A[]: ");
printArray(a);
int diff = 10;
System.out.println("A[] Tot: "+tot(a));
System.out.println("Target Diff for Adjacent Numbers: "+diff);
int[] b = distribute(a,diff);
System.out.print("B[]: ");
printArray(b);
System.out.println("B[] Tot: "+tot(b));
int diffAB = 0;
for(int i=0;i<a.length;i++) {
diffAB=diffAB+(Math.abs(a[i]-b[i]));
}
System.out.println("SUM(A[i]-B[i]): "+diffAB);
}
}
Hi,
I understand from the description of the problem that we need to return the first
integer that is not possible to obtain by summing different elements in the array;
I suppose that this integer must be at least larger than the smallest element in the
array, otherwise the solution will be just return 1 if the minimum element is larger
than 1. Also, I assume this number cannot be a number contained in the array.
Example 1:
Input array: [3, 2, 2, 2, 9]
Minimum int that is not sum: 8
Example 2:
Input array: [6, 1, 2, 7, 5]
Minimum int that is not sum: 4
Example 3:
Input array: [1, 2, 3, 2]
Minimum int that is not sum: 9
Example 4:
Input array: [8, 9, 3, 1, 1]
Minimum int that is not sum: 6
Example 5:
Input array: [2, 3, 4, 5, 8]
Minimum int that is not sum: 21
To obtain the minimum integer that cannot be formed from the sum of numbers of the array
I generate the powerset of the elements in the array, than compute the sum for each powerset
excluding the empty set; finally I scan the set of the sums of every set in the powerset,
and the minimum int that is not formed by the sum of the element of the array will be the first
missing int in the set of sums (ordered using a TreeSet). If no element is missing in the sequence
the minimum int that cannot be formed will be the maximum sum plus 1;
The time complexity will be O(2^n), time needed to compute all the sets in the powerset.
Here is my code, you can use genList(int n, int range) to generate a random list of n numbers
between 1 and range; int minNotSum(List<Integer> l) will retrieve the minimum number not formed by a sum,
Set<List<Integer>> powerSet(List<Integer> originalSet) computes the powerSet,
Set<Integer> sums(Set<List<Integer>> sets) computes the set of all the possible sums,
int computeSum(List<Integer> l) compute the sum of a single list:
import java.util.*;
public class MinIntNotSum {
public static Set<List<Integer>> powerSet(List<Integer> originalSet){
Set<List<Integer>> sets = new HashSet<List<Integer>>();
if(originalSet.size()==0) {
sets.add(originalSet);
return sets;
}
int head = originalSet.get(0);
List<Integer> rest = originalSet.subList(1, originalSet.size());
for(List<Integer> s: powerSet(rest)) {
List<Integer> newSet = new ArrayList<Integer>();
newSet.add(head);
newSet.addAll(s);
sets.add(newSet);
sets.add(s);
}
return sets;
}
public static List<Integer> genList(int n,int range) {
List<Integer> l = new ArrayList<Integer>();
Random r = new Random();
for(int i=0;i<n;i++) {
l.add(r.nextInt(range)+1);
}
return l;
}
public static Set<Integer> sums(Set<List<Integer>> sets) {
if(sets==null || sets.size()==0) {
return new TreeSet<Integer>();
}
Set<Integer> sums = new TreeSet<Integer>();
for(List<Integer> l:sets) {
if(l.size()>0)
sums.add(computeSum(l));
}
return sums;
}
public static int computeSum(List<Integer> l) {
int sum = 0;
for(Integer i: l) {
sum+=i;
}
return sum;
}
public static int minNotSum(List<Integer> l) {
if(l==null || l.size()==0) {
return -1;
}
Set<List<Integer>> ps = powerSet(l);
Set<Integer> sums = sums(ps);
List<Integer> lsums = new ArrayList<Integer>(sums);
//System.out.println("List from TreeSet:\n"+lsums);
for(int i=0;i<lsums.size()-1;i++) {
if(lsums.get(i)+1!=lsums.get(i+1)) {
return lsums.get(i)+1;
}
}
return lsums.get(lsums.size()-1)+1;
}
public static void main(String[] args) {
List<Integer> l = genList(5,10);
/*l = new ArrayList<Integer>();
l.add(4);
l.add(4);
l.add(3);
l.add(2);
l.add(4);
*/
System.out.println(l);
/*
Set<List<Integer>> ps = powerSet(l);
for(List<Integer> ll: ps) {
System.out.println(ll);
}
System.out.println("Power Sets: "+ps.size());
*/
int min = minNotSum(l);
System.out.println("Min not Sum: "+min);
}
}
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
You got me!
- gigi84 January 04, 2015it is O(n) in the average case but O(n^2) in the worst case, and good catch on the worst case! +1 for you ;)