Published: Dec 30 2013 / 01:17
Voted down for a bad solution (don't know why there were a lot of up votes). Rudy in the comment section was right.
Please understand the code written above is the most efficient code as the hashtable takes O(n) in look up for the element . Any one can do the above question through arrays also . But thats solution is not good as it will utilize more memory . In the post itself I clarified that this is interview question of Amazon and equivalent companies which always ask efficient algorithms . Hope you got my point . ,
If you think scanning the string twice is better then go ahead.
hashtable takes O(1) for lookup, not O(n)!
I was talkin about worst case scenario . O(1) is the best case scenario . If you are writing algorithm you are more concerned with th worst case scenario in real world .
here is a solution in mathematica. its more elegant imho, but also slower ( O(n^2) ) http://pastebin.com/94z7UbBd (can't paste mathematica code in here, sorry)
Html tags not supported. Reply is editable for 5 minutes. Use [code lang="java|ruby|sql|css|xml"][/code] to post code snippets.
Advertising - Terms of Service - Privacy - © 1997-2014, DZone, Inc.