These are some of the questions I practiced for my interviews when applying for internships during my junior year of university.

This wasn't intended to be a replacement to actually thinking about and doing the questions, but more as a quick way to review the problems.

The questions are bolded, and the way of solving the problem is described in bullet points.

LeetCode

Easy

Array

• Remove Duplicates from Sorted Array (in place): link
  • loop through array once
  • keep track of previous and curr value, compare and pop

• Best Time to Buy and Sell Stock II (sell multiple times): link
  • loop through array once
  • keep track of curr and next. If curr < next add the difference to return

• Rotate Array: link
  • if number of rotations greater than length then reduce it, then pop and insert

• Contains Duplicate: link
  • put each element in set and as iterating through array check if in set

• Single Number (find element that appears only once): link
  • put in dictionary with number of elements found. Then loop through dictionary and find element found only once

• Intersection of Two Arrays II: link
  • Question: given two arrays return the elements that appear more than once
  • loop through first array and put in dictionary with number of items found. Loop through second array and put in another dictionary with number of items found. Loop through first dictionary and see if that element is in the other dictionary and take the min of the elements of these dictionaries

• Plus One: link
  • Question: integer represented as array. Increase by 1
  • Loop array backwards. Add 1 to end of array. If last index not 10 return that. If it is 10 loop backwards, set curr as 0 and add 1 to prev

• Move Zeroes: link
  • Question: move zeroes in array to the end
  • loop through array once. Pop zeroes out and count the number of times this was done. Then add 0s the number of times counted to the end

• Two Sum: link
  • make dictionary of the number of times elements have been found in array. Loop through array again if answer - element in array then return answer. If answer - element is same as element see that the dictionary has 2 of them

• Rotate Image (rotate 90 CW): link
  • transpose matrix so swap[i][j] with [j][i]. Then reverse each row

Strings

• Reverse String: link
  • return s[::-1]

• Reverse Integer: link
  • Question: -123 becomes -321
  • check if symbol present in front. Reverse rest of string then add symbol back

• First Unique Character in a String: link
  • loop through string and create a dictionary which keeps count of number of elements found. Then loop through string and check that in dictionary if it is 1 return it

• Valid Anagram: link
  • Question: Given 2 lists find if 1 word can make up other by rearranging letters
  • Loop through first string create dictionary with number of elements in it. Loop through second array subtracting elements from the same dictionary, while doing this if a letter cannot be found then not anagram. Loop through the dictionary once again if any element not equal to 0 then it is not an anagram

• Valid Palindrome (considering only alphanumeric characters): link
  • go through the string first and fix palindrome. Then iterate from left and right till it meets in the middle. Can be done without the first iteration

• String to integer (atoi): link
  • Question: remove whitespace till first non-whitespace character is found. Then take optional + or - sign, followed by as many numerical digits
  • start iterating while ignoring whitespace. The first character is +/- or a numerical digit. End iterating when anything other than an integer is found

• Implement strStr(): link
  • Question: from "hello" find location of "ll" if not found return -1
  • .find in python or iterate through string looking for the substring if not found -1

• Longest common prefix: link
  • Question: ["flower", "flow", "flight"] returns "fl"
  • loop through list, then loop through each string. Firstly the prefix is flower, then flow, then fl. So break when the characters are mismatched.

Linked List

• Delete Node in a Linked List (given the node): link
  • put val of next node in current node. And move the pointer two next

• Remove Nth Node From End of List: link
  • move first counter N times. Then start iterating first and second counter till first counter.next != None then point second counter next twice

• Reverse Linked List: link
  • need prev, curr, next. curr points to prev. set prev as curr and curr as next. Move next one over and repeat

• Merge Two Sorted Lists: link
  • create dummyNode and point it to the first smallest node and set the smallest node pointer to None. Keep repeating till both of the of the lists reach None. Then return dummyNode.next as this will be the actual smallest node.

