interview questions

problem_01.md

Problem

Write a function which given a string argument, returns a count the occurences of each word in that string.

• A string represents a single line of text.
• A word is defined as a sequence of characters that are delimited by , or ,, or ;, or ..
• To count as an occurence, there has to be a full word match (not a partial match).

Input

the monkey donkey donkey monkey a face

Output

the: 1
monkey: 2
donkey: 2
a: 1
face: 1

Note that the ordering of the output can be in any order.

Expected function signature

function count(arg: string): Map<string, number>;

Expected usage

let arg: string = "the monkey donkey donkey monkey a face";
let output: Map<string, number> = count(arg);
assert(output["the"], 1);
assert(output["monkey"], 2);

problem_02.md

Problem

Write a function to coalese an array of numbers into ranges of values.

• Each item in this array will be an integer (not a float).

Input

[0, 1, 2, 5, 10]

Output

[0-2, 5, 10]

Expected function signature

function coalesce(arg: number[]): string[]);

Expected usage

let arg: number[] = [0, 1, 2, 5, 10];
let output: string[] = coalesce(arg);
assert(output[0], "0-2");
assert(output[1], "5");
assert(output[2], "10");

problem_03.md

Problem

Write a function to count to the number of times a pattern shows up in a string.

• The pattern is a string itself.
• Bonus - if you can provide a O(n) solution and not O(n^2); this might require the use of a state machine.

Notes:

1. Brute force: https://developerlife.com/2018/08/16/algorithms-in-kotlin-2/#on--m---brute-force-approach
2. State machine: https://developerlife.com/2018/08/16/algorithms-in-kotlin-2/#on--m---using-a-state-machine

Input

• Pattern: abcd
• Content: abcdabcdefghabce

Output

2

Expected function signature

function count(content: string, pattern: string): number;

Expected usage

let content = "abcdabcdefghabce";
let pattern = "abcd";
assert(count(content, pattern), 2);

problem_04.md

Problem

Write a function that implements a very simple syntax highlighter that applies bold styling to the words cat and dog in a given string.

Input

the cat jumped over the dog

Output

[
  [`the `, Style.None], 
  [`cat`, Style.Bold],
  [` jumped over the `, Style.None],
  [`dog`, Style.Bold]
]

Expected function signature

enum Style { Bold, None }; // https://www.typescriptlang.org/docs/handbook/enums.html
type StyledString = { content: string, style: Style };
function synhi(arg: string): StyledString[]

Expected usage

let text: string = "the cat jumped over the dog";
let output: StyledString[] = synhi(text);

assert(output[0].content, "the ");
assert(output[0].style, Style.None);

assert(output[1].content, "cat");
assert(output[1].style, Style.Bold);

problem_05.md

Problem

Implement a ring buffer in TypeScript. The ring buffer is a queue abstract data type that’s implemented using a fixed size array.

• This makes it performant with additions and deletions from a runtime and memory standpoint. Since it does not change its size once created, there's no overhead w/ increasing or shrinking the size of it's underlying array.
• The ring buffer API is very similar to that of a queue; it hides the fact that there's a fixed size buffer that's underpinning its implementation.
• When creating a ring buffer you have to specify it's size.

Here's some TS code that you might consider using to start implementing your ring buffer.

/**
 * RingBuffer uses a fixed length array to implement a queue, where,
 * - [tail] Items are added to the tail
 * - [head] Items are removed from the head
 * - [capacity] Keeps track of how many items are currently in the queue
 */
class RingBuffer<T> {
  constructor(size: number);
  clear();
  enqueue(item: T);
  dequeue(): T?;
  peek(): T?;
  len(): number;
}

Here's an example of how this ring buffer might be used:

const buffer: RingBuffer<string> = new RingBuffer(3);
buffer.enqueue("one");
buffer.enqueue("two");
buffer.enqueue("three");

assert(buffer.peek(), "one");
assert(buffer.len(), 3);

buffer.clear();
assert(buffer.len(), 0);

buffer.enqueue("one");
buffer.enqueue("two");
buffer.enqueue("three");
buffer.enqueue("four");

assert(buffer.dequeue(), "two");
assert(buffer.len(), 2);

