Posts Tagged Puzzle

Finding Duplicate Ints: Ruby and Groovy

Feb 2

Posted by Christopher J. Stehno in Programming | No Comments

I am going back to my old standard playtime function, finding the duplicated integer in a set of integers. I have been playing around a lot more with Groovy lately and I realized that I had never really done a Groovy version of that little function.

1
2
3
4
5
6

def findDups( n ){
n.sort()
for( i in (1..n.size())){
if(n[i] == n[i-1]) return n[i]
}
}

In this case, I am allowing null to be the value returned when no duplicate is found. It does seem to be a more realistic value for Groovy. It’s a pretty straight forward function, along the same lines as the other languages. I thought maybe I could find some really cool feature of Groovy that would make this radically different from the Java version… nope. It does collapse nicely down to a single line though:

1	def findDups( n ){ n.sort(); for( i in (1..n.size()) ) if(n[i] == n[i-1]) return n[i] }

If you like that sort of thing.

Shortly after, I decided to do a quick little Ruby version as well:

1
2
3
4
5
6
7

def findDups( n )
n.sort!()
for i in (1..n.size())
if(n[i] == n[i-1]) then return n[i] end
end
return nil
end

Nothing exciting in either case, but worth doing for completeness.

Popularity: 3% [?]

Tags: Groovy, Puzzle, Ruby, Tidbits

Converting Numbers to Ranges: Java

Nov 22

Posted by Christopher J. Stehno in Programming | No Comments

Yesterday I posted my Python code for the Converting Numbers to Ranges problem. Today I decided to do a quick Java implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class HomeOnTheRange {

public static void main( final String[] args ) {
System.out.println( convertToRanges( args ) );
}

public static String convertToRanges(final String[] args){
final int[] nums = new int[args.length];
for( int n=0; n<args.length; n++){
nums[n] = Integer.valueOf( args[n] );
}

String hold = null;
final StringBuilder str = new StringBuilder();

for(int i=0; i<args.length; i++){
if( i+1 < args.length && nums[i]+1 == nums[i+1] ){
if(hold == null) hold = args[i];
} else {
if(hold != null){
str.append(hold).append('-').append(args[i]).append(", ");
hold = null;
} else {
str.append( args[i] ).append(", ");
}
}
}

str.delete( str.length()-2, str.length() ).append( '.' );

return str.toString();
}
}

There is not much difference from the Python version; I guess with simple problems like these you are going to end up with pretty much the same form of solution unless you can find some tricky little piece of the language that works better as a solution.

One thing I did different in the Java solution is that I pre-converted the argument String array into an integer array. I noticed that you really end up doing the string to int conversion twice for most of the input elements, which in Java can really add up for a large data set. I wonder if the same problem is inherent in the python solution? I also did the ending period a little different here, simple deleting the end of the string buffer and adding a period; an approach similar to the python version would probably be a little better, but either way is fine.

I guess you could write a separate method to do the string to int conversion and then cache the results so that you are still doing the conversion once and “inline” with the main loop. With a little thought about the problem space you can see that each string is converted and used at most twice, so you can setup the caching to convert and cache on the first use and then just return the converted int on the second call.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public class HomeOnTheRange2 {

private static final ThreadLocal<Converter> converter = new ThreadLocal<Converter>(){
@Override
protected Converter initialValue() {
return new Converter();
};
};

public static void main( final String[] args ) {
System.out.println( convertToRanges( args ) );
}

public static String convertToRanges(final String[] args){
String hold = null;
final StringBuilder str = new StringBuilder();

final Converter conv = converter.get();
for(int i=0; i<args.length; i++){
if( i+1 < args.length && conv.toInt( args[i] )+1 == conv.toInt( args[i+1] )){
if(hold == null) hold = args[i];
} else {
if(hold != null){
str.append(hold).append('-').append(args[i]).append(", ");
hold = null;
} else {
str.append( args[i] ).append(", ");
}
}
}

str.delete( str.length()-2, str.length() ).append( '.' );

return str.toString();
}

private static final class Converter {

private String key;
private int value;

public int toInt(final String str){
if( !str.equals( key ) ){
this.key = str;
this.value = Integer.valueOf( str );
}
return value;
}
}
}

