- Q1: Chocolate distribution problem.
- Q2: Maximum size square sub-matrix of a given matrix (of 0s and 1s) with all 1s.
- Q3: Find row of the matrix (of 0s and 1s) with max number of 1s.
- Q4: Find max sum of leaf-to-root path in a binary tree.
- Q5: Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other. Order of the elements should be retained.
- Q6: Rearrange positive and negative numbers alternatively in O(n) time and O(1) extra space.
- Q7: Rearrange positive and negative numbers in O(n) time and O(1) extra space.
- Q8: Merge k sorted arrays.
- Q9: Construct Tree from given Inorder and Preorder traversals.
- Q10: Construct a binary tree from postorder and inorder traversals.
- Q11: Connecting n ropes with minimum cost.
- Q12: Find the longest palindromic substring. Desired time complexity is O(n^2) and space complexity is O(1).

- Q1: How to implement undo/redo functionality?
- Q2: How strtok() split strings into tokens in C?
- Q3: Given a list of array, returns a list of arrays, where each array is a combination of one element in each given array.
- Q4: Longest Increasing subsequence (DP solution).
- Q5: Combination sum: given a set of candidate numbers (C) and a target number (T), find all unique combinations in C, where the candidate nummbers sums to T.
- Q6: Lenght of the longest common subsequence.
- Q7: Print the longest common subsequence.
- Q8: Longest Palindromic subsequence.
- Q9: Find the k most frequenct words in a file.
- Q10: Power set.
- Q11: Relative sorting: sort an array according to the order defined by another array.
- Q12: Inversion count for a given array.

- Q1: Partition Function (Quicksort)
- Q2: Nuts and Bolts Problem (Lock & Key problem)
- Q3: Amend the sentence (put space between words, convert uppercase to lowercase)
- Q4: Orientation of 3 ordered points (clockwise, counterclockwise, collinear)
- Q5: Check if two line segments intersect (using orientation technique)
- Q6: Count all distinct pairs in an integer array with difference equal to k.
- Q7: Sort an array of 0s, 1s and 2s (Dutch National flag problem).
- Q8: Multiply large numbers as strings.
- Q9: Dijkstras's shortest path algorithm.
- Q10: Deleting a node in a BST.
- Q11: Construct BST from a preorder traversal.
- Q12: Serialize/Deserialize a binary tree.

- Q1: Remove duplicates from a sorted linked list.
- Q2: Remove duplicates from an unsorted linked list.
- Q3: Detect cycles in an undirected graph.
- Q4: Write a linked list class along with append function (add node to the end) and destructor function.
- Q5: Given two numbers in the form of a singly linked list in such a way that the most significant bit is at the end (e.g., 123 will be 1 -> 2 -> 3), write a function that takes arguments as pointers to the head of the lists and returns pointer to the head of another linked list which represents the added number.
- Q6: Add two numbers represented as lists (similar to the above question) such that the most significant bit is at the tail.
- Q7: Find the pairs with a given sum in a doubly linked list.
- Q8: Given a string, find its first non-repeating character.
- Q9: Trie data structure (insertion, search).
- Q10: k''th non-repeating character in a string.
- Q11: How to implement a search engine?
- Q12: Given a text file, find the positions that the word occurs in the file (you have to find positions of many words in the same file).

- Q1: Multiply two matrices (in O(n^3))
- Q2: Implement sizeof
- Q3: The 2 Egg puzzle.
- Q4: Find types and values of the expressions.
- Q5: Find error in code.
- Q6: Given a boolean matrix, modify it such that if m[i][j] is 1, then make all the i'th row and j'th column as 1.
- Q7: Given a set of time intervals, merge all overlapping intervals into one.
- Q8: Find the repeating and the missing number in the array.
- Q9: 3 ants on a triangle riddle.
- Q10: Pots of gold game (classic dynamic programming qn)
- Q11: Right view of a binary tree.
- Q12: Max product subarray: given an array containing both positive and negative numbers, find the product of the max product subarray. Expected time complexity O(n) and space complexity O(1).

- Q1: Maximum difference between 2 elements such that larger element appears after the smaller number.
- Q2: Stock Buy Sell to Maximize Profit – 1 (sell stock before you buy again)
- Q3: Stock Buy Sell to Maximize Profit – 2
- Q4: Product array except itself: given an array of integers, return output array such that output[i] is equal to the product of elements except input[i]. Solve it without division & in O(n).
- Q5: Union and intersection of two sorted arrays.
- Q6: Union and intersection of two unsorted arrays.
- Q7: Length of the longest substring without repeating characters.
- Q8: Arrange given numbers to form the biggest number.
- Q9: Minimum number of jumps to reach end (dynamic programming).
- Q10: Special Stack data structure which has get_min() operation. Requirement: push(), pop, top() and get_min() has to be executed in O(1) time complexity.
- Q11: Unique paths count (dynamic programming).
- Q12: Merge two sorted arrays: given two sorted arrays a1 and a2, merge a2 into a1 as one sorted array. Assume a1 has enough space to hold additional elements from a2.
- Q13: 3Sum (set 1) - find a triplet that sums to a given value (expected complexity: O(n^2))
- Q14: 3Sum (set 2) - all unique triples.
- Q15: 3Sum (set 3) - get the closest triplet that sums to a given target.