assert(buffer.dequeue(), "three");
assert(buffer.len(), 1);

assert(buffer.dequeue(), "four");
assert(buffer.len(), 0);

Hints (feel free to ignore this when doing your implementation)

From https://developerlife.com/2018/08/16/algorithms-in-kotlin-3/#ring-buffer:

1. Since the array is re-used for insertions and deletions, it becomes important to be able to track the usage or capacity of the array (as items are added and removed). This capacity is used to determine whether the array is full or empty, and is used to iterate thru the elements of the array if needed.
2. In order to cycle around the array, the head and tail indices are updated such that when they hit the “end” of the array, they “flip” over. This means that when head reaches maxSize + 1, it just goes to 0. This can be achieved easily by using the % operator. tail = (tail+1) % maxSize is the equivalent of if (tail == maxSize) tail = 0.
3. In order to get all the elements out of the array (as a list) the capacity and the head (or read index) is used in order to get all the elements out as we would expect (which isn’t necessarily how they are laid out in the array).

problem_06.md

Problem

Let's say that you are working on a text editor application. This editor allows lines of plain text to be edited by a user who is running this application. More details about this application are not provided.

The task is to create a function that will allow the user to move the caret to the left and to the right. The details about how these input events are captured are not provided.

This is what the editor data might look like.

{
  caret: {
    row: 0,
    column: 0,
  },
  lines: [
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
  ],
}

• The caret is represented by a row and column index.
• The lines are represented by a 2D array of strings (not chars).
• When the caret is at the end of a line, and is moved to the right it will move to the beginning of the next line.
• Similarly, when the caret is at the start of a line, and is moved to the left it will move to the end of the previous line.

Expected function signatures

Here's the function signatures that you need to implement:

function moveCaretLeft(editorData);
function moveCaretRight(editorData);

Note that this function will mutate the argument that is passed in. This is not a pure function.

Expected usage

And here is what a test might look like. However, this test is not exhaustive and doesn't really capture all the edge cases. As a bonus, you can provide a test w/ the edge cases (eg: caret is at the end of a line and is moved to the right, but there are no more lines, etc.)

const editorData = {
  caret: {
    row: 0,
    column: 0,
  },
  lines: [
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
  ],
};
moveCaretLeft(editorData);
assert(editorData.caret.row === 0);
assert(editorData.caret.column === 0);

moveCaretRight(editorData);
moveCaretRight(editorData);
moveCaretRight(editorData);
assert(editorData.caret.row === 1);
assert(editorData.caret.column === 1);

problem_07.md

Problem

Let's say that you are working on a text editor application. This editor allows lines of plain text to be edited by a user who is running this application. More details about this application are not provided.

The task is to create a function that will clip the line at the caret, to a given start and end position. This can happen in cases where you have a long line of text and the editor application wants to display just a portion of the line to the end user.

This is what the editor data might look like.

{
  caret: {
    row: 0,
    column: 0,
  },
  lines: [
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
  ],
}

• The caret is represented by a row and column index.
• The lines are represented by a 2D array of strings (not chars).

Expected function signatures

Here's the function signatures that you need to implement:

function clipLineTo(editorData, columnStartIndex, columnEndIndex);

This function will also return the clipped line. It does not modify the editor data (caret & lines).

Expected usage

And here is what a test might look like. However, this test is not exhaustive and doesn't really capture all the edge cases.

const editorData = {
  caret: {
    row: 0,
    column: 0,
  },
  lines: [
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
  ],
};

{
  let line = clipLineTo(editorData, 1, 2);
  assert(line === "bc");
}

{
  editorData.caret.row = 1;
  editorData.caret.column = 1;  
  line = clipLineTo(editorData, 0, 1);
  assert(line === "de");
}

problem_08.md

Problem

Let's say that you are working on a text editor application. This editor allows lines of plain text to be edited by a user who is running this application. More details about this application are not provided.

The task is to create a function that will take a viewport (specified by origin position and size) and clip the content to the viewport & return that as a new array of lines. This can happen in cases where you have a many lines of text and each line can be very wide, and the editor application has to clip the content to the viewport. This is something we take for granted in all modern GUI apps.

This is what the editor data might look like.

{
  caret: {
    row: 0,
    column: 0,
  },
  lines: [
    ["a", "b", "c", "d", "e", "f"],
    ["g", "h", "i", "j", "k", "l"],
    ["m", "n", "o", "p", "q", "r"],
    ["s", "t", "u", "v", "w", "x"],
  ],
}

• The caret is represented by a row and column index.
• The lines are represented by a 2D array of strings (not chars).
• The viewport is represented by:
  • row and column index
  • width and height.

Expected function signatures

Here's the function signatures that you need to implement:

function clipToViewport(editorData, viewport);

This function will also return the clipped document itself which is the same shape as the lines property of the editor data shown above. It does not modify the editor data (caret & lines).

Expected usage

And here is what a test might look like. However, this test is not exhaustive and doesn't really capture all the edge cases.

const editorData = {
  caret: {
    row: 0,
    column: 0,
  },
  lines: [
    ["a", "b", "c", "d", "e", "f"],
    ["g", "h", "i", "j", "k", "l"],
    ["m", "n", "o", "p", "q", "r"],
    ["s", "t", "u", "v", "w", "x"],
  ],
};

let clippedDocument = clipToViewport(editorData, {
  rowIndex: 1,
  columnIndex: 1,
  width: 2,
  height: 2,
});

assert(clippedDocument === [
  ["h", "i"],
  ["n", "o"],
]);

problem_09.md

Problem 09

File systems on computers have a hierarchical file system. Searching for a folder by name is a very common thing to do on computers. On Unix machines, we can use the find folder_name command. The task is to implement a very simplified version of this command.

Here's an example of a hierarchial folder structure on a Linux machine.

root                   <- On Linux, the root folder of the filesystem is `/`
  + opt                <- insertion order must **not** preserved for folders
    + chrome
  + apps
    + idea
    + android_studio
  + dev
    + java
      + java11
      + java12

1. The first step of the task is to create a data structure that can be used to represent this type of folder structure. Note that we are not concerned w/ the files that may be contained in a folder.

   const root = new Folder("root");
   let opt = root.addSubFolder(new Folder("opt"));
   let apps = root.addSubFolder(new Folder("apps"));
   let dev = root.addSubFolder(new Folder("dev"));
   opt.addSubFolder(new Folder("chrome"));
   // etc.

2. The second step of the task is to create a function that can search for a folder by name.

Expected function signature

Here's the function signatures that you need to implement:

function search(folderName: string, root: Folder, depth: number): boolean;

1. It returns true or false depending on whether it found the folder or not.
2. The depth number is used to restrict how many folders deep we can search for a folder name.
3. Note that partial matches for the names should not be considered.

Expected usage

And here is what a test might look like. However, this test is not exhaustive and doesn't really capture all the edge cases.

const root = new Folder("root");
let opt = root.addSubFolder(new Folder("opt"));
let apps = root.addSubFolder(new Folder("apps"));
let dev = root.addSubFolder(new Folder("dev"));
opt.addSubFolder(new Folder("chrome"));
// etc.

assert(search("chrome", root, 5) === true);
assert(search("java11", root, 2) === false);

Bonus # 0 - Search all the folder names in a given depth

The search() function does not return the path to the folder that is found and it doesn't report how many folders were found. You can implement both these features as a bonus if you want.

So the signature would be:

function search(
  folderName: string, 
  root: Folder, 
  depth: number
): {found: boolean, path: string[][], count: number};

So if we were searching the following hierarchy, for "java":

root                   <- On Linux, the root folder of the filesystem is `/`
  + opt                <- insertion order **should** be preserved for folders
    + chrome
  + apps
    + idea
    + android_studio
    + java
  + dev
    + java
      + java11
      + java12
      + java

The path would look something like this:

[
  ["root", "apps", "java"],
  ["root", "dev", "java"],
  ["root", "dev", "java", "java"],  
]

1. The count is simply the number of folders of the given name that were found.
2. Make sure to restrict your search to the given depth.

Hints

If you need help solving this, check out this article: https://developerlife.com/2018/08/16/algorithms-in-kotlin-3/

