Задачи для IT интервью

[assazello]

helg,
Попробовал ваш алгоритм на своем коде:
answer = (i % 2 == 0 ? ((right - left) % 3 == 0 ? left : left + 1 ) : left);

Все верно, действительно ваше решение дает 66%!

А вот мое решение: на каждом нечетной попытке называть самое первое число из допустимого интервала, а на каждой четной - случайное число из допустимого интервала.
answer = (i % 2 == 0 ? rand() % right + left : left);

Вы будете смеяться, но оно дает ~95%. Почему - я не знаю, то есть логически понимаю (уменьшаем шансы угадать на четном ходу), доказывать пытался, запутался в вероятностях и бросил.

[helg]

answer = (i % 2 == 0 ? rand() % right + left : left);

Возможно, Вы хотели сказать:

answer = (i % 2 == 0 ? rand() % (right-left+1) + left : left);

По правилам нельзя же называть числа за пределами интервала между left и right.

Если не называть на чётном ходу числа за пределами диапазона, строго доказано, что максимальный шанс выигрыша - 1333/2000.

Попробовал ваш алгоритм на своем коде:
answer = (i % 2 == 0 ? ((right - left) % 3 == 0 ? left : left + 1 ) : left);

Небольшое уточнение. Размер диапазона между left и right включительно: (right - left + 1), а не (right - left). Несмотря на то, что оба варианта: с единчкой и без, асимптотически, на больших интервалах дают вероятность выигрыша 2/3 с единичкой выигрыш выше, он теоретически максимальный. Например, на интервале 4 - он даёт шанс 0.75 против 0.5.

[assazello]

Да, вот она, ошибка копи-паста. Я чувствовал, что тут что-то не так, но прекрасный результат затмил доводы разума.
Спасибо, helg.

Ваш ответ, скорее всего, оптимальный. В том месте, где я эту задачу нашел, формулировка и была "есть ли у игрока стратегия, позволяющая добиться выигрыша в 2/3 случаев?" Т.е., ответ уже был дан и вы его нашли. Я позже код посмотрю, может еще задам пару вопросов. Спасибо!

[helg]

Ваш ответ, скорее всего, оптимальный. В том месте, где я эту задачу нашел, формулировка и была "есть ли у игрока стратегия, позволяющая добиться выигрыша в 2/3 случаев?"

Тогда нужно внимательно перечитать оригинальную формулировку условия и побуквоедить. Если интервал 1..2000 понимать в "программистском" смысле, когда левая граница включена, а правая - нет, всего чисел в таком интервале 1999. Для него ответ из таблицы 1333/1999. Это немного больше, чем 2/3, и стратегия есть. Если же оба края интервала включены, то ответ 1333/2000. Это немного меньше, чем 2/3. Стало быть, требуемой стратегии нет.

[Сабина]

-how would you architect various things around Twitter company.

Нашелся ответ на то вопрос в книжке Designing Data intensive applications. Может кому то пригодится

To make this idea more concrete, let’s consider Twitter as an example, using data published in November 2012 [13]. Two of Twitter’s main operations are:
Post tweet
A user can publish a new message to their followers (4.6 k requests/sec on average, over 12 k requests/sec at peak).
Home timeline
A user can view tweets recently published by the people they follow (300 k requests/sec).

Simply handling 12,000 writes per second (the peak rate for posting tweets) would be fairly easy. However, Twitter’s scaling challenge is not primarily due to tweet volume, but due to fan-outii — each user follows many people, and each user is followed by many people. There are broadly two approaches to implementing these two operations:

1. Posting a tweet simply inserts the new tweet into a global collection of tweets. When a user requests home timeline, look up all the people they follow, find all recent tweets for each of those users, and merge them (sorted by time). In a relational database like the one in Figure 1-2, this would be a query along the lines of:
SELECT tweets.*, users.* FROM tweets
JOIN users ON tweets.sender_id = users.id
JOIN follows ON follows.followee_id = users.id
WHERE follows.follower_id = current_user

2. Maintain a cache for each user’s home timeline — like a mailbox of tweets for each recipient user (see Figure 1-3). When a user posts a tweet, look up all the people who follow that user, and insert the new tweet into each of their home timeline caches. The request to read the home timeline is then cheap, because its result has been computed ahead of time.

The first version of Twitter used approach 1, but the systems struggled to keep up with the load of home timeline queries, so the company switched to approach 2. This works better because the average rate of published tweets is almost two orders of magnitude lower than the rate of home timeline reads, and so in this case it’s preferable to do more work at write time and less at read time.
However, the downside of approach 2 is that posting a tweet now requires a lot of extra work. On average, a tweet is delivered to about 75 followers, so 4.6 k tweets per second become 345 k writes per second to the home timeline caches. But this average hides the fact that the number of followers per user varies wildly, and some users have over 30 million followers. This means that a single tweet may result in over 30 million writes to
home timelines! Doing this in a timely manner — Twitter tries to deliver tweets to followers within 5 seconds — is a significant challenge.

In the example of Twitter, the distribution of followers per user (maybe weighted by how often those users tweet), is a key load parameter for discussing scalability, since it determines the fan-out load. Your application may have very different characteristics, but you can apply similar principles to reasoning about its load.

The final twist of the Twitter anecdote: now that approach 2 is robustly implemented, Twitter is moving to a hybrid of both approaches. Most users’ tweets continue to be fanned out to home timelines at the time when they are posted, but a small number of users with a very large number of followers are excepted from this fan-out. Instead, when the home timeline is read, the tweets from celebrities followed by the user are
fetched separately and merged with the home timeline when the timeline is read, like in approach 1. This hybrid approach is able to deliver consistently good performance

