Data structure and algorithm interview question for java programmers
Posted on May 3, 2014
(Last modified on August 7, 2020)
| 8 minutes
| Kinshuk Chandra
Question 1 : How to find middle element of linked list in one pass?
One of the most popular question from data structures and algorithm, mostly asked on telephonic interview. Since many programmer know that, in order to find length of linked list we need to first traverse through linkedlist till we find last node, which is pointing to null, and then in second pass we can find middle element by traversing only half of length.
[Read More]Memory requirement of a program in java
Posted on May 2, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Consider the class below, and notice the comment telling how much bytes they use.
There is a overhead of 16bytes for maintaining class, 1 Byte for byte and boolean, 2Byte for char and short, 4 bytes for integer, 8 bytes for long and double, and some overhead for padding, to make overall memory even, to sum up:
Java type
Bytes required
boolean
1
byte
char
2
short
int
4
float
[Read More]Hash Functions
Posted on May 2, 2014
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Importance of Hash function
Why Hash-function matter?
Chaining implementation of hashtable
We will discuss about hashtable with chain. Insertion in the hashtable is O(1), so does lookup. Invoke hash function and see where is our bucket. Now go to the bucket and traverse the list until we find our element.
Suppose we have 100 elements which are inserted in the hash function, then we have
Lucky hash function - 1 element per bucket
[Read More]Symbol table data structure
Posted on May 2, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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]Fit 1*2 dominos in 2*N strip
Posted on May 2, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem In how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?
Solution Please notice that we can put tiles either vertically or horizontally. For putting vertical tiles, we need a gap of at least 2 X 2. For putting horizontal tiles, we need a gap of 2 X 1. Number of arrangements will be the same as the arrangements, we can make with gaps of 1 and 2 (order dependent).
[Read More]Atomicity and Atomic operations
Posted on May 2, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Atomic Operation
What is an atomic operation? An idea of atomic operation helps in understanding reentrancy, critical section, thread safety, synchronization primitives, etc… (we will have upcoming articles on each).
Atomicity, Atomic Operation:
In simple terms, atomicity is unbreakability, i.e. an uninterrupted operation. If two users issue a print command, each print should go in single attempt. If the printer driver is sending parts of data from two users, the printout will not be as expected.
[Read More]Selection Algorithms
Posted on May 1, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Deterministic Selection - Select the i th smallest element
Posted on May 1, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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]Find kth largest element from a 2-d sorted array
Posted on May 1, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Given the 2D matrix or array - sorted row-wise and column-wise, find the kth largest element.
Example Input
Consider the array below and k=4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Output
Output should be 22
Solution Method 1 - Use MaxHeaps
We know if k=1, we should return A[n-1][n-1] i.
[Read More]Nut and Bolt Problem (OR Key and Lock Problem) - Matching Nuts and Bolts when nuts cannot be compared with nuts and bolts with bolts
Posted on May 1, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. Suggest an algorithm to match each bolt to its matching nut.
Compute time complexity of your algorithm.
[Read More]