Priority Queue

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

What is priority queue? A data structure for maintaining items or elements in a queue of priorities, which is usually implemented using an array. A queue of this nature helps to insert every item with an assigned priority and these inserted items could be deleted if required. Minimum number of queues needed to implement the priority queue? Two. One queue is used for actual storing of data and another for storing priorities. [Read More]
kodeknight  queue  Data Structures  DS  PriorityQueue  Data Structure 

Bloom filters

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

The bloom filter is a data structure designed in 1970. It is similar to a hash table. They are more efficient than a hash table, but they do raise false positives at times. Supported Operations A bloom filter supports super fast lookup and insertion, just like a hash table. So why have this data structure? Pros It is much more space efficient. It takes the space even less than that of the object. [Read More]
cpp  kodeknight  Data Structures  DS  incomplete  hashtable 

Some Stack Question

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

1)How do you implement 2 stacks using only one array.Your stack routines should not indicate an overflow unless every slot in the array is used? **Solution:**given an Array,start the first stack S1 from left end and other stack S2 from the right end.while S1 gets grows towards right ,S2 grows towards left. (By the way we can implement n stacks in 1 array, eg. of 3 stacks in 1 array is given in question 3 below) [Read More]
kodeknight  String  catalan  Data Structures  DS  stack 

Advantage and disadvantage of datastructures

 Posted on September 14, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Characteristics of Data Structures Data Structure Advantages Disadvantages Array Quick inserts Fast access if index known< Slow search Slow deletes Fixed size Ordered Array Faster search than unsorted array Slow inserts Slow deletes Fixed size Stack Last-in, first-out acces Slow access to other items Queue First-in, first-out access Slow access to other items Linked List Quick inserts Quick deletes Slow search Binary Tree Quick search Quick inserts Quick deletes (If the tree remains balanced) [Read More]
kodeknight  Data Structures  DS  compare 

Sorting a Stack using push,pop,isEmpty and peek

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem Definition: Sort a Stack using standard operations push,pop,isEmpty and peek. This question is asked in cracking the coding interview. Other ways of asking the question Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that should be used to write this program: push | pop | peek | isEmpty Note - peek is equivalent to top() function in java, where you dont pop out the element but peek and see. [Read More]
kodeknight  interview  Data Structures  DS  sorting  CrackingTheCodingInterview  stack 

What is a data structure?

 Posted on June 9, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

A data structure is encapsulation of data and relevant operations. It is referred to as an Abstract Data Type (ADT), signifying that the actual implementation is left open, subject to satisfying the intended meaning of the operations. For the most part the exact data representation is not presented; rather, all access to the data is through the operations. The Java class is a perfect model for an ADT. In addition to the encapsulation with accessibility via operations only, the presentation of operations are in the modern object-oriented fashion in which the data takes precedence over the operation. [Read More]
kodeknight  Data Structures  DS 

C++ STL: Iterators and Containers

 Posted on August 5, 2010  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

This article was contributed by Eric Sanchez Environment: ANSI C++ As one explores further into the standard template library, there must be a basic understanding of a few trivial terms. Perhaps the two most important are containers and iterators. Container Classes As the name implies, instances of container classes are objects that “contain” other objects. C++ STL comes with a rich set of such components that aid in storing collection of values. [Read More]
cpp  kodeknight  templates  Data Structures  DS  generic classes  Data Structure Templates 

Important ds question

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  16 minutes  |  Kinshuk Chandra

a) Write a function that validates whether a tree is a BST or not. b) Write a function to find the common ancestor of two given nodes of binary tree. c) In a BST, value of two of the nodes got exchanged by mistake. Write a function to correct the BST. d) In a array, there exists a majority element(a no. repeated atleast n/2 + 1 times) and rest of the no. [Read More]
kodeknight  Microsoft  Amazon  Data Structures  DS  sorting  binary-search-tree  BST