Sample Technical Interview Questions - Part 3

- Q1: Minimum number of moves to equal array elements II
- Q2: Shortest Word Distance
- Q3: Moving average from data stream
- Q4: Add strings
- Q5: Find difference
- Q6: Plus One
- Q7: Word Ladder
- Q8: Evaluate Reverse Polish Notation
- Q9: Factor Combinations
- Q10: Zig Zag Iterator
- Q11: Wiggle Sort
- Q12: Wiggle Sort 2
- Q13: Nested List Weighted Sum
- Q14: Nested List Weighted Sum 2
- Q15: Shortest Word Distance 2
- Q16: Shortest Word Distance 3
- Q17: Permutations 2 (may contain duplicate entries; find unique permutations)
- Q18: Add binary (as strings)
- Q19: Binary Tree Paths
- Q20: Binary Tree right side view.

- Q1: Binary Tree Inorder Traversal (iterative)
- Q2: Minimum depth of a binary tree.
- Q3: Binary Tree Level order Traversal 2: given a binary tree, return the bottom-up level order traversal of its nodes' values.
- Q4: Binary Tree Preorder traversal (iterative).
- Q5: Binary Tree Vertical Order Traversal (from top to bottom, column by column).
- Q6: Top K frequent elements: given a non-empty array of integers, return the k most frequent elements.
- Q7: Find the mode (most frequently occuring element) in a Binary Search Tree. (try a solution without extra space).
- Q8: Decode Ways: given an encoded message containing digits, determine the total number of ways to decode it (dynamic programming).
- Q9: Flip Game 1: Given a string that contains only '+' and '-' characters, you and your friend takes turn to flip two consecutive '++' into '--'. Write a function to compute all possible states of the string after one valid move.
- Q10: Flip Game 2: for the question above, the game ends when a person can no longer make a move and therefore the other person will be the winner. Write a function to determine if the starting player can guarentee a win.
- Q11: Differences between C++03, C++11 and C++14.
- Q12: Sum of perfect square numbers (tricky).
- Q13: Number of Islands (DFS).
- Q14: Inorder successor in BST.
- Q15: Path Sum 2: given a binary tree and a sum, find all root to leaf paths where each path's sum equals the given sum.
- Q16: Add and search word data structure design: desing a data structure that supports the following two operations: void addWord(word) and bool search(word). search(word) should be able to search a literal word or a regular expression containing a-z or a dot (.) character. The dot (.) character represents any one letter (application of Trie Data Structure).
- Q17: Boundary of a binary tree: given a binary tree, return the values of its boundary in anti-clockwise direction starting from the root.
- Q18: Two Sum 3 data structure design: Design and implement a TwoSum class. It should support the add and find operations. The add(int) adds a number to the interal data structure and find(int value) checks whether there exists a pair of numers whose sum is equal to the value.
- Q19: Binary Tree Postorder Traversal (iterative).
- Q20: Flatten Nested List iterator: given a nested list of integers, implement an iterator to flatten it. For example, if the list is [[1, 1], [2,[3, 4]], [1, 1]], the output should be [1, 1, 2, 3, 4, 1, 1].

- Q1: Flatted 2D Vector: implement an iterator to flatten a 2D vector.
- Q2: Construct binary tree from string (consisting of parenthesis and integers).
- Q3: Combination Sum 2: given a collection of candidate numbers (C) and target number (T), find all unique combinations in C where the candidate numbers sums to T.
- Q4: Target Sum: you are given a list of non-negative integers and a target sum S. Find how many ways to assign symbols '+' and '_' to make sum of integers equal to S.
- Q5: Closest Binary Search Tree value: find the value in the BST that is closest to the target.
- Q6: Count the complete tree nodes: given a complete binary tree, count the number of nodes.
- Q7: Integer Replacement: given a positive integer n and two operatios (if n is odd, replace n with either n+1 or n-1; and if n is even, replace n with n/2), find the minimum number of replacements needed for n to become 1.
- Q8: Power of 3: given an integer, write a function to determine if it is a power of 3.
- Q9: UTF-8 validation: given an array of integers representing the data, return whether it is a valid utf-8 encoding.
- Q10: Random Pick index: given an array of integers with possible duplicates, randomly output the index of a given target number (reservoir sampling).
- Q11: Linked list random node: given a singly linked list, return a random node's value from the list such that each node has the same probability of being chosen (reservoir sampling).
- Q12: Compute the max of two numbers without using any branching or looping operation.
- Q13: Max product of word lenghts: given a string of words, find the max value of length(word[i]) * length(word[j]) where the two words do not share common letters.
- Q14: Reverse bits (of a given 32 bit unsigned integer)
- Q15: Permutation in string: given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1 (rolling hash)
- Q16: Find all anagrams in a string: given a string s and a non-empty string p, find all the start indices of p's anagram in s (rolling hash).
- Q17: design Tic-Tac-Toe: can you do better than O(n^2) per move() operation?
- Q18: Course Schedule: given the total number of courses (n) and a list of pre-requisite pairs, is it possible for you to finish all courses? (topological sorting).
- Q19: Course Schedule 2: given the total number of courses (n) and a list of pre-requisite pairs, return the ordering of courses that you should take to finish all courses (topological sorting).
- Q20: Excel sheet column number: given a column title as appear in an excel sheet, return its corresponding column number. For example, A --> 1, Z --> 26, AA --> 27, CA --> 79, etc.

