Выпуск#2: ITренировка — актуальные вопросы и задачи от ведущих компаний

в 13:43, , рубрики: ITренировка, SpiceIT, uber, Блог компании Spice IT Recruitment, Занимательные задачки, Программирование, собеседование

На этой неделе мы публикуем подборку из задач и вопросов, которые даёт на собеседованиях 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.

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.

Автор: SpiceIT

Источник

Поделиться

* - обязательные к заполнению поля