Win a copy of Programmers Guide to Apache Thrift this week in the Open Source forum!

- Post Reply Bookmark Topic Watch Topic
- New Topic

programming forums
Java
Mobile
Certification
Databases
Caching
Books
Engineering
Micro Controllers
OS
Languages
Paradigms
IDEs
Build Tools
Frameworks
Application Servers
Open Source
This Site
Careers
Other
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Devaka Cooray
- Knute Snortum
- Paul Clapham
- Tim Cooke

Sheriffs:

- Liutauras Vilda
- Jeanne Boyarsky
- Bear Bibeault

Saloon Keepers:

- Tim Moores
- Stephan van Hulst
- Ron McLeod
- Piet Souris
- Frits Walraven

Bartenders:

- Ganesh Patekar
- Tim Holloway
- salvin francis

posted 1 week ago

Hello guys, i have a question about linked list i got for homework and i need your help:

i got these 2 classes:

now, i need to write a method in the IntListTwo class that gets an average int from the user, and returns true if there is a sub-list that it's average is equals to the given average. and false if not.

the method should look like this :

so i thought about the algorithm:

1. i will calculate the sum of all the list + count the number of numbers in the list.

2. i will calculate the average of the list ( sum/count)

3. if the average is bigger than the given average, i will subtract the last element from the sum and subtract 1 from the counting and take the last element of the list one step back.

3. if the average is smaller than the given average, i will subtract the first element from the sum and subtract 1 from the counting and take the first element of the list one step forward.

By the way- the list is sorted!

Now, when i have the algorithm im still struggling to write it,

would you help me ?

Thank you !

i got these 2 classes:

now, i need to write a method in the IntListTwo class that gets an average int from the user, and returns true if there is a sub-list that it's average is equals to the given average. and false if not.

the method should look like this :

so i thought about the algorithm:

1. i will calculate the sum of all the list + count the number of numbers in the list.

2. i will calculate the average of the list ( sum/count)

3. if the average is bigger than the given average, i will subtract the last element from the sum and subtract 1 from the counting and take the last element of the list one step back.

3. if the average is smaller than the given average, i will subtract the first element from the sum and subtract 1 from the counting and take the first element of the list one step forward.

By the way- the list is sorted!

Now, when i have the algorithm im still struggling to write it,

would you help me ?

Thank you !

posted 1 week ago

hi Rian,

are you sure that this is a Beginners item?

I like your algorithm, but my first thought is that you need to sort your list first. If it is unsorted, removing your last element might increase the calculated average. Alternatively, you could start with element 0, and maintain a running average, to which you can apply your algo. Might be a tad easier to implement. But these are my first two thoughts, Does this sublist need to contain only consecutive elements?

Edit: your edit about the list being sorted came just before my reply!

are you sure that this is a Beginners item?

I like your algorithm, but my first thought is that you need to sort your list first. If it is unsorted, removing your last element might increase the calculated average. Alternatively, you could start with element 0, and maintain a running average, to which you can apply your algo. Might be a tad easier to implement. But these are my first two thoughts, Does this sublist need to contain only consecutive elements?

Edit: your edit about the list being sorted came just before my reply!

Piet Souris

Saloon Keeper

Posts: 3250

128

posted 1 week ago

I would start by writing a method 'int removeLastNode()' and 'int removeFirstNode()' in your IntListTwo class. The return value is the value of the removed node.

posted 1 week ago

I would suggest starting with a method which takes an `IntListTwo` object and returns its average. Then you could use a method which takes an `IntListTwo` object and returns another `IntListTwo` object which is the input object with the tail node removed. And another method which does the same for head node.

rian bron

Ranch Hand

Posts: 117

posted 1 week ago

yes, i know this one , but i am struggling to write those 2 methods and basically those 2 methods are the answer plus some things around it but basically this is that answer.

can you show me how to write on of them and i will try to write the other one?

thank you

Piet Souris wrote:I would start by writing a method 'int removeLastNode()' and 'int removeFirstNode()' in your IntListTwo class. The return value is the value of the removed node.

yes, i know this one , but i am struggling to write those 2 methods and basically those 2 methods are the answer plus some things around it but basically this is that answer.

can you show me how to write on of them and i will try to write the other one?

thank you

posted 1 week ago

