settyblue
BAN USERyour solution is wrong.
Consider the following simple case.
What is the probability of getting 2 or 4?
it is not 1/12. it is 2/12.
What is the probability of getting 7, 9 or 11? it is 0.
There are many other mistakes, these are the simple ones that I can point out.
public class Main {
public static void main(String[] args) {
String s = "hello world!" ;
//String orderingPattern = "hlo!";
String orderingPattern = "he!";
if(checkOrderpattern(s,orderingPattern)){
System.out.println("The string is ordered.");
}else{
System.out.println("The string is not ordered.");
}
}
public static boolean checkOrderpattern(String s, String orderingPattern){
for(int i=0;i<orderingPattern.length()-1; i++){
if(!( s.lastIndexOf(orderingPattern.charAt(i)) < s.indexOf(orderingPattern.charAt(i+1)) )){
return false;
}
}
return true;
}
}
Implemented Logic:
1. First create a new result array which is nothing but appending array1 to array2. O(n)
2. Sort this result object array by id. O(nlogn)
3. Iterate through result array and add the weights of the items having same Ids. O(n)
(And keep track of unique elements, overwrite repeated id. Refer code for actual implementation.)
4. Sort the result array by weight. O(nlogn)
Overall time Complexity = O(nlogn)
Space Complexity = O(n)
public class Main {
public static void main(String[] args) {
Item[] array1 = {new Item(2,5),new Item(5,10),new Item(1, 10), new Item(4,12)};
Item[] array2 = {new Item(3,7),new Item(2,10),new Item(1, 10)};
print(array1);print(array2);
mergeAndPrint(array1,array2);
}
public static class Item {
int id, weight;
Item(int id, int weight){
this.id = id;
this.weight = weight;
}
public String toString(){return "("+id+", "+weight+")";}
}
public static class compareById implements Comparator<Item>{
public int compare(Item i1, Item i2) {
return i1.id - i2.id;
}
}
public static class compareByWeight implements Comparator<Item>{
public int compare(Item i1, Item i2) {
return i1.weight - i2.weight;
}
}
public static void print(Item[] array){
System.out.println(Arrays.toString(array));
}
public static void mergeAndPrint(Item[] array1, Item[] array2){
Item[] result = new Item[array1.length + array2.length];
System.arraycopy(array1, 0, result, 0, array1.length);
System.arraycopy(array2, 0, result, array1.length, array2.length);
Arrays.sort(result,new compareById());
int count = 0;
for(int i=1; i<result.length; i++){
if(result[count].id == result[i].id){
result[count].weight += result[i].weight;
}else{
count++;
result[count] = result[i];
}
}
result = Arrays.copyOf(result, count+1);
Arrays.sort(result,new compareByWeight());
print(result);
}
}
This is a recursive solution.
public class Main {
public static void main(String[] args) {
int[] array = {1,2,3,5,8,7,6,9,5,7,3,0,5};int[] subArray = {5,7};
printMinLength(array,subArray);
}
public static void printMinLength(int[] array, int[] subArray){
int minLength = Integer.MAX_VALUE, startIndex = -1;
for(int i=0; i<array.length-subArray.length; i++){
if(array[i] == subArray[0]){
int end = find(array,i,subArray,0);
if(end != -1 && minLength > end-i+1){
minLength = end-i+1;
startIndex = i;
}
}
}
if(startIndex != -1){
int[] answer = Arrays.copyOfRange(array, startIndex, startIndex+minLength);
System.out.println("minimum length = "+minLength+"; start index = "+startIndex);
System.out.println(Arrays.toString(answer));
}else{
System.out.println("No solution exists.");
}
}
public static int find(int[] array, int startArray, int[] subArray, int startSubArray){
if(startSubArray == subArray.length)return startArray-1;
if(subArray.length - startSubArray > array.length - startArray )return -1;
if(array[startArray] == subArray[startSubArray]){
return find(array,startArray+1,subArray,startSubArray+1);
}else{
return find(array,startArray+1,subArray,startSubArray);
}
}
}
This is called as a partition problem.
It can be solved using dynamic programming.
Also the time complexity is polynomial in n and not 2^n if we have liberty of space. Otherwise we will have to use recursive solution which has time complexity of 2^n.
public class Main {
public static void main(String[] args) {
int[] array = {1, 5, 11, 5, 2};
if(canBePartitioned(array)){
System.out.println("the given array can be partitioned.");
}else{
System.out.println("the given array cannot be partitioned.");
}
}
public static boolean canBePartitioned(int[] array){
int sum = 0;
for(int i=0; i<array.length; i++){
sum += array[i];
}
if(sum%1 == 1){
return false;
}
boolean[][] partition = new boolean[sum/2+1][array.length+1];
for(int i=0;i<array.length+1;i++){
partition[0][i] = true;
}
for(int i=1;i<sum/2+1; i++){
partition[i][0] = false;
}
for(int i=1; i<sum/2+1; i++){
for(int j=1; j<array.length+1; j++){
partition[i][j] = partition[i][j-1];
if(i >= array[j-1])partition[i][j] = partition[i-array[j-1]][j-1] || partition[i][j];
}
}
return partition[sum/2][array.length];
}
}
public class Main {
public static void main(String[] args) {
File file = new File("Log.txt");
HashMap<String,String> currentPageTracker = new HashMap<String,String>();
HashMap<String,HashSet<String>> links = new HashMap<>();
try {
Scanner input = new Scanner(file);
while(input.hasNextLine()){
String line = input.nextLine();
String[] tokens = line.split(" ");
//System.out.println(tokens[2]+" "+tokens[4]);
if(!currentPageTracker.containsKey(tokens[2])){
currentPageTracker.put(tokens[2], tokens[4]);
}else{
String prevPage = currentPageTracker.get(tokens[2]);
if(links.containsKey(prevPage)){
links.get(prevPage).add(tokens[4]);
}else{
HashSet<String> set = new HashSet<String>();
set.add(tokens[4]);
links.put(prevPage, set);
}
currentPageTracker.put(tokens[2], tokens[4]);
}
}
System.out.println(links);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
public class Main {
public static void main(String[] args) {
int[][] matrix = {{6, 7, 8, 9, 2},
{4, 6, 7, 8, 9},
{1, 4, 6, 7, 8},
{0, 1, 3, 6, 7}};
if(checkToepliz(matrix)){
System.out.println("It is toepliz matrix.");
}else{
System.out.println("It is not a toepliz matrix.");
}
}
public static boolean checkToepliz(int[][] matrix){
for(int i=0; i<matrix.length-1; i++){
for(int j=0; j<matrix[0].length-1; j++){
if(matrix[i][j] != matrix[i+1][j+1]){
return false;
}
}
}
return true;
}
}
public class Main {
public static void main(String[] args) {
//String s = "ttaatta"; //attatta
//String s = "ttaatt"; //atttta
String s = "ttaata"; //attta
printLongestPalindrome(s);
}
public static void printLongestPalindrome(String s){
HashMap<Character,Integer> map = new HashMap<>();
for(Character c:s.toCharArray()){
if(map.containsKey(c)){
map.put(c, map.get(c)+1);
}else{
map.put(c, 1);
}
}
int oddMaxCount = 0;
StringBuffer result1 = new StringBuffer("");
StringBuffer result2 = new StringBuffer("");
for(Character key:map.keySet()){
if(map.get(key)%2!=0){
oddMaxCount = Math.max(oddMaxCount, map.get(key));
}
for(int i=0;i<map.get(key)/2;i++){
result1.append(key);
}
}
char middle='q';
boolean middleExists = false;
for(Character key:map.keySet()){
if(map.get(key)%2!=0 && map.get(key)==oddMaxCount){
middle = key;
middleExists = true;
}
for(int i=0;i<map.get(key)/2;i++){
result2.append(key);
}
}
if(middleExists)System.out.println(result1+Character.toString(middle)+result2.reverse());
else System.out.println(result1+""+result2.reverse());
}
}
public class Main {
public static void main(String[] args) {
String s = "11aa22bb33dd44S";
System.out.println("The string sum is "+stringSum(s));
}
public static int stringSum(String s){
int sum = 0, curNumber = 0;
for(int i=0; i<s.length();i++){
if(Character.isDigit(s.charAt(i))){
curNumber = curNumber*10 + (s.charAt(i)-'0');
}else{
sum += curNumber;
curNumber = 0;
}
}
return sum+curNumber;
}
}
Sorting Solution:
Time Complexity = O(nlogn)
Space Complexity = O(1)
HashSet Solution:
Time Complexity = O(n) (amortized)
Space Complexity = O(n)
There is a trade-off for both the solutions.
Implemented both of them below:
public class Main {
public static void main(String[] args) {
int[] array = { 1, 94, 93, 1000, 2, 92, 1001};
System.out.println("Max continuous length = "+maxContinuousLength2(array));
}
//Using sorting.
public static int maxContinuousLength(int[] array){
int maxLength = 1, curLength = 1;
Arrays.sort(array);
int prev = array[0];
for(int i=1; i<array.length; i++){
if(prev == array[i]-1){
curLength++;
}else{
maxLength = max(maxLength,curLength);
curLength = 1;
}
prev = array[i];
}
return maxLength;
}
//using HashSet
public static int maxContinuousLength2(int[] array){
int maxLength = 0;
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0; i<array.length; i++){
set.add(array[i]);
}
for(Integer i: set){
if(!set.contains(i-1)){
int curLength = 0;
while(set.contains(i)){
i++;curLength++;
}
maxLength = max(maxLength, curLength);
}
}
return maxLength;
}
}
I have implemented it using Iterative Dynamic Programming.
public class Main {
public static void main(String[] args) {
int[][] costMatrix = { {4, 5, 6},
{1, 2, 3},
{0, 1, 2} };
System.out.println("Minimum cost to traverse = "+minCost(costMatrix));
}
public static int minCost(int[][] costMatrix){
int[][] mat = new int[costMatrix.length][costMatrix[0].length];
mat[mat.length-1][mat[0].length-1] =
costMatrix[mat.length-1][mat[0].length-1];
for(int j=mat[0].length-2; j>=0; j--){
int lastRow = mat.length-1;
mat[lastRow][j] = mat[lastRow][j+1] + costMatrix[lastRow][j];
}
for(int i=mat.length-2; i>=0; i--){
int lastCol = mat[0].length-1;
mat[i][lastCol] = mat[i+1][lastCol] + costMatrix[i][lastCol];
for(int j=mat[0].length-2; j>=0; j--){
mat[i][j] = costMatrix[i][j] + Math.min(mat[i+1][j+1],
Math.min(mat[i+1][j], mat[i][j+1]));
}
}
return mat[0][0];
}
}
public class Main {
public static void main(String[] args) {
String s1 = "abc";
String s2 = "de";
printInterleave(s1,s2);
}
public static void printInterleave(String s1,String s2){
String soFar = "";
printInterleaveUtil(s1,s2,0,0, soFar);
}
public static void printInterleaveUtil(String s1, String s2, int l1, int l2, String soFar){
if(l1 == s1.length() && l2 == s2.length()){
System.out.println(soFar);
return;
}
if(l1 < s1.length()){
printInterleaveUtil(s1,s2,l1+1,l2,soFar+s1.charAt(l1));
}
if(l2 < s2.length()){
printInterleaveUtil(s1,s2,l1,l2+1,soFar+s2.charAt(l2));
}
}
}
Time Complexity = O(klogk)
Space Complexity = O(k)
Logic:
1. Create a minHeap of size k. (This heap stores the k largest elements in the array)
2. Initialize the heap with first k elements.
3. For the next elements,
verify if the next element is greater than heap.peek().
if it is greater remove the top and add this element to the heap.
otherwise continue.
4. After iterating through all the elements in the array return heap.peek()
public class Main {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
int k = 4;
System.out.println(k+"th largest number is "+kthLargest(array,k));
}
public static int kthLargest(int[] array, int k){
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
if(array.length < k+1){
System.out.println("Array size is smaller than k.");
return 0;
}
for(int i=0;i<k+1;i++){
queue.add(array[i]);
}
for(int i=k; i<array.length; i++){
if(array[i] > queue.peek()){
queue.remove();
queue.add(array[i]);
}
}
return queue.peek();
}
}
I feel this is a better solution:
-----------------------------------
Time Complexity = O(klogk)
Space Complexity = O(k)
-----------------------------------
Logic:
1. Create a minHeap of size k. (This heap stores the k largest elements in the array)
2. Initialize the heap with first k elements.
3. For the next elements,
verify if the next element is greater than heap.peek().
if it is greater remove the top and add this element to the heap.
otherwise continue.
4. After iterating through all the elements in the array return heap.peek()
-----------------------------------
public class Main {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
int k = 4;
System.out.println(k+"th largest number is "+kthLargest(array,k));
}
public static int kthLargest(int[] array, int k){
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
if(array.length < k+1){
System.out.println("Array size is smaller than k.");
return 0;
}
for(int i=0;i<k+1;i++){
queue.add(array[i]);
}
for(int i=k; i<array.length; i++){
if(array[i] > queue.peek()){
queue.remove();
queue.add(array[i]);
}
}
return queue.peek();
}
}
public class Main {
public static void main(String[] args) {
String s = "Man bites dog";
printReverseWords(s);
}
public static void printReverseWords(String s){
String[] words = s.split(" ");
Collections.reverse(Arrays.asList(words));
System.out.println(String.join(" ", words));
}
}
Solved by dividing the problems into sub-problems of smaller size.
But I am not caching any intermediate results.
That might fasten the algorithm.
public class Main {
public static void main(String[] args) {
//String s = "1234"; //3
//String s = "5555"; //1
String s = "11111"; //8
System.out.println("Number of possible decodes : "+countOfPossibleDecodes(s));
}
public static int countOfPossibleDecodes(String s){
int count=0;
if(s.length()==1){
return 1;
}
if(s.length()==0){
return 1;
}
count = countOfPossibleDecodes(s.substring(1));
if(s.charAt(0)=='1'){
count += countOfPossibleDecodes(s.substring(2));
}
if(s.charAt(0)=='2' && s.charAt(1)<='6'){
count += countOfPossibleDecodes(s.substring(2));
}
return count;
}
}
Time Complexity = O(n)
The idea is to maintain a HashMap of sum and Integer-pairs.
public class Main {
public static class Pair{
int a,b;
Pair(int a, int b){
this.a = a;
this.b = b;
}
public String toString(){
return "("+this.a+", "+this.b+")";
}
}
public static void main(String[] args) {
int n = 100000;
printTaxiCabNumbers(n);
}
private static void printTaxiCabNumbers(int n) {
HashMap<Integer, Pair> map = new HashMap<Integer, Pair>();
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
int m = (int) (Math.pow(i, 3)+Math.pow(j, 3));
if(map.containsKey(m)){
System.out.println(new Pair(i,j).toString()+" and "+map.get(m).toString());
}else{
map.put((int) (m), new Pair(i,j));
}
}
}
}
}
Time Complexity = O(n^2)
The idea is to maintain a hash map of integer and pair-of-numbers as shown below.
public class Main {
public static class Pair{
int a,b;
Pair(int a, int b){
this.a = a;
this.b = b;
}
public String toString(){
return "("+this.a+", "+this.b+")";
}
}
public static void main(String[] args) {
int n = 100000;
printTaxiCabNumbers(n);
}
private static void printTaxiCabNumbers(int n) {
HashMap<Integer, Pair> map = new HashMap<Integer, Pair>();
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
int m = (int) (Math.pow(i, 3)+Math.pow(j, 3));
if(map.containsKey(m)){
System.out.println(new Pair(i,j).toString()+" and "+map.get(m).toString());
}else{
map.put((int) (m), new Pair(i,j));
}
}
}
}
}
"Doubles (and floats in general) are designed so that when ordered lexicographically, they'll be ordered from the largest to the smallest. This is important because this means that if a double is smaller than another double based only on the first 32 bits, the rest don't matter."
--can you elaborate more on this statement?
If the rest of the bits doesn't matter..what do they contribute to the value of the double variable? nothing?
Thanks.
But I think I am missing something here.
Initially while counting the number of doubles belonging to each bucket, you are not considering the exponent, which means numbers having completely different exponent will go to the same bucket. Doesn't this imply that the median we are computing is completely wrong?
Rep
RepKimRPierce, Employee at Achieve Internet
I am a customer service-oriented Travel Agent in Travel and Tourism industries. I strongly believe that the skills and abilities ...
- settyblue December 16, 2016