Тогда нужно внимательно перечитать оригинальную формулировку условия и побуквоедить. Если интервал 1..2000 понимать в "программистском" смысле, когда левая граница включена, а правая - нет, всего чисел в таком интервале 1999. Для него ответ из таблицы 1333/1999. Это немного больше, чем 2/3, и стратегия есть. Если же оба края интервала включены, то ответ 1333/2000. Это немного меньше, чем 2/3. Стало быть, требуемой стратегии нет.assazello wrote:Ваш ответ, скорее всего, оптимальный. В том месте, где я эту задачу нашел, формулировка и была "есть ли у игрока стратегия, позволяющая добиться выигрыша в 2/3 случаев?"
Нашелся ответ на то вопрос в книжке Designing Data intensive applications. Может кому то пригодитсяСабина wrote: -how would you architect various things around Twitter company.
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
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.
. (До чего только народ на ютьюбе не додумается )Никто не поддержал... потому, что очевидно или потому, что непонятно?assazello wrote: Кстати, не все знают, но есть и обобщенное решение для N игроков.
Не меньше пяти километров думаю, иначе никакBerlaga wrote:Есть подраздел Головоломки, то я хочу все таки что-то попроще и более приближенного к IT сфере. То, что можно спросить на интервью и понять, как кандидат думает и думает ли он вообще.
Например.Что скажете, Умы?Программист преследует Вора, который пытается скрыться в пещере. Пещера представляет собой 3 туннеля одинаковой длины, расходящихся из небольшой комнаты под углом 60гр к друг другу и заканчивающихся тупиком. В пещере темно, и Программист может разглядеть Вора только с расстояния не более 10м. Скорость Программиста в два раза больше скорости Ворв. При какой максимальной длине туннеля Программист может гарантированно поймать Вора за конечное время?
Задачка на multiset может быть простая, например дан string "adbafgeef" а на выходе надо выдать "a2b1d1e2f2g1"Сабина wrote:Спросили на днях закодировать Multiset. Сделала через HashMap, но нашла в И-нете варианты с LinkedLists ( keySet, valueSet).
Никому не доводилось ? Как сделали ?
PS. Что там гуглогуава написала в оригинале смотреть поленилась, многа буков
Code: Select all
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();
}
}
Сразу приходит в голову простое двухпроходное решение, если разрешается временно модифицировать входной список, т.е. временно установить поля 'random' входного списка в новые значения, а потом вернуть обратно (т.е. в итоге исходный список останется неизменным). Но такая возможность должна быть явно оговорена в постановке задачи, ибо традиционная каноническая постановка задачи предполагает, что входные данные являются read-only.Сабина wrote:Задача написать clone метод для листа.
Можно вместо random модифицировать поля next исходного списка: на первом проходе вставлять клонированый узел в оригинальный список сразу за соответствующим неклонированым. Соглашусь с AndreyT, что это бомба замедленного действия. Стандартную реализацию clone() можно вызывать из нескольких нитей одновременно, равно как и другине немодифицирующие методы. А такую нельзя, - и умудрённый опытом инженер так писать не будет.AndreyT wrote:Сразу приходит в голову простое двухпроходное решение, если разрешается временно модифицировать входной список, т.е. временно установить поля 'random' входного списка в новые значения, а потом вернуть обратно (т.е. в итоге исходный список останется неизменным). Но такая возможность должна быть явно оговорена в постановке задачи, ибо традиционная каноническая постановка задачи предполагает, что входные данные являются read-only.Сабина wrote:Задача написать clone метод для листа.
Да, это второй правильный вариант, но есть еще вариант без мапа.John Smith wrote:меп старых нодов на новые, тогда на очередном next node - если меппинг для него уже в мэпе есть - значит он у кого то был рандомом - нужно будет только проапдетить его data.
Побочных эффектов, пусть даже они у красивого решения, надо стараться избегать. В данном случае, клонированный список всё равно ест O(N) памяти, и потратить объём такого же порядка на временный маппинг в решении без побочных эффектов вполне нормально.Сабина wrote:Про первый вариант не совсем поняла почему "умудренный опытом инженер так писать не будет".
Уточните задачу. Несвязный граф, к примеру, подходит под определение "любой граф"?avitya wrote:Для тех, кому легко, рекомендую сделать clone() для любого графа (сейчас это граф с 2 выходящими ребрами из каждой вершины, кроме последней).
Everytime when a url is to be shortened, url_id field is incremented, url_id is converted to base-36 ( 26 alphabets + 10 digits ) OR base-62 ( 26 small alphabets + 26 capital alphabets + 10 digits ) which serves as primary key for each tuple. A string i.e. the actual url is added corresponding to this key in database. The primary key is appended to service providers domain name after '/' and returned to the user.
Usually its better to add a new url_id rather than searching for existence of a url in database. So same url can be shortened to multiple short url's.
But some sites do take care of not adding multiple short url's in database if same user try to reproduce it. They consider user location for this purpose.