- Q1: Number of squared in an nxn matrix/board.
- Q2: Ugly Numbers (numbers whose prime factors only include 2, 3 & 5).
- Q3: Ugly Numbers 2: find the nth ugly number.
- Q4: Super ugly number (+ve numbers whose prime factors are only those present in a given list of prime numbers of size k).
- Q5: Find all duplicates in an array
- Q6: Find all numbers disappeared in an array: in an array, some elements appear twice and others appear once. Find all elements in the range [1..n] that do not appear in the array.
- Q7: Remove duplicates from Sorted List (II): given a sorted linked list, delete all nodes that have duplicate numbers.
- Q8: Angry kids problem (HackerRank).
- Q9: Count primes: count the number of primes less than a non-negative number n.
- Q10: Polymorphism in C++, pure virtual functions.
- Q11: Private and protected members in C++.
- Q12: Why C++ do not have 'finally' block? RAII (Resource Acquisition Is Initialization). RAII and Smart Pointers in C++, SBRM (Scope Bound Resource Management).
- Q13: Virtual Method Table (VTable), Virtual function Table, vptr
- Q14: What is the use of virtual functions? Open close principle. SOLID Principles in OOD.
- Q15: Thread safety of static variables.
- Q16: Single Number III: given an array in which exactly two elements appear only once and all other elements appear exactly twice. Find the two elements that appear only once.
- Q17: Single Number II: given an array where every element appears thrice except for one, which appears exactly once. Find that single one.
- Q18: Sum of two integers: calculate sum of two integers without using '+' and '-' operators.
- Q19: Find the nth-last node of a singly linked list using only one pass.
- Q20: Difference between Semaphore and Mutex.

- Q1: Difference between HTTP Get, Post and Put methods.
- Q2: Valid Sudoku: determine if a partially filled Sudoku is valid.
- Q3: Minimum index sum of two lists
- Q4: Line reflection: given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points. Could you do it better than O(n^2).
- Q5: Number of Boomerangs: given n points in a plane, find tuple of points (i, j, k) such that distance between i & j is same as the distance between i & k.
- Q6: Remove element: given an array and a value, remove all instances of that value in place and return the new lenght.
- Q7: Remove linked list elements: remove all elements from a linked list of integers that have the value val.
- Q8: Summary ranges: given a sorted array without duplicates, return the summary of its ranges. Give [0, 1, 2, 4, 5, 7], return ["0->2", "4->5", "7"]
- Q9: Missing ranges: given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return the missing ranges. Given [0, 1, 3, 50, 75], return ["2", "4->49", "51->74", "76->99"]
- Q10: Convert to Hexadecimal.
- Q11: Total hamming distance
- Q12: Longest uncommon subsequence 1: given a group of strings, find the longest uncommon subsequence of this group of two strings.
- Q13: Relative ranks: given scores of N atheletes, find their relative ranks and the people with the top three highest scores who will be awarded medals.
- Q14: Array partition 1: given an array of 2n integers, group these integers into n pairs of integers (a1, b1), (a2, b2),... (an, bn) which makes the sum if (ai, bi) as large as possible.
- Q15: Lonely Pixel 1: given a picture consisting of lack and white pixels, find the number of black lonely pixels. The picture is represented as a 2D character array consisting of B and W. Black lonely pixel is a B that is located at a specific position where the same row and the same column don't have any other black pixel.
- Q16: Largest rectangle in Histogram
- Q17: Maximal rectangle: given a 2D binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.
- Q18: Construct string from binary tree. The string is represented as paranthesized version of the tree.
- Q19: Happy number: write an algorithm to determine whether a number is happy. Eg. 19 --> 1^2+9^2 = 82 --> 8^2+2^2 = 68 --> 6^2+8^2 = 100 --> 1^2+0^2+0^2 = 1. So, 19 is happy.
- Q20: Linked list cycle II: given a linked list, return the node where the cycle begins. If there is no cycle, return null.

