Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively. Notes: – Expected solution is linear in time and constant in space. For example, List 1–>2–>1 is a palindrome. List 1–>2–>3 is not a palindrome. Solution: This method takes O(n) time and O(1) … Read More →
Rotate Matrix By 90 Degree
Problem description: Given an N X N integer matrix, rotate it bye 90 degrees in place.In-place means minimal extra memory to be used, i.e. don’t make a new array to copy into). Rotate clockwise means top-row becomes right-column, right column becomes bottom-row etc. eg. Solution: The idea is to do a “four-way” swap variable, we … Read More →
Combination Sum Problem
Problem: Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2,…, ak) must … Read More →
Find a Peak Element in Array
Question: A peak element in an integer array is defined as an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. … Read More →
Check if Binary Tree is Height Balanced?
Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. The solution presented is a recursive. Find the height of left and right subtrees and check the difference of … Read More →
Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is … Read More →
Find Largest Area Triangle from 2D Matrix
Problem: Given a table of size n * m, with each cell having a color value from the set {r, g, b}, find the area of the largest triangle that has one side parallel with the y – axis (vertical) and has no two vertices that have the same color value. Input : First line … Read More →
Cousin nodes in Binary Tree
Given the binary Tree and the two nodes say ‘p’ and ‘q’, determine whether the two nodes are cousins of each other or not. Solution: What are cousin nodes ? Two nodes are said to be cousins of each other if they are at same level of the Binary Tree and have different parents. For … Read More →
Sort a Linked List of 0s, 1s and 2s
Given a Singly linked list with each node containing either 0, 1 or 2. Write code to sort the list. Input : 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> 0 Output : 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 Solution: … Read More →
Find Buy/Sell Prices in Array of Stock Values to Maximize Profit
Problem: You have given a stock prices for next 10 days. Find out: max benefit in best time complexity in buy and sell 1 share ? Condition: Share must be sold any day after buying date. For ex: Share price in thousands 5 1 4 6 7 8 4 3 7 9 Max benefit 9 – 1 … Read More →
Largest Difference in an Array
You have an array of integers: int[] A = { 10, 3, 6, 8, 9, 4, 3 }; My goal is to find the largest difference between A[Q] and A[P] such that Q > P. If P = 1 and Q = 4 diff = A[Q] – A[P] diff = 9 – 3 diff = … Read More →
Remove Duplicates from a Linked List
Given an unsorted linked list, and without using a temporary buffer, write a method that will delete any duplicates from the linked list. Implemntation: Complexity: O(n^2) If you can sort the list in O(nlogn) then it will take O(nlogn). Post your solution in comments.
What’s going on ?