Monday, August 22, 2011

NxN numbers spiral

This evening I was reading a forum about questions google ask to software engineers during job interviews and it came to my mind a programming challenge that Softonic made me and my classmates the second year of my BCS.

The problem consists in printing a spiral array of a given size. The input of the program is the size of the spiral, and the output is the spiral itself.

For instance, for N=4 we would get the following output:
00 01 02 03 
11 12 13 04 
10 15 14 05 
09 08 07 06 

For N=11, the output would be:
000 001 002 003 004 005 006 007 008 009 010 
039 040 041 042 043 044 045 046 047 048 011 
038 071 072 073 074 075 076 077 078 049 012 
037 070 095 096 097 098 099 100 079 050 013 
036 069 094 111 112 113 114 101 080 051 014 
035 068 093 110 119 120 115 102 081 052 015 
034 067 092 109 118 117 116 103 082 053 016 
033 066 091 108 107 106 105 104 083 054 017 
032 065 090 089 088 087 086 085 084 055 018 
031 064 063 062 061 060 059 058 057 056 019 
030 029 028 027 026 025 024 023 022 021 020 

The solution is quite easy, I implemented it in java, the code basically creates an array of N size, and there are 4 for loops in a main for loop, these fill the array, one for loop each side of the spiral, as shown in the following figure:




The last part of the code (lines 46 to 53) are a little bit tricky, I had to make this to have zeros padded properly to have a good-looking output (same number of digits for each array value).

The complexity of the code in big O notation is O(N^2).



I think it can be useful to somebody. Any suggestion to improve it will be appreciated.

No comments:

Post a Comment