• Palindrome Linked List: link
  • first counter goes by one, second counter goes by two. When second reaches end. First starts reversing linked list. Then go through both the linked lists.

• Linked List Cycle: link
  • first counter goes by one. Second counter goes by two. When both counters intersect the reset first counter, each counter goes by one again and when they intersect that where cycle begins.

Trees

• Maximum Depth of Binary Tree: link
  • base case if None return 0
  • return 1 + max(maxDepth(root.left), maxDepth(root.right))

• Validate Binary Search Tree: link
  • base case if None return True, if r <= val <= l return False
  • return (isValid(root.left, min, val) and isValid(root.right, val, max))

• Symmetric Tree (mirror passed through middle): link
  • check root. Then do inorder traversal on both left and right child

• Binary Tree Level Order Traversal: link
  • Level Order means BFS and therefore queue

• Convert Sorted Array to Binary Search Tree: link
  • mid is root, node.left = createBST(arr, left, mid - 1), node.right = createBST(arr, mid + 1, right)

Sorting and Searching

• Merge Sorted Array: link
  • Question: [1,2,3,0,0,0], [2,5,6]
  • loop through both array backwards from their first non-zero value. Arr 1 pointer is m, arr 2 pointer is n. If m < n then arr2 val goes in arr1 at m+n. If m >= n then the val at m is moved to m+1

• First Bad Version: link
  • Question: Find first bad version of code making minimal API calls
  • Use binary search

Dynamic Programming

• Climbing Stairs: link
  • base case if there is 1 stair return 1 ways, if there is 2 return 2 ways. answer += climb_stairs(n-1), answer += climb_stairs(n-2). Make this faster by memoization(save prev calculated values in dictionary)

• Best Time to Buy and Sell Stock I (only once): link
  • keep track of local min and profit. Then iterate through list once. Profit is curr - local min. Local min is the lowest val we found at the time

• Maximum Subarray: link
  • Question: find subarray which holds the highest number
  • keep track of best and prev. If prev is > 0 then append to it, else start new prev count. Best is the max of prev and best

• House Robber: link
  • Question: robber cant rob two adjacent house. Maximize profit
  • odd and even counter. even = max(num[curr] + even, odd), odd = max(num[curr] + odd, even). Answer is max of odd and even

Please disable adblock

Medium

Array and String

• 3 sum: link
  • O(nlogn) + O(n^2)
  • sort list, have pointer beginning and end. If sum of curr, beginning and end > 0 then move end pointer back, if < 0 then move beginning pointer forward, stop loop if i == j or == 0

• Set Matrix Zeroes: link
  • Time O(nm),Space O(1)
  • Solution
    • check row or column contains any zeroes, set booleans true if it does or false otherwise
    • use first row and column to mark zeroes
    • set each row and columns by using marks in first row and column
    • depending on the boolean found in step 1 set rows and columns back if false set back to 1, if true set to 0

• Group Anagrams: link
  • Sort letter and use that as key for dictionary, values is a list of the original words

• Longest Substring Without Repeating Characters: link
  • O(n) time, O(26) space
  • have a hashset, a counter that keeps track of max, and two pointers, i is slow j is fast. Move j and add char to set and update max accordingly, move i only if a character is already found in set

• Longest Palindromic Substring: link
  • Time: O(n^2), Space: O(n^2)
  • Need to use dynamic programming. Create matrix n*n. Set matrix where i==j as T. For 3 letters if i==i+2 then set T accordingly. For words larger than 3 letters compare first and last letter if T then check matrix for previously calculated boolean, if that is T set as T, if F set as F.

• Increasing Triplet Subsequence (Unsorted Array): link
  • Time: O(n), Space: O(1)
  • set var low, mid as infinite. Low will be lowest number, mid will be > low and < mid. If curr is > mid then True. If loop finishes running return False

Linked Lists

• Add Two Numbers (stored reversed): link
  • loop through both linked list and create new one. Have a carry and treat null as 0

