Indeed Technial

Question 1

Subdomain Visit Count

Answer 1

Runtime

Time Complexity: O(N)O(N), where NN is the length of cpdomains, and assuming the length of cpdomains[i] is fixed.

Space Complexity: O(N)O(N), the space used in our count.

Pattern

• Create a hash table
• loop through domains, and split count and domain.
• Recursively call a helper function that stores the count and breaks down the subdomain.
• Return domain after each call
• Print out domain into a list

Question 2

Find Words That Can Be Formed by Characters

Answer 2

Run Time:

• O(N^2)

Pattern:

• Create a counter of chars and result
• Loop through each word
  
  • Make a copy of the counter of chars (we will be deleting elements and need original every time)
  • Set a temp to add
  • Loop through the char in word
    
    • If the char is in counter, and the char in hashtable > 0
      
      • Decrement char
      • increase temp
    • else reset temp and break
  • Add the temp to result

Question 3

Shortest Word Distance

Answer 3

Run Time

O(N * M) Time, O(1) Space

Pattern

• Create two idxs for word1 and word2, and minDistance = len(words)
• Loop through words, and check if and words equal word1 or word2
• Update index if so.
• Compare the minDistance if word1 or word2 ≠ -1

Question 4

Moving Average from Data Stream

Answer 4

Run Time:

O(N) time, O(N) space

Pattern:

• Create a list as a storage within the constructor
• Within the next() method, append the val to the list
• Pop the list if the list is greater than the length indicated or that the len is not 0.
• return the float average of sum(list)/len(list)

Question 5

String Matching in an Array

Answer 5

Run Time

O(N^2) time, O(N) space

Pattern

• Sort through the words, since you smaller fits into bigger.
• Loop through words and a second loop starting at I + 1
• If word[I] is in word[j], append and break

Question 6

Binary Tree Pruning

Answer 6

Run Time:

O(N) Space, O(N) Time

Pattern:

• Recursive base case for trees
• Recurse to the bottom of the tree first
  
  • Set node.left and right = recursive call
• Condition: if node left and right are None and val = 0, return None
• else return root

Question 7

Kth Largest / Smallest Element in an Array

(Heap)

Answer 7

Run Time:

• O(N log k) Time, and O(N) space
• Adding to heaps are O(log k)

Pattern

heapq. heappush(heap, item): Push the value item onto the heap
heapq. heappop(heap): Pop and return the smallest item from the heap. To access the smallest item without popping it, use heap[0].
heapq. heappushpop(heap, item): Push item on the heap, then pop and return the smallest item from the heap.
heapq. heapreplace(heap, item): Pop and return the smallest item from the heap, and also push the new item. The heap size doesn’t change.
heapq. heapify(x): Transform list x into a heap, in-place, in linear time.
heapq. merge(*iterables, key=None, reverse=False) Merge multiple sorted inputs into a single sorted output.
heapq. nlargest(n, iterable, key=None) Return a list with the n largest elements from the dataset defined by iterable.
heapq. nsmallest(n, iterable, key=None): Return a list with the n smallest elements from the dataset defined by iterable.

Question 8

Excel Sheet Column Number

Answer 8

RunTime

O(N) time, O(1) Space

Pattern

• Create an alphabet dict
  
  • {char(I + 65} : i + 1 for I in range(26)}
• Set a result, and decimal to 0
• Starting from the right to left, since thats how numerical base works
  
  • Get the idx from alphabet dict
  • The idx * 26 (number of options)^power of decimal)

Question 9

Remove Duplicate Letters in Lexicon Order

Answer 9

Run Time:

O(N) Time, O(1) Space

Pattern:

• Create a dictionary with last seen
• Create a stack to keep track of last seen letters
  
  • If the letter is not in stack:
  • Loop and pop while stack is not empty, top of stack is greater than char, and last seen of top of stack is greater than idx
  • Append the new letter
• Return joined list

Question 10

Intersection of Two Arrays

Answer 10

Run Time:

O(N + M) time, O(N + M)

Pattern:

• Make both lists into sets
• return using list comprehension if one set is in another

Question 11

First Unique Character in a String

Answer 11

Run Time:

O(N) Time, O(1) Space

Pattern:

• Create a counter object
• Find first frequency = 1

Question 12

Longest Substring Without Repeating Characters

Answer 12

Run Time:

O(N) Time, O(N) Space

Pattern:

• Create a dictionary to keep track of last idx location, and left idx, result
• Loop through right
  
  • If it not in seen, increment result (right - left + 1)
  • else:
    
    • If it is outside window, we keep incrementing
    • If it is inside window, we set the left to last seen idx
  • increment the last seen in dict

Question 13

Repeated String Match

Answer 13

Run Time:

O(N) time, O(N) space

Pattern:

• Set a temp string and a count
• Loop while the length of temp is less than both A and B.
  
  • Add a copy of temp and increment count
  • See if b is in temp, if so return count
• else return -1

Question 14

Find All Anagrams in a String

Answer 14

Run Time:

O(N) time, O(N) space

Pattern:

• Create two counters, one for pattern, other for length of pattern
• Create I, J for sliding window
• Loop while J is smaller or equal to len(s)
  
  • If the two counters equal, add result
  • Decrement the count for tail char
  • Deletes tail count if it is a 0
  • Move the counter forward
  • increment I, J

Question 15

Maximum Length of Repeated Subarray

Answer 15

Run Time:

O(N) Time, O(N) Space

Pattern:

• convert one of the lists into strings, making it faster to compare
• create a window and result null
• loop through nums1
  
  • Add the num1 into window
  • if window is in max_str, then compare and get max
  • else: shift window right

Question 16

Minimum Cost Tree From Leaf Values

Answer 16

Run Time:

O(N) Time, O(log N) Space

Pattern:

• Set a result = 0
• Loop while there is still one element left.
  
  • We find the min of the arr, since we want to find the minimum product
  • Find the second min in either left or right of the minIdx
  • Corner Case: if minIdx is first or last, times the first or second last.
  • Pop the min ele from arr