Problem Given the root of a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. Examples Example 1: ...
Problem Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense). ...
Problem You are given the head of a singly linked-list. The list can be represented as: $$ L_0 → L_1 → … → L_{n - 1} → L_n $$ Reorder the list to be on the following form:: $$ L_0 → L_n → L1 → L_{n - 1} → L2 → L_{n - 2} → … $$ Examples Example 1: --- title: Input List --- graph LR A1[1] --> B2[2] --> C3[3] --> D4[4] ...