Skip to content

Latest commit

 

History

History
303 lines (254 loc) · 12 KB

todo.md

File metadata and controls

303 lines (254 loc) · 12 KB

TODO

  • Manacher

https://leetcode.com/problems/maximal-rectangle/ 85 https://leetcode.com/problems/number-of-islands/ 200

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/776/ https://leetcode.com/problems/task-scheduler/ 621 https://leetcode.com/problems/group-anagrams/ 49 https://leetcode.com/problems/longest-valid-parentheses/ 32 https://leetcode.com/problems/knight-probability-in-chessboard/ 688 https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/ 381

https://leetcode.com/problems/clone-graph/ 133 https://leetcode.com/problems/course-schedule/ 207 https://leetcode.com/problems/pacific-atlantic-water-flow/ 417 https://leetcode.com/problems/unique-morse-code-words/ 804 https://leetcode.com/problems/maximum-length-of-pair-chain/ 646 https://leetcode.com/problems/profitable-schemes/ 879

Reorder Data in Log Files ⭐⭐⭐ [Experienced] Optimal Utilization ⭐⭐⭐ [Experienced] Min Cost to Connect Ropes / Min Time to Merge Files ⭐⭐⭐[Experienced] Treasure Island / Min Distance to Remove the Obstacle (BFS) ⭐⭐⭐ [Experienced] Treasure Island II (Multi-source BFS) Find Pair With Given Sum (a.k.a. Sort Center) ⭐ [Experienced] Copy List with Random Pointer ⭐⭐ [New Grad] Merge Two Sorted Lists ⭐⭐ [New Grad] Subtree of Another Tree ⭐⭐ [New Grad] Search a 2D Matrix II ⭐⭐ [New Grad] Critical Connections ⭐⭐ [New Grad] Favorite Genres ⭐⭐ [New Grad] Two Sum - Unique Pairs ⭐⭐ [New Grad] Spiral Matrix ⭐ [New Grad] Count substrings with exactly K distinct chars ⭐ [Intern] Path With Maximum Score ⭐ [Intern] Longest Palindromic Substring ⭐ [Intern] Movies on Flight ⭐ [Experienced] Distance Between Nodes in BST Most Common Word ⭐ [Intern] K Closest Points to Origin Find Pair With Max Appeal Sum Min Cost to Connect All Nodes (a.k.a. Min Cost to Add New Roads) Min Cost to Repair Edges (MST) Prison Cells After N Days Substrings of size K with K distinct chars Partition Labels Subtree with Maximum Average

paranthesis create bst minimum spannign tree K’th Smallest/Largest Element in Unsorted Array

DP https://leetcode.com/problems/word-break/ https://leetcode.com/problems/longest-common-subsequence/

Ebay

  • steve

    • linked list
    • --common ancestor
    • string
    • search & sort
    • --compute avg of numbers, floats, buffer over under flow, unit test
    • substring, etc,
    • design browser, data structure

  • others

    • implement sliding window protocol, array , queue, how multithreading, blocking concurrent queue
    • alert monitoring service
    • 3 tier arch
    • stateless service
    • pub sub mechanism
    • cycles in linked list, in O(n)
    • 2 phase commit protocol
    • --queue with 2 stack
    • hashtable implement
    • lru
    • read write lock, multithreading
    • distributed key value
    • design alert system

  • Find the least common ancestor (LCA) in a binary tree. Pointer from node to parent is NOT present. Design the tree node and write the method that returns the LCA

  • Given a circularly rotated array [3 5 6 7 8 -3 -1 -1 1 2] design an algorithm to find an element in an efficient way.

  • What do you know about concurrency? Describe in minute detail

  • How will you develop a ReadWriteConcurrentLock?

  • What do you know about websockets, long polling, short polling etc.?

  • Simple Database questions. Join queries etc.

Others

BellmanFord reverse linked list add binary numbers is binary tree balanced

