QUESTIONS.md

Technical Interview Questions

General

• Find the most frequent integer in an array

• Find pairs in an integer array whose sum is equal to 10 (bonus: do it in linear time)

• Given 2 integer arrays, determine if the 2nd array is a rotated version of the 1st array

  Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3}

• Write fibonacci iteratively and recursively (bonus: use dynamic programming)

• Find the only element in an array that only occurs once

• Find the common elements of 2 int arrays

• Implement binary search of a sorted array of integers

• Implement binary search in a rotated array (ex. {5,6,7,8,1,2,3})

• Use dynamic programming to find the first X prime numbers

• Write a function that prints out the binary form of an int

• Implement parseInt

• Implement squareroot function

• Implement an exponent function (bonus: now try in log(n) time)

• Write a multiply function that multiples 2 integers without using *

• Given n points, return the top k points that are closest to the origin

• We’re going to find “Word Twins”, which are pairs of English words, at least 4 letters long, where the first three letters of one are the last three letters of another. For example, “strategy” and “Egypt”

• Given a 3*3 matrix with the numbers 1-8 in random order and a space in the middle spot: Write code to find the min exchange of numbers to put the matrix in order

        5 4 1           1 2 3
        3   2   --->    8   4
        7 8 6           7 6 5
  

• For k parenthesis, write code to calculate how many permutations they could have For 2 parenthesis, there are 2 permutations: ()() and (())

• HARD: Given a function rand5() that returns a random int between 0 and 5, implement rand7()

• HARD: Given a 2D array of 1s and 0s, count the number of "islands of 1s" (e.g. groups of connecting 1s)

Strings

• Find the first non-repeated character in a String
• Reverse a String iteratively and recursively
• Determine if 2 Strings are anagrams
• Check if a String is a palindrome
• Check if a String is composed of all unique characters
• Determine if a String is an int or a double
• HARD: Find the longest palindrome in a String
• HARD: Print all permutations of a String
• HARD: Given a single-line text String and a maximum width value, write the function 'String justify(String text, int maxWidth)' that formats the input text using full-justification, i.e., extra spaces on each line are equally distributed between the words; the first word on each line is flushed left and the last word on each line is flushed right

Trees

• Implement a BST with insert and delete functions
• Print a tree using BFS and DFS
• Write a function that determines if a tree is a BST
• Find the smallest element in a BST
• Find the 2nd largest number in a BST
• Given a binary tree which is a sum tree (child nodes add to parent), write an algorithm to determine whether the tree is a valid sum tree
• Find the distance between 2 nodes in a BST and a normal binary tree
• Print the coordinates of every node in a binary tree, where root is 0,0
• Print a tree by levels
• Given a tree, verify that it contains a subtree
• Convert a binary tree to a doubly linked list
• HARD: Find the max distance between 2 nodes in a BST
• HARD: Construct a BST given the pre-order and in-order traversal Strings

Stacks, Queues, and Heaps

• Implement a stack with push and pop functions
• Implement a queue with queue and dequeue functions
• Find the minimum element in a stack in O(1) time
• Write a function that sorts a stack (bonus: sort the stack in place without extra memory)
• Implement a binary min heap. Turn it into a binary max heap
• HARD: Implement a queue using two stacks

Linked Lists

• Implement a linked list (with insert and delete functions)

• Find the Nth element in a linked list

• Remove the Nth element of a linked list

• Check if a linked list has cycles

• Given a circular linked list, find the node at the beginning of the loop.

  Ex. A-->B-->C --> D-->E -->C, C is the node that begins the loop

• Check whether a linked list is a palindrome

• Reverse a linked list iteratively and recursively

• Given a linked list, where each node has a link to a random node in the list, make a copy of the entire list

• Given a singly LL A->B->C->D->E->F... convert to B->A->D->C->F->E...

Sorting

• Implement bubble sort
• Implement selection sort
• Implement insertion sort
• Implement merge sort
• Implement quick sort

BSTs, Heaps, Search Algorithms, Sort Algorithms, Intersection, median, hashmap, caching system, basic algorithms

• Basic bitwise operations

• How do you program a min heap using Nodes

