Given a number “n”, find the least number of perfect square numbers that sum to n For Example: n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1) n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + […]
Given a binary tree and two nodes. Find Least Common Ancestor (LCA) of the two nodes. For example given the tree T below. LCA(T, 5, 6) = 3, LCA(T, 4, 6) = 1, etc. 1 / \ 2 3 / / \ 4 5 6 \ / 7 8 With parent pointer If we are […]
Given a 2D array of 1 and 0, Find the largest rectangle of 1’s or 0’s ie. rectangle (may not be square) which is made up of all 1’s or 0’s. For example, A = 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 Then the largest rectangle is […]
Given a binary search tree. Find the kth smallest element in the BST. A quick solution would be to perform a modified inorder traversal with an extra parameter k. Each time inorder traversal is popping a node out of recursion/call stack (i.e. unwinding a recursion)then we keep decreasing the k. When k=0 then the current […]
Given an array of integer. Find the kth smallest element in the array in a most efficient manner. For example: A = [2, 1, 0, 3, -1, 3] and k=3 then the 3rd smallest element is 1. This is also (6-3) = 3rd largest element. A trivial solution is to sort the array. But question […]
Given two sorted arrays find the element which would be kth in their merged and sorted combination. For example, A=[1, 1, 2, 3, 10, 15] and B=[-1, 2, 3, 4, 6, 7] then k=8th smallest element would be 4 as it appears in 8th position of the merged sorted array=[-1, 1, 1, 2, 2, 3, […]
Given n and k, return the k-th permutation sequence of permutations of numbers {1,2,..,n}. Note: Given n will be between 1 and 9 inclusive. By listing and labeling all of the permutations in order, we get the following sequence (ie, for n = 3): “123” “132” “213” “231” “312” “321” Then, k=5th permutation sequence will […]
Given an array containing N points find the K closest points to the origin in the 2D plane. You can assume K is much smaller than N and N is very large. Notice the key requirement here: “K is much smaller than N. N is very large”. Definitely the brute-force solution by finding distance of […]
Usual approach using linear space (stack) We can easily do the traversal by using a stack where we keep pushing left. If no left is there then we pop an element to print it and then push its right. This is O(n) time and O(n) space algorithm. public static void InorderTraversal(BTNode root){ Stack<BTNode> stack […]
Why is it needed? When data is stored on disk based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to […]