You will see that this code no longer does the initial conversion loop. The string to int conversion is now done using the Converter class, which simply converts and caches the value on the first request for a value, and will simply return the cached int for a second call of the same number. This makes the assumption that the numbers are in ascending order, which is valid for this problem. I also added the converter as a ThreadLocal variable since this conversion is now very tied to the order in which the values are converted. Making it thread-safe ensures that two calls to this method on different threads will not mess with each others values.

I considered just using a Map of some sort, but without some sort of bounds you end up caching every number, when as you can see you really only need one.

Technically delving that deep into the problem to come up with a custom caching solution is really premature optimization, which is generally a bad thing. You should just to the original conversion as needed and then do the followup refactoring if performance bottlenecks lead you to do so.

Popularity: 1% [?]

Tags: Java, Puzzle

Converting Numbers to Ranges: Python

Nov 21

Posted by Christopher J. Stehno in Programming | No Comments

I have decided to start doing little programming puzzle problems in various languages, since my duplicate int finding problem is getting old and repetitive. My first puzzle comes from a site called Code Golf and it is titled Home on the Range. I decided to start with Python since it is something I have been playing with.

Basically the puzzle boils down to taking a series of numbers (in sequence) as input and producing a result where the numbers that are reduced to ranges where applicable, as below:

[1 2 3 6 9 10 11 15] becomes "1-3, 6, 9-11, 15."

After a couple iterations and a handful of language/api reference searches I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

def convert_to_ranges(nums):
ranges, holder = '',''
num_count = len(nums)
cap = endcap(num_count)

for i in range(num_count):
if i+1 < num_count and int(nums[i])+1 == int(nums[i+1]):
if not holder: holder = nums[i]
else:
if holder:
ranges += holder + '-' + nums[i] + cap(i)
holder = ''
else:
ranges += nums[i] + cap(i)

return ranges

def endcap(ln):
return lambda idx: '.' if idx == ln-1 else ', '

print(convert_to_ranges(sys.argv[1:]))

I had originally had the holder variable as a list to hold each grouped number, but I realized that you really only need to store the first one so that you can use it to create the start of the grouping once you find the end of it. The lambda function (endcap()) was originally just a normal function, but I wanted to play with some interesting built-in features, and it actually worked out nicely. The python ternary operator is also interesting ( VAL if CONDITION else OTHERVAL ); it reads better than other ternary operators.

The int() calls I make in the function are simply there because the input comes from the standard in, where they are strings.

Popularity: 1% [?]

Tags: Puzzle, Python

Finding Duplicate Ints: Python

Nov 19

Posted by Christopher J. Stehno in Programming | No Comments

I decided to start playing around with Python a bit and figured I should do what is becoming my personal tradition of implementing the Duplicate Int Finding Problem with Python.

It’s actually a very interesting language and I am surprised that I have not really looked into it sooner. It has a rich set of built-in libraries and tons of extension modules.

The code I came up with is pretty straight-forward:

1
2
3
4
5
6

def find_dup_int(items):
items.sort()
for i in range(len(items)-1):
if items[i] == items[i+1]:
return items[i]
raise RuntimeError('No duplicate values found!')

I need to find a handful of other more interesting problems to try when playing with other languages, since this one seems to look basically the same in each language I have tried.

I will have to spend a little more time with Python, it feels very useful, and as you can see, not very verbose (though not to a fault).

Popularity: 1% [?]

Tags: Puzzle, Python, Thoughts

Find Matching Ints with JavaScript

Oct 30

Posted by Christopher J. Stehno in Programming | No Comments

I realized that I had yet to come up with a JavaScript solution for my duplicate ints interview question, (see Interview Question: Find 2 Matching Ints) so I decide a quick implementation would be fun.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<html>
<head>
<script type="text/javascript">
function findDup(items){
items.sort();
for( var i=0; i<items.length-1; i++){
if( items[i] == items[i+1] ) return items[i];
}
throw "No duplicate values!";
}
</script>
</head>
<body onload="alert( findDup( new Array( 6, 9, 2, 5, 1, 6) ) )">
</body>
</html>