- Q1: Number of Connected Components in an Undirected Graph.
- Q2: Friend Circles.
- Q3: Spiral Matrix II
- Q4: Graph valid tree: given n nodes & a list of undirected edges, write a function to check whether these edges make make up a valid tree.
- Q5: Soft characters by frequency: given a string, sort it in decreasing order based on the frequency of characters.
- Q6: Sum of left leaves: find the sum of all left leaves in a given binary tree.
- Q7: Beautiful arrangement (google qn).
- Q8: Heaters: you are given positions of heaters and houses on a horizontal line; find out the minimum radius of heaters so that all houses could be covered by those heaters.
- Q9: Kill Process: given n processes, each with it's own unique PID and PPID. Return list of processes that will be killed if given the PID of a process that you want to kill.
- Q10: Generate parenthesis: given n, write a function to generate all valid combinations of well-formed n-pair parenthesis.
- Q11: Letter combinations of a phone number.
- Q12: Tader profit: stock sell-buy problem (from Hackerrank contest).
- Q13: Time Series query: for stock prices (from Hackerrank contest).
- Q14: License key formatting
- Q15: Gray code
- Q16: Compare version numbers.
- Q17: Rotate list: given a list, rotate the list to the right by k places.
- Q18: Palindrome number.
- Q19: Isomorphic Strings: given two strings s & t, determine if they are isomorphic.
- Q20: Zig zag conversion.

- Q1: Elevator algorithm
- Q2: Range Sum Query 2D - Immutable: find the sum of elements defined inside the rectangle defined by its upper left corner and lower right corner.
- Q3: Range Sum Query - Immutable: given an integer array, find the sum of elements between indices i and j inclusive.
- Q4: Rectangle Area: find the total area covered by two rectilinear rectangles in a 2D plane.
- Q5: Arithmetic slices
- Q6: Binary Tree Zig-Zag level order traversal.
- Q7: Average of levels in binary tree: given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
- Q8: Add one row to tree: given the root of a binary tree, value v and a depth d, add a row to the nodes with value v at the given depth d.
- Q9: Contiguous array: given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
- Q10: Contiguous subarray sum: given a list of non-negative numbers and a target integer k, write a function to check if the array has a contiguous subarray of size at least 2 that sums up to the multile of k.
- Q11: Decode string: for example, 3[a]2[bc] should return "aaabcbc".
- Q12: Counting bits: given a non-negative integer number, for even number in the range 0 to num, calculate the number of 1s in their binary representation.
- Q13: Integer to Roman
- Q14: Find the median from data stream.
- Q15: Roman to integer.
- Q16: Bit-wise AND of number ranges.
- Q17: Binary number with alternating bits.
- Q18: Brick wall: draw a vertical line from top to the bottom of the wall such that it crosses least number of bricks.
- Q19: Bulb switcher: there are n bulbs that an initially off. You first turn on all the bulbs. Then you turn off every second buld. On the third round, you toggle every third bulb. And for the ith round, you toggle every ith bulb. Find how many bulbs are in the ON state after n rounds.
- Q20: Find duplicate file in system: given a list of directory paths and all the files with contents in this directory, you need to find out, all the groups of duplicate files in the file system in terms of their paths.

