** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** - Page 419 - Computer Technical Help

Two Plus Two Forums Other Topics Computer and Technical Help

** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Post Reply Subscribe

...

Page 419 of 1603

First

219 319 369 399 409 414 415 416 417 418 419 420 421 422 423 424 429 439 469 519 619 919 1419

Last

Page 419 of 1603

First

219 319 369 399 409 414 415 416 417 418 419 420 421 422 423 424 429 439 469 519 619 919 1419

Last

10-08-2013 , 01:21 AM

#10451

clowntable

Carpal \'Tunnel

Join Date: Jun 2006 Posts: 45,557

Oh lol I thought you were talking about low end cheap stuff (thus the <200$ Asus)...somehow had Chromebook in that bin

Quote

10-08-2013 , 09:51 PM

#10452

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Didn't know there was a <$200 Asus (certainly isn't one in America?).

I was considering going for a cheap one for meetups and stuff, but now I'm not so sure.

Quote

10-09-2013 , 05:17 AM

#10453

DirtySprite

adept

Join Date: Jun 2012 Posts: 755

Can someone help me with this java code i'm trying to write for my programming class. I'm supposed to write a method that takes in an array of integers and counts how many different numbers appear more than once.
Example given is for the input { 1; 1; 1; 2; 4; 4; 5; 6; 6 } the answer would be 3 because three different numbers (1,4,6) appear more than once.

The code I've written so far is:

Code:

public static int checkRepetition(int[] a)
	{
		int repetitionCount = 0;
	
		for(int i=0; i<a.length; i++)
		{
			for(int j=0; j<i; j++)
			{
				if(a[i] == a[j]) 
				{						
					repetitionCount++;	
				}
			}			
		}		
		return repetitionCount;	
	}

As you can see what I'm doing here is for every element in a[] I'm checking if any previous element has the same value as a[i].
What this does though is counts every repetition so that if any same integer appears 3 times in the array then it will be counted as two repetitions, which isn't what I want to do, since I only wanna count how many integers appear more than once (doesn't matter if an integer appears twice, three times, ... it should still only add 1 to my repetitionCount.

Hope the question is clear and if this isn't the right thread for this I apologize

Quote

10-09-2013 , 06:20 AM

#10454

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

To do it your way, you 'd need to create a separate array that kept track of numbers that you'd previously marked are repeats. Then you'd just skip past any number that was already on your list.

A better and more scalable approach would be to sort the array first. Then you just start with the first elm, and move down the line. If at any point the current elm equals the previous one, you'd add 1 to your repetition count and then keep advancing down the line (ignoring elms) until the elment changed again. When you did, you would return to searching for two in a row that were the same. This may be too advanced for your current assignment, though, I don't know.

EDIT:

Though this clearly isn't the point of your exercise, it's worth noting that in ruby the solution is:

Code:

arr.count - arr.uniq.count

And here's the gross java analog:

Code:

int uniqueCount = new HashSet<Integer>(Arrays.asList(arr)).size();
int numRepeats = arr.length - uniqueCount

Last edited by gaming_mouse; 10-09-2013 at 06:29 AM.

Quote

10-09-2013 , 06:23 AM

#10455

jtollison78

grinder

Join Date: Aug 2004 Posts: 502

Quote:

Originally Posted by DirtySprite

Off thee top of my head couldn't you record the "number" and a "mark" (=false initially) as to whether it's been "counted"? Then you walk the array once, either counting a duplicate, resetting the number/mark, or ignoring the position.

edit: just saw gaming_mouse's answer. I was assuming your array was sorted, or at least you could do this easily (higher level languages spoil you with these sorts things coming in a single built in command)

Quote

10-09-2013 , 06:29 AM

#10456

Gullanian

Carpal \'Tunnel

Join Date: Dec 2006 Posts: 14,014

There's a lot of different ways of doing this, these questions can be important for a good solution:

- Is the given array sorted?
- What's the range of numbers that can appear? 0 - 6 or 0 to int.Max?
- How many integers are you ever expected to test?

For a sorted array, simply loop each item and increment counter if there's more than one instance.

For an unsorted short array, sort first

For an unsorted long (very long) array with a limited range, iterate each element and increment an array keeping count of each occurrence