P35 P50 P51 P52 P53 P54

C16Q20 C8Q6 C8Q7 C8Q8 C8Q12

L55 L93 L134 L236

http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/

Sudoku problems

Design a stack of integers in which we can get its minimum number with a function Min. The time complexity of Min, Push, and Pop should be all O(1). The interesting part is to design such stack without using any extra auxiliary memory/data structure. You can use a constant variable though.

QOTD: given an array that contains zero, positive and negative integers. find the product of the maximum product subarray ? O(n) time and constant space.

Given a set of non-overlapping & sorted intervals, insert a new interval into the intervals (merge if necessary).

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Find Common Ancestor of given list of nodes in a Binary Tree

Q1: Maximum square area in a 2D array of elements 0s and 1s. It's a square iff when sub array(s) of N X N contains all 1s.

Q2: Make a MinStack class, with min operation (returns the minimum value of the stack) along with basic operations push, pop and top.

Q3: Find number of ways you can reach from the top of a 2-D array to the bottom right corner. You can go either right or down (one step) from current cell.

Q4: Same as Q3, but now you are given a 2-D array which can have guards in the cell (denoted as -1), then you cannot pass through that cell. Find number of ways to reach to the bottom right corner.

Q5: Count the number of connected components in a given graph. Build your own graph from given input: N: number of vertices (starts with 1; if n = 5, there will be 5 vertices: 1,2,3,4,5) Edges: Array of arrays. E.g. [[1,2], [2,7], ..]

Q6: Topological sorting of directed acyclic graph.

===============================================

Find the closest node in BST Finding two numbers in an array summing up to a given input Find H index (Leetcode question) Convert Sorted Linked List to Binary Search Tree How to find a number which exist odd times in a list Maximum of all subarrays of size k (Added a O(n) method) Write a program to check whether it is a valid binary tree or not. Multiply two numbers represented by linked lists Diameter of a Binary Tree Dynamic Programming | Set 17 (Palindrome Partitioning) convert.toint32 implementation diff of two numbers without airthmetic operation string to int bindary tree implementation given binary tree and two numbers, find the root node of the two.... in case of BSt and other cases too

convert roman numerals into decimals, object modeling a parking lot attendant, Merge two arrays Find Excel column name from a given column number

  • https://en.wikipedia.org/wiki/Open_Shortest_Path_First

  • https://en.wikipedia.org/wiki/Link-state_routing_protocol

  • https://en.wikipedia.org/wiki/Border_Gateway_Protocol

  • https://en.wikipedia.org/wiki/OSI_model

  • Arrays/Strings:

    • Determine if a string is a palindrome
    • Merge two sorted arrays
    • Reverse an array in place
    • Find substring
    • All sorting algorithms
    • Binary search in a sorted rotated array
    • Max profit stock problem
    • Matrix multiplication
    • Find all duplicates in an array
    • Print a matrix in a spiral manner

  • Linked List:

    • Reverse a singly linked list
    • Delete/Insert a node in a linked list
    • Detect if there is a cycle in the list and return its starting point
    • Merge two sorted lists
    • Split a list into two lists one has even indexes other has odd indexes

  • Trees:

    • Check if tree is balanced
    • All traversals, recursive and iterative implementations
    • BFS/DFS
    • Construct a BST from a sorted array
    • Check if two trees are mirror image of each other
    • Find max path sum in the tree, negative nodes possible
    • Lowest common ancestor of 2 nodes in a tree

  • Backtracking:

    • Find all permutations or combinations
    • Find all possible subsets
    • N queens problem
    • Convert numbers into words according to letters on an old phone keypad

  • Hashtables:

    • Questions where you need to keep track of multiple occurences of same object
    • Questions where you want to have a 2 tuple as a key

  • Dynamic programming:

    • Given you can climb 1, 2, or 3 stairs in one step, how many ways of reaching the top
    • How many ways to go from top left of a grid to bottom right of the grid with some obstacles in between
    • Implement both bottom up and top down solutions for both of the above
  1. Returns the largest value in an array of non-negative integers
  2. Create Single Linked list (SLL)
  3. Create Double Linked List (DLL)
  4. Create Circular Linked list (using single) (CSLL)
  5. Create Circular Linked list (using double) (CDLL)
  6. Insert node in front of SLL
  7. Insert node in end of SLL
  8. Traversing SLL
  9. Delete element from SLL
  10. Delete all nodes from SLL
  11. Insert node at random location in SLL
  12. Create Stack using LL
  13. Create Stack using dynamic array
  14. Delete and InsertAfter in SLL with Head & Tail
  15. Find mth to last element in SLL
  16. List flattening
  17. List un-flattening
  18. Check if list is Cyclic or Acyclic
  19. Create Generic Tree
  20. Create Binary Tree
  21. Create Binary Search Tree
  22. Find a node in Tree
  23. Create Heap
  24. Tree search using breadth first search (BFS)
  25. Tree search using depth first search (DFS)
  26. Pre-Order Traversal on tree
  27. In-Order Traversal on tree
  28. Post-Order Traversal on tree
  29. Height of Tree
  30. PreOrder without recursion
  31. Lowest Common Ancestor
  32. Heapify BT
  33. Unbalanced BST
  34. Clone Linked list with next and random pointer. Return head of cloned list