- Q1: Basic Calculator 2: Implement a basic calculator to evaluate a simple expression string (contains only non-negative integers and operators +, -, *, / and spaces).
- Q2: Diagonal Traverse: return all elements of a matrix in diagonal order
- Q3: Top K frequent words
- Q4: Validate IP address (IPV4 and IPV6).
- Q5: Delete node in a BST
- Q6: Search insert position: given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
- Q7: Unique Binary Search Trees: given n, how many structurally unique BSTs can you create that stores integers 1 to n? [Catalan number]
- Q8: Different ways to add parentheses: given a string of numbers and operators, return all possible results from computing all different possible ways to group numbers and operators. For example, 2-1-1 could be grouped as ((2-1)-1) = 0 or as (2-(1-1)) = 2.
- Q9: Valid parentheses string: given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. '*' could be treated as a single right-parentheses or a single left-parentheses or as an empty string.
- Q10: Pacific-Atlantic water flow: given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the pacific ocean touches the left and top edges of the matrix and the atlantic ocean touches the right and bottom edges. Water can only flow in four directions and from a cell to another with height equal to or lower. Find the list of grid coordinates where water can flow to both pacific and Atlantic ocean.
- Q11: Fraction to recurring decimal: given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fraction is repeating, enclose the repeating part in parentheses.
- Q12: Magical string
- Q13: Teemo attacking
- Q14: 132 pattern
- Q15: Serialize and deserialize a BST.
- Q16: Shuffle an array: shuffle a set of numbers without duplicates.
- Q17: Bulls and Cows: write a function to return a hint according to the secret number and friend's guess.
- Q18: Set matrix to zeroes: given an m x n matrix, if an element is zero, set it's entire row and column to 0.
- Q19: Island perimeter: determine the permeter of an element represented by a matrix of 1st and 0s.
- Q20: Minimum time difference: given a list of 24 hour clock time points in HH:MM format, find the minimum minutes difference between any two points in the list.

- Q1: Reconstruct Original Digits from English: given a non-empty string containing out of order representation of digits zero to nine, output the digits.
- Q2: Implement Stack using Queues:
- Q3: Reorder list: given a linked list L0->L1->L2->...->Ln, reorder it to L0->Ln->L1->Ln-1->L2->... For example, given {1, 2, 3, 4}, reorder it to {1, 4, 2, 3}
- Q4: Invert Binary Tree
- Q5: First Bad version
- Q6: Word Pattern: given a pattern and a string 'str', find if 'str' follows the same pattern.
- Q7: Range sum query: : given an integer array, find the sum of elements between i and j. The array is modifiable (segment tree and Fenwick Tree).
- Q8: Partition list: given a linked list and a value x, partition x such that all nodes less than x come before nodes greater than or equal to x.
- Q9: Remove duplicate letters: given a string that only contains lower case letters, remove duplicate letters so that every letter appear only once.
- Q10: Flood fill
- Q11: Clone graph
- Q12: Delete a node from a doubly linked list.
- Q13: Mini parser: given a nested list of integers represented as a string, implement a parser to deserialize it.
- Q14: Buffer class with undo/redo functionality
- Q15: Subarray sum equals K: given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
- Q16: Rectangle overlap: given two axis-aligned rectangles, return whether they overlap.
- Q17: Queue reconstruction by height
- Q18: Longest increasing path in a matrix.
- Q19: Longest substring with at least 'k' repeating characters.
- Q20: Longest substring with at most 'k' distinct characters

- Q1: Bomb enemy: given a 2D cell, each cell being a wall (W), enemy (E) or empty (0), find max enemies you can kill using the bomb
- Q2: Word Square: given a set of words, find all word squares you can build from them.
- Q3: Valid word square: given a set of words, check whether it forms a valid word square.
- Q4: Sentence screen fitting: given a row x col screen, and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.
- Q5: Binary tree longest consecutive sequence: given a binary tree, find the longest consecutive sequence path.
- Q6: Binary tree longest consecutive sequence II
- Q7: Next closest time: given a time represented in the format 'HH:MM', form the next closest time by rearranging the current digits.
- Q8: Unique email addresses
- Q9: Longest absolute file path
- Q10: Shortest distance from all buildings: you want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can given a 2d grid of values 0, 1 & 2 (0 is empty, 1 is building, 2 is obstacle).
- Q11: Encode and Decode strings: the encoded string is sent over the network and decoded back to the original set of strings.
- Q12: Triangle: given a triangle, find the minimum path sum from top to bottom; each step you may move to adjacent numbers on the row below.
- Q13: Strobogrammatic numbers: write a function to determine if a number is strobogrammatic.
- Q14: Strobogrammatic numbers II: find all strobogrammatic numbers that are of length n.
- Q15: Range addition: problem solved using range caching technique.
- Q16: Unique word abbreviation
- Q17: 3Sum smaller: given an array of n integers 'num' and a target, find the number of index triples i, j, k that satisfy the condition nums[i] + nums[j] + nums[k] < target.
- Q18: Reverse vowels of a string
- Q19: Longest word in dictionary through deleting: s = 'abpcplea' and dict = ['ale', 'apple', 'monkey', 'plea'], the output should be 'apple'.
- Q20: Evaluate division: equations are given in the format 'a/b=k', where 'a' and 'b' are variables represented as strings and 'k' is a real number; given some queries, return the answers.