Solved

NotAlone Challenge

Posted on 2016-08-14
20
70 Views
Last Modified: 2016-08-16
Hi,

I am working on below challenge
http://codingbat.com/prob/p169506

Psuedo code approach of logic

1. Iterate through given array starting element at index 1 till penultimate element.
2.if following element more than previous element assign current element with following element
3.if following element less than previous element assign current element with previous element
4. return array
I wrote my code as below

public int[] notAlone(int[] nums, int val) {
  for(int i=1;i<nums.length-1;i++){
    if(nums[i-1]<nums[i+1]){
      nums[i]=nums[i+1];
    }
    else 
    nums[i]=nums[i-1];
    
  }
  return nums;
}

Open in new window




I am failing couple of tests
Expected      Run            
notAlone([1, 2, 3], 2) → [1, 3, 3]      [1, 3, 3]      OK      
notAlone([1, 2, 3, 2, 5, 2], 2) → [1, 3, 3, 5, 5, 2]      [1, 3, 3, 5, 5, 2]      OK      
notAlone([3, 4], 3) → [3, 4]      [3, 4]      OK      
notAlone([3, 3], 3) → [3, 3]      [3, 3]      OK      
notAlone([1, 3, 1, 2], 1) → [1, 3, 3, 2]      [1, 1, 2, 2]      X      
notAlone([3], 3) → [3]      [3]      OK      
notAlone([], 3) → []      []      OK      
notAlone([7, 1, 6], 1) → [7, 7, 6]      [7, 7, 6]      OK      
notAlone([1, 1, 1], 1) → [1, 1, 1]      [1, 1, 1]      OK      
notAlone([1, 1, 1, 2], 1) → [1, 1, 1, 2]      [1, 1, 2, 2]      X      
other tests
X

How to improve my design, approach, code? please advise
0
Comment
Question by:gudii9
  • 7
  • 6
  • 5
  • +1
20 Comments
 
LVL 26

Assisted Solution

by:dpearson
dpearson earned 250 total points
ID: 41755785
This is the first time I've read a codingbat problem and I'm not clear on what they're asking for.

It seems to me this should be the solution:

public int[] notAlone(int[] nums, int val) {
  int[] result = new int[nums.length] ;
  
  for (int i = 0 ; i < nums.length ; i++) {
    boolean isAlone = (i > 0 && i < nums.length-1) && (nums[i-1] != nums[i]) && (nums[i+1] != nums[i]) ;
    int value = isAlone ? Math.max(nums[i-1], nums[i+1]) : nums[i] ;
    result[i] = value ;
  }
  
  return result ;
}

Open in new window


But this code passes all the tests:

public int[] notAlone(int[] nums, int val) {
  int[] result = new int[nums.length] ;
  
  for (int i = 0 ; i < nums.length ; i++) {
    boolean isAlone = (i > 0 && i < nums.length-1) && (nums[i-1] != nums[i]) && (nums[i+1] != nums[i]) ;
    int value = isAlone ? Math.max(nums[i-1], nums[i+1]) : nums[i] ;
    result[i] = Math.max(nums[i],value) ;    // This line is different
  }
  
  return result ;
}

Open in new window


And just like in your solution, I don't use the "val" parameter passed in.  Which in itself is very odd.

I hope you can see how this translates from the way the problem is described into code - each step of the problem is one line inside the loop.

Your solution is  modifying the array as it goes, which also may be fine but does change the problem (if you start with 1,2,3 and modify "1" to become "5" (e.g.) then when you test "2" its neighbors will be 5,3 instead of 1,3).
 
It's hard for me to give you advice since I don't really understand why their test answers are correct.  I must be misreading their problem statement somehow.

I'd like to see what other experts think of this and what's going on here :)

Doug
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 41756142
@Doug

notAlone([1, 2, 3, 2, 5, 2], 2) → [1, 3, 3, 5, 5, 2]

So if you take this (their) example, you look for 2, it's not at the end or beginning of the array, so it's a valid candidate, so then you replace it with the larger of 1 or 3, i.e. 3 so now you have 1,3,3 for that part of the array, now look for 2 again, (which is at index pos 3) and replace it with the largest of 3 and 5, which is 5, so now we have 1,3,3,5 and another 5, making 1,3,3,5,5 (after the next search for a 2), and then do the final search for a 2, (which I just mentioned), which is at the end of the array, so it is not replaced this time, making 1,3,3,5,5,2.
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41756361
to add to above comment:

