Problem Design the data structures for a generic deck of cards. Explain how you would sub-class it to implement particular card games. Solution Before that lets understand deck of cards: Understanding Deck of Cards. We’ll start by defining the basic structures: Card, Deck, and Suit. Basic Components Suit Enum public enum Suit { HEARTS, DIAMONDS, CLUBS, SPADES; } ...
Problem Design the data structures for an online book reader system. Solution We will have 2 simple classes - book and user. Book.java public class Book { private long id; private String title; private long authorId; public long getID() { return ID; } public Book(long id, String title, long authorId) { // ... } } ...
Problem Imagine you have a call center with three levels of employees: fresher, technical lead (TL), product manager (PM). There can be multiple employees, but only one TL or PM. An incoming telephone call must be allocated to a fresher who is free. If a fresher can’t handle the call, he or she must escalate the call to technical lead. If the TL is not free or not able to handle it, then the call should be escalated to PM. Design the classes and data structures for this problem. Implement a method getCallHandler(). ...
Stack of Plates Problem Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack). ...
Problem Given a set of distinct integers/characters, S, return all possible subsets. OR Given an integer array nums of unique elements, return all possible subsets (the power set). Examples If we’re given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the set of all subsets i.e. P(S) we get are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Here is {} is empty set denoted by Φ. ...
Problem Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself. Examples Example 1: ...
Problem Given an m x n matrix of 0s and 1s, provide an algorithm such that if an element is 0, its entire row and column is set to 0 OR Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s. You must do it in place. Follow Up: Can you do it in one pass? ...
Problem Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. If there is no cycle, return null. Try solving it using constant additional space. Definition - Circular Linked List A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. This is extension of Linked List Cycle 1 - Detect Cycle ...
Problem An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color. ...
Problem Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement the MyQueue class: void push(int x) Pushes element x to the back of the queue. int pop() Removes the element from the front of the queue and returns it. int peek() Returns the element at the front of the queue. boolean empty() Returns true if the queue is empty, false otherwise. Notes: ...