Indeed Software Engineer Interview PlayBook

This guide is designed for people who: • believe live coding is not the best approach to interviewing software engineers • don't have time to practice 200+ LeetCode questions • need additional practice before interview

Karat面接（60分）

Coding

Given two user's browser histories, find the longest continuous common
the history between user1 and user2.
Example: 

Input: [
    ["1.com", "2.com", "3.com"], 
    ["1.com", "3.com", "2.com", "3.com"]
]
Output: ["2.com", "3.com"]

You're creating a game with some amusing mini-games, and you've decided to make a simple variant of the game Mahjong. In this variant, players have a number of tiles, each marked 0-9. The tiles can be grouped into pairs or triples of the same tile. For example, if a player has "33344466", the player's hand has a triple of 3s, a triple of 4s, and a pair of 6s. Similarly, "55555777" has a triple of 5s, a pair of 5s, and a triple of 7s. 

A "complete hand" is defined as a collection of tiles where all the tiles can be grouped into any number of triples (zero or more) and exactly one pair, and each tile is used in exactly one triple or pair.
Write a function that takes a string representation of a collection of tiles in no particular order, and returns true or false depending on whether or not the collection represents a complete hand.

tiles1 = "11133555" # True. 111 33 555
tiles2 = "111333555" # False. There are three triples, 111 333 555 but no pair.
tiles3 = "00000111" # True. 000 00 111. Your pair and a triplet can be of the same value
There is also no limit to how many of each tile there is.
tiles4 = "13233121" # True. Tiles are not guaranteed to be in order
tiles5 = "11223344555" # False. There cannot be more than one pair
tiles6 = "99999999" # True. You can have many of one tile
tiles7 = "999999999" # False.
tiles8 = "9" # False.
tiles9 = "99" # True. One pair.
tiles10 = "000022" # False.
tiles11 = "888889" # False. There cannot be any tiles left over.
tiles12 = "889" # False. There cannot be any tiles left over.
tiles13 = "88888844" # True. Two triples and one pair
tiles14 = "77777777777777" # True. Four triples and one pair
tiles15 = "1111111" # False.
tiles16 = "1111122222" # False.

complete(tiles1) => True
complete(tiles2) => False
complete(tiles3) => True
complete(tiles4) => True
complete(tiles5) => False
complete(tiles6) => True
complete(tiles7) => False
complete(tiles8) => False
complete(tiles9) => True
complete(tiles10) => False
complete(tiles11) => False
complete(tiles12) => False
complete(tiles13) => True
complete(tiles14) => True
complete(tiles15) => False
complete(tiles16) => False

Complexity Variable
N - Number of tiles in the input string

Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique positive integer identifier.
For example, in this diagram, 6 and 8 have common ancestors of 4 and 14.
             15
             |
         14  13
         |   |
1   2    4   12
 \ /   / | \ /
  3   5  8  9
   \ / \     \
    6   7     11
parentChildPairs1 = [
    (1, 3), (2, 3), (3, 6), (5, 6), (5, 7), (4, 5),
    (4, 8), (4, 9), (9, 11), (14, 4), (13, 12),
    (12, 9),(15, 13)
]
Write a function that takes the graph, as well as two of the individuals in our dataset, as its inputs and returns true if and only if they share at least one ancestor.
Sample input and output:
hasCommonAncestor(parentChildPairs1, 3, 8) => false
hasCommonAncestor(parentChildPairs1, 5, 8) => true
hasCommonAncestor(parentChildPairs1, 6, 8) => true
hasCommonAncestor(parentChildPairs1, 6, 9) => true
hasCommonAncestor(parentChildPairs1, 1, 3) => false
hasCommonAncestor(parentChildPairs1, 3, 1) => false
hasCommonAncestor(parentChildPairs1, 7, 11) => true
hasCommonAncestor(parentChildPairs1, 6, 5) => true
hasCommonAncestor(parentChildPairs1, 5, 6) => true


Additional example: In this diagram, 4 and 12 have a common ancestor of 11.
        11
       /  \
      10   12
     /  \
1   2    5
 \ /    / \
  3    6   7
   \        \
    4        8
parentChildPairs2 = [
    (1, 3), (11, 10), (11, 12), (2, 3), (10, 2),
    (10, 5), (3, 4), (5, 6), (5, 7), (7, 8),
]
hasCommonAncestor(parentChildPairs2, 4, 12) => true
hasCommonAncestor(parentChildPairs2, 1, 6) => false
hasCommonAncestor(parentChildPairs2, 1, 12) => false
n: number of pairs in the inp