• Odd Even Linked List: link
  • Question: odd elements first then even elements by position. O(1) space and O(n) time
  • Need to work for empty LL, 2 nodes, odd nodes, even nodes
  • two pointers, odd and even. Update next for odd pointers first and then even. Hold the head location for the even LL so the end of odd can point to that

• Intersection of Two Linked Lists: link
  • calculate length of both linked list, find difference in the length, move the difference in length in longer linked list, then iterate both and find intersection

Trees and Graph

• Binary Tree Inorder Traversal: link
  • use stack. Root not null then put into stack, put left in stack, when left null pop and push right into stack

• Binary Tree Zigzag Level Order Traversal: link
  • two stacks, push root in s1. pop from s1 and print. push left and right child in s2 till s1 empty and print, pop nodes from s2 and add left and right to s1 till s2 empty

• Construct Binary Tree from Preorder and Inorder Traversal: link
  • Preorder - VLR, Inorder - LVR
  • First element in preorder is root, find that root in the inorder traversal and everything left of that is left subtree do this by length and recurse

• Populating Next Right Pointers in Each Node: link
  • Question - Every left of tree points from left to right to null
  • 2 while loops first for going down level, 2nd for going across levels. Have childhead which stores head of level, process for left and right hand side of root in inner loop. Then set root as childhead once going down levels in main loop

• Kth Smallest Element in a BST: link
  • Method 1: iterative inorder traversal using stack, every pop from stack is counted
  • Method 2: put in min heap

• Number of Islands: link
  • iterate if 1 found increase island found and change all the 1s nearby to 0s recursively

Backtracking

• Letter Combinations of a Phone Number: link
  • Question: given number return every possible string from phone
  • build dict that sets all numbers associated with letters. Loop through letters, recursively send [1:] letters, ignore charAt -1 to send again

• Generate Parentheses: link
  • Question: give n number generate all combinations of parentheses
  • use recursion. if number of open paren == 0 then close. If number of closed paren == 0 then add an open, subtract open counter, add closed counter, else open paren sets counters accordingly + closed paren set counters accordingly

• Permutations: link
  • Time: O(n!)

1if len <= 1: return itself
2for i, x in enumerate(nums):
3  for elem in func(nums[:i] + nums[i+1:]):
4    res.append(elem)

• Subsets: link
  • Time: O(2^n)

1nums.sort()
2line = res = []
3res.append([x for x in line])
4  for i, x in enumerate(nums):
5    line.append(x)
6    func(nums[i + 1:], res, line)
7    line.pop()

• Word Search: link
  • loop through and do DFS

Searching and Sorting

• Sort Colors: link
  • Question: [2,0,2,1,1,0] -> [0,0,1,1,2,2] do in place. 0 = red, 1 = white, 2 = blue
  • set red pointer at beginning, blue pointer end of array. Loop through array with white pointer. If element is red swap with red pointer and increase by one, if blue swap with blue and decrease blue by one

• Top K Frequent Elements: link
  • Put elements in dictionary and then use either max heap or counting sort

• Kth Largest Element in an Array: link
  • Max Heap

• Find Peak Element: link
  • use binary search, if curr_left > curr binary search left, if curr_right > curr binary seach right, else curr is peak

• Search for a Range: link
  • Question: search for element in sorted array
  • use binary search twice, once to look for left and once for right

• Merge Intervals: link
  • Question: merge overlapping intervals given in list of lists
  • Time: O(nlogn), Space: O(1)
  • sort all intervals by start values and then find overlap

• Search in Rotated Sorted Array: link
  • Question: [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2] due to pivot
  • find pivot, do this by binary search. If array[0] <= array[length - 1] not rotated. If array[start] < array[mid] means it is sorted so go right, else go left. Then do binary search for target on the likely side of pivot

