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
  • Q19: Palindrome Linked list
  • 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.
  • 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.

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