Rough Book

random musings of just another computer nerd

Tag: algorithms

Maintaining a sorted array in O(1)

Yesterday, I came across an interesting question on StackOverflow. The question is as follows: assuming you have a sorted array, is it possible to increment locations by 1 (one at a time) and still ensure that the array is sorted in O(1)? Assuming you are not allowed to use any other secondary data-structures, the answer is no. This becomes evident when you have repeated values. Assume a degenerate case where you have an array of identical values; let’s say [0, 0, 0, 0, 0]. If you increment the value in location 0, you now have [1, 0, 0, 0, 0]. For this array to be sorted, the value 1 must be moved to the end of the array (index 4). This will require four comparisons, which means that this will inevitably turn into an O(n) algorithm.

How can we do better?

Read the rest of this entry »

A simple trie-implementation

I’ve known about tries for sometime. They’re a pretty neat data-structure for storing and looking-up strings.I decided to try and implement one in Java so that I can learn more about them. I’ll post another article later that goes into some more detail about this implementation, but for now you can check out the source here. It’s not production-ready by any means; it’s just me playing around.

All original content on these pages is fingerprinted and certified by Digiprove
%d bloggers like this: