WuchiOnline

/*

Given a string and a set of words, break the string into a list of words from the set. If the string can not be segmented fully, return an empty list.

Example:
Set: {"jump", "jumped", "jumpedov", "over", "some", "thing", "something"}
String: "jumpedoversomething", 
Can return [“jumped”, “over”, “something”] or  [ “jumped”, “over”, “some”, “thing”]

WuchiOnline

/*

Kth Smallest Number in M Sorted Lists:
Given ‘M’ sorted arrays, find the K’th smallest number among all the arrays.

Example:

Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4], K=5
Output: 4

WuchiOnline

/*

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]

Approach:
// Create a class NumCountPair that implements IComparable to use in a MinHeap, which CompareTo other NumCountPairs based on their Count properties
// Use a dictionary to hold KeyValuePairs where the key is the number and the value is its frequency // tO(N), sO(N)

WuchiOnline

/*

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

Example:

Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]

Approach:

WuchiOnline

public class MaxHeap<T> where T: System.IComparable<T> 
{
    public List<T> heapList {get; set;}

    public int Count {get => heapList.Count;}

    private int GetLeftChildIndex(int elementIndex) => 2 * elementIndex + 1;
    private int GetRightChildIndex(int elementIndex) => 2 * elementIndex + 2;
    private int GetParentIndex(int elementIndex) => (elementIndex - 1) / 2;

WuchiOnline

/*

Full solution to Merge K Sorted Lists with custom MinHeap<T> and ListNode classes implemented.

*/

using System;
using System.Collections;
using System.Collections.Generic;

WuchiOnline

/*

Given a directed graph, find the topological ordering of its vertices.

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
Output: Following are the two valid topological sorts for the given graph:
1) 3, 2, 0, 1
2) 3, 2, 1, 0

Underlying concepts:

WuchiOnline

public class MinHeap<T> where T: System.IComparable<T> 
{
    public List<T> heapList {get; set;}

    public int Count {get => heapList.Count;}

    private int GetLeftChildIndex(int elementIndex) => 2 * elementIndex + 1;
    private int GetRightChildIndex(int elementIndex) => 2 * elementIndex + 2;
    private int GetParentIndex(int elementIndex) => (elementIndex - 1) / 2;

WuchiOnline

public class MinHeap
{
    private readonly int[] _elements;
    private int _size;
    public int Count {get => _size;}

    public MinHeap(int size)
    {
        _elements = new int[size];
    }

WuchiOnline

System Design Cheatsheet

Picking the right architecture = Picking the right battles + Managing trade-offs

Basic Steps

1. Clarify and agree on the scope of the system

• User cases (description of sequences of events that, taken together, lead to a system doing something useful)
  • Who is going to use it?
  • How are they going to use it?