For an unsorted long (very long) array with a very large range the above solutions might be quite slow or require a lot of memory, (depends on if efficiency is an issue or not). For this there's a bunch of more creative solutions you might be able to do but I imagine this is outside the scope of the assignment.

Last edited by Gullanian; 10-09-2013 at 06:36 AM.

Quote

10-09-2013 , 07:04 AM

#10457

DirtySprite

adept

Join Date: Jun 2012 Posts: 755

The array is sorted, I should have pointed that out but I didn't realize it untill now.

Trying to solve this now,
theoretically could I simply check if an element i is the same as element i-1 (the previous element), and do count++;
but first i'd check if the element i is the same as element i-2, in which case I'd skip over to the next element because if a[i] == a[i-2] then it must have been already counted as a duplicate?

Quote

10-09-2013 , 07:13 AM

#10458

DirtySprite

adept

Join Date: Jun 2012 Posts: 755

This is what I have right now. The code works and gives the right answer but it probably could be more practical.
I compare the 1st and 2nd element in the array separately, because in the for loop I compare a[i] with a[i-2] and therefore need to start at the 3rd array to avoid going out of bounds

Code:

	public static int checkRepetition(int[] a)
	{
		int repetitionCount = 0;
		
		if(a[1] == a[0]) repetitionCount++;
	
		for(int i=2; i<a.length; i++)
		{
			if(a[i] != a[i-2])
			{
			
				if(a[i] == a[i-1]) 
				{						
					repetitionCount++;					
				}
			}
		}	
		return repetitionCount;		
	}

Quote

10-09-2013 , 07:25 AM

#10459

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

instead of nested if statment, use an && to combine them.

Quote

10-09-2013 , 07:27 AM

#10460

kerowo

lolcat

Join Date: Nov 2005 Posts: 37,190

Who would have thought an old COBOL gem would show up in this thread? You're writing a control break program. Load your control element, the first number in the array and count how many are there until it changes, or breaks. On the break you finish whatever you were doing (counting occurrences, doing something if it is greater than 1), re-load the control element with the next new number and start the process over.

It is literally the only pattern I know!

Quote

10-09-2013 , 07:33 AM

#10461

DirtySprite

adept

Join Date: Jun 2012 Posts: 755

Thank you.

Is it okay to separately check if a[1] == a[0] is true and then start the for loop at i=2?
It seems to me like it should be possible to write a prettier code that doesn't have to compare the first two elements separately, but maybe I'm wrong

Quote

10-09-2013 , 07:34 AM

#10462

kerowo

lolcat

Join Date: Nov 2005 Posts: 37,190

You can't assume there isn't a break on the first item in the list. You should write the code without making any assumptions about the data.

Quote

10-09-2013 , 07:36 AM

#10463

DirtySprite

adept

Join Date: Jun 2012 Posts: 755

My post was a reply to gaming_mouse btw

trying to digest what you're saying kerowo..

Quote

10-09-2013 , 07:41 AM

#10464

kerowo

lolcat

Join Date: Nov 2005 Posts: 37,190

It still holds.

Quote

10-09-2013 , 07:49 AM

#10465

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

i don't see a way to avoid it (or some other exceptional case check at the beginning or end of the array).

Quote

10-09-2013 , 07:52 AM

#10466

Gullanian

Carpal \'Tunnel

Join Date: Dec 2006 Posts: 14,014

Code:

if(a[1] == a[0]) repetitionCount++;

Is no good if the array passed in only holds one element, it will crash.

I'd probably approach it this sort of way:

Code:

if(a.length <= 1) return 0;

int repetitionCount = 0;
int lastValue = a[0];
bool accountedFor = false;

for(int i=1; i<a.length; i++){

  if(!accountedFor && a[i] == lastValue)
  {
      repetitionCount ++;
      accountedFor = true;
  }

  if(lastValue != a[i])
  {
      lastValue = a[i];
      accountedFor = false;
  }
}

return reptitionCount;

I feel ill today so my brain isn't working too well so that might not work, but you get the gist

In the second if block, you could also throw a `InvalidArrayFormat` type exception if a[i] < lastValue as this implies that the given array is not in an ordered format which is expected.

Last edited by Gullanian; 10-09-2013 at 08:01 AM.

Quote

10-09-2013 , 08:11 AM

#10467

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Quote:

Originally Posted by Gullanian

Code:

