Self check

 In what circumstance would you use BFS (Breadth First Search) instead of Dijkstra's for finding a shortest path in a graph?

a) When you have an unweighted graph

or

b) When you have a weighted graph

What is the worst-case lookup time for a self-balancing binary search tree? Can you name a common example or type?

What is the average running time of heapsort in big-O notation? What is one benefit of using heap sort compared to merge sort?

Which of the following typically uses a Queue for an efficient implementation?

a) Breadth First Search (BFS)

b) Depth First Search (DFS)

c) Recursion

Which of the following data structures do NOT guarantee O(log n) lookup time?

a) red-black tree

b) binary tree

c) linked list

d) hash table

bcd

1. Score Negative 

2. Communication - was good 

3. Explain theory very well

4. Better solution - pick up hints

5. Data Structure & Algorithm 

6. Coding - Pretty readable and boundary cases.

7. Time Management - M 20 mins, H 35 mins 

A Supply Chain

Cap Theorem  where cosmos db stads for ?

how Distributed system works 

Gossip protocol - they maintain consistency with this

Raft protocol - 

consensus protocol

Adapter Pattern

SOLID Principles

composition over inheritance 

Strategy Pattern - DI - change dynamically 

Anti Patterns 

Flatten [[1,2],[3,[4,[5]]]] in javascript 

1. Given a set of boxes, reduce the total number of boxes by placing smaller box inside a bigger box.

you can't put more than one box of same size inside a bigger box. return the sum of final box sizes.
{10, 50, 20, 40, 30} Returns: 50
{100, 50, 100, 50, 50, 100} Returns: 300

2. Given an array of integers of size 2n, write an algorithm to arrange them such that first n elements and last n elements are set up in alternative manner.

Say n = 3 and 2n elements are {x1, x2, x3, y1, y2, y3} , then result should be {x1, y1, x2, y2, x3, y3}.
2n is always in power of 2, that is 2^i

Example:

 A [] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10}, n= 5
Output: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A SAP :

3. Given a stream of integers, find the first non-duplicate integer

4. Check whether the tree is complete binary tree or not.

Topics to cover:

Binary search

Graphs, BFS/DFS/Flood fill Tree traversals Hash tables Linked list, stacks, queues, two pointers/sliding window Binary heaps Dynamic programming Union find Ad hoc/string manipulations Arrays Recursion. Backtracking. Greedy algorithms. Other good to know topics: Trie, segment trees/fenwick trees, bitmasks

SF:

1. Trapping Rain water

2. Generate Paranthesis

3. Design rating system of employee

4. Maximum Subarray square

M365:

Input:

Hex Array= [0, a, f]

Roll Array = [2,3,1]

RollArray[0] = 2 => Roll the first two elements

Hex array = [1,b,f]

RollArray[1] = 3

HexArray=[2,c,0]

0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f

RollArray[2] = 1

HexArray = [3,c,0]

Design Tiny bit shorten url 

Viva:

Given a binary matrix mat[][] of dimensions of N * M and pairs of integers src and dest representing source and destination cells respectively, the task is to find the shortest sequence of moves from the given source cell to the destination cell via cells consisting only of 1s. The allowed moves are moving a cell left (L), right (R), up (U), and down (D) (if exists). If no such path exists, then print “-1”. Otherwise, print the sequence of moves.

Substrate:

Design online paint - enums for tools, bucket fill algo - utilised surrounding 1 in matrix coloring

m365  

Design coauth in editor

Rotate an array by shifting its elements 3 positions to right

Find 3rd highest element  in BST

Internal team

Given a linked list with duplicate elements, remove all duplicate elements

a bit tricky -     You are given a maze (unknown dimensions) & a robot is placed somewhere in the maze. The robot has 4 functions… canMoveLeft(), canMoveRight()….etc

       There is gold somewhere in the maze. Return the path from start to gold. Follow up - There is no gold now…. just traverse the entire maze…. How do you traverse the entire maze?

3. Given a binary tree, return the reverse level order traversal….. ie the first entry should be the list of all leaves

4. Given a string, find the biggest palindrome & return the biggest palindrome

Microsoft - PowerBI

Find the Kth largest element in an array

Microsoft - Azure

Given a list of integers, all intergers occur more than once except one. Find that element

Given a list of integers, all elements occur twice except one. Find it

2nd team -

Given 2 linked list , findout if its merged & return the first common element

Given a list of stock prices of a company , find the best time to buy & sell

Amazon

1. events[i] = [startTimei, endTimei, valuei]

Example : 

Input: events = [[1,3,2],[4,5,2],[2,4,3]]

Output: 4

Max value from 2 events or 1.

(1) Two Best Non-Overlapping Events - LeetCode

2. /*

      a

     /  \

    b    c

   / \   / \

  d   f c   b

  

  ab < aba

Lexicographically smallest from leaf to root

(1) Smallest String Starting From Leaf - LeetCode

Fb:

1. https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

2. https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Rubrik:

/**

class Work:

  def do_work(self):

    // few mins to days.

    pass

class WorkCompleter:

 

  # Fill in as necessary.

  def __init__(self):

    pass

 

  # Schedules work to be done on [work], i.e. the user

  # schedules work.do_work() to be called.

  # This method should return as quickly as possible.

  def schedule(self, work):

    pass

 

  # Does not return until all previously scheduled work

  # has been completed.

  def block_until_complete(self):

    pass

*/