Shivam Maharshi
BAN USERTotal Algorithms Geek
This is how the recursive function will look like:
f(n) = f(n-2) + f(n-1) + 6;
When we cut one block of width 1, then there is only one way to fill it using 2*1 blocks. i.e two of 1*2 vertical block one above the other.
When we cut one block of width 2, then there are 5 ways to fill it using 2*1 blocks. Shown below.
a. All 2*1 blocks lying horizontally on top of each other.
b. Two 2*1 blocks lying horizontally and 2 on top of them vertically.
c. Vice Versa of above case.
d. One 2*1 block lying horizontally then 2 on top of it vertically and then another one on top of them horizontally.
e. 2*1 blocks all standing vertically.
Hence at any point we can either choose to reduce width by 1 block (1 way) or by 2 blocks (5 way) giving:
f(n) = f(n-1) + 1 + f(n-2) + 5 = f(n-1) + f(n-2) + 6.
Solve it using DP now.
Complexity: O(n(m+p))
1. Sort all the arrays - a,b,c. - This will improve average time complexity.
2. If c[i] < Sum, then look for Sum - c[i] in array a and b. When pair found, insert c[i], a[j] & b[k] into the result list. This can be done in O(n).
3. Keep on doing the above procedure while going through complete c array.
1. Use HashMap to store Key Node -> Values pairs.
2. Use LinkedList to maintain the order of usage of these key nodes in the HashMap.
3. Whenever a Key is read or written, put it at the end of the LinkedList.
4. Whenever you need space in cache, remove from LinkedList head and remove these nodes from HashMap as well.
Your logic is wrong, you switched 3 and 4.
3. If length is odd then all the characters except one should have even occurrences.
4. If even, then all the characters should have even occurrences.
1. Start traversing from the end of the array. This is O(n).
2. Create a sorted list as you go from the end of the array.
3. Apply a binary search on the sorted list to find the rank of the new number and insert that number in the list. This is O(log(n)).
Overall O(n*log(n)) complexity and you save all the effort of creating BinaryTrees or writing Merge Sort which is undoubtedly a smart solution but might not click at the time of the interview. However if the interviewer asks to not use auxiliary memory, then it is the solution to go. :)
Rather than using Self Balancing Binary Tree, why not simply create a sorted list as you go from the end of the array and apply a binary search on it to find the rank of the new number from that sorted list. That would still be O(n*log(n)) complexity and you save all the effort of creating Self Balanced Trees. :)
- Shivam Maharshi January 25, 2016Store values in a Tree Map with value as keys, and the prime number with which they are made as values. Since Tree Map is already sorted on the basis of keys, you can simply remove the first key and add its next multiple. Put / Get / Delete / Contains are Log(n) in Tree Map. Hence the complexity of this solution would be : O(n * log(m)). Where M is the size of the subset.
Java Code Below:
/*
* @author shivam.maharshi
*/
public class NthSmallestMulFromSet {
// O(n*log(m)). M is size of set.
public static int get(int[] set, int n) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int a : set) {
map.put(a, a);
}
int num = 0;
while (n > 0) {
num = map.firstKey();
int value = map.get(num);
map.remove(num);
if (!map.containsKey(num + value)) {
map.put(num + value, value);
} else {
map.put(num + 2 * value, value);
}
n--;
}
System.out.println(num);
return num;
}
public static void main(String[] args) {
int[] set = { 2, 3 };
get(set, 6);
}
}
An easier solution would be to store the value in a Tree Map and then remove them one by one till we reach Nth number. That code is way easier. Java Code below:
*
* @author shivam.maharshi
*/
public class NthSmallestMulFromSet {
// O(n*log(m)). M is size of set.
public static int get(int[] set, int n) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int a : set) {
map.put(a, a);
}
int num = 0;
while (n > 0) {
num = map.firstKey();
int value = map.get(num);
map.remove(num);
if (!map.containsKey(num + value)) {
map.put(num + value, value);
} else {
map.put(num + 2 * value, value);
}
n--;
}
System.out.println(num);
return num;
}
public static void main(String[] args) {
int[] set = { 2, 3 };
get(set, 6);
}
}
I have one question. You said, you take out the minimum and then multiply n numbers of the array and push them into heap after checking for duplicates. That would keep on increasing the size of the heap, right ?
- Shivam Maharshi January 25, 2016So here is my solution.
1. Create a Trie for the list of Strings given.
2. Store the maximum depth of the Trie or in other words, the length of the longest string in a variable called MaxLen.
3. When ever we receive a new character, we search it and the combination of all its previous MaxLen-1 characters. Because we know that any pattern more than MaxLen characters will not be found in the Trie anyway.
4. Every time we find a word, we print the index of the pattern match, however we do not stop the search. The only criteria to stop the search would be when the length of stream under consideration would reach MaxLen value. Then we will remove the first character from the StringBuilder and add the new character at the end and search for all the combinations for that StringBuilder. Which would be MaxLen combinations.
So for every new character you are doing MaxLen search. Assuming there are N characters in the stream, the complexity of this solution is O(MaxLen*n).
This is not linear time. I don't believe there could be any linear time solution possible for this. Since we at least need to match every single character of the stream with all the characters of the words in the list for the worst case. Which would look like this:
List : {a, aa, aaa, aaaa, aaaaa, aaaaaa};
Stream: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
I will post the code soon.
An elegant solution !
- Shivam Maharshi January 25, 2016Looks like you understood the question pretty well. Can you please explain the question ?
- Shivam Maharshi January 25, 2016Java Code
/*
* @author shivam.maharshi
*/
public class MakeFairCoinFromUnfairCoin {
public static int fairCoinToss() {
int a = unfairCoinToss();
int b = flipUnfairToss();
while (a + b == 1) {
a = unfairCoinToss();
b = flipUnfairToss();
}
// Probability of 0,0 is 0.24. Probability of 1,1 is 0.24.
return a + b == 0 ? 0 : 1;
}
private static int flipUnfairToss() {
return unfairCoinToss() == 0 ? 1 : 0;
}
// Returns 0 with 60% probability.
private static int unfairCoinToss() {
return Math.random() < 0.6F ? 0 : 1;
}
public static void main(String[] args) {
System.out.println(fairCoinToss());
}
}
Java Code:
/*
* @author shivam.maharshi
*/
public class MakeFairCoinFromUnfairCoin {
public static int fairCoinToss() {
int a = unfairCoinToss();
int b = flipUnfairToss();
while (a + b == 1) {
a = unfairCoinToss();
b = flipUnfairToss();
}
// Probability of 0,0 is 0.24. Probability of 1,1 is 0.24.
return a + b == 0 ? 0 : 1;
}
private static int flipUnfairToss() {
return unfairCoinToss() == 0 ? 1 : 0;
}
// Returns 0 with 60% probability.
private static int unfairCoinToss() {
return Math.random() < 0.6F ? 0 : 1;
}
public static void main(String[] args) {
System.out.println(fairCoinToss());
}
}
The concept that I applied is similar i.e., you toss once and store value in var a. You toss again, flip the value and store in b. Now you check if a + b == 1. If they are then you toss again. If not, then if a+b ==0, you return 0 else you return 1.
The probability would be equal for both cases :: p*(1-p) == (1-p) * p.
Code below:
/*
* @author shivam.maharshi
*/
public class MakeFairCoinFromUnfairCoin {
public static int fairCoinToss() {
int a = unfairCoinToss();
int b = flipUnfairToss();
while (a + b == 1) {
a = unfairCoinToss();
b = flipUnfairToss();
}
// Probability of 0,0 is 0.24. Probability of 1,1 is 0.24.
return a + b == 0 ? 0 : 1;
}
private static int flipUnfairToss() {
return unfairCoinToss() == 0 ? 1 : 0;
}
// Returns 0 with 60% probability.
private static int unfairCoinToss() {
return Math.random() < 0.6F ? 0 : 1;
}
public static void main(String[] args) {
System.out.println(fairCoinToss());
}
}
zr.roman I have a doubt about your approach. Can you please correct me ?
Lets say that probability of returning 1 is p. So according to your logic, you can get 0 as the output in these two cases:
1. First toss was 1 (a[0]=1 & a[1]=0), second toss was 1 so return a[1]. This has probability p*p.
2. Fist toss was 0 (a[0]=0 & a[1]=1), second toss was 0 so return a[0]. This has probability (1-p)*(1-p).
So P(0) = 1 -2p + p*p;
Similarly the output of your function will be 1, with the probability of p*(1-p) + p*(1-p).
P(1) = 2*(1-p)*p
Since P(0) != P(1), this is not a fair toss.
Please correct me if I am wrong.
For questions like these I would prefer writing a Comparator class and then sort the given list of numbers using that comparator. Since conversion to String for a huge amount of number could be very memory inefficient. Below is the Java / Comparator Code:
/*
* @author shivam.maharshi
*/
public class HighestValueByConcantenation {
public static void getHighest(int[] a) {
List<Integer> list = new ArrayList<>();
for (int aa : a)
list.add(aa);
Collections.sort(list, new ConComp());
for (int aa : list)
System.out.print(aa);
}
public static void main(String[] args) {
// int[] a = {9, 918, 917};
int[] a = { 1, 112, 113 };
getHighest(a);
}
}
class ConComp implements java.util.Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>();
while (o1 != 0) {
l1.add(o1 % 10);
o1 = o1 / 10;
}
while (o2 != 0) {
l2.add(o2 % 10);
o2 = o2 / 10;
}
int i = l1.size() - 1;
int j = l2.size() - 1;
while (i >= 0 && j >= 0) {
if (l1.get(i) > l2.get(j))
return -1;
else if (l1.get(i) < l2.get(j))
return 1;
i--;
j--;
}
if (i != -1) {
int lastDigit = l1.get(i + 1);
while (i >= 0) {
if (l1.get(i) < lastDigit)
return 1;
else if (l1.get(i) > lastDigit)
return -1;
i--;
}
}
if (j != -1) {
int lastDigit = l2.get(j + 1);
while (j >= 0) {
if (l2.get(j) < lastDigit)
return -1;
else if (l2.get(j) > lastDigit)
return 1;
j--;
}
}
return 0;
}
}
Using the algorithm proposed above, here is the code in Java. Time Complexity: O(n^2). Space Complexity: O(n). The logic is:
1. If there exist an index which has the minimum number, than its product and remove the index. However this must not lie in the corner.
2. If 1 is not possible than chose the index that gives maximum product and remove this index.
/ *
* @author shivam.maharshi
*/
public class BurstBaloons {
public static int maxValue(int[] a) {
int res = 0;
List<Integer> list = new ArrayList<>();
for (int num : a)
list.add(num);
while (list.size() > 3) {
int min = getMinValue(list);
int index = findIndexOfValue(list, min);
if (!(index > 0 && index < (list.size() - 1))) {
index = getMaxProductIndex(list);
}
res += list.get(index - 1) * list.get(index) * list.get(index + 1);
list.remove(index);
}
res += list.get(0) * list.get(1) * list.get(2) + list.get(0) * list.get(2) + Math.max(list.get(0), list.get(2));
System.out.println(res);
return res;
}
private static int getMaxProductIndex(List<Integer> list) {
int index = 0;
int maxProd = Integer.MIN_VALUE;
for (int i = 1; i < list.size() - 1; i++) {
if (list.get(i - 1) * list.get(i) * list.get(i + 1) > maxProd) {
maxProd = list.get(i - 1) * list.get(i) * list.get(i + 1);
index = i;
}
}
return index;
}
private static int getMinValue(List<Integer> list) {
int min = Integer.MAX_VALUE;
for (int num : list)
if (num < min)
min = num;
return min;
}
private static int findIndexOfValue(List<Integer> list, int num) {
for (int i = 0; i < list.size(); i++)
if (list.get(i) == num)
return i;
return -1;
}
@zr.roman your solution is perfect. However I wouldn't say the implementation is straight forward. Below is what I coded in Java.
* @author shivam.maharshi
*/
public class ArraySerializerDeserializer {
public static String serialize(String[] a) {
StringBuilder output = new StringBuilder();
int maxLenght = 0;
for (String s : a)
if (s.length() > maxLenght)
maxLenght = s.length();
maxLenght++;
output.append(maxLenght).append(":");
String delimiter = generateRandString(maxLenght);
for (String s : a)
output.append(delimiter).append(s.length()).append(":").append(s);
System.out.println(output.toString());
return output.toString();
}
public static String[] deserialize(String s, int size) {
String[] output = new String[size];
StringBuilder sb = new StringBuilder();
StringBuilder num = new StringBuilder();
int i = 0;
while (s.charAt(i) != ':') {
num.append(s.charAt(i));
i++;
}
i++;
int maxWordSize = Integer.valueOf(num.toString());
num = new StringBuilder();
boolean parsingNum = false;
boolean parsingDelimiter = true;
int charCount = 0;
int nextWordLenght = 0;
int wordCount = 0;
while (i < s.length()) {
if (parsingDelimiter) {
while (charCount < maxWordSize) {
i++;
charCount++;
}
parsingDelimiter = false;
parsingNum = true;
charCount = 0;
} else if (parsingNum) {
while (s.charAt(i) != ':') {
num.append(s.charAt(i));
i++;
}
parsingNum = false;
nextWordLenght = Integer.valueOf(num.toString());
num = new StringBuilder(); // Emptying.
i++;
} else {
while (nextWordLenght > 0) {
sb.append(s.charAt(i));
i++;
nextWordLenght--;
}
parsingDelimiter = true;
output[wordCount] = sb.toString();
wordCount++;
sb = new StringBuilder(); // Emptying.
}
}
return output;
}
private static String generateRandString(int size) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
sb.append((char) (65 + (26 * Math.random())));
}
return sb.toString();
}
public static void main(String[] args) {
String[] a = { "this", "is", "very", "nice", "I", "like" };
String s = serialize(a);
String[] output = deserialize(s, a.length);
for (String out : output)
System.out.print(out + " ");
}
}
@EPavlova & @zr.roman
If instead of a HashSet a SortedSet is used, then the complexity would be O(n*lg n). Because the lookup can then be done via binary search in lg n time.
This code has: O(nlog(n) + n*n*26 + n*m) worst case complexity. But two major optimizations:
1. When the length of the outer loop string is less than the sqrt of the maximum product reached, no further computations are required.
2. When the product of the length of the inner loop string and the outer loop string is less than the maximum product reached, no further inner loop computations are required.
/*
* @author shivam.maharshi
*/
public class DiffCharArrMaxLenProduct {
public static int max(String[] a) {
Arrays.sort(a, new LengthComprarator());
int max = 0;
boolean[] flag = new boolean[26];
for (int i = 0; i < a.length; i++) {
if (a[i].length() * a[i].length() <= max)
break; // Optimization.
for (char c : a[i].toCharArray()) {
flag[(int) c - 65] = true;
}
for (int j = i = 1; j < a.length; j++) {
if (a[i].length() * a[j].length() <= max) {
break; // Optimization.
} else if (!hasSimilarCharacters(a[j], flag)) {
max = a[i].length() * a[j].length();
break;
}
}
Arrays.fill(flag, false);
}
System.out.println(max);
return max;
}
private static boolean hasSimilarCharacters(String s, boolean[] flag) {
for (char c : s.toCharArray()) {
if (flag[c - 65])
return true;
}
return false;
}
We don't have to think about the case when there is not majority element because the question mentions that your algo may assume that the array has a majority element.
- Shivam Maharshi January 19, 2016Using backtracking.
public class CountPatternsInAndroidLockScreen {
private static int count = 0;
private static int[][] graph = new int[][] { { 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 0, 1, 0 } };
/*
* Must take care of the corner cases. 1->9 is not a valid case because 5
* lies in the way, however 1->5->9 is.
*/
public static void count(int level, int index, boolean[] visited, int minLevel) {
if (allVisited(visited))
return;
if (level >= minLevel)
count++;
for (int i = 0; i < 9; i++) {
if (!visited[i] && graph[index][i] == 1) {
visited[i] = true;
count(level + 1, i, visited, minLevel);
visited[i] = false;
}
}
}
private static boolean allVisited(boolean[] visited) {
for (boolean b : visited)
if (!b)
return false;
return true;
}
public static void main(String[] args) {
for (int i = 0; i < 9; i++) {
count(0, i, new boolean[9], 3);
}
System.out.println(count);
}
}
This will work. I feel that the question is incomplete. It should specify what to return when all numbers are negative. Since in that case the product will not be positive, which is mentioned in the question - "Maximum positive product". Anyways, the below code works fine for all other situations except for these two
1. All numbers negative.
2. Array of size 3 with 1 negative number.
/**
* Find the maximum positive product of three distinct numbers in an array when
* sorting is not allowed.
*
* @author shivam.maharshi
*
*/
public class MaxPositiveProduct {
public static int get(int[] a) {
int m1 = Integer.MIN_VALUE, m2 = m1, m3 = m2;
int n1 = Integer.MAX_VALUE, n2 = n1;
for (int i = 0; i < a.length; i++) {
if (a[i] > m1) {
m1 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] > m2 && a[i] != m1) {
m2 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] > m3 && a[i] != m1 && a[i] != m2) {
m3 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] < n1) {
n1 = a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] < n2 && a[i] != n1) {
n2 = a[i];
}
}
return m1 * Math.max(m2 * m3, n1 * n2);
}
public static void main(String[] args) {
int[] a = new int[] { -10, -9, -11, 1, 3, 5, 2, 8, 0, -1, 3 };
System.out.println(MaxPositiveProduct.get(a));
}
}
Hi Vicky,
You algorithm and thinking is perfect. Just one improvement. I see you are calculating sum by repeatedly parsing the array of size k. You don't need to do this. Running average = Previous Running Average + ( Element read from stream - Element eliminated from store this time) / K
/**
* Consider a stream of doubles. At any moment find the moving average of the
* last k numbers. If received less than k numbers than return average of only
* those numbers.
*
* @author shivam.maharshi
*/
public class StreamAverage {
public static void runningAverage(double[] stream, int k) {
double avg = 0F;
double[] store = new double[k];
int i = 0, sl = stream.length;
boolean touchedK = false;
for (int j = 0; j < sl; j++) {
if (j == k) {
touchedK = true;
}
if (i == k) {
i = 0;
}
if (touchedK) {
avg = (avg * k - store[i] + stream[j]) / k;
} else {
avg = (avg * (j) + stream[j]) / ( j + 1);
}
System.out.println(avg);
store[i] = stream[j];
i++;
}
}
public static void main(String[] args) {
double[] stream = new double[] { 1, 3, 5, 7, 0, 2, 5, 6 };
StreamAverage.runningAverage(stream, 3);
}
}
// Given an array reverse the consecutive positive numbers between -ve numbers.
public class ReversePositiveNumbers {
public static int[] reverse(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int i = 0, j = 1;
while (j < arr.length) {
if (arr[j] <= 0) {
if (i != j - 1) {
if(arr[i]<=0) {
i++;
}
reverse(arr, i, j-1);
}
/*
* Print it or whatever because the array has already been
* reversed.
*/
i = ++j;
}
j++;
}
return arr;
}
private static void reverse(int[] arr, int i, int j) {
while (j > i) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
public static void main(String[] args) {
int[] arr = new int[] { 4, 3, 8, 9, -2, 6, 10, 13, 4, 5, -9, 0, -2 };
ReversePositiveNumbers.reverse(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
You are right. For reaching to the parent of any node we can create a HashMap with Key as an employee and Value as its Manager. Constant time lookup and classic common parent node solution would work.
- Shivam Maharshi October 26, 2015I like the overall approach however this will not work in the case where the Second Set is bigger than the First set take this case for example:
First Set:- 1,2,3,4,5
Second Set:- 1,2,3,4,5,6,7,8
Fill map will put all entries from 1-5 into map, and check map will remove all of them from map but 7 and 8 were not present, so ideally it should return false but your program will return true.
Solution:-
When you find some entry not present, return false immediately.
public static void printAllSets(char[] c) {
List<String> list = new ArrayList<String>();
list.add("");
printSets(c, 0, list);
}
private static void printSets(char[] c, int index, List<String> list) {
if(index==c.length) return;
int len = list.size();
for(int i=0; i<len; i++) {
System.out.println(list.get(i) + c[index]);
list.add(list.get(i) + c[index]);
}
index++;
printSets(c, index, list);
}
This is the algorithm that I would propose:
1. Split the sentence via space into an array. (You can optimize with using it as well, but this is easier to explain.)
2. Maintain three int variables - Pos1 & Pos2 and Min = Integer.MAX.
3. Update pos1 with the word position when you encounter input1.
4. Update pos2 when you encounter input2.
5. Update Min if Math.abs(pos2 - pos1) < Min.
6. If Min==1 at any time you break from loop, since the distance can't be less than 1 in any case.
7. Repeat the steps till the end for worst case. By the end you have Min distance in Min variable.
PS:- If the words are same, then just modify steps 3 & 4 to be executed for the input encounters alternatively. Since input1=input2 in this case.
Also for this case you could just use pos1 variable only to store the new encounters and update the Min variable if the difference from the previous pos1 is less than Min.
/*
* Given n fair dice with m side, return the histogram of frequency of their sum.
*/
public class DiceRollHistogram {
public static Map<Integer, Integer> getHistogram(int n, int m) {
Map<Integer, Integer> histogram = new HashMap<Integer, Integer>();
int[] a = new int[n];
Arrays.fill(a, 1);
while (true) {
try {
int sum = computeSum(a);
if (histogram.containsKey(sum)) {
histogram.put(sum, histogram.get(sum) + 1);
} else {
histogram.put(sum, 1);
}
a = incermentCounter(a, m);
} catch (OverFlowExecution e) {
break;
}
}
return histogram;
}
private static int computeSum(int[] a) {
int count = 0;
for (int i = 0; i < a.length; i++) {
count += a[i];
}
return count;
}
private static int[] incermentCounter(int[] a, int m) {
if (isMax(a, m))
throw new OverFlowExecution();
for (int i = 0; i < a.length; i++) {
if (a[i] == m) {
a[i] = 1;
continue;
} else {
a[i] = a[i] + 1;
break;
}
}
return a;
}
private static boolean isMax(int[] a, int m) {
for (int i = 0; i < a.length; i++) {
if (a[i] < m)
return false;
}
return true;
}
public static void main(String[] args) {
Map<Integer, Integer> histogram = DiceRollHistogram.getHistogram(2, 3);
System.out.println(histogram.size());
}
}
class OverFlowExecution extends RuntimeException {
private static final long serialVersionUID = -3553581134335170678L;
}
/*
* Given n fair dice with m side, return the histogram of frequency of their sum.
*/
public class DiceRollHistogram {
public static Map<Integer, Integer> getHistogram(int n, int m) {
Map<Integer, Integer> histogram = new HashMap<Integer, Integer>();
int[] a = new int[n];
Arrays.fill(a, 1);
while (true) {
try {
int sum = computeSum(a);
if (histogram.containsKey(sum)) {
histogram.put(sum, histogram.get(sum) + 1);
} else {
histogram.put(sum, 1);
}
a = incermentCounter(a, m);
} catch (OverFlowExecution e) {
break;
}
}
return histogram;
}
private static int computeSum(int[] a) {
int count = 0;
for (int i = 0; i < a.length; i++) {
count += a[i];
}
return count;
}
private static int[] incermentCounter(int[] a, int m) {
if (isMax(a, m))
throw new OverFlowExecution();
for (int i = 0; i < a.length; i++) {
if (a[i] == m) {
a[i] = 1;
continue;
} else {
a[i] = a[i] + 1;
break;
}
}
return a;
}
private static boolean isMax(int[] a, int m) {
for (int i = 0; i < a.length; i++) {
if (a[i] < m)
return false;
}
return true;
}
public static void main(String[] args) {
Map<Integer, Integer> histogram = DiceRollHistogram.getHistogram(2, 3);
System.out.println(histogram.size());
}
}
class OverFlowExecution extends RuntimeException {
private static final long serialVersionUID = -3553581134335170678L;
}
Good Maker, your description is very comprehensible. Thank a lot !! Voted up.
- Shivam Maharshi October 15, 2015This is not O(1) space. You are using recursion, that means implicit method stacks.
Worst case space complexity O(N) -- In case it is a totally unbalanced binary search tree, like a linked list, the space complexity would be O(N) since all the nodes have to be traversed as part of successive recursion.
Average case space complexity: O(lg(n)) -- In case of a balanced binary search tree, the space complexity would be O(lg(n)). First all left, then all right.
Best case space complexity O(1) -- In case of a failure at early stages.
{ public static void printLexographicalOrder(int num, int n) {
if (n > num)
return;
else {
System.out.println(n);
printLexographicalOrder(num, n * 10);
if (( (n + 1) / 10) % 10 != (n / 10) % 10) {
return;
} else {
printLexographicalOrder(num, n + 1);
}
}
}
}
public static void printLexographicalOrder(int num, int n) {
if (n > num)
return;
else {
System.out.println(n);
printLexographicalOrder(num, n * 10);
if (( (n + 1) / 10) % 10 != (n / 10) % 10) {
return;
} else {
printLexographicalOrder(num, n + 1);
}
}
}
really good.
- Shivam Maharshi April 03, 2013I am sorry. One correction. k^2 ranges from 1 - 10^10.
- Shivam Maharshi February 02, 2013Time complexity is not O(k). Its O(k^2). you will need to run this loop within another loop which will reach to k itself. Try it.
- Shivam Maharshi February 01, 2013As the question asked for different ordered set, so a!=b. But no condition on k.
- Shivam Maharshi February 01, 2013@Geek. Can you tell me the hash function for this ? Becuase it would totally depend on your hash function what the order is.
- Shivam Maharshi December 11, 2012@ashu. Practically even a hash map can never reach O(1) complexity dear. It can be very close to log(n) though. So still the order would not be linear.
- Shivam Maharshi December 11, 2012@Geek this is O(nLog(n)) so better than this would be like Linear time. Do you know any better than this. If yes, then please tell us. :)
- Shivam Maharshi December 10, 2012public class ListPair {
// Returns list of the pairs
// with the addition equal to
// the sum mentioned.
public List<Pair> getPair(int sum, LinkedList<Integer> l1, LinkedList<Integer> l2) {
List<Pair> res = new ArrayList<Pair>();
Collections.sort(l1);
Collections.sort(l2, new MyComparator());
int oneIndex=0, twoIndex=0;
Pair pair = null;
while(oneIndex<l1.size() && twoIndex<l2.size()) {
if(l1.get(oneIndex)+l2.get(twoIndex)==sum) {
pair = new Pair(l1.get(oneIndex),l2.get(twoIndex));
res.add(pair);
twoIndex++;
oneIndex++;
} else if (l1.get(oneIndex)+l2.get(twoIndex)>sum) {
twoIndex++;
} else {
oneIndex++;
}
}
return res;
}
public static void main(String[] args) {
LinkedList<Integer> l1 = new LinkedList<>();
LinkedList<Integer> l2 = new LinkedList<>();
l1.add(1);
l1.add(2);
l1.add(6);
l1.add(-4);
l1.add(-2);
l1.add(4);
l1.add(5);
l1.add(-7);
l2.add(1);
l2.add(3);
l2.add(6);
l2.add(-4);
l2.add(-3);
l2.add(2);
l2.add(5);
l2.add(-7);
List<Pair> list = new ListPair().getPair(3, l1, l2);
for(Pair pair : list) {
System.out.println(pair.getV1() +" :: "+pair.getV2());
}
}
}
class MyComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
if(o1.intValue() < o2.intValue()) {
return 1;
} else {
return -1;
}
}
}
class Pair {
private int v1;
private int v2;
public Pair(int v1, int v2) {
this.v1 = v1;
this.v2 = v2;
}
public int getV1() {
return v1;
}
public void setV1(int v1) {
this.v1 = v1;
}
public int getV2() {
return v2;
}
public void setV2(int v2) {
this.v2 = v2;
}
}
I think this is a very elegant and obvious solution. But still looking for something better.
- Shivam Maharshi December 10, 2012Perhaps I did not get your map concept. If you search in the map for the number Sum-Node, then the order of your program goes O(n^2). Because you are iterating the second list which is O(n) and inside it searching the map for this value which is also O(n).
Please correct me if I am wrong.
@LoocalVinci....
Firstly you're right it's O(2^n).
Secondly you're wrong, it's working properly for small test cases. Check it for yourself.
Why would the answer start from 1? Question is not clear enough. Please explain the movements with another example.
- Shivam Maharshi January 11, 2017