http://www.programcreek.com/2014/05/leetcode-divide-two-integers-java/ https://sites.google.com/site/spaceofjameschen/annnocements/merge3sortedarrays https://codebysteven.wordpress.com/2016/03/15/leetcode-find-the-middle-of-a-linked-list/ http://www.geeksforgeeks.org/merge-one-array-of-size-n-into-another-one-of-size-mn/

Google Code Jam https://code.google.com/codejam/contest/3264486/dashboard https://code.google.com/codejam/contest/5304486/dashboard#s=p0

Miller Rabin https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem Bin packing problem https://en.wikipedia.org/wiki/Bin_packing_problem Edit distance https://en.wikipedia.org/wiki/Edit_distance

Finding the vertical sum in a binary tree finding vertical sum of a 'n' ary tree

Q 1 . F IN D T H E M O D E O F G IVE N AR R AY In statistics maths, a mode is a value that occurs the highest numbers of time.Given an array of integer (upto 100k elements), find the mode. Solution Guidance: 1.Time: O(n), Space O(n) 2.Time: O(nlog n), Space O(1) -May destroy existing array. 3.Time: O (n2), Space O(1)

Q2 . H O P P IN G T O T H E V I C T ORYGiven an array of non-negative integers, each number representing the maximum jump you can make from that spot. From spot i, you can to go any location from i to i+a[i]–Find the minimum number of jumps you need to make to go from a[0] to a[n-1].

Q 3 . F IN D L O N G E S T P O S I T IVE S U B-AR R AYGiven an array of integers, find the indices x and y to maximize y-x, such that i=x to y, and a(i) >= 0. Example: Input: 1,-6,2,-1,4,-3 Output: x=0, y=5, Sum = 0

Q1. FIND THE CLOSEST NUMBERWrite a function that accepts an integer, and returns a number that is closest number you can find in a binary search tree. Solution Guidance (where n is the number of nodes in the tree) 1.Time: O(n)–Ok 2.Time: O(log n)-Good

Q2. MIRROR MIRROR ON THEWALLWrite a function thataccepts a binary tree (may not be fully formed), and returns true if the Left Subtree is a mirror image of the Right Sub Tree. Solution Guidance: 1.Time: O(n) –Traverse every element only once.

Q3. MAKE ME A MIRRORGiven a Binary Tree, assume fully formed, you are permitted to “exchange”the values of any two arbitrary nodes. Find the minimum number of “swaps”you need to make to transform thistree to a mirrored tree. If any number of swaps will not transform this, return -1