Problem Solving: Sort an Array

You have an array of size ‘n’ with numbers from 1 to ‘n’. You need to sort this array in the most optimal way.

HINT(Don’t read the hint if you think you can do without it): The solution has a complexity of O(n). i.e. even less than the O(n.log(n)) which is given by the best sorting algorithms.

Find the answer in the comments section.

About this entry

You’re currently reading “Problem Solving: Sort an Array,” an entry on /kapil/blog

Published:: 10.30.07 / 10am

Category:: Logic

Tags:: algorithm, problem solving

1 Comment

Jump to comment form | comments rss [?] | trackback uri [?]

Kapil Chhabra 10.30.07 / 11am

Answer: There is no need to sort the array at all. Just enumerate the array in a loop of ‘n’. Remember that array had numbers from 1 to ‘n’.

Let me know if you could solve this. I am curious.

Have your say

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

About

I have over 6 years of experience in architecting and developing web applications.

I am currently working at Akamai Technologies as a Sr. Software Engineer responsible for gathering/conceptualizing requirements and architecting the “Media Analytics” product, which is part of the Akamai HD Network. Previously at Akamai, I was working in the portal development team for the “Performance Analytics” suite of products, responsible for feature development and usability enhancements. At Akamai, I have gained an in-depth understanding of the business of online “Analytics”, and building & using large-scale software for it.

Prior to this, I worked as a Technical Architect at Info Edge (I) Ltd (company that owns high traffic portals like: Naukri.com, Jeevansaathi.com, Brijj.com, 99acres.com etc.). I was the first member of the Brijj.com technical team and was responsible for hiring and bootstrapping the complete team; and architecting the product. For Naukri.com, I played a key role in implementing and optimizing Lucene based distributed and scalable Resume Search Engine in Core Java. I was also responsible for performance tweaking (Apache & Lighttpd for high performance and low response time), and taking initiatives to deliver smart, fast and quality products for the company.

Apart from these, I have also undergone six months of extensive training experience at Tata Consultancy Services, responsible for re-writing existing Pro*COBOL code in equivalent PL/SQL scripts.