Bonus # 1 - Preserve the insertion order of sub folders

root                   <- On Linux, the root folder of the filesystem is `/`
  + opt                <- insertion order **should** be preserved for folders
    + chrome
  + apps
    + idea
    + android_studio
  + dev
    + java
      + java11
      + java12

Bonus # 2 - Pretty print the tree to a string

Implement the following function that takes a Node and turns into a string that can be printed to the terminal via console.log. Note that the depth of each folder is indicated by the number of spaces before the folder name (each depth is 2 spaces, so depth of 0 is 0 spaces, depth of 1 is 2 spaces, depth of 2 is 4 spaces, and so on).

function prettyPrint(root: Folder): string;

The string produced by this function might look something like:

root                      
  opt                
    chrome
  apps
    idea
    android_studio
  dev
    java
      java11
      java12

Also here's more information on tree traversal / walking on wikipedia

• https://en.wikipedia.org/wiki/Tree_traversal

problem_10.md

Problem

Caching is a very common and powerful technique used in computer programming. It is used to improve the performance of applications by storing the results of expensive operations and returning the cached result when the same operation is requested again.

The trick is to come up with a way to identify the input to the operation. This is called the cache key. The cache key is used to look up the cached result for the operation. If the result is found, it is returned immediately. If the result is not found, then the operation is performed and the result is cached using the cache key.

Another trick is to come up with a way to identify when the cached result is no longer valid. This is called the cache expiry or invalidation. The cache expiry or invalidation is used to determine when the cached result should be discarded.

Here's a signature for a function that performs a very simple operation and returns a result:

function expensiveOperation(key: any): any;

1. The first step of the task is to create a class that can cache the results of the expensive operation.

   const cache = new Cache();
   
   function expensiveOperation(key: any): any {
     // Some expensive operation happens here, but just calling stringify for now...
     return JSON.stringify(key);
   }
   
   let result = cache.get("foo", expensiveOperation); // runs expensiveOperation, returns JSON.stringify("foo")
   let result2 = cache.get("bar", expensiveOperation); // runs expensiveOperation, returns JSON.stringify("bar")
   let result3 = cache.get("foo", expensiveOperation); // returns cached result

2. The second step of the task is to provide a maximum capacity for the cache, and provide a way to discard the least frequently used keys from the cache. This means that if a key is unpopular then we discard it from the cache. If you have to choose between multiple keys to discard (since they're all unpopular) then you can choose any one of them.

Expected function and class signatures

Here's an example of the code that you might write.

class Cache {
  constructor(maxCapacity: number) {
    // ...
  }

  get(key: any, operation: (input: any) => any): any {
    // ...
  }

  contains(key: any): boolean {
    // ...
  }

  size(): number {
    // ...
  }
}

Expected usage

And here is what a test might look like. However, this test is not exhaustive and doesn't really capture all the edge cases.

const cache = new Cache(3);

function expensiveOperation(input: any): any {
  return JSON.stringify(input);
}

cache.get("foo", expensiveOperation);
cache.get("foo", expensiveOperation);
cache.get("foo", expensiveOperation);
cache.get("bar", expensiveOperation);
cache.get("fuz", expensiveOperation);
cache.get("qux", expensiveOperation);

assert(cache.size() === 3);
assert(cache.contains("foo") === true);
assert(cache.contains("qux") === true);

Bonus

If you want to go the extra mile, when you are faced w/ discarding multiple unpopular keys, you can choose the one that has been in the cache the longest (ie, discard the oldest one). This will require you to change the implementation of the cache to keep track of the order in which the keys were added to the cache.

const cache = new Cache(3);

function expensiveOperation(input: any): any {
  return JSON.stringify(input);
}

cache.get("foo", expensiveOperation);
cache.get("foo", expensiveOperation);
cache.get("foo", expensiveOperation);
cache.get("bar", expensiveOperation);
cache.get("fuz", expensiveOperation);
cache.get("qux", expensiveOperation);

assert(cache.size() === 3);
assert(cache.contains("foo") === true);
assert(cache.contains("qux") === true);
assert(cache.contains("fuz") === true);
assert(cache.contains("bar") === false);