• Search a 2D Matrix II: link
  • Question: Matrix is sorted ascending in rows and columns
  • Stair search time: O(n)
  • if element is < [r][c] then r++, if > [r][c] c--. Means we start on top right and go down and left only

Please disable adblock

Glassdoor

• Find the kth largest element in an array.
  • max heap

• How to square integers in an array and keep it sorted.
  • two arrays one of negative and one of positive, sort each of the arrays and then merge

• Merge k sorted streams.
  • one iteration

• Convert non-decreasing list of ints to a balanced binary tree.
  • remember list structure. Mid is root, smaller is left, large is right

• Difference between mergesort and quicksort.
  • quicksort has higher worst case scenario (unlikely), takes less memory space

• Find closest number in array (given target).
  • sort and then binary search

• Given two arrays, output an array with the elements that are contained in both.
  • loop through first array and put in dictionary with number of items found. Loop through second array and put in another dictionary with number of items found. Loop through first dictionary and see if that element is in the other dictionary and take the min of the elements of these dictionaries

• Conway's Game of Life.
  • O(1) space and O(nm) time. Represent dead -> live = 2, live -> dead = 3. Dead cell to become live 3 live neighbours, live cell to stay live 2 or 3 alive neighbours. Iterate through array again to make 2->1 and 3->0.

• Implement DFS/BFS.
  • BFS - Queue
  • DFS - Stack

• How do you balance a binary tree without using self-balancing algos like Red-Black or AVL trees?
  • B/B++ tree: does it by range. Node holds certain values, those less of its range go to left, those in middle go middle and those more than range go right. Total disk access is low.

• Taking two strings find if they are anagrams.
  • put in dictionary and keep counter

• Given open and close parenthesis, make sure that the string is valid such that each open parenthesis has a matching close parenthesis in the correct place.
  • use stack

• Find middle element of linked list.
  • two counters. One goes by one and the other goes by two. When two reaches end then one reaches middle

• Calculate first n prime numbers.
  • check if number is prime, put in list and add

• Prime factors of a number.
  • O(squrt(N)). (1) If n%2 == 0 then n = n/2, (2) loop 3..sqrt(n) skip by 2 since n is odd, if n%i == 0 then n/i (3) n > 2 then print (n)

• Find loop in graph.
  • two counter increase one by one and the other by two. When they meet we know circular. Reset one counter and then increase each by one and when they meet that is intersection

• 0-1 Knapsack
  • fractional: greedy. Find ratio of each (val/weight). Sort and then add.
  • dynamic. create matrix: horizontal-> total(0..max(val)) and vertical-> (val, weight). For selection max(curr_val + total weight - curr weight location in matrix row above, dont consider value so look directly above). To get answer retrace, if max val(exact) comes from top then curr not in answer subtract value from it, if max val (not exact) comes from above then subtract val from total from previous and find it

• Reverse linked list
  • keep track of prev, curr and next

• 2 Sum
  • dictionary counting characters and match. Special case double multiple of character

• Find all combinations of elements in array to make target. Leetcode: combination sum ii
  • use backtracking(all possible results) if total is zero then add answer, if < 0 ignore it,
    if > 0 backtrack on that.

• Find most repeated character in random string of characters.
  • dictionary counting characters

Please disable adblock

CTCI

Array and Strings

• Determine if string has all unique characters. What if you cannot use additional data structures?
  • ascii for array of booleans. Set true if found. O(n)
  • brute force. O(n^2)
  • sort string. O(n log n)

• Given two string, check if one is permutation of another.
  • sort strings and check. O(n log n)
  • identical character count. O(n)

• Write a method to replace all spaces in a string with '%20'.
  • iterate and replace char in python. O(n)

• Given string, check if it is permutation of a palindrome.
  • may have one unique character the rest are paired. Place in hashmap. O(n)