[assazello]

Задача из Белого Дома.
https://www.whitehouse.gov/blog/2015/05/17/hello-world

Alice and Bob are playing a game. They are teammates, so they will win or lose together. Before the game starts, they can talk to each other and agree on a strategy.

When the game starts, Alice and Bob go into separate soundproof rooms – they cannot communicate with each other in any way. They each flip a coin and note whether it came up Heads or Tails. (No funny business allowed – it has to be an honest coin flip and they have to tell the truth later about how it came out.) Now Alice writes down a guess as to the result of Bob’s coin flip; and Bob likewise writes down a guess as to Alice’s flip.

If either or both of the written-down guesses turns out to be correct, then Alice and Bob both win as a team. But if both written-down guesses are wrong, then they both lose.

The puzzle is this: Can you think of a strategy Alice and Bob can use that is guaranteed to win every time?

To get you started, here is an example of a strategy that doesn’t work: Alice and Bob decide in advance that they will both guess Heads. This isn’t a guaranteed-winning strategy, because a quarter of the time they will both flip Tails so both guesses will be wrong. They’ll win 75% of the time, but that isn’t enough – they need to win every time.

It might seem at first like this puzzle is impossible, but don’t give up – there is a solution, which I’ll reveal in a future post. In the meantime, watch my Twitter stream @edfelten44 for hints.

[helg]

А загадывает то, что у неё выпало, Б - обратную сторону того, что выпало у него. Когда монетки выпали одной стороной, угадывает A, когда разными - Б.

[assazello]

Да, это старая загадка. А вот источник забавный.

Кстати, не все знают, но есть и обобщенное решение для N игроков.

[Сабина]

Кстати если кому из ребят скучно готовится к интервью, вот вам в подмогу . (До чего только народ на ютьюбе не додумается )

https://www.youtube.com/user/itcuties/videos

[XpoH]

Огонь!

[assazello]

Кстати, не все знают, но есть и обобщенное решение для N игроков.

Никто не поддержал... потому, что очевидно или потому, что непонятно?

Я сформулирую тогда. N человек играют в игру - каждый генерирует случайное число из отрезка от 1..N (подбрасывая монету или используя генератор случайных чисел), а после называет число из того же отрезка. Если хотя бы один из участников назвал число, сгенерированное хотя бы одним из других участников, то игра выиграна, иначе - проиграна. Найти 100% выигрышную стратегию.

[MaximS]

Есть подраздел Головоломки, то я хочу все таки что-то попроще и более приближенного к IT сфере. То, что можно спросить на интервью и понять, как кандидат думает и думает ли он вообще.

Например.

Программист преследует Вора, который пытается скрыться в пещере. Пещера представляет собой 3 туннеля одинаковой длины, расходящихся из небольшой комнаты под углом 60гр к друг другу и заканчивающихся тупиком. В пещере темно, и Программист может разглядеть Вора только с расстояния не более 10м. Скорость Программиста в два раза больше скорости Ворв. При какой максимальной длине туннеля Программист может гарантированно поймать Вора за конечное время?

Что скажете, Умы?

Не меньше пяти километров думаю, иначе никак

[Сабина]

Спросили на днях закодировать Multiset. Сделала через HashMap, но нашла в И-нете варианты с LinkedLists ( keySet, valueSet).
Никому не доводилось ? Как сделали ?
PS. Что там гуглогуава написала в оригинале смотреть поленилась, многа буков

[Сабина]

Спросили на днях закодировать Multiset. Сделала через HashMap, но нашла в И-нете варианты с LinkedLists ( keySet, valueSet).
Никому не доводилось ? Как сделали ?
PS. Что там гуглогуава написала в оригинале смотреть поленилась, многа буков

Задачка на multiset может быть простая, например дан string "adbafgeef" а на выходе надо выдать "a2b1d1e2f2g1"

MultiSet для этого дела:
a: 2,
b: 1,
d: 1,
e: 2,
f: 2,
g:1


Вот например парень делает через два листа - http://magicoftutorial.blogspot.com/201 ... ation.html" onclick="window.open(this.href);return false;

А то что я делала через ХашМап примерно было вот так

Получается что такая вот версия например не очень efficient

Код: Выделить всё

public class MultiSet {
	private static Map<Character, Integer> m = new HashMap<Character, Integer>();
	
	private static Map<Character, Integer> buildMultiSet(String s) {
		char[] stringChars = s.toCharArray();
				for (int i = 0; i < stringChars.length; i++) {
					if (m.containsKey(stringChars[i]))
						m.put(stringChars[i], m.get(stringChars[i]) + 1);
					else
						m.put(stringChars[i], 1);
				}
		return m;
	}
	
	public static String printStringMultiSet (String s) {
		StringBuffer buf = new StringBuffer();
		for (Map.Entry<Character, Integer> entry: buildMultiSet(s).entrySet()) {
			buf.append(entry.getKey()).append(entry.getValue());
			
		}
		return buf.toString();
	}
}

Оказывается самое еффективное бы было сделать через char[] array.
Index = (Integer) charAt
value = count of this char occurences.

При условии что речь идет об ASCII chars (всего в массиве 128)

[Сабина]

Сегодня интересную задачку дали. Точнее оптимальное решение шокировало простотой.

У вас есть linked list с nodes следующего формата:

public class Node {

int data,
Node next,
Node random}

Где random - это линк на любой другой node в том же листе, включая null, self etc.
Задача написать clone метод для листа.