• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

2 small algorithm questions , that require optimized code

 
Ranch Hand
Posts: 115
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1) Write a java (J2SE) function that takes a String as an input and outputs a String that encodes the input , by replacing a char that appears multiple times by that char followed by the int number fo times it appears.

Meaning for input = "aazcdddd" output is "a2zcd4"

2) Given an array of int , compute the sum of the squares of its elements. Meaning for input int[] x = {1,2,3} the output is 14 = 1*1 + 2*2 + 3*3

These questions do not sound hard , but I guess they are both about optimising code and about treating exceptions/anticipating exceptions.

For example in question 1 , how long is the String ? What to do when it is very long, same goes for question 2.

Anyway , they were given in a programming contest , I already solved them (the classic way) , but I am wondering if there is a better way/trick to them.
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For #2: The sum of squares one...

I think the point here is to reduce the number of multiplies you do. (...assuming you're optimizing for time as opposed to space.)

You could keep a hash of previously computed squares and use those if you see the same array element again.

e.g.
int[] x = {1, 2, 3, 2, 1}
CachedSquares["1"] = 1*1 = 1
SumSoFar = 0 + CachedSquares["1"] = 1

CachedSquares["2"] = 2*2 = 4
SumSoFar = 1 + CachedSquares["2"] = 5

CachedSquares["3"] = 3*3 = 9
SumSoFar = 5 + CachedSquares["3"] = 14

CachedSquares["2"] exists so...
SumSoFar = 14 + CachedSquares["2"] = 18

CachedSquares["1"] exists so...
SumSoFar = 18 + CachedSquares["1"] = 19


5 array elements, only three multiplies, O(n) time.

 
Sheriff
Posts: 3837
66
Netbeans IDE Oracle Firefox Browser
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'd say that multiplication is so fast nowadays that a lookup even in an array of ints (or Integers) might take more time than the multiplication itself. A lookup in a HashMap will be much more expensive than an integer multiplication (have a look at the HashMap source code).

(Things would probably be different if we were speaking about multiplication of BigIntegers.)
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Integer multiplies are pretty darn fast, but I bet an array lookup is at least a little faster. As long as the max size of an element is small enough where we can keep an array that large. I mean we are talking optimization, not goodenoughimization.

What else is there to optimize? The "obvious" solution is O(n). I don't see how you can sum the squares of the array elements without looking at every single one, so unless I'm mistaken, any solution would have to be at least O(n).

I can see a lot of things that could wrong, such as integer overflow with either the multiplication or the addition, but that falls more under exception handling than optimization.
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ryan McGuire wrote:Integer multiplies are pretty darn fast, but I bet an array lookup is at least a little faster.


Well, you seemed to be showing a hash lookup in some non-Java language, not an array lookup. I don't know how to do an array lookup with a string as key/index. Even if we use a proper array lookup by int index, we need to consider the cost of failed lookups. Like all caching strategies, the effectiveness depends on the ratio of uncached- to previously-cached- lookups.
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:

Ryan McGuire wrote:Integer multiplies are pretty darn fast, but I bet an array lookup is at least a little faster.


Well, you seemed to be showing a hash lookup in some non-Java language, not an array lookup. I don't know how to do an array lookup with a string as key/index. Even if we use a proper array lookup by int index, we need to consider the cost of failed lookups. Like all caching strategies, the effectiveness depends on the ratio of uncached- to previously-cached- lookups.



A bit of a misunderstanding here.

Yes, my first post used a hash lookup. Once Martin pointed it out, I implicitly agreed that a hash lookup is pretty bad. I don't know of any "good" hash functions that A) don't include at least one multiply and B) don't degenerate into just an array lookup. e.g. For integer hash indexes, you could make the hash function return the index itself.

My second post backed away from the hash idea and tried to see if we we could use a plain old array lookup to possibly do better than the straightforward obvious solution.

Again, the solution to this question seems so obvious that I don't see much room for optimization. The only possibilities rely on an assumption or two. e.g. You could use an array to cache squares iff the maximum value is <= the max array size. There are other tricks we could use if we knew that the input array was sorted ahead of time. Also there may be an O(n*n) algorithm that's faster than the obvious linear algorithm for some inputs if we can be sure n is small enough and the input data is repetitive enough: e.g. [56,34,34,45,56,45,56,67,34,45,34,67,78,45,78,56,56,78,34,23,67,23,67,78,56,78,23] might be calculatable using an O(n*n) or O(n logn) algorithm faster than with the obvious O(n) way.

 
Rancher
Posts: 1044
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
> There are other tricks we could use if we knew that the input array was sorted ahead of time.

If you know the array is sorted, you can remember the previous element and its square and reuse the square if possible.
So you have to do extra comparisons for the sake of saving the squaring of the repeating elements.

The number of the operations increased but the int comparison might be cheaper than the integral multiplication.
I doubt its buying much tough.

reply
    Bookmark Topic Watch Topic
  • New Topic