There is not much to it, and nothing really exciting. I also worked up quick versions using Prototype and JQuery; however, neither one really provided any useful deviation from the standard JavaScript approach.

Popularity: 1% [?]

Tags: JavaScript, Puzzle, Tidbits

Puzzle of the Jars and Pebbles

Apr 8

Posted by Christopher J. Stehno in Uncategorized | No Comments

I had an interesting puzzle during a recent interview. I am paraphrasing this from memory so forgive me if you know this one and I am misquoting it somehow:

You have two types of pebbles, white and black, and three jars labeled white, black and black & white, respectively. One jar contains all white pebbles, one contains all black pebbles and one contains a mixture of black and white pebbles. The three jars a all mislabeled so that they will not contain the pebbles noted on the label. How many pebbles would you have to draw and from which jars in order to determine the true distribution?

Don’t read any farther if you are going to try and solve this one for yourself. The next paragraph contains the answer.

The answer is one, from the jar labeled “black & white”. If you got it on your first try through, congratulations, I did not. I figured it out on my second run through it.

Basically, you draw one pebble from the “black & white” jar. Say you draw a white one, you then know that the jar labeled “black & white” is the jar containing the white pebbles. This leaves you with two unknown jars, one labeled “white” and one labeled “black”. Since you know that both of these are incorrect and you have a white pebble, you know that the jar labeled “white” contains the black pebbles and the one labeled “black” contains the black and white pebble mixture.

It’s an interesting problem, but honestly I have never felt that these sorts of problems are useful in a technical interview. We would usually have one question of this nature in our interviews more to see how they would go about solving it than looking for an actual answer. Google apparently loves this type of question in an interview, but asks very little of a technical nature.

Popularity: 4% [?]

Tags: Puzzle

Finding Duplicate Ints: PHP

Aug 13

Posted by Christopher J. Stehno in Programming | No Comments

In my over-long running thread about Finding Matching Ints (initial posting), I have have come across another solution from a php developer that I recently interviewed… in php.

1
2
3
4
5
6
7
8
9

