DSA All

DS , Algo ,Bit Magic (Solve each problem in every possible way)

Write code to find loop in linkedlist.
Write code to reverse a linkedlist.
Write code to reverse a string without using any API.
Implement Djikstra.
Write code for  DFS,BFS,inorder,preorder,postorder,zigzag in tree.
Implement quick sort.
Implement merge sort.
Implement autosuggest feature from a list of words.
Implement LRU.

Check if a tree is BST?

Print numbers in order using two threads.

Write code to find diameter, height of tree(or binary tree?).
Write code to check if a number is power of 2.
Write code to search a number in rotated array.
Write code to check if a number is prime.

Find LCA(Lowest Common Ancestor) in a binary tree.
12. Write code to find number of set bits in an integer.
5. Write code to find k^th element from end in a linked list ?
6. Write code to find the missing number in an integer array having 1 to 100 in random order except a number.
10. Write code to check if linkedlist is palindrome.
12. Implement Prim.

15. Write code to search a number in a sorted 2d matrix.
16. Write code to print 2d matrix in spiral order.
17. Write code to find k^th largest element in an array.
18. Implement stack using queue.
19. Implement queue using stack.
20. Implement two stack using an array.
21. Implement three stacks using an array.
19. Write code to check integer is palindrome.
19. Write code to check string is palindrome.
20. Write code to find maximum continous subarray in an array.
21. Write code to find longest palindrome substring in a string.
22. Write code to find best time to buy sell stock.

22. Write code to swap two numbers.
23. Write code to find sum of digits
24. Write code to reverse an integer.
24. Write code to print first n numbers infibonacci series.
25. Write code to print nth fibonacci number.
25. Write code to add two numbers represented by a linked list.
26. Write code for bubble sort.
27. Implement radix sort.
28. Implement counting sort.
29. Implement insertion sort.
30. Implement selection sort.
31. Implement heap sort.
32. Implement bucket sort.
33. Write code to find first repeated character in a string.
34. Write code to find first unique character in a string.
How to find middle element of linkedlist in one pass?
Write code to remove duplicates from an array.
Implement BST.
Implement doubly linked list.
Implement doubly linked list using single pointer.
Write code to convert decimal to binary.
Write code to sort a map by value.
Write code to find common elements in two arrays.
Find longest substring without repeating characters.
Determine whether a point lies inside a triangle.
Nuts and bolts problem.
What is the probability that knight stays inside the chess board?
Implement stack using likedlist.
Implement queue using linkedlist.
Check for balanced paranthesis in an expression.
Sort an array containing only 0 and 1.
Sort a linkedlist containing 0,1,2.
Minimum number of platforms required at railway station.
convert word to another , one time one character , from a list of words.
Break string into dictionary words.
Find seed of a number. A number X is seed of Y if multiplying X by it's digits equates to Y.
Finds pairs of numbers with difference k  from an unsorted array.
Find number of trailing zeros in a number factorial.
Given an array containing 0 and 1 , find the largest subarray cotaining equal number of 0 and 1.
Sort an array of elements by decreasing order of frequency.
Given an array of words , group all anagrams in set
Find the min element in a sorted rotated array.
Delete all leaves from a binary tree.
Find two elements in an array whose sum is closest to zero.
Given two rectangles if they overlap or not (Imp)Find max sub square submatrix in a 2d matrix of 0 and 1 with all 1.
Minimum coin problem
Rotate an array by k
Find the level of a given node in a binary tree
Implement heap sort
Implement priority queue.
Find difference in the sum of nodes at odd level and nodes at even level of  a binary tree.
Check for children sum property of a binary tree.
Inorder predecessor in a binary tree
Inorder successor in a binary tree.
Rotate linked list by k nodes
Sort an array of 0,1,2.
Find pair of elements in an array whose sum is equal to given number.
Check whether two strings are anagram.
Given a  linked list , each node has two pointers , one point to next , another to some random node , How to copy it  ?
Get intersection point of two linked lists. (imp)
count nodes in a tree
determine if two binary trees are identical?
Implement binary search algorithm(imp)
sort an almost sorted array with two elements swapped
merge two sorted array without using extra space , assuming first array has enough space
Find minimum distance between two elements in an array
Print all the leaders in an array.
Given a 2d matrix m of 0 and 1 , if m[i][j] is 1 , fill row i and col j with 1
Replac each element of an array with next greatest element.
Find row with max 1 in sorted matrix
Find the number occuring odd number of times in an array , rest occur even number of times.
Given k sorted arrays of size n , merge them.
Find all pythogorean triplets in an array.
Convert sorted array to balanced BST.
Find LIS contigous.
Find LIS non contigous.
Find sub array whose sum equals given number.
Find max diff. between two elements in an array such that larger appears after smaller.
Find majority(occurs more than half) element in an array in O(n).
Even numbers at even pos , odd at odd in an array
Find union and intersection of two arrays.
Find smallest positive number missing from an array.
Shift zeros to end of array
Reverse linkedlist in group of k
Remove spaces from a sentence.
Reverse each word of a sentence
multiply two numbers using min. number of additions
detect cycle in graph
print bottom view of binary tree
print top view of binary treeadd two integers without using +
randomized quick sort
In a 2d matrix , a sub square matrix is painted , find minimal/optimal cost of painting the rest using a fixed block. which block to use ?
Floyd WarshallA 2d matrix containing 0,1,2 , 0 -> empty orange , 1-> fresh orange , 2-> rotten orange , how much time so that all are rotten , a rotten orane will rot adjacent (not diagonal) in one time frame.
Given a binary tree, n and k , find sum of all nodes which are k nodes away from node n.
mirror a binary tree
check if two binary trees are mirror
Convert BST to DLL.
check binary tree is bst
convert sentence like 'these are twelve pens and two shirts. convert it to 'these are 12 pens and 2 shirts'. Inline
Given linkedlist of moves of 2 players on tic tac toe , find who won
Given pile of 9 objects , Pick 1,2,or 3. 2 Players , last one to pick is looser. Give winning strategy.
Given stream of integers , give me median at any time.
Construct BST from pre and inorder
Rod cutting problem
Deletion in bst
Implement using BST
How many bits need to change to convert one num to other?
Check MSB is 0/1 ?
T9 dictionary implement

