Number of unique elements in sorted array with repeated elements

 Posted on March 25, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Find the number of unique elements in sorted array with repeated elements. Follow up - How can you do it without using extra space Example Input = [1,1,1, 2] Output = 2 i.e. 1 and 2. Example for follow up Input = [1,1,2] Output = 2 Solution It’s not really possible to know in constant time how many unique items are in a collection, even if the collection is sorted, unless you only allow one instance of the item in the collection at any given time. [Read More]
kodeknight  duplicate  count  sorted-array  java 

Data Structure to Emulate LRU Cache

 Posted on January 23, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Implement the LRU cache Solution Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows: find the item as fast as we can Once a cache misses and a cache is full, we need to replace the least recently used item as fast as possible. We use two data structures to implement an LRU Cache : [Read More]
kodeknight  cache  concurrency  java 

Iterators - Allowing iteration over data structures (in java)

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

Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves. Here’s where java gives us the power called iterators which allows us to iterate over data structure. Design Challenge Consider the stack data structure and we want to support iteration over it on client side. [Read More]
kodeknight  incomplete  Data Structure  java 

Generic data structures in java

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

Suppose we have a stack of string, but later we want to use it for integers. We have to re-write the code again and again for every data type. So how can we solve this.

Attempt 1 - Creating the stack for every data type, which is very exhaustive and needs code changes again.

**Attempt 2 - **Implement a stack using Object class.
Example

Downside -

  • Discover type mismatch errors at run time
  • Casting has to be done at client side
  • Code looks ugly because of so many castings

Attempt 3 - Java generics

kodeknight  incomplete  generic classes  stack  java 

Adjacency list represention of graph in Java

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Here is the program for adjacency list representation of graphs using java. If you are new to Graphs please read about graphs here before reading the rest of this post. Code: package com.vaani.algo.graph.impl; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class GraphUsingAdjList { class Node { int node; List<Integer> adjList; boolean visited; } void insertVertices() throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter number of nodes in a graph: "); int n=(Integer. [Read More]
Graph  kodeknight  AdjacencyList  Adjacency  java 

Selection Sort

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

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort. Pseudocode of selection sort Get the smallest element and put it in the first position Get the next smallest element and put it in the 2nd position …. [Read More]
cpp  kodeknight  c  array  Selection Sort  Sorting Algorithm  sorting arrays  sorting  In-place sorting  Data Structure  Comparison Sort  java 

Search an element in the sorted rotated array

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

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer: We can do a binary search with some modified checks. So lets take arr as array, start be start of the array, end be arr. [Read More]
ArraySearch  kodeknight  Amazon  recursion  array  binary search  rotated array  CrackingTheCodingInterview  sorted-array  sorting-and-searching  java 

atoi() in Java

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

Problem: Write a function to convert an ASCII string to integer, similar to atoi() function of C++. Solution: The solution is too simple, it’s simple checks for erroneous inputs that makes writing such a function fun. public class AsciiToInteger { public static void main(String args) { AsciiToInteger instance \= new AsciiToInteger(); int x \= instance.atoi("-683"); System.out.println("Conversion is: " + x); } private int atoi(String number) { // check for NULL or empty if(number \=\= null || number. [Read More]
conversion  kodeknight  String  array  java 

XML Sequence Delimiter

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

An XML sequence delimiter might be required for processing XML streams without the boiler plate code that comes with well known XML Parsers. A simple use case might be converting xml transformations on the fly like producing a partial output of the xml transformation as the user punches the script, etc. This one uses a simple pattern based filter and recursion to achieve it. The delimiter is assumed to be comma (,). [Read More]
kodeknight  recursion  xml  java 

Counting sort

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

Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence. Example For simplicity, consider the data in the range 0 to 9. [Read More]
kodeknight  sorting  integer-sort  count  java