Data Structure Interview Questions

Check if a Singly Linked List is Palindrome

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.