Link to home
Start Free TrialLog in
Avatar of gudii9
gudii9Flag for United States of America

asked on

firstswap challenge

Hi,

I am working on below challenge

http://codingbat.com/prob/p150113
I was not clear on below description, please advise

We'll say that 2 strings "match" if they are non-empty and their first chars are the same. Loop over and then return the given array of non-empty strings as follows: if a string matches an earlier string in the array, swap the 2 strings in the array. A particular first char can only cause 1 swap, so once a char has caused a swap, its later swaps are disabled. Using a map, this can be solved making just one pass over the array. More difficult than it looks.

firstSwap(["ab", "ac"]) → ["ac", "ab"]
firstSwap(["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]) → ["ay", "by", "cy", "cx", "bx", "ax", "aaa", "azz"]
firstSwap(["ax", "bx", "ay", "by", "ai", "aj", "bx", "by"]) → ["ay", "by", "ax", "bx", "ai", "aj", "bx", "by"]
Avatar of phoffric
phoffric

Of the three examples, what exactly don't you understand?
Avatar of gudii9

ASKER

firstSwap(["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]) → ["ay", "by", "cy", "cx", "bx", "ax", "aaa", "azz"]
firstSwap(["ax", "bx", "ay", "by", "ai", "aj", "bx", "by"]) → ["ay", "by", "ax", "bx", "ai", "aj", "bx", "by"]
 

Open in new window


not clear on above two outputs. how they came. when first characters are same which one we should return?
ASKER CERTIFIED SOLUTION
Avatar of phoffric
phoffric

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
>> when first characters are same which one we should return?
I am not sure what you mean by "which one we should return".
After a swap (as a result of Step 1), we do not return from the function until all the required swaps are made.
Step 2 explains when you are not allowed to swap.

Once all required swaps are made, we do not return an entire array of String. That is why I am unclear about what you mean by "which one".

For problems like this, where we have specific input of arrays and the answer. I struggle to do the problem by hand in order to reach the same provided answer.

To make sure we are on the same page, in general, if given a non-empty set of strings, do you know the relationship between the length of the input array and the length of the output array? I only ask because I do not understand what you meant: "which one we should return"
Avatar of gudii9

ASKER

Definition: We'll say that 2 strings "match" if they are non-empty and their first chars are the same.

if say 2 strings match according to above definition of first character same then what are we supposed to return? not clear on that? we are not returning boolean though? we are doing some manipulation of input data right that part i am not clear
>>  we are not returning boolean though?
True, we are not returning a Boolean. The link actually helps out in the question wording by providing you with the API:
public String[] firstSwap(String[] strings) {

Open in new window

You have an input array and also return an array.

>> if say 2 strings match according to above definition of first character same then what are we supposed to return?
If you have an array of 100 strings, and the first string matches some other string, we are not supposed to return anything at that point, because the instructions say to loop over the entire array.

Algorithm:
 Loop over and then return the given array of non-empty strings as follows:
 1) if a string matches an earlier string in the array, swap the 2 strings in the array.
 2) A particular first char can only cause 1 swap
    (Clarification: once a char has caused a swap, its later swaps are disabled.)

You have to manipulate the entire array internally before returning something.
The array might change sometimes in the body of the loop.

["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]
On the first pass of the loop, what do you think this array will look like?
Avatar of gudii9

ASKER

If you have an array of 100 strings, and the first string matches some other string, we are not supposed to return anything at that point, because the instructions say to loop over the entire array.

Algorithm:
 Loop over and then return the given array of non-empty strings as follows:
 1) if a string matches an earlier string in the array, swap the 2 strings in the array.
 2) A particular first char can only cause 1 swap
    (Clarification: once a char has caused a swap, its later swaps are disabled.)
firstSwap(["ab", "ac"]) → ["ac", "ab"]//ac string matches an earlier string ab first character so swap two string to return ["ac", "ab"]??which make sense
Avatar of gudii9

ASKER

firstSwap(["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]) → ["ay", "by", "cy", "cx", "bx", "ax", "aaa", "azz"]
here how to swap?i see ax then there is ay so swap ax with ay
bx and by there so swap tem too

then cs cy so swap them too..
then there is aaa and aaaa so swap them too
then azz and azz so swa them too to result
 ["ay", "by", "cy", "cx", "bx", "ax", "aaa", "azz"]

i think i got it
Avatar of gudii9

ASKER

firstSwap(["ax", "bx", "ay", "by", "ai", "aj", "bx", "by"]) → ["ay", "by", "ax", "bx", "ai", "aj", "bx", "by"]

if more than one string matches with first character what we do? how to swap? swap first with last matching???
Avatar of gudii9

ASKER

2) A particular first char can only cause 1 swap
    (Clarification: once a char has caused a swap, its later swaps are disabled.)

ok you explained that too..
Avatar of gudii9

ASKER

let me think
>> then there is aaa and aaaa so swap them too
I don't see aaaa.

>> then azz and azz so swa them too to result
azz and azz
I do not see two azz.

Let's try this. Put out the starting array:
["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]
but do not include the  → followed by the answer. Answers are confusing because they may include many steps. (You have to think big - these problems are setups for 100's or 1000's or M's of strings in the array.)

Then, just looking at the first string, "ax", show the array with just one swap (as you have described). Don't look ahead at "bx" yet because that hurts trying to find the algorithm. There is a natural tendency for the eye to scan and come up with a solution. Instead, think of 1000's of strings to prevent this tendency from occurring. With large arrays, we can't remember the 1000's of strings, so when attempting this problem by hand, you need to take a one step at a time approach.

You can have a set of arrays under each other, and you can make bold the change from one array to the next.

BTW, when I tried some algorithms, I did it by hand, sometimes putting a deck of cards on the table and working it one step at a time until I established a pattern. Forget the computer and the programming. Try to do this by hand and work out what pattern you use to get to a final array.
Avatar of gudii9

ASKER

>> then there is aaa and aaaa so swap them too
I don't see aaaa.

sorry i mean

>> then there is aaa and aaa so swap them too
may be no need of swap as same strings right?
>> then there is aaa and aaa so swap them too
I do not see two aaa either. Are you looking at both the starting array and final solution array?
In any case, just put down the starting array, and directly underneath it put down the new array from the very first swap, ignoring other potential swaps.
I may not have been clear enough in the approach to take to understand the description.

Let's try this. First show the starting array:
["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]

// 1st string is "ax"; look for another string beginning with "a"
["ay", "bx", "cx", "cy", "by", "ax", "aaa", "azz"]

//  found "ay" so swap it with "ax"; 2nd string is "bx"
["ay", "by", "cx", "cy", "bx", "ax", "aaa", "azz"]

//  found "by" so swap it with "bx"; 3rd string is "cx"
["ay", "by", "cy", "cx", "bx", "ax", "aaa", "azz"]

//  found "cy" so swap it with "cx"; 4th string is "cx"

Try to take a stab at the next step(s). And don't worry at first about "Using a map, this can be solved making just one pass over the array. More difficult than it looks." First, as you point out, understanding the question is paramount to answer the challenge.
Avatar of gudii9

ASKER

public class FirstSwap {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("hi is---->"+firstSwap("ab", "ac"]));

	}
	public String[] firstSwap(String[] strings) {
		   
		  Map<String, Integer> map = new HashMap<String, Integer>();
		     
		  for (int i = 0; i < strings.length; i++) {
		     
		    String key = String.valueOf(strings[i].charAt(0));
		     
		    if (map.containsKey(key)) {
		       
		      int val = map.get(key);
		      if (val == -1) {
		        continue;
		      }
		       
		      // swap
		      int    pos   = map.get(key); 
		      String tmp   = strings[pos];
		      strings[pos] = strings[i];
		      strings[i]   = tmp ;
		       
		      // set a flag
		      map.put(key, -1);
		       
		    } else {
		      map.put(key, i);
		    }
		     
		  }
		   
		  return strings;
		}
}

Open in new window


how to write the java class to debug in eclipse?


public class FirstSwap {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("hi is---->"+firstSwap("ab", "ac"]));

	}
	public String[] firstSwap(String[] strings) {
		   
		  Map<String, Integer> map = new HashMap<String, Integer>();
		     
		  for (int i = 0; i < strings.length; i++) {
		     
		    String key = String.valueOf(strings[i].charAt(0));
		     
		    if (map.containsKey(key)) {
		       
		      int val = map.get(key);
		      if (val == -1) {
		        continue;
		      }
		       
		      // swap
		      int    pos   = map.get(key); 
		      String tmp   = strings[pos];
		      strings[pos] = strings[i];
		      strings[i]   = tmp ;
		       
		      // set a flag
		      map.put(key, -1);
		       
		    } else {
		      map.put(key, i);
		    }
		     
		  }
		   
		  return strings;
		}
}

Open in new window

Avatar of gudii9

ASKER

import java.util.HashMap;
import java.util.Map;

public class FirstSwap {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// String[] myFirstStringArray = new String[]{"String 1", "String 2", "String 3"};
		String[] st=new String[]{"ab","ac"};
		System.out.println("hi output is---->"+firstSwap(st));

	}
	public static String[] firstSwap(String[] strings) {
		   
		  Map<String, Integer> map = new HashMap<String, Integer>();
		     
		  for (int i = 0; i < strings.length; i++) {
		     
		    String key = String.valueOf(strings[i].charAt(0));
		     
		    if (map.containsKey(key)) {
		       
		      int val = map.get(key);
		      if (val == -1) {
		        continue;
		      }
		       
		      // swap
		      int    pos   = map.get(key); 
		      String tmp   = strings[pos];
		      strings[pos] = strings[i];
		      strings[i]   = tmp ;
		       
		      // set a flag
		      map.put(key, -1);
		       
		    } else {
		      map.put(key, i);
		    }
		     
		  }
		   
		  return strings;
		}
}

Open in new window


above gave below output

hi is---->[Ljava.lang.String;@15db9742



how to see meaningful output?
Avatar of gudii9

ASKER

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FirstSwap {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// String[] myFirstStringArray = new String[]{"String 1", "String 2", "String 3"};
		String[] st=new String[]{"ab","ac"};
		System.out.println("hi output is---->"+(Arrays.toString(firstSwap(st))));
		
	/*	 //Prior to Java 8
	    System.out.println(Arrays.toString(intArray));
	    System.out.println(Arrays.toString(strArray));

	    // In Java 8 we have lambda expressions
	    Arrays.stream(intArray).forEach(System.out::println);*/

	}
	public static String[] firstSwap(String[] strings) {
		   
		  Map<String, Integer> map = new HashMap<String, Integer>();
		     
		  for (int i = 0; i < strings.length; i++) {
		     
		    String key = String.valueOf(strings[i].charAt(0));
		     
		    if (map.containsKey(key)) {
		       
		      int val = map.get(key);
		      if (val == -1) {
		        continue;
		      }
		       
		      // swap
		      int    pos   = map.get(key); 
		      String tmp   = strings[pos];
		      strings[pos] = strings[i];
		      strings[i]   = tmp ;
		       
		      // set a flag
		      map.put(key, -1);
		       
		    } else {
		      map.put(key, i);
		    }
		     
		  }
		   
		  return strings;
		}
}

Open in new window


i got below
hi output is---->[ac, ab]
Avatar of gudii9

ASKER

i was wondering how to print the map
Avatar of gudii9

ASKER

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class FirstSwap {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// String[] myFirstStringArray = new String[]{"String 1", "String 2", "String 3"};
		String[] st=new String[]{"ab","ac"};
		System.out.println("hi output is---->"+(Arrays.toString(firstSwap(st))));
		
	/*	 //Prior to Java 8
	    System.out.println(Arrays.toString(intArray));
	    System.out.println(Arrays.toString(strArray));

	    // In Java 8 we have lambda expressions
	    Arrays.stream(intArray).forEach(System.out::println);*/

	}
	public static String[] firstSwap(String[] strings) {
		   
		  Map<String, Integer> map = new HashMap<String, Integer>();
		  
		    Set set = map.entrySet();
		      Iterator iterator = set.iterator();
		      while(iterator.hasNext()) {
		         Map.Entry mentry = (Map.Entry)iterator.next();
		         System.out.print("key is: "+ mentry.getKey() + " & Value is: ");
		         System.out.println(mentry.getValue());
		      }
		     
		  for (int i = 0; i < strings.length; i++) {
		     
		    String key = String.valueOf(strings[i].charAt(0));
		     
		    if (map.containsKey(key)) {
		       
		      int val = map.get(key);
		      if (val == -1) {
		        continue;
		      }
		       
		      // swap
		      int    pos   = map.get(key); 
		      String tmp   = strings[pos];
		      strings[pos] = strings[i];
		      strings[i]   = tmp ;
		       
		      // set a flag
		      map.put(key, -1);
		       
		    } else {
		      map.put(key, i);
		    }
		     
		  }
		   
		  return strings;
		}
}

Open in new window


above did not print map