function findInts($array){
$out = Array();
foreach($array as $num){
if(array_exist($out,$num){
return $num;
}
array_push($num);
}
}

He also mentioned the pre-sorting approach as well in order to speed things up. I still need to fully validate the php functions that he mentions, but it seems correct. I also didn’t go into the error-case much with him, not really being a php expert myself.

Popularity: 3% [?]

Tags: Php, Puzzle, Tidbits

Finding Matching Ints Using Regex

Jun 4

Posted by Christopher J. Stehno in Programming | No Comments

If you are following along you may have noticed that I have been compiling a long list of solutions to my Finding Matching Ints problem. I was talking to one of my co-workers, who is not a developer but used to do some Perl hacking, and he suggested that it could be done with regular expressions. Lo and behold, with the help of another of my more regular-expression-ized co-workers we found this to be true:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public int findDuplicate(final int[] array){
final Pattern p = Pattern.compile(".*?(\\d+. ).*?\\1.*");
final Matcher m = p.matcher(join(array));
if(m.find()){
return Integer.valueOf(m.group(1).trim());
}
throw new IllegalArgumentException("No match found!");
}

private String join(final int[] array){
final StringBuilder str = new StringBuilder();
for(final int i : array){
str.append(i).append(" ");
}
return str.toString();
}

Granted, it’s not quite as straight-forward as the other solutions, but it is a very novel approach to solving the problem… leave it to a Perl guy. I wonder what the runtime of this would be?

Popularity: 1% [?]

Tags: Java, Puzzle, Regex, Tidbits

Recursive Solution to Finding Ints Question

May 28

Posted by Christopher J. Stehno in Programming | No Comments

Back in my posting of Interview Question: Find 2 Matching Ints I showed a few different solutions to the problem. A candidate we had recently suggested solving it via recursion; I decided to whip up a little recursive solution for my collection:

1
2
3
4
5
6
7
8
9
10
11
12

public static int find(int[] array){
return scan(new HashSet<Integer>(),array,0);
}

private static int scan(Set<Integer> values, int[] array, int idx){
if(idx == array.length){
throw new IllegalArgumentException("No match exists");
} else if(!values.add(array[idx])){
return array[idx];
}
return scan(values,array,++idx);
}

Note that this solution requires an additional method to perform the recursion but there are no loops. An alternate version removes the Set and uses pre-sorting of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13

public static int find(int[] array){
Arrays.sort(array);
return scan(array,0);
}

public static int scan(int[] array, int idx){
if(idx == array.length){
throw new IllegalArgumentException("No match exists");
} else if(array[idx] == array[idx+1]){
return array[idx];
}
return scan(array,++idx);
}

This problem has really become an interesting study; as I use it as one of our tests for interview candidates I really find it an interesting ruler to compare how various developers think. Two interesting common threads are that most developers find the brute-force approach (double for loop) which is good but very telling, the other is that when faced with the idea that it is possible an array may be passed in without a match, they struggle on what to do at that point. The first solution people look at is some signal like a -1 or null, neither of which works. After hinting they will come across the idea of the exception but usually want to create their own unique exception for this method.

I think it would also be an interesting exercise to implement this problem in other languages such as Groovy, Ruby or Scala.

Popularity: 1% [?]

Tags: Java, Puzzle, Tidbits

Interview Question: Find 2 Matching Ints

Feb 2

Posted by Christopher J. Stehno in Programming | No Comments

Okay, here is a little question I have taken to asking in the interviews we have been giving lately. The questions is as follows:

Assume that you have an array of ints with exactly two of them being equivalent. Write a method to return the int that is duplicated.

Upon the first candidates failing this one for the most part, I have started compiling a catalog of all the possible and sensible solutions to the problem. It’s kind of a fun little project. Below are some of the implementations I have come up with.

When I came across this question, it did not have an answer provided. My first shot at it was the following, but without the array sorting. Oops, without the sorting it works as long as they are next to each other, hence the need for sorting:

1
2
3
4
5
6
7

public int findMatching(final int[] array){
Arrays.sort(array);
for(int i=0; i<array.length-1; i++){
if(array[i] == array[i+1]) return array[i];
}
throw new IllegalArgumentException("Array contains no matches!");
}

The second implementation was something I had as a first thought but could not remember the exact functionality of the Set add(Object) method, which is kind of important in this case.

1
2
3
4
5
6
7

public int findMatching(final int[] array){
final Set<Integer> set = new HashSet<Integer>(array.length);
for(int i : array){
if(!set.add(i)) return i;
}
throw new IllegalArgumentException("Array contains no matches!");
}

The third implementation is the one most of our candidates seem to jump for, brute force, comparing every element with every other element (we still give credit for it though):

1
2
3
4
5
6
7
8

public int findMatching(final int[] array){
for(int i=0; i<array.length; i++){
for(int j=0; j<array.length; j++){
if(i != j && array[i] == array[j]) return array[i];
}
}
throw new IllegalArgumentException("Array contains no matches!");
}

You will notice that I used an IllegalArgumentException to denote the lack of matches. You can’t really return a -1 or something like that since your ints could be of any value.

I am sure that there are one or two more interesting solutions for this problem, but thought I would share what I have found. These are always fun little code problems to play with.

Yes, we are still using this in our interview process, but I am not afraid that a potential candidate will find this since they generally don’t know my name, and likewise I don’t advertise what company I work for. Actually, I would probably give a “golf clap” to the candidate that walks into our interview with a print out of this entry. Don’t break yourself trying to find out… it’s not worth it.

Popularity: 1% [?]

Tags: Interview, Java, Puzzle

CoffeaElectronica

A smooth well-coded brew.

Posts Tagged Puzzle

Finding Duplicate Ints: Ruby and Groovy

Converting Numbers to Ranges: Java

Converting Numbers to Ranges: Python

Finding Duplicate Ints: Python

Find Matching Ints with JavaScript

Puzzle of the Jars and Pebbles

Finding Duplicate Ints: PHP

Finding Matching Ints Using Regex

Recursive Solution to Finding Ints Question

Interview Question: Find 2 Matching Ints

Recently Updated

Most Popular

Tags

Top Downloads

Archives

Blogroll

Meta