Sample Technical Interview Questions - Set 11 (12 Questions) (Pages 103)

• 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).

Sample Technical Interview Questions - Set 12 (12 Questions) (Pages 170)

• 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.

Sample Technical Interview Questions - Set 13 (12 Questions) (Pages 179)

• 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.

Sample Technical Interview Questions - Set 14 (12 Questions) (Pages 124)

• 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).

Sample Technical Interview Questions - Set 15 (12 Questions) (Pages 85)

• 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).

Sample Technical Interview Questions - Set 16 (15 Questions) (Pages 153)

• 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.

Sample Technical Interview Questions - Set 17 (20 Questions) (Pages 185)

• 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.

Sample Technical Interview Questions - Set 18 (20 Questions) (Pages 205)

• 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
• Q20: Hamming Distance (bit manipulation)

Sample Technical Interview Questions - Set 19 (20 Questions) (Pages 237)

• 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.
• 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.

Sample Technical Interview Questions - Set 20 (20 Questions) (Pages 194)

• 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