• Find the max value in an array. The array is "semi-sorted"

  Ex. { 1 3 4 7 9 10 12 13 12 6 3 }

• Write a code that accepts integers as arrays and outputs the multiplication result as an array

• Write a code that takes the coordinates of multiple rectangles as input and returns as output the coordinates of the rectangle that is the intersection of all the rectangles

• Typical low level CS questions about sorting algorithms and operational cost

• Median finding algorithm - find the median of 'n' numbers and a little bit of binary search tree implementation

• Find the largest rectangle with all 0s in an matrix with only 0 and 1

• Convert char string to integer

• Find occurrences of a number in sorted array (allow duplicates)

• If integer array used to store big integers (one integer store one digit), implement arithmetic operations

• How do you build a heap?

• What is the optimized version of the knn algorithm?

• Write a recursive function to calculate pascal's pyramid numbers

• A question related to binary search, which is a kind of weak spot and I always avoid using it

• Explain Singleton structure, how to create

• Given k sorted pivots, write procedure partition in quicksort

• Find the median of three numbers

• Find two missing integers in an unsorted array

• Given an array of characters, how would you reverse it?

• Write a program to comparing two arrays, one being very large

• Merge two sorted integer arrays

• How to randomly select a number with equal probability from an array with unknown size?

• Write an algorithm to find the 3rd highest number from an array of random integers

• Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. Sorted in increasing order

  Input: find 5 in (15, 16, 19, 20, 25, 1, 3, 4, 5, 6, 10, 14) Output 8

• Implement a simple regular expression matching function

Uncategorized

• Given a max-heap, how do I find the top k items?
• Find the border length created from a conglomeration of various 2D rectangles
• Write a minPeak function for a stack (function that returns the minimum element in the stack)
• Design a function in your favorite programming language to convert a camelCase string to all lowercase
• Implement a hashset
• Given a corpus of valid words, design a function that takes a word as input and outputs all valid anagrams of that word
• Given an input of a 3D matrix of ones and zeros, count the number of contiguous 1-filled regions (as separated by 0-filled regions), as well as the size of the largest one (I think; doesn't really change the problem much)
• You have two sets. How would you know that they converge?
• Given a bag of nuts and a bag of bolts, each having a different size within a bag but exactly one match in the other bag, give a fast algorithm to find all matches
• Preorder traversal without recursion
• Find the largest possible difference in an array of integers, such that the smaller integer occurs earlier in the array
• Determine if n numbers in a list sum up to an integer k
• Make an anagram solver that returns all valid dictionary words given a set of characters
• Sort a string by the order its characters appear in another string
• Given a value k and an array, design an efficient algorithm that should output the number of pairs that sum up to k.
• How do you find three numbers that sum to 0? (in a list). Now can you do it under O(n^3)?
• Given a Fibonacci number, tell us which index it occurs at
• Describe an algorithm that would find n numbers in a list that sum to 0
• Given an array of n unsorted ints, with the condition that each number is at most k positions away from its final sorted position, give an efficient sorting algorithm
• Give an efficient solution for subset sum
• Given two (i,j) coordinates of a cell in two dimensional matrix. These coordinates are the lower left and upper right corner of a rectangle contained within the matrix. Sum all the elements in the matrix. Time and space?
• Check two strings to see if one is a permutation
• Remove duplicates from an unsorted linked list
• Delete a node in the middle of a singly linked list given access to that node
• Write code to partition a linked list around a value x such that all nodes less than x come before all nodes greater than or equal to x
• Single array to implement three stacks
• Stack with min element
• Towers of Hanoi
• Sort a stack in ascending order using at most one additional stack to hold items but you may not copy the elements into any other data structure
• Function to see if a tree is balanced
• Graph algorithm, route between two nodes
• Create bst from sorted array with minimal height
• Binary tree is a bst
• A child is running up a staircase with n steps, and cah hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs
• Two sorted arrays, A has a large enough buffer at the end to hold B, merge B into A in sorted order
• Write a method to sort an array of strings so that all the anagrams are next to each other
• Find an element in a sorted array that has been rotated an unknown number of times
• Implement a method that returns true if the edit distance between two strings is less than 2 (1 or 0) or false otherwise
• Given two lists of chars, return the first with removed characters that appear in the second list