• Given two strings, check if they are one or zero edits away (insert, remove, replace).
  • first and second word are of same length (bale, pale)
  • one edit replace. Return false if more than one diff is found
  • first and second word length differ by 1 (apple, aple)
  • one edit insert. Increment index of both string by 1. If difference found and indexes are same increment index of second string but not string one. If indexes are not same return false.
  • O(n) time

• Perform string compression to count repeated characters. Ex: aabccccaaa would be a2b1c5a3. Return original if compressed not shorter.
  • Get length of original. Traverse through the original compressing. If compress overtakes length of original without finishing return original. O(n) time.

• Given image represented by N*N matrix, where each pixel is 4 bytes, rotate the image by 90 degrees. Can you do it in place?
  • Do layer by layer. Since touches all nodes O(n^2)
  • In place is done by: temp = top[i]; top[i] = left[i]; left[i] = bottom[i]; bottom[i] = right[i]; right[i] = temp

• If an element in an M*N matrix is 0, its entire row and column are set to 0.
  • make two array: column and row. Traverse through matrix and set the row and column where 0 was found. Second traversal nullify row and column. O(n) time and O(n) space.
  • To make more space efficient O(1) instead of using row and column array to keep track, set the first column or first row index to 0 whenever 0 is found. Nullify on second iteration.

• Method isSubstring is given which checks if one word is substring of another. Given two strings, s1 and s2, check if s2 is a rotation of s1 using one call to isSubstring(eg 'waterbottle' is rotation of 'erbottlewat').
  • s1 = xy = waterbottle; x = wat; y= erbottle; s2 = yx = erbottlewat; yx will be in substring xyxy. So s2 will be substring of s1s1.
  • isSubstring(s1s1, s2). O(N) time

Linked List CTCI

• Remove duplicates from unsorted linked list. No temporary buffer.
  • If temporary buffer. Store in hash map and if found in hash map remove. O(N) time.
  • No buffer. Two pointers: current and iterator. O(N^2) and O(1) space.

• Find kth to last element of a singly linked list.
  • Without recursion. 2 pointers: move first pointer k nodes. Then move both pointers when first pointer reaches end second pointer is pointing to kth last node.
  • With recursion. Recurses through linked list, hits end and passes back a counter set to 0. Each parent call adds 1 to this counter. When counter equals k return it.

• Delete middle node of linked list given only access to that node.
  • Copy data of the next node to the current node and delete the next node.

• Partition linked list around value x, nodes less than x come before all nodes greater than or equal to x.
  • Two linked list: one with elements smaller than x, another with elements with value equal to or greater than x. Then one traversing the initial linked list is completed, connect tail of linked list with smaller values to head of linked list with greater or equal values.

• Two numbers represented by linked list, each node contains single digit. Digits stored in reverse order. Return sum. Ex input: (7 -> 1 -> 6) + (5 -> 9 -> 2). That means 617+295. Return 2->1->9.
  • 7 + 5 = 2 and carry 1
  • 1 + 9 + 1(carried) = 1 and carry 1
  • 6 + 2 + 1(carried) = 9

• Check if linked list is palindrome.
  • find middle using fast runner and slow runner technique
  • put first half in stack
  • pop out from stack while running the second pointer to see if it matches

• Given two singly linked list, determine if they intersect and return that node. Intersection is defined by reference not value.
  • run through each linked list to get the lengths and the tails
  • if tails are different there is no intersection
  • set to pointers to start of linked list
  • on the longer linked list, advance its pointer by the difference in lengths
  • traverse each linked list until the pointers are the same

• Given a circular linked list return node at beginning of loop.
  • Create two pointers, FastPointer: moves rate of 2 steps, SlowPointer: moves rate of 1 step
  • If they collide then there is a loop.
  • Set one pointer to head and keep another at collision
  • now move both pointer one step at a time. When they collide again that is the beginning of the loop

Stacks and Queues

• Implement three stacks using single array.
  • [[], [], []]