So if you take this (their) example, you look for 2

@Doug
you said 'I don't use the "val" parameter passed in.' but exactly this is the crucial point of the challenge.

if you look only for one number, two consecutive items with that number either could be neighbors or one or both are alone (beside of the ends). because of that you don't need to use a separate  result array but could replace the 'alone' items inplace since the modification of the current array item doesn't change the problem.

pseudocode:

for index := 1 to (num_items - 2)  step 1
do
      previous := item[index-1]
      current   := item[index]
      next := item[index+1]     
      if current == val and current <> previous and current <> next 
      then
            item[index] := maximum(previous, next)
            // skip next step
            index := index+1
      end if
end for

Open in new window


Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41756435
public int[] notAlone(int[] nums, int val) {
  for(int i=1;i<nums.length-1;i++){
    if(nums[i-1]<nums[i+1]){
      nums[i]=nums[i+1];
    }
    else 
    nums[i]=nums[i-1];
    
  }
  return nums;
}

Open in new window


with above approach why i am failing only two tests and passing mst of the tests

notAlone([1, 3, 1, 2], 1) → [1, 3, 3, 2]      [1, 1, 2, 2]      X
notAlone([1, 1, 1, 2], 1) → [1, 1, 1, 2]      [1, 1, 2, 2]      X

How to tweak my code to pass those two tests also?
0
 
LVL 32

Accepted Solution

by:
sarabande earned 250 total points
ID: 41756624
you didn't check for val is equal to current

you didn't check that both previous and next are different to current

you didn't take maximum of previous or next for update

Sara
0
 
LVL 26

Expert Comment

by:dpearson
ID: 41757369
@krakatoa

You're right that if we assume that you should be modifying the array as you go then we get this case:
notAlone([1, 2, 3, 2, 5, 2], 2) → [1, 3, 3, 5, 5, 2]

But then this one seems wrong:
notAlone([1, 3, 1, 2], 1) → [1, 3, 3, 2]

because when we reach "3" it seems to me this is "alone" with neighbors 1 and 1, so it should become 1, so if we modify as we go, we'd get "1,1,2,2" not "1,3,3,2".

Strange stuff ;)

Doug
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 41757471
because when we reach "3"

Well no, because we are looking for 1, not 3. 1 is the val. When found, in this case, it changes to a 3.
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 41757662
You can re-phrase the challenge, (or, rather, re-phrase the algorithm needed to) :


Whenever you find 'val' in the array - provided it is NOT at the beginning NOR the end of the array - then replace it with the largest of its two immediate neighbours.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41758095
public int[] notAlone(int[] nums, int val) {
  //int val=0;
  for(int i=1;i<nums.length-1;i++){
  
    if(nums[i]==val&&(nums[i-1]<nums[i+1])){
      nums[i]=nums[i+1];
    }
    else if(nums[i]==val&&(nums[i-1]>nums[i+1])){
    nums[i]=nums[i-1];
    } 
     else if(nums[i]==val&&(nums[i-1]==nums[i+1])){
    nums[i]=nums[i];
    }
  }
  return nums;
}

//you didn't check for val is equal to current 

//you didn't check that both previous and next are different to current

//you didn't take maximum of previous or next for update

Open in new window



Expected      Run            
notAlone([1, 2, 3], 2) → [1, 3, 3]      [1, 3, 3]      OK      
notAlone([1, 2, 3, 2, 5, 2], 2) → [1, 3, 3, 5, 5, 2]      [1, 3, 3, 5, 5, 2]      OK      
notAlone([3, 4], 3) → [3, 4]      [3, 4]      OK      
notAlone([3, 3], 3) → [3, 3]      [3, 3]      OK      
notAlone([1, 3, 1, 2], 1) → [1, 3, 3, 2]      [1, 3, 3, 2]      OK      
notAlone([3], 3) → [3]      [3]      OK      
notAlone([], 3) → []      []      OK      
notAlone([7, 1, 6], 1) → [7, 7, 6]      [7, 7, 6]      OK      
notAlone([1, 1, 1], 1) → [1, 1, 1]      [1, 1, 1]      OK      
notAlone([1, 1, 1, 2], 1) → [1, 1, 1, 2]      [1, 1, 2, 2]      X      
other tests
OK
i passed one other test but failing last one. please advise
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41758175
&&(nums[i-1]<nums[i+1])
in the original challenge they defined 'an item is alone' as 'current item is different to previous item and is different to next  item'. you check whether the previous is less than the next, what is not the same.

   if(nums[ i ]==val&&(nums[i-1]<nums[i+1])){
      nums[ i ]=nums[i+1];
    }
    else if(nums[ i ]==val&&(nums[i-1]>nums[i+1])){
    nums[ i ]=nums[i-1];
    }
     else if(nums[ i ]==val&&(nums[i-1]==nums[i+1])){
    nums[ i ]=nums[ i ];
    }

