gudii9
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
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"]
Of the three examples, what exactly don't you understand?
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"]
not clear on above two outputs. how they came. when first characters are same which one we should return?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>> 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"
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"
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:
>> 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?
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) {
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?
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.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
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.)
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
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
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???
if more than one string matches with first character what we do? how to swap? swap first with last matching???
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..
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.
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.
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 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.
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.
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;
}
}
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;
}
}
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;
}
}
above gave below output
hi is---->[Ljava.lang.String;
how to see meaningful output?
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;
}
}
i got below
hi output is---->[ac, ab]
ASKER
i was wondering how to print the map
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;
}
}
above did not print map