Showing posts with label data structure; java investment bank;. Show all posts
Showing posts with label data structure; java investment bank;. Show all posts

Thursday 8 August 2013

Top Most Data Structure questions for Java developer

'Data Structure questions' or 'Java Algorithm questions' is covered in this topic. These questions are always asked by interviewer if they are from CS background. This is very useful to understand java collection sorting and searching algorithm so that we can use correct collection type in our application. It help us to understand how indexes work in database and how the data retrievals become so fast due to B Tree data structure.

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.
Example -- 8 6 7
Compare 8 and 6 and re arrange to 6,8,7
Next number compare 8 and 7 and rearrange 6,7,8
This process continues till there is no swaping
Output : 6,7,8

Average : n^2 and 
worst case  n lon(n)










Quick Sort: Pivot
Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3.  Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.
Quick Sort
Average:  n log n
Worst : n^2









Merge Sort
a merge sort works as follows
1.   Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2.   Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.
Example 4 8 9 0
Devide till single element :   4  ||  8 ||  9  || 0
Group into 2 :                        4 8  ||  0  9
Merge these 2 list :             0 4 8 9


Avg case :  n ( log n )
Worst case: n long (n)







Binary Search tree:
In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
· The left subtree of a node contains only nodes with keys less than the node's key.
· The right subtree of a node contains only nodes with keys greater than the node's key.
· Both the left and right subtrees must also be binary search trees.
· There must be no duplicate nodes.


Best case :  O (1)
Avg case : O (log n )
Worst case : O (log n)









SkipList:
  A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly used values for p are 1/2 or 1/4). On average, each element appears in 1/(1-p) lists, and the tallest element (usually a special head element at the front of the skip list) in lists.A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. 
         If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most 1/p, which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total expected cost of a search is which is when p is a constant. By choosing different values of p, it is possible to trade search costs against storage costs.














LinkWithin

Related Posts Plugin for WordPress, Blogger...

Labels

Core Java programming core java interview question Core Java Faq's Servlets coding database jsp-servlet spring Java linux unix interview questions java investment bank Web Services Interview investment bank mysql Senior java developer interviews best practices java collection tutorial RMI SQL Eclipse FIX protocol tutorial tibco J2EE groovy java questions SCJP grails java 5 tutorial jdbc beginner error and exception Design Patterns Java Programming Tutorials fundamentals general object oriented programming xml Java Programs Hibernate Examples Flex JAMon Java xml tutorial logging Jsp Struts 2.0 Sybase and SQL Server debugging java interviews performance FIX Protocol interview questions JUnit testing WebSphere date and time tutorial experienced java IO tutorial java concurrency thread Ejb Freshers Papers IT Management Java Exapmle Java Script SQL and database tutorial examples Scwcd ant tutorials concurrency example and tutorial future state homework java changes java threading tricky Agile Business of IT Development JSTL Java JSON tutorial Java multithreading Tutorials PM Scrum data structure and algorithm java puzzles java tips testing tips windows 8 5 way to create Singleton Object Architect Interview Questions and Answers Architecture Architecure Bluetooth server as swing application that searches bluetooth device in 10 meter circle and show all devices. You can send file to any bluetooth device. C Programming CIO Callable Statement in Java Circular dependency of Objects in Java Comparable Example in Collection Custom annotation in Java Developer Interview Divide and rule example in java Drupal Example of Singleton Pattern FIX protocol ForkJoin Example in Java 7 Get data from dynamic table with Java Script Git HTML and JavaScript Health Hello World TCP Client Server Networking Program Hibernate Basics Hibernate Interview Question Answer J2EE Interview Question And Answers J2ME GUI Program JEE Interview QA JMS interview question Java J2EE Hibernate Spring Struts Interview Question Java System Property Java Threads Manager Portlets Provident Fund Read data from any file in same location and give the required result. Reading Properties File in Java Redpoint Rest WebService Client Rest Webservice Test SAL join with ven diagram SCP UNIX COMMAND SSL Singleton Pattern in Java Spring Bean Initialization methods and their order Spring Interview Questions Struts Struts 2.0 Basics Struts 2.0 Design Pattern Submit Html Form With Java Script On The Fly Unix executable For Java Program XOM DOM SAX XP books computers core java; core java; object oriented programming data structure; java investment bank; design pattern dtd duplicate rows in table get browser name with jquery grails podcast inner class java beginners tutorial java cache java networking tutorial java spring java util; java collections; java questions java.java1.5 linked list mailto function with all browser oracle database oracle duplicate rows orm schema social spring mvc questions struts transaction tricks tweet windows xslt