DS Overlapping Problem

  1. Tree and Stack –  Iterative Postorder Traversal | Set 1 (Using Two Stacks) and  Iterative Postorder Traversal | Set 2 (Using One Stack)  and Check if a given array can represent Preorder Traversal of Binary Search Tree
  2. Tree and Stack – Print ancestors of a given binary tree node without recursion
  3. Tree and Deque – Sliding Window Maximum (Maximum of all subarrays of size k)   – Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
  4. Hashing and Tree – Print a Binary Tree in Vertical Order
  5. Hashing and Tree – Advantages of BST over Hash Table
  6. Tree and Hash – Given an unsorted array with repetitions, the task is to group multiple occurrence of individual elements. The grouping should happen in a way that the order of first occurrences of all elements is maintained.
  7. Tree and Queue – Iterative Method to find Height of Binary Tree
  8. Tree and Linked List – Construct Complete Binary Tree from its Linked List Representation
  9. Convert a given Binary Tree to Doubly Linked List | Set
  10. [Done] ***Queue and Stack – Code – Implement Queue using Stacks (using 2 stack)
    We create two stack, s1 and s2. s1 is the one where all queue operation happen. When we need to dequeue, we move all s1 item to s2 and pop from s2, until s2 is empty. This will have a FIFO effect. Now we keep popping from s2(for every dequeue op) until it’s empty and meanwhile all push op will be in s1.  When s2 is empty and another dequeue op is needed we pop all s1 to s2.
  11. Graph and Stack – Iterative Depth First Traversal of Graph
  12. Stack/Queue and Tree – Algo to invert a Binary Tree
  13. Stack and Queue – Implement a stack using single queue
  14. [Done] ***Stack and Queue – Implement Stack using Queues – two approach – check here
  15. [Done] * Stack and Linked List – Stack Implementation using Linked List – Simple.
    Stack is LIFO. Keep adding(pushing) new item to head and keep removing(popping) from  head. Peek is also just to show head data.
  16. Sort and Doubly Linked List – Quick Sort and Merge
  17. Stack and Doubly Linked List – Design a stack with operations on middle element. How to implement a stack which will support following operations in O(1) time complexity – push(), pop(), findMiddle(), deleteMiddle();
  18. [Done] Queue and Linked List – How to use Queue with Linked List  Implementation Code. This is pretty straight forward. We just need to create a Linked List class will be used as out node. In our Queue class we will need to maintain front and rear(which will be reference to the Linked List Node created to hold). Rest we just need to keep maintaining these front and end as and when we queue and dequeue nodes from the queue. Handle the case of empty queue(when both front and rear are null).
  19. *** Linked List and Sorting – Sort a Linked List using Merge Sort
  20. Tree and Linked List – Tree to Linked List – Byte-by-byte
  21. [Done] Linked List and Hashing – Union and Intersection of two Linked Lists
  22. Tree and Queue – Check whether a given Binary Tree is Complete or not
  23. [Done] Implement Stack using Queue –
      Using One Queue  – when we queue an element to the queue we dequeue all the other element one by one and enqueue them, remove the element and enqueue it and then do the same with the next element. This happens in a loop size -1 time, this will cause the last element added to get to the front of the queue.
    We do this for every element that’s added to the queue. So the pop operation will pop the last element added, LIFO like a stack.
      Using Two Queue  –  Idea is to push elements into the Queue “mainQueue” and while popping element, pop all elements except the last element one by one from “mainQueue” to temporary Queue “tempQueue”, return the last element and initialize “mainQueue” with “tempQueue”.
    One small but impactful change we do is, while copying tempQueue to mainQueue, we do not actually copy the data but initialize mainQueue = tempQueue and reinitialize the tempQueue. Basically renaming temp to main and creating a new temp.
    mainQueue = tempQueue;
    tempQueue = new LinkedList();
  24. Sort and Queue – Sort a queue using quick sort
  25. Sort and Linked List – QuickSort on Singly Linked List
  26. Insertion Sort and Linked List – Sort linked list which is already sorted on absolute values
  27. Merge Sort and Linked List – Point to next higher value node in a linked list with an arbitrary pointer
  28. Sort and Linked List – Merge Sort for Linked Lists –
    • Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
  29. BFS and DFS Flood FillWiki
  30. BST and array – Majority element in array
  31. BST and Array – Count number of occurrences (or frequency) in a sorted array
  32. HEAP – http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s