The `removeLastNode` method which Piet suggests will have to be a method of the `IntListTwo` class, of course. Now ask yourself "What information in the IntListTwo class would I have to change to remove its last node?" And then "How would I do that?" The latter question might involve drawing pictures which contain nodes linked together with arrows.

Piet Souris

Saloon Keeper

Posts: 3250

128

posted 1 week ago

hi Rian,

first of all: we must be careful not to make your homework for you. That could bring about all sorts of misery.

Second: I would first make a copy of your IntListTwo object. That is easy, you just need a new IntListTwo, with _head and _tail of your original. Then you can freely remove heads and tails, but alternatively you can do what Paul suggests and return a new List with altered heads or tails.

Suppose you want to remove _head. It means that the new _head will be the node referred to by _head.next (if present, it could be null if the list only contains a head and a tail). So, make a note of the heads value (that you can use as your return value). Now, all that is left to do is making _head.next your new _head. How would you do that? And analoguus for removing the _tail.

Edit: almost forgot: remember that _head.next has a previous field that refers to its predecessor. Now, what to do if this predecessor gets removed? Follow Pauls suggestion and draw some nodes with arrows in between them, so that it becomes clear what will happen to the arrows if a node gets eliminated.

first of all: we must be careful not to make your homework for you. That could bring about all sorts of misery.

Second: I would first make a copy of your IntListTwo object. That is easy, you just need a new IntListTwo, with _head and _tail of your original. Then you can freely remove heads and tails, but alternatively you can do what Paul suggests and return a new List with altered heads or tails.

Suppose you want to remove _head. It means that the new _head will be the node referred to by _head.next (if present, it could be null if the list only contains a head and a tail). So, make a note of the heads value (that you can use as your return value). Now, all that is left to do is making _head.next your new _head. How would you do that? And analoguus for removing the _tail.

Edit: almost forgot: remember that _head.next has a previous field that refers to its predecessor. Now, what to do if this predecessor gets removed? Follow Pauls suggestion and draw some nodes with arrows in between them, so that it becomes clear what will happen to the arrows if a node gets eliminated.

Piet Souris

Saloon Keeper

Posts: 3250

128

posted 1 week ago

Ajakkes.

It is more complicated than I thought. The problem is that when replacing _head by _head.next, you must, as I wrote, edit the 'previous' field of _head.next. But that means that you also change the original _head.next, since it is the same object. And that means that your original IntListTwo will be in an inconsistent state.

So, you can't change your _head.next directly. What about making a constructor in your IntNodeTwo class that takes an IntNodeTwo object as parameter (a copy constructor, as it were)?

It is more complicated than I thought. The problem is that when replacing _head by _head.next, you must, as I wrote, edit the 'previous' field of _head.next. But that means that you also change the original _head.next, since it is the same object. And that means that your original IntListTwo will be in an inconsistent state.

So, you can't change your _head.next directly. What about making a constructor in your IntNodeTwo class that takes an IntNodeTwo object as parameter (a copy constructor, as it were)?

Piet Souris

Saloon Keeper

Posts: 3250

128

posted 1 week ago

It's midnight here in Holland, time for me to go to bed. But my last remark before making a complete mess of this topic:

forget about all that removing of heads an tails and copying nodes and editing fields: way too complicated. Just maintain two nodes: currentHead and currentTail, that you initiate by making them equal to _head and _tail. Now, iff you want to 'remove' the _head, just do: currentHead = currentHead.next. No editing, no complicated things, and likewise for the 'removal' of _tail.

forget about all that removing of heads an tails and copying nodes and editing fields: way too complicated. Just maintain two nodes: currentHead and currentTail, that you initiate by making them equal to _head and _tail. Now, iff you want to 'remove' the _head, just do: currentHead = currentHead.next. No editing, no complicated things, and likewise for the 'removal' of _tail.

posted 6 days ago

Rule 2 of Life, the Universe, and Everything: "It's actually more complicated than that."

Piet Souris wrote:It is more complicated than I thought.

Rule 2 of Life, the Universe, and Everything: "It's actually more complicated than that."

Piet Souris

Saloon Keeper

Posts: 3250

128

posted 6 days ago

Or to quote Hofstadters Law: it is always more difficult than you think, even if you take Hofstadters Law into account.

Or to quote Hofstadters Law: it is always more difficult than you think, even if you take Hofstadters Law into account.