*****************************ANSWERS******************************

1. Write code to find loop in linkedlist

package dsa;


public class LoopInLinkedList {
 
 class Node{
  int data;
  Node next;
  
  Node(int data){
   this.data=data;
  }
 }
 
 Node head;
 Node tail;
 
 void add(int i){
  Node temp = new Node(i);
  if(head==null){
   head = temp;
  }else{
   temp.next=head;
   head=temp;
  }
 }
 void createLoop(){
  Node temp = new Node(1);
  head=temp;
  tail=temp;
  temp = new Node(2);
  Node node2=temp;
  tail.next=temp;
  tail=temp;
  temp = new Node(3);
  tail.next=temp;
  tail=temp;
  temp = new Node(4);
  tail.next=temp;
  tail=temp;
  temp = new Node(5);
  tail.next=node2;
  tail=temp;
  
 }

 void findLoop(){
  Node slow = head;
  Node fast = head.next;
  
  while(true){
   slow = slow.next;
   fast = fast.next.next;
   if(slow==fast){
    System.out.println("Loop found");
    break;
   }
  }
 }
 
 public static void main(String[] args) {
  LoopInLinkedList l = new LoopInLinkedList();
  l.createLoop();
  l.findLoop();
 }

}

2. Write code to reverse a linkedlist

3. Write code to reverse a string without using any API.

package strings;


public class ReverseString {
 
 static String reverse1(String str){
  StringBuilder sb = new StringBuilder(str);
  return sb.reverse().toString();
 }
 
 static String reverse2(String str){
  char[] arr = str.toCharArray();
  char temp='a';
  for(int i=0;i<=arr.length/2;i++){
   temp = arr[i];
   arr[i]=arr[arr.length-1-i];
   arr[arr.length-1-i]=temp;
  }
  return new String(arr);
 }
 
 public static void main(String[] args) {
  System.out.println(reverse1("Hello how are you?"));
  System.out.println(reverse2("Hello how are you?"));
 }

}

4. Implement Djikstra.
5. Write code for  DFS,BFS,inorder,preorder,postorder,zigzag in tree.
6. Implement quick sort.
7. Implement merge sort.
8. Implement autosuggest feature from a list of words.
9. Implement LRU.
10. Write code to find diameter, height of tree(or binary tree?).