На этой неделе мы публикуем подборку из задач и вопросов, которые даёт на собеседованиях Uber. Задачи подобрали различного уровня сложности от «Easy» до «Hard», чтобы всем было интересно. Условие дано на английском языке.
Ответы, как и прошлый раз, опубликуем в течение недели. Круто, если вы будете писать в комментариях свои варианты решений 🙂
Вопросы:
1.Какие KPI вы бы использовали, если бы запустили новый сервис Uber в определенной части мира и хотели знать, насколько он успешен?
2.Какой проект, над которым вы работали, провалился? Могли бы вы сделать что-нибудь, чтобы предотвратить его провал?
Задачи:
1.
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set. RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomSet.insert(1); // Returns false as 2 does not exist in the set. randomSet.remove(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomSet.insert(2); // getRandom should return either 1 or 2 randomly. randomSet.getRandom(); // Removes 1 from the set, returns true. Set now contains [2]. randomSet.remove(1); // 2 was already in the set, so return false. randomSet.insert(2); // Since 2 is the only number in the set, getRandom always return 2. randomSet.getRandom();
3.
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]", serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
ссылка на оригинал статьи https://habrahabr.ru/post/329208/
Добавить комментарий