Piet Souris

Saloon Keeper

Posts: 3250

128

posted 6 days ago

hi Rian,

when I went to bed last night, I was thinking about a problem. If your list has n elements, then there are n(n+1)/2 subsets that have only consecutive elements, so possible candidates. Your procedure however, considers only n of them. So, is that procedure so clever that it can eliminate most of the possible solutions? If we define (a, b) as the subset that starts with element at index a and ends with element at index b, and suppose your list has 10 elements, your procedure might be:

(0, 9) -> av. too small (compared to the user input) ->

(1, 9) -> av. still too small ->

(2, 9) -> av. too high ->

***

now there are two possibilities to decrease the average: either reduce the 2 (making it 1) or reduce the 9 (making it 8). However, reducing the 2 brings us back to (1, 9) that we already investigated. So, we consider (2, 8). That is what your procedure does anyway

***

(2, 8) -> av. too high ->

***

Now your procedure continues with (2, 7), but it does not consider (1, 8). Conclusion is that not all candidates will be investigated.

***

A classic way is to use a Queue, with a breadth-first-search for instance, but that is certainly not simple to implement. What, for instance, should the objects be that you put in the Queue?

I don't know your knowledge and experience, but is there anything that you were taught that sounds like it could be of use here?

when I went to bed last night, I was thinking about a problem. If your list has n elements, then there are n(n+1)/2 subsets that have only consecutive elements, so possible candidates. Your procedure however, considers only n of them. So, is that procedure so clever that it can eliminate most of the possible solutions? If we define (a, b) as the subset that starts with element at index a and ends with element at index b, and suppose your list has 10 elements, your procedure might be:

(0, 9) -> av. too small (compared to the user input) ->

(1, 9) -> av. still too small ->

(2, 9) -> av. too high ->

***

now there are two possibilities to decrease the average: either reduce the 2 (making it 1) or reduce the 9 (making it 8). However, reducing the 2 brings us back to (1, 9) that we already investigated. So, we consider (2, 8). That is what your procedure does anyway

***

(2, 8) -> av. too high ->

***

Now your procedure continues with (2, 7), but it does not consider (1, 8). Conclusion is that not all candidates will be investigated.

***

A classic way is to use a Queue, with a breadth-first-search for instance, but that is certainly not simple to implement. What, for instance, should the objects be that you put in the Queue?

I don't know your knowledge and experience, but is there anything that you were taught that sounds like it could be of use here?

Piet Souris

Saloon Keeper

Posts: 3250

128

posted 5 days ago

Hmm, when coding some BFS search with a queue, I realised I made a big blunder in my reasoning. I said that the algo did not inspect (1, 8), and that that was wrong, but it is absolutely correct! Before, I said that the average of (1, 9) was too small, well, then that is certainy true for (1, 8). So I have faith in the correctness of the algo, although I have not proven it completely, yet.

I just finished the code with what I suggested, using the variables currentHead, currentTail, currentSum and currentNrOfElements, and it works great. I used this algo:

1) set currentHread = head, currentTail = tail, sum = sum of all elements, N = number of elements.

2) if calculated average is too low, then sum = sum - currentHead.value, N = N - 1, currentHead = currentHead.next (i.e. making the step from (0, 9) to (1, 9))

3) et cetera.

You could start by checking that the user supplied average is at least equal to the first element, and that it is not higher than the last element.

Sorry for all the confusion I caused. How are you doing?

Hmm, when coding some BFS search with a queue, I realised I made a big blunder in my reasoning. I said that the algo did not inspect (1, 8), and that that was wrong, but it is absolutely correct! Before, I said that the average of (1, 9) was too small, well, then that is certainy true for (1, 8). So I have faith in the correctness of the algo, although I have not proven it completely, yet.

I just finished the code with what I suggested, using the variables currentHead, currentTail, currentSum and currentNrOfElements, and it works great. I used this algo:

1) set currentHread = head, currentTail = tail, sum = sum of all elements, N = number of elements.

2) if calculated average is too low, then sum = sum - currentHead.value, N = N - 1, currentHead = currentHead.next (i.e. making the step from (0, 9) to (1, 9))

3) et cetera.

You could start by checking that the user supplied average is at least equal to the first element, and that it is not higher than the last element.

Sorry for all the confusion I caused. How are you doing?

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!