- Q1: Reverse Integer
- Q2: Find duplicate number: given an array containing n+1 integeres, where each integer is between 1 & n. Assume there is only one duplicate number, find it.
- Q3: Container with most water.
- Q4: Lexicographhical numbers: example: 13 should give [1, 10, 11, 12, 2, 3, 4, ..., 9]
- Q5: Kth largest element in an unsorted array.
- Q6: Symmetric tree: given a binary tree, check whether it's a mirror of itself (symmetric around center).
- Q7: Palindrome permutation: determine if a permutation of the string could form a palindrome.
- Q8: Factorial trailing zeroes: find number of trailing zeroes in n!.
- Q9: Palindrome partitioning: partition string such that every substring is a palindrome. Example: s = "aab", output: [["aa", "b"], ["a", "b", "b"]].
- Q10: Remove duplicates from a sorted array.
- Q11: Binary search tree iterator: next() and hasNext() functions.
- Q12: Find peak element (divide and conquer).
- Q13: Find local minima in an array (divide and conquer).
- Q14: Flatten a binary tree into a linked list.
- Q15: Water and Jug problem: given 2 jugs with capacities x and y, find if you can measure exactly z litres using them.
- Q16: Minimum number of arrows to burst balloons (greedy).
- Q17: Valid palindrome: given a string, determine if it's a palindrome.
- Q18: Rotate image by 90 degree clockwise.
- Q19: Add digits: find the digital root.
- Q20: Find bottom left tree value: given a binary tree, find the leftmost value in the last row of the tree.

- Q1: House Robber (dynamic programming)
- Q2: House Robber 2 (dynamic programming)
- Q3: Coin Change (dynamic programming)
- Q4: Paint Fence (dynamic programming)
- Q5: Russian Doll Envelopes
- Q6: Valid Parentheses
- Q7: Longest Common Prefix
- Q8: Word Search (DFS)
- Q9: Count and say.
- Q10: Meeting Rooms
- Q11: Median of two sorted arrays (divide & conquer)
- Q12: Valid perfect square
- Q13: Is subsequence
- Q14: Insert, Delete, GetRandom in O(1).
- Q15: Design Tiny URL
- Q16: Sliding Window Maximum
- Q17: Search a 2D Matrix II
- Q18: Search a 2D Matrix I
- Q19: Palindrome Linked list
- Q20: Hamming Distance (bit manipulation)

- Q1: Permutation Sequence
- Q2: Word Break (dynamic Programming)
- Q3: H-Index
- Q4: Fork & copy-on-write.
- Q5: How malloc() and free() work?
- Q6: Memory layout of C programs.
- Q7: Data Structure for Phone book/contacts.
- Q8: Read N characters given Read4() II - call mutiple times.
- Q9: Read N characters given Read4() - call once.
- Q10: Swap nodes in pairs.
- Q11: Missing number: given array containing n distinct numbers, find the one that is missing.
- Q12: First missing postive number.
- Q13: Intersection of two arrays.
- Q14: Power of 4: given a signed integer (32 bits), check whether if it's a power of 4.
- Q15: Game of life: write a function to compute the next state of the board given its current state.
- Q16: Majority element (Boyer-Moore algorithm)
- Q17: Majority element II - find all elements that appear more than n/3 times.
- Q18: Nim Game
- Q19: Ordered map implementation using BST & Hashtable.
- Q20: Singleton design pattern: restrict the instantiation of a class to one object.

- Q1: Sort strings by length.
- Q2: Print linked list in reverse order without reversing it.
- Q3: Given an array of n non-negative integers, find the frequency of a particular element in arbitrary range.
- Q4: Max depth of a binary tree.
- Q5: Contains duplicate I: given an array of integers, find if the array contains duplicates.
- Q6: Contains duplicate II: find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
- Q7: Repeated DNA sequences.
- Q8: Search for a range: given an array of sorted integers, find the starting and the ending position of a given value (with complexity O(log n))
- Q9: Find the leaves of a binary tree and repeatedly delete leaves until empty.
- Q10: Valid number: validate if a string is numeric.
- Q11: Insert interval: insert a new interval to a given set of intervals and merge if necessary.
- Q12: Minimum window substring: find the smallest window in a string containing all characters of another string.
- Q13: Minimum size subarray sum: find the minimum lenght of a contiguous subarray of which the sum >= s.
- Q14: Ternary expression parser.
- Q15: Max points on a line: given n points on a 2D plane, find the max number of points that lie on the same straight line.
- Q16: Find the largest value in each tree row.
- Q17: Lowest Common Ancestor of a BST.
- Q18: Lowest Common Ancestor of a binary tree.
- Q19: Increasing triplet subsequence: find a sorted subsequence of size 3 in linear time.
- Q20: Minimum moves to equal array elements: find the minimum number of moves required to make all array elements equal, where a move is incrementing n-1 elements by 1.

Sample Technical Interview Questions - Part 2