if(a[1] == a[0]) repetitionCount++;

Is no good if the array passed in only holds one element, it will crash.

good catch.

but your solution is too complicated for my taste. i'd rather handle the 1 element case with a simple guard clause that returns immediately.[/QUOTE]

Quote

10-09-2013 , 08:19 AM

#10468

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Here's a version with the guard clause that makes the code intent more clear as well:

Code:

public static int checkRepetition(int[] a)
{
    if (a.length <= 1) return 0;

    int repetitionCount = 0;
    if (a[1] == a[0]) repetitionCount++;

    for(int i=2; i<a.length; i++)
    {
        boolean notAlreadyCounted = a[i] != a[i-2];
        boolean sameAsLast = a[i] == a[i-1];
        if (sameAsLast && notAlreadyCounted)
            repetitionCount++;					
    }	
    return repetitionCount;		
}

Oh and also your method shoudl be called "countRepititions" not "checkRepitition" -- accurate names really do matter.

Last edited by gaming_mouse; 10-09-2013 at 08:24 AM. Reason: correction

Quote

10-09-2013 , 08:31 AM

#10469

Gullanian

Carpal \'Tunnel

Join Date: Dec 2006 Posts: 14,014

Looks good, but if the array has 2 elements a[0] and a[1], the first line of the loop will crash when it checks for a[2] Edit: perhaps not sorry! Guess the loop wont start?

Also what are peoples thoughts on throwing an UnsortedArrayException if a[i] < a[i-1]?

Quote

10-09-2013 , 08:35 AM

#10470

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

yeah i didnt test it but i think the loop gets skipped

to answer your other question, it depends on who the clients of the library will be, but in general i would avoid it like the plague.

Quote

10-09-2013 , 02:42 PM

#10471

clowntable

Carpal \'Tunnel

Join Date: Jun 2006 Posts: 45,557

Better problem than FizzBuzz for job interviews imo

Quote

10-09-2013 , 06:55 PM

#10472

jjshabado

Carpal Tunnel

Join Date: Jul 2006 Posts: 22,732

We ask a question very similar to that as part of our phone screen. Super useful.

Edit: Which brings me to a good interview tip - never assume the first question you're being asked is some crazy hard trick question requiring a gajillion data structures and a cutting edge machine learning algorithm.

Quote

10-09-2013 , 08:55 PM

#10473

DirtySprite

adept

Join Date: Jun 2012 Posts: 755

Thanks for the feedback guys didn't expect this much help. Might have to keep posting questions when I'm having trouble with my homework

Anyway my teacher had a solution which I think is a bit more elegant

Code:

public static int countTwo(int[] a) 
{
	int total = 0; 
	if (a.length <= 1) 
	{
		return 0;
	}
	int count = 1; 
	for(int i = 1; i < a.length; i++) 
	{
		if (a[i] == a[i-1]) 
		{
			count++;  
		} 
		else 
		{
			count=1; 
		}
		if (count == 2) 
		{
			total++; 
		}
	}
	return total;
}

Quote

10-09-2013 , 10:02 PM

#10474

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Wouldn't it be easier (perhaps faster?) if the structure was something like this (in pseudo-code 'cause I know no Java):

Code:

if array.length < 2: 
     return 0
else:
counter = 0
candidate = array[0]
array = array[1:]
while array.length > 0:
    if candidate = array[0]:
          counter += 1
          array = array[1:] until candidate != array[0]
          candidate = array[0]
    else: 
        array = array[1:]

I know there is probably a bug somewhere, but my first instinct is to start with that.

Is there any benefit to doing array comparisons over the same array over the above implementation?

Last edited by daveT; 10-09-2013 at 10:08 PM.

Quote

10-10-2013 , 12:00 AM

#10475

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

I don't think there's any convenient way to get array slices in Java

EDIT: oh, I just found it right after I posted:

http://stackoverflow.com/questions/1...-array-in-java

Doubt it's faster or even reasonably close b/c of all the copying overhead

Quote

Page 419 of 1603

First

219 319 369 399 409 414 415 416 417 418 419 420 421 422 423 424 429 439 469 519 619 919 1419

Last

Post Reply Subscribe

...

Page 419 of 1603

First

219 319 369 399 409 414 415 416 417 418 419 420 421 422 423 424 429 439 469 519 619 919 1419

Last