• Stack which has push, pop, and a function min that returns value of minimum element. All operations O(1) time.
  • Node containing value and value of min int pushed to stack. Min int compares min int of previous node and its current value and sets accordingly.
  • More space efficient. Have another stack that on push checks if the value is smaller than its value on top. If so then push the current value on stack.

• Create SetOfStacks composed of several stacks and create a new stack once the previous one exceeds capacity. push and pop functions behave exactly like a single stack. Also implement function popAt(int index) which performs a pop operation at a specific sub-stack.
  • Array of stacks

• Implement MyQueue class which implements a queue using two stacks.
  • One stack to hold and the other to reverse.
  • If peek performed move all the elements to reverse stack and keep there. Hold stack will only contain element being peeked. This is done so if pop performed the reverse process does not need to be done again. But if push performed bring contents back to holder and add. This is done to save some evaluation.

• Sort stack with smallest on top. Can use additional temporary stack, but no other data structure allowed. Stack supports push, pop, peek and isEmpty.
  • O(N^2) time and O(N) space. Pop from unsorted stack, hold in variable. Pop from sorted stack and push into unsorted and then place the variable into stack. And then bring all the popped elements from the sorted stack back.

• Animal shelter holds only dogs and cats, operates on FIFO. People only get oldest animal and can only select type of animal(cat or dog). Create data structure and implement operations enqueue, dequeueAny, dequeueDog, and dequeueCat. May use LinkedList data structure.
  • Two queues one for cat and one for dog, have a wrapper class which will maintain infos in the queues.

Trees and Graphs

• Given a directed graph, find out whether there is a route between two nodes.
  • Simple traversal, BFS(preferred) or DFS. Discuss trade-offs between each

• Given a sorted (increasing order) array with unique integer elements, create a binary search tree with minimal height.
  • middle of each subsection of the array becomes the root. Left side becomes left subtree and right side becomes right subtree
  • time O(n Log n)

• Given a binary tree, create a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, there will be D linked lists).
  • BFS. O(N) time and O(N) space

• Check if a binary tree is balanced. Balanced tree is a tree such that heights of two subtrees of any node never differ by more than one.
  • recurse through tree and for each node compute height of each subtree
    • Math.max(getHeight(root.left), getHeight(root.right)) + 1
    • Optimize by stopping traversal when height of subtree differing greater than one is found. This is done by sending an error code (min int)

• Check if a binary tree is a binary search tree.
  • Option 1: Traverse in-order and check that left <= current < right
  • Option 2: Property of BST left <= current < right
    • Make the ranges smaller as it progresses down the tree. Start with min = NULL, max = NULL. When branching left max gets updated, when branching right min gets updated. Stop when BST property fails
    • O(N) time, O(log n) space

• Find the next node (i.e., in-order successor) of a given node in a binary search tree. May assume each node has a link to its parent.
  • if n has a right subtree then return leftmost child of the right subtree; while n is right child of n.parent go to parent. Return parent

• Find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. Not BST.
  • first traverse left and then traverse right. If any of the nodes found pass its value up, if not found pass null up. If a node has two values come to it then pass the value of that node up. If one value and null then pass its value up.
  • if root is null return null. If root == n1 or n2 return null. Traverse left and right. If left and right is not null return root. If left and right is null then return null. Return whatever value is value is not null.
  • O(N) time

• Given a BST print all possible arrays that could have led to this tree.
  • Go through each level and permute. Root will always be beginning of array

• Given trees T1 and T2, T1 is larger. Determine if T2 is a subtree of T1.
  • Search to find T2 head in T1. Then perform pre-order traversal on both. O(nm) worst case time.

• Count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards. Nodes can contain positive and negative integers.
  • O(n) time, O(n) space
  • Pre-order traversal with cache

Please disable adblock

References:

• LeetCode Easy Questions Collection
• LeetCode Medium Questions Collection
• Cracking the Coding Interview
• Curated List of Top 75 LeetCode Questions to Save Your Time