Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# 2 small algorithm questions , that require optimized code

Myke Enriq
Ranch Hand
Posts: 115
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.

Ryan McGuire
Ranch Hand
Posts: 1142
9
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.

Martin Vajsar
Sheriff
Posts: 3752
62
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
Ranch Hand
Posts: 1142
9
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.

Mike Simmons
Ranch Hand
Posts: 3090
14
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
Ranch Hand
Posts: 1142
9
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.

Ivan Jozsef Balazs
Rancher
Posts: 999
5
> 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.