Each course at our university has at most one prerequisite that must be taken first. No two courses share a prerequisite. There is only one path through the program.

 Write a function that takes a list of (prerequisite, course) pairs, and returns the name of the course that the student will be taking when they are halfway through their program. (If a track has an even number of courses, and therefore has two "middle" courses,   you should return the first one.)

  Sample input 1: (arbitrarily ordered)
  const prereqs_courses1 = [
      ["Foundations of Computer Science", "Operating Systems"],
      ["Data Structures", "Algorithms"],
      ["Computer Networks", "Computer Architecture"],
      ["Algorithms", "Foundations of Computer Science"],
      ["Computer Architecture", "Data Structures"],
      ["Software Design", "Computer Networks"]
  ] 

  In this case, the order of the courses in the program is:
      Software Design
      Computer Networks
      Computer Architecture
      Data Structures
      Algorithms
      Foundations of Computer Science
      Operating Systems
  
  Sample output 1:
      "Data Structures"
  
  
  Sample input 2:
  prereqs_courses2 = [
      ["Data Structures", "Algorithms"],
      ["Algorithms", "Foundations of Computer Science"],
      ["Foundations of Computer Science", "Logic"]
  ]
  
  
  Sample output 2:
      "Algorithms"

  Sample input 3:
  prereqs_courses3 = [
      ["Data Structures", "Algorithms"],
  ]
  
  
  Sample output 3:
      "Data Structures"
  
  Complexity analysis variables:
  
  n: number of pairs in the input

Given an array of start times and end times of meetings, return the minimum number of rooms required to host every meeting.

Sample 1

Room1 |-------|---|
      4       9   10
Room2  |-------------------|
       5                   11

Input: intervals = [[9,10],[4,9],[5,11]]
Output: 2

Sample 2

Room1 |-------|   |---|
      4       9   12  13

Input: intervals = [[7,10],[12,13]]
Output: 1

Loop Interview x 5

Coding x 2

Given a prefix String, and a dictionary.
Find all auto-complete words for the given prefix string


Dictionary: ["ab", "a", "de", "abde"]

Example 1:
Input: ["ab"]
Output: ["ab", "abde"]

Example 2:
Input: ["a"]
Output: ["a", "ab", "abde"]

Example 3:
Input: ["abde"]
Output: ["abde"]

Example 4:
Input: ["e"]
Output: []

You are given a list of jobs, each job has an ID number(type is long).

Implement two functions,
expire(long jobid) to set a job as "expired"
isexpired(long jobid) to check if a job is "expired"

Follow Up: Space efficient
Considering the type Long is 64-bit, we will run out of space if we store large amounts of job ids. Can you think of a method to store 4 billion of jobid within memory? If you used hashmap, 4 billion rows will result in 32 TB (8 bytes * 4 * 10^9 = 32 * 10^9 bytes)

Given a stream of numbers, and an API getNow():int to get the current time stamp,

Finish two methods:

1. void record(int val) to save the record.
2. double getAvg() to calculate the average value of all the records in 5 minutes.

Example: 

movingAverage = NewMovingAverage()
movingAverage.record(2) // when called getNow() returns 0
movingAverage.record(3) // when called getNow() returns 1
movingAverage.record(5) // when called getNow() returns 2
movingAverage.record(10) // when called getNow() returns 3
movingAverage.record(10) // when called getNow() returns 4

movingAverage.getAvg() // when called getNow() returns 4. So returns (2+3+5+10+10)/5 = 6

movingAverage.getAvg() // when called getNow() returns 5. So returns (3+5+10+10)/5 = 28/5

movingAverage.record(2) // when called getNow() returns 6
movingAverage.getAvg() // when called getNow() returns 6. So returns (3+5+10+10+2)/5 = 6

Follow Up: Median
3. Double getMedian() to calculate the median of all records in 5 minutes

Given n sorted stream, and a constant number k. The stream type is like an iterator and it has two functions, move() and getValue(), create a method mergeKSortedStream to find a list of numbers that each of them appears at least k times in these streams. Duplicate numbers in a stream should be counted once.


Example:
streams = [
[1->2->3-4]
[2->5->6]
[2->5->7]
]

Input
mergeKSortedStream(streams, k=2) // [2,5]
mergeKSortedStream(streams, k=3) // [2]
mergeKSortedStream(streams, k=4) // []

type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

Example 1:

t1 := new TreeNode(1)
t2 := new TreeNode(2)
t3 := new TreeNode(3)
t1.left = t2
t1.right = t3

/*
This will create
		    1
		  /   \
		2      3
*/
Input: Compress(t1)
Output: // expect something with smaller memory footprint

Hint: You can compress it to an array, such as [1,2,3]


Example 2:
/*
Imagine another tree
		    1
		  /   \
		2      3
           /
         4
*/

If we compress it to an array, we have a few options, such as:

[1,2,3,4,0,0,0] // Level traversal
[1,2,4,0,0,0,3,0,0] // Preorder

Discuss what is the tradeoff in choosing how you compress. For example preorder will save more space compared to level traversal if we have a linked-list like array

Example 3:

/*
	1 -> 2 -> 3 -> 4
*/

[1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4] // Level traversal
[1, 0, 2, 0, 3, 0, 4, 0, 0] // Preorder, less space

Architecture（60分）

• Design Indeed job search

• Design Indeed comment

Code Review（60分）