codingAddicted
BAN USERthanks for pointing it out. I have added another function getCount which takes care of cases specified by you.
/*Given a list of strings, write an alogirthm that will return a list of sets of
permutations.
*
* sample input: [abc, cab, ba, b, ba]
* sample output: [{abc, cab}, {ba}, {b}]
*/
import java.util.*;
public class CheckForPermutation {
static String[] words= {"abcc","cabb","ba", "b", "ba","bca","ab","cba"};
public static boolean checkIfPermutation(String s1,String s2)
{
if(s1.length()!=s2.length())
return false;
char[] lett= s1.toCharArray();
for(char c:lett)
{
String s= Character.toString(c);
if(!s2.contains(s))
return false;
}
return true;
}
public static void printPermutations()
{
boolean match=false;
boolean countEqual=false;
int[] id=new int[words.length];
for(int k=0;k<id.length;k++)
{
id[k]=-1;
}
for(int i=0;i<words.length-1;i++)
{
if(id[i]!=1){
match=false;
System.out.print(words[i]+" ");
for(int j=i+1;j<words.length;j++){
match=checkIfPermutation(words[i],words[j]);
countEqual= getCount(words[i],words[j]);
if(match==true && words[i]!=words[j]&&id[j]==-1 && countEqual==true)
{
id[i]=1;
id[j]=1;
System.out.print(words[j]+" ");
continue;
}
if(match==true && words[i]==words[j])
{
id[i]=1;
id[j]=1;
continue;
}
}
System.out.println();
}
}
}
public static boolean getCount(String a,String b)
{
if(a.length()!=b.length())
return false;
Map<Character,Integer> ha = new HashMap<Character,Integer>();
Map<Character,Integer> hb = new HashMap<Character,Integer>();
for(int i=0;i<a.length()-1;i++)
{
int count=0;
for(int j=i+1;j<a.length();j++)
{
if(!ha.containsKey(a.charAt(i)))
{
if(a.charAt(i)==a.charAt(j))
count++;
}
}
ha.put(a.charAt(i), count);
}
for(int i=0;i<b.length()-1;i++)
{
int count=0;
for(int j=i+1;j<a.length();j++)
{
if(!hb.containsKey(b.charAt(i)))
{
if(b.charAt(i)==b.charAt(j))
count++;
}
}
hb.put(b.charAt(i), count);
}
Set sa= ha.entrySet();
Set sb= hb.entrySet();
Iterator ia= sa.iterator();
Iterator ib = sb.iterator();
while(ia.hasNext())
{
Map.Entry pairs= (Map.Entry)ia.next();
Character ch= new Character((char) pairs.getKey());
Integer va= new Integer((int)pairs.getValue());
if(hb.containsKey(ch))
{
int vb= new Integer((int)hb.get(ch));
if(va!=vb)
{
return false;
}
}
else
return false;
}
return true;
}
public static void main(String[] args) {
printPermutations();
}
}
the following code handles cases when more then one permutation of a string is present and also deals with duplicate case
public class CheckPermutation {
static String[] words= {"abc","cab","ba", "b", "ba","bca","ab","cba"};
public static boolean checkIfPermutation(String s1,String s2)
{
if(s1.length()!=s2.length())
return false;
char[] lett= s1.toCharArray();
for(char c:lett)
{
String s= Character.toString(c);
if(!s2.contains(s))
return false;
}
return true;
}
public static void printPermutations()
{
boolean match=false;
int[] id=new int[words.length];
for(int k=0;k<id.length;k++)
{
id[k]=-1;
}
for(int i=0;i<words.length-1;i++)
{
if(id[i]!=1){
match=false;
System.out.print(words[i]+" ");
for(int j=i+1;j<words.length;j++){
match=checkIfPermutation(words[i],words[j]);
if(match==true && words[i]!=words[j]&&id[j]==-1)
{
id[i]=1;
id[j]=1;
System.out.print(words[j]+" ");
continue;
}
if(match==true && words[i]==words[j])
{
id[i]=1;
id[j]=1;
//System.out.println(words[i]);
continue;
}
}
System.out.println();
}
}
}
public static void main(String[] args) {
printPermutations();
}
}
this one takes o(n^3logn) ...can anyone give it in n^2???
public class GivenSumInArray {
static int[] numbers= {2,3,4,5,7,8,9,10};
public static void calculateSum()
{
int low1= 0;
int high1=numbers.length-1;
int mid1=low1+((high1-low1)/2);
int x=23;
for(int i=numbers.length-1;i>mid1+1;i--)
{
for(int j=i-1;j>mid1;j--){
int sum1=numbers[i]+numbers[j];
for(int k=0;k<mid1;k++)
{
int sum2= sum1+numbers[k];
int low2= k+1;
int high2=mid1;
int requiredNum= x-sum2;
while(low2<=high2)
{
int mid2= low2+ ((high2-low2)/2);
int midVal2= numbers[mid2];
if(midVal2==requiredNum)
{
System.out.println(numbers[k]+" "+ midVal2+" "+numbers[j]+" "+numbers[i]);
break;
}
else if(midVal2>requiredNum)
high2=mid2-1;
else if(midVal2<requiredNum)
low2=mid2+1;
}
}
}
}
}
public static void main(String[] args) {
calculateSum();
}
}
please clarify one thing to me....
do we need to only insert in an already sorted linked list or do we need to sort the linklist as we insert.
again O(n^2) solution. we need O(n)
- codingAddicted September 01, 2012Isnt this taking O(n^2) time???? the question puts constraint on the time to be O(n)
- codingAddicted September 01, 2012what if there are more than 10 elements in both the lists.
- codingAddicted September 01, 2012space constraint is not mentioned in the question. Time complexity needs to be O(N)
- codingAddicted September 01, 2012here is one that uses hashmap
package diffof2linkedlistMicrosoft;
import java.util.*;
public class Program
{
public static LinkedList returnDifference(LinkedList a,LinkedList b)
{
HashMap<Integer,Node> hm= new HashMap<Integer,Node>();
Node currentA= a.first;
while(currentA!=null)
{
hm.put(currentA.data, currentA);
currentA=currentA.next;
}
Node currentB= b.first;
while(currentB!=null)
{
if(hm.containsKey(currentB.data))
hm.remove(currentB.data);
currentB=currentB.next;
}
LinkedList c = new LinkedList();
Set<Integer> set= hm.keySet();
Iterator<Integer> it= set.iterator();
while(it.hasNext())
{
c.insert(it.next());
}
return c;
}
public static void main(String args[])
{
LinkedList ll=new LinkedList();
LinkedList lb=new LinkedList();
ll.insert(4);
ll.insert(5);
ll.insert(6);
ll.insert(1);
ll.insert(2);
ll.insert(3);
lb.insert(1);
lb.insert(2);
lb.insert(3);
LinkedList lc= returnDifference(ll,lb);
lc.display();
}
}
1. Put the elements of the 1st linked list in a set.
2.From this set remove the elements which occur in second linked list,
3.Convert this set into a 3rd linked list.
I am using a temporary variable for shifting. hope that is allowed
package practicepackage;
public class RotateArrayLeft {
public static void main(String[] args) {
int[] numbers={1,2,3,4,5,10,20,30};
int k=4; // assuming array is shifted by 4 values to the left
for(int i=0;i<k;i++)
{
int temp= numbers[0];
int j=0;
for(j=1;j<=numbers.length-1;j++)
numbers[j-1]=numbers[j];
numbers[j-1]=temp;
}
for(int l=0;l<numbers.length;l++)
System.out.print(numbers[l]+" ");
}
}
A very simple java code that takes O(N) and uses set
package practicepackage;
import java.util.TreeSet;
import java.util.Set;
public class FindIfStringIsInterleaved {
public static boolean findIfInterleaved(String a,String b,String c)
{
if ((a+b).length()!=c.length())
return false;
char[] sum= (a+b).toCharArray();
char[] cChar= c.toCharArray();
Set<Character> input= new TreeSet<Character>();
for(int i=0;i<sum.length;i++)
input.add(sum[i]);
for(int j=0;j<sum.length;j++)
input.remove(cChar[j]);
if(input.isEmpty())
return true;
else
return false;
}
public static void main(String[] args) {
String A="abcd";
String B="xyz";
String C="axybczd";
System.out.println("is the string interleaved? "+findIfInterleaved(A,B,C) );
}
}
It will take O(N)
- codingAddicted August 29, 2012use hashmap to store the characters in a and b along with their indices.
use another hashmap to store characters in c and their indices. for each character in c then, just retrieve the values and check whether the index of that character in a or b is lesser then or equal to the index in c. if it is so return true else return false
here is the code
import java.util.HashMap;
import java.util.Map;
public class FindIfStringIsInterleaved {
public static boolean findIfInterleaved(String a,String b,String c)
{
char[] aChar= a.toCharArray();
char[] bChar= b.toCharArray();
char[] cChar= c.toCharArray();
Map<Character,Integer> ho= new HashMap<Character,Integer>();
Map<Character,Integer> hc= new HashMap<Character,Integer>();
boolean isInterleaved= true;
int sumOfInputStrings=a.length()+b.length();
if(sumOfInputStrings!=c.length())
return false;
for(int i=0;i<aChar.length;i++)
{
ho.put(aChar[i], i);
}
for(int i=0;i<bChar.length;i++)
{
ho.put(bChar[i], i);
}
for(int i=0;i<cChar.length;i++)
{
hc.put(cChar[i], i);
}
for(int i=0;i<cChar.length;i++)
{
int vc= hc.get(cChar[i]);
Object vo= (int)ho.get(cChar[i]);
if(vo==null)
return false;
else if ((int)vo<=vc)
continue;
else
return false;
}
return isInterleaved;
}
public static void main(String[] args) {
String A="abcd";
String B="xyz";
String C="axybczd";
System.out.println("is the string interleaved? "+findIfInterleaved(A,B,C) );
}
}
Taking arrays when array contains +ve numbers too. time complexity O(N)
class LargestSumContiguousSubarray{
public static void maxSubArraySum(int[] a)
{
int currentSum=0;
int maxSum=0;
int endIndex=0;
int beginIndex=0;
for(int i=0;i<a.length;i++)
{
currentSum+=a[i];
if(currentSum<0)
currentSum=0;
if(currentSum>maxSum)
{
maxSum=currentSum;
endIndex=i;
}
}
int temp=maxSum;
for(int j=endIndex;j>=0;j--)
{
temp-=a[j];
if(temp==0)
{
beginIndex=j;
break;
}
}
System.out.println("endIndex: "+endIndex);
System.out.println("beginIndex: "+beginIndex);
}
public static void main(String[] args)
{
int[] a= {-2, -3, 4, -1, -2, 1, 5, -3};
maxSubArraySum(a);
}
}
- codingAddicted August 28, 2012why do we need rand(3) -3 in the statement return (3*rand(3) + rand(3) -3)?????
isnt 3*rand(3) sufficient???
errr!!! i think it confusing. I am using current.next.next.next.next.next only as a checking condition
i am incrementing current as current.next.
correct me if i am wrong
whats wrong with using something like
current=first
while(current.next.next.next.next.next!=null)
current=current.next;
where next is the next node.
the code in java
package practicepackage;
public class SpecialMultiplication{
public static void main(String[] args)
{
int[] numbers={1,2,3,4};
int value=1;
for(int i=0;i<numbers.length;i++)
{
value*=numbers[i];
}
for(int j=0;j<numbers.length;j++)
{
numbers[j]= value/numbers[j];
}
for(int k=0;k<numbers.length;k++)
{
System.out.println(numbers[k]);
}
}
}
public class Series {
public int calculateSeries(int number)
{
if(number==1)
return 1;
int multiplier=1;
for(int i=0;i<number;i++)
{
multiplier*=number;
}
return multiplier+ calculateSeries(number-1);
}
public static void main(String[] args) {
Series s= new Series();
System.out.println(s.calculateSeries(4));
}
}
I am simply adding a characters to a string and then checking if the string is palindrome or not
- codingAddicted July 16, 2012java code
public class OnlyAlphabetsString {
public static void main(String[] args) {
String str= "a,a,b, , , c, , ,d,e";
String delim= "[ ,]";
String[] atr= str.split(delim);
String output =atr[0];
for(int i=1;i<atr.length;i++)
{
output+=atr[i];
}
System.out.println(output);
}
}
Cant we just deep clone the linked list?
- codingAddicted July 16, 2012import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
public class MaximumThreeAndAverage {
int[] arr= new int[10];
int max1=0;
int max2=0;
int max3=0;
public MaximumThreeAndAverage() throws IOException
{
load();
}
public void load() throws IOException
{
System.out.println("Enter 10 numbers in the array:");
Scanner sc= new Scanner(new InputStreamReader(System.in));
for(int i=0;i<arr.length;i++)
{
arr[i]=sc.nextInt();
if(arr[i]==0)
break;
}
System.out.println("thankyou");
}
public void calculateThreeMaximums()
{
System.out.println(" ");
max1=arr[0];
for(int i=0;i<arr.length;i++)
{
if(arr[i]>max1)
{
max1=arr[i];
}
}
for(int i=0;i<arr.length;i++)
{
if(arr[i]<max1&&arr[i]>max2)
{
max2=arr[i];
}
}
max3=arr[0];
for(int i=0;i<arr.length;i++)
{
if(arr[i]<max2&&arr[i]>max3)
{
max3=arr[i];
}
}
System.out.println("the Final three maximum numbers are: Max1: "+ max1+ " Max2: " + max2 +" Max3: "+max3);
}
public void averageOfRestNumbers()
{
int size=arr.length;
int sum = 0;
double average;
for(int i=0;i<arr.length;i++)
{
if(arr[i]==max1||arr[i]==max2||arr[i]==max3)
{
arr[i]=0;
size--;
}
sum+=arr[i];
}
average=(double)sum/size;
System.out.println("the average is: " +average);
}
public static void main(String[] args) throws IOException {
MaximumThreeAndAverage ax= new MaximumThreeAndAverage();
ax.calculateThreeMaximums();
ax.averageOfRestNumbers();
}
}
public class PrintListInColumns {
public static void main(String[] args) {
char arr[] ={'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
char brr[][]= new char[4][3];
int k=0;
for(int j=0;j<3;j++)
{
for(int i=0;i<4;i++)
{
if(i>=2&&j>1)
{
brr[i][j]=' ';
}
else
{
brr[i][j]=arr[k];
k++;
}
}
}
for(int j=0;j<brr.length;j++)
{
for(int i=0;i<brr[j].length;i++)
{
System.out.print(brr[j][i]+" ");
}
System.out.println(" ");
}
}
}
isnt charAt() a built in java function????
- codingAddicted July 14, 2012The heap can be implemented either in array or by making the nodes refer to each other.
the approaches are either keep travelling the nodes and when a duplicate is found , replace the duplicate with the last node and apply trickle down ..... or what i find more simpler is keep applying remove method of heap to fill the array in a sorted manner... then it would be much easier to find the duplicates
}
- codingAddicted October 25, 2012