Data Structure

Goal To understand skiplist. Definition Skiplist is a dynamic search structure, as it is dynamic when it comes to insertion and deletion, which supports search). Other dynamic search structure: Treaps Red black tree B-Trees (2-3 trees etc) Operations on skiplist Search - O(log n) Insert - O(log n) Delete - O(log n) These operations are with high probability, 1/polynomial depending on polynomial number of operation. [Read More]

Definition A symbol table is a data type that we use to associate values with keys. Clients can store (put) an entry into the symbol table by specifying a key-value pair and then can retrieve (get) the value corresponding to a particular key from the symbol table. Operations Symbol table is key value abstraction. Operations supported Insert - Insert a value with specified key Search - Given key, search for the corresponding value Application Application [Read More]

We have already seen RSelect or Random Selection here. Now lets focus on DSelect. Though RSelect is good, and works in linear time, but it deterministically runs in O(n) time, even in worst case. But the downside is that it doesn’t runs as fast as RSelect, but its worst case is still better. Like in quicksort, we had it better than merge sort, but worst case of quicksort was worse than mergesort. [Read More]

Problem - Implement a stack using a queue Solution Method 1 - Implement a stack using 2 queues We have already discussed the problems here. Method 2 - Implement a stack using a single queue Here are the operations(note that push operation is expensive) push: enqueue new element. If n is the number of elements in the queue, then remove and insert element n-1 times. pop: dequeue push 1 front +----+----+----+----+----+----+ | 1 | | | | | | insert 1 +----+----+----+----+----+----+ push2 front +----+----+----+----+----+----+ | 1 | 2 | | | | | insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | 2 | 1 | | | | remove and insert 1 +----+----+----+----+----+----+ insert 3 front +----+----+----+----+----+----+ | | 2 | 1 | 3 | | | insert 3 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | 1 | 3 | 2 | | remove and insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | | 3 | 2 | 1 | remove and insert 1 +----+----+----+----+----+----+ Code: [Read More]

Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size) Solution A similar problem has been blogged here, where we implement a queue using 2 stacks. There should be TWO versions of the solution. Version A: The stack should be efficient when pushing an item. Version B: The stack should be efficient when popping an item. Method 1 - When push is efficient and pop is costly [Read More]

**Definition: ** An algorithm is a finite set of discrete statements (or Steps) in some particular sequence (or Order) to accomplish a predefined particular task. **Properties: ** An algorithm must have the following properties: Input(s) : An algorithm must have one(1) or more pre-specified input(s). Output(s) : An algorithm must have one(1) or more output(s). Definiteness : Each steps of an algorithm must define clearly (i.e. without any confusion or Contradiction or Ambiguity). [Read More]

Problem Given a number X find the number Y which is next higher number than X using the exact same digits as in X. Example For example: given 38276 return 38627 Solution Method 1 - Brute force The brute-force method is to generate the numbers with all digit permutations and consider all the higher numbers than the given number and return the minimum number from those higher numbers. [Read More]