you check for 'nums[ i ]==val' 3 times in all if and else if conditions. it would be easier if you were nesting the if statements.

// outer condition
if (nums[ i ] == val)
{
       // inner condition
       if (...)
       {
            ...

Open in new window


the if condition to check whether both previous and next are different to current is

if (nums[ i ] != nums[i-1] && nums [ i ] != nums[i+1])

Open in new window


if the condition is true you would assign the maximum of previous and next to current. you could do that by using a maximum function (see 1st comment of DPearson) or by

if (nums[i-1] < nums[i+1])
{
      nums[ i ] = nums[i+1];
}
else
{
      nums[ i ] = nums[i-1];
}

Open in new window


note, if it comes to assignment both nums[i-1]  and nums[i+1] are different from val. therefore in the next loop cycle the new current nums[i+1] will not be 'alone' since the outer condition that it is equal to val would not apply.

Sara
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 16

Expert Comment

by:krakatoa
ID: 41758180
It's starting to look to me as if the implementation at the Coding bat site is wrong. I would have said that your code should pass all the tests, and the answer to the one that it fails on should be 1,1,2,2, which is what you've got.

Walking through the logic, bareback, I'd say for this case :
* find val (which is 1) starting at index 1
result = found at index 1
* get the largest value from the two adjacent
result = 1
* replace val with result
array snapshot = 1,1,1,2
* find next val
result = found at index 2
* get the largest value from the two adjacent
result = 2
*replace val with result
array snapshot = 1,1,2,2
*find next val
result = no more vals
end.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41758227
public int[] notAlone(int[] nums, int val) {
  //int val=0;
  for(int i=1;i<nums.length-1;i++){
  
    if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]&&nums[i]==val&&(nums[i-1]<nums[i+1])){
      nums[i]=nums[i+1];
    }
    else if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]&&nums[i]==val&&(nums[i-1]>nums[i+1])){
    nums[i]=nums[i-1];
    } 
     else if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]&&nums[i]==val&&(nums[i-1]==nums[i+1])){
    nums[i]=nums[i];
    }
  }
  return nums;
}

//you didn't check for val is equal to current 

//you didn't check that both previous and next are different to current

//you didn't take maximum of previous or next for update

Open in new window


i see i have to do only for alone element. now i am passing all tests
Expected	Run		
notAlone([1, 2, 3], 2) → [1, 3, 3]	[1, 3, 3]	OK	
notAlone([1, 2, 3, 2, 5, 2], 2) → [1, 3, 3, 5, 5, 2]	[1, 3, 3, 5, 5, 2]	OK	
notAlone([3, 4], 3) → [3, 4]	[3, 4]	OK	
notAlone([3, 3], 3) → [3, 3]	[3, 3]	OK	
notAlone([1, 3, 1, 2], 1) → [1, 3, 3, 2]	[1, 3, 3, 2]	OK	
notAlone([3], 3) → [3]	[3]	OK	
notAlone([], 3) → []	[]	OK	
notAlone([7, 1, 6], 1) → [7, 7, 6]	[7, 7, 6]	OK	
notAlone([1, 1, 1], 1) → [1, 1, 1]	[1, 1, 1]	OK	
notAlone([1, 1, 1, 2], 1) → [1, 1, 1, 2]	[1, 1, 1, 2]	OK	
other tests
OK

Open in new window


how to refine and refactor my code?
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41758234
* get the largest value from the two adjacent
that is the 3rd condition. the 2nd condition was that the current item is 'alone' what is not the case as the previous item is 1.

so, the challenge for [1, 1, 1, 2], 1)  rightly doesn't change the sequence because none of the '1' items is 'alone'.

Sara
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 41758239
ok - I see - what the question asks for is that BOTH numbers before and after val are different. That's not so clearly worded I dont think.
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 41758253
if there are values before and after it,

This part is very badly phrased : unless the array is short, there are going to always be values "before and after it".
0
 
LVL 7

Author Comment

by:gudii9
ID: 41758260
import java.util.Arrays;

public class NotAlone {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] ar = { 1, 2, 3 };
		System.out.println("value==>" + Arrays.toString(notAlone(ar, 2)));

	}

	public static int[] notAlone(int[] nums, int val) {
		// int val=0;
		for (int i = 1; i < nums.length - 1; i++) {

			if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
				if (nums[i] == val) {
					if (nums[i - 1] < nums[i + 1]) {
						nums[i] = nums[i + 1];
					} else if (nums[i - 1] > nums[i + 1]) {
						nums[i] = nums[i - 1];
					} else if (nums[i - 1] == nums[i + 1]) {
						nums[i] = nums[i];
					}
				}
			}
			// return nums;
		}
		return nums;

		// you didn't check for val is equal to current

		// you didn't check that both previous and next are different to current

		// you didn't take maximum of previous or next for update

	}
}

Open in new window

i refactored
value==>[1, 3, 3]


public int[] notAlone(int[] nums, int val) {
  


		// int val=0;
		for (int i = 1; i < nums.length - 1; i++) {

			if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
				if (nums[i] == val) {
					if (nums[i - 1] < nums[i + 1]) {
						nums[i] = nums[i + 1];
					} else if (nums[i - 1] > nums[i + 1]) {
						nums[i] = nums[i - 1];
					} else if (nums[i - 1] == nums[i + 1]) {
						nums[i] = nums[i];
					}
				}
			}
			// return nums;
		}
		return nums;

}

		// you didn't check that both previous and next are different to current

		// you didn't take maximum of previous or next for update

	

Open in new window



Expected      Run            
evenOdd([1, 0, 1, 0, 0, 1, 1]) → [0, 0, 0, 1, 1, 1, 1]      [1, 0, 1, 0, 0, 1, 1]      X      
evenOdd([3, 3, 2]) → [2, 3, 3]      [3, 3, 2]      X      
evenOdd([2, 2, 2]) → [2, 2, 2]      [2, 2, 2]      OK      
evenOdd([3, 2, 2]) → [2, 2, 3]      [3, 2, 2]      X      
evenOdd([1, 1, 0, 1, 0]) → [0, 0, 1, 1, 1]      [1, 1, 0, 1, 0]      X      
evenOdd([1]) → [1]      [1]      OK      
evenOdd([1, 2]) → [2, 1]      [1, 2]      X      
evenOdd([2, 1]) → [2, 1]      [2, 1]      OK      
evenOdd([]) → []      []      OK      
other tests
X      
Your progress graph for this problem

0
 
LVL 32

Expert Comment

by:sarabande
ID: 41758262
how to refine and refactor my code?

you can drop the last else if block since it doesn't change anything.


as already told you can put the check whether nums[ i ] is equal to val into an outer if block and remove this condition from inner if statements.

then you can add a first inner if block where you check that both neighbors were different. and finally you have a most inner block where you check whether the left or the right neighbor is larger.

finally you have (pseudo code)

for each item from nums[1] to nums[len-2]
do
     if item equals val 
     then
            if previous not equals item and next not equals item
            then
                    if previous is less than next
                    then
                           item = next
                    else // if previous is greater or equal to next
                          item = previous 
                    end if
             end if
       end if
end for

Open in new window


Sara
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41758267
This part is very badly phrased : unless the array is short, there are going to always be values "before and after it".

yes, i assume they wanted to make clear that both the ends 'never are alone' regardless of their neighbors.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41758306
as already told you can put the check whether nums[ i ] is equal to val into an outer if block and remove this condition from inner if statements.

then you can add a first inner if block where you check that both neighbors were different. and finally you have a most inner block where you check whether the left or the right neighbor is larger.

i thought i did the same with 3 nested if loops inside for loop as below?
for (int i = 1; i < nums.length - 1; i++) {

			if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
				if (nums[i] == val) {
					if (nums[i - 1] < nums[i + 1]) {
						nums[i] = nums[i + 1];

Open in new window


psedu code of logica approach is:
1.loop through given array.
2.VErify the given array elemnt is not equal to prvious or after value
3. if above step true then verify larger among previous and after value
4. return largest of above 2.
5. if equal return same value
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41758560
the most outer condition is that current item is equal to val.

you may change the conditions without going wrong but without doubt the first criterium to check is that the current item has the right value since it is the precondition request by the caller.

nevertheless your solution is also valid.

Sara
0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now