Wireless Generation Interview Question
Java DevelopersCountry: United States
Interview Type: Phone Interview
Improving the soln to ensure same number of duplicates exists in both the lists.
public static boolean isAppears(String A,String B){
int[] Appears=new int[256];
for(int i=0;i!=B.length();i++){
Appears[(int)(B.charAt(i))]++;
}
for(int i=0;i!=A.length();i++){
Appears[(int)(A.charAt(i))]--;
}
for(int i=0;i<256;i++)
{
if(Appears[(int)(A.charAt(i))] != 0){
return false;
}
}
return true;
}
Hi HS,
Could you please explain this in detail?
What is the set here?
What is the S.C and T.C for your algorithm?
Thanks,
CVD
A Set in Java will not work: hashcodes and keys will cause conflict and not store dups.
@jack: he is using set to not store the duplicates. why do think it won't work. His solution is fairly simple and straightforward but it does require extra space.
int main()
{
char str1[]="ram shyakm mohailn";
char str2[]="kaali";
int arr[256]={0};
int i=0;
for(i=0;str1[i]!='\0';i++)
{
arr[str1[i]]+=1;
}
for(i=0;i<str2[i]!='\0';i++)
{
arr[str2[i]]-=1;
}
for(i=0;i<256;i++)
{
if(arr[i]==-1)
{
printf("false");
getch();
return 0;
}
}
printf("true");
getch();
return 0;
}
class Matching
{
void main(String args[])
{
char a[]={'a','b','c','d'};
char b[]={'c','d','e','f','a','b'};
int count=0;
for(int i=0;i<a.length;i++)
{
for(int j=0;j<b.length;j++)
{
if(a[i]==b[j])
{
count++;
break;
}
}
}
if(count==a.length)
System.out.println("true");
else
System.out.println("false");
}
}
/**
*
*/
package edu.cc.probs;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author RAHULCHA
* Input: two unsorted char arrays A,B(may contain dups) where A.length <= B.length
* If each character in A appears in B, return true. Else false. Write the code.
*/
public class SetProb {
static
{
System.out.println("Mention size of A and B at command line as java SetProb A_arg B_arg");
}
public static void main(String[] args) {
if(args.length!=2)
return;
List<Integer> A=new ArrayList<Integer>();
List<Integer> B=new ArrayList<Integer>();
Scanner sc=new Scanner(System.in);
System.out.println("Filling A");
if((Integer.parseInt(args[0]))>(Integer.parseInt(args[1])))
return;
for(int i=0;i<Integer.parseInt(args[0]);i++){
A.add(sc.nextInt());
}
System.out.println("Filling B");
for(int i=0;i<Integer.parseInt(args[1]);i++){
B.add(sc.nextInt());
}
if(B.containsAll(A)) {
System.out.println("True");
return;
}
else {
System.out.println("False");
System.exit(1);
}
}
}
ONE good Solution can as follow:
Take an array of int of length 26 like int word[26]; and
initialize it to 0
for(i=0;i<26;i++) word[i] = 0;
Now process each character of Array A as
for(i=0;A[i]!='\0'; i++)
{
word[A[i]-65] ++; //considering all charater in array are small letter (not capital)
}
Now process each character of Array B as
for(i=0;B[i]!='\0'; i++)
{
word[B[i]-65] --; //considering all charater in array are small letter (not capital)
}
Now check if any value in word is not zero then return false else true
flag=true;
for(i=0;i<26;i++)
{
if(word[i] != 0)
{
flag=false;
break;
}
}
return flag;
=====================
False means all character of A is not in B
True means all character of A is in B
public class charAray {
public static void main(String[] args) {
int a[]={'a','b','g'};
int b[]={'a','b','c','d','e','f'};
int c[]=new int[26];
boolean flag=false;
int i=0,k=0;
for(i=0;i<26;i++)
c[i]=0;
for(i=0;i<b.length;i++){
System.out.println("b");
c[(b[i]-97)]=1;
}
for(i=0;i<a.length;i++)
{
System.out.println("i"+i);
if(c[(a[i]-97)]==1)
{ flag=true;
continue;
}
else
{flag=false;
break;
}
}
if(flag==true)
System.out.println("a is subset");
else
System.out.println("a is not subset");
}
}
Try with List.containsAll()
import java.util.ArrayList;
import java.util.List;
public class Test1 {
public static void main(String[] args) {
char[] firstArray = {'a' , 'b' , 'c' , 'e'};
char[] secondArray = {'a' , 'b' , 'e' , 'c' , 'd'};
List<Character> character1 = getArrayAsList( firstArray );
List<Character> character2 = getArrayAsList( secondArray );
if ( character2.containsAll( character1 ) ) {
System.out.println( true );
}
else {
System.out.println( false );
}
}
public static List<Character> getArrayAsList( char[] ca ) {
List<Character> character1 = new ArrayList<Character>();
for ( char c : ca ) {
character1.add(c);
}
return character1;
}
}
or don't allow duplicates property of Set
import java.util.HashSet;
import java.util.Set;
public class Test1 {
public static void main(String[] args) {
char[] smallArray = {'a' , 'b' , 'c' , 'd'};
char[] largeArray = {'a' , 'b' , 'e' , 'c' , 'd'};
Set< Character > set = getSetFromArray( largeArray );
for ( char c : smallArray ) {
set.add( c );
}
if ( set.size() == largeArray.length ) {
System.out.println( true );
} else {
System.out.println( false );
}
}
public static Set< Character > getSetFromArray( char[] arr ) {
Set<Character> set = new HashSet<Character>();
for ( char c : arr ) {
set.add( c );
}
return set;
}
}
Cheers
static boolean compareCharArrays (char [] a, char [] b){
int it_b, it_a = 0;
boolean appearsAll = true;
boolean foundLocally;
while (appearsAll && it_a < a.length()){
it_b = 0;
foundLocally = false;
while (!foundLocally && it_b < b.length()){
if(a[it_a] == b[it_b]){
it_a ++;
foundLocally = true;
}else {
it_b ++;
}
}
if(!foundLocally){
appearsAll = false;
}
}
return appearsAll;
}
Scanner scanner = new Scanner(System.in);
String [] A = scanner.nextLine().split(" ");
String [] B = scanner.nextLine().split(" ");
HashSet<String> ASet = new HashSet<String>();
HashSet<String> BSet = new HashSet<String>();
for(String As : A)ASet.add(As);
for(String Bs: B)BSet.add(Bs);
if(BSet.containsAll(ASet)){
return true;
}else{
return false;
}
}
use hashtable. key = char in B; value = number of occurence of key in B.
def is_contain(A, B):
d = {}
for c in B:
if c in d:
d[c] += 1
else:
d[c] = 1
for c in A:
if c not in d or d[c] <= 0:
return False
else:
d[c] -= 1
return True
do you mean hashtable is not suitable here because of the large database? in that way we can sort the two strings and compare.
for the bug, which line do you refer to
no. it should be d[c] <= 0, by which i mean if we encounter a char, say 'X', in A, but 'X' in B has been used up. in this case, we should return false.
Okay. Let me correct myself; it's okay to do d[c]<0, but not d[c]==0; in any case, it's inefficient. It's better to store A's elements in d[c], so that there will be O(A.length) space overhead, where B.length could be very large; if you do this, then d[c]>0 will be the condition for falseness.
The below solution is a basic solution. There can be better approaches than this.
1. Sort both the character arrays.
2. Now, loop into both the arrays by keeping the index at the start of array:
a) If A's char array character matches with B's char array character then increment both the indices.
b) If A's char array character does not match:
b.1) If A's char array ascii value is less than B's char array ascii value then increment B array index.
b.2) Else return not false.
3. If out of loop then return true.
public static boolean isAppears(String A,String B){
- Chengyun Zuo August 30, 2012boolean[] Appears=new boolean[256];
for(int i=0;i!=B.length();i++){
Appears[(int)(B.charAt(i))]=true;
}
for(int i=0;i!=A.length();i++){
if(Appears[(int)(A.charAt(i))]==false){
return false;
}
}
return true;
}