ganceanu

[ganceanu]

Solution for Cute Quiz #1

I posted "Cute Quiz #1" 4 weeks ago. For the first 2 weeks nobody submitted a solution, but then I found the Chrome pillow in the box with my children's stuffed toys.

Soon after I advertised the pillow, five people submitted working solutions. Two said they would like the pillow to go to someone else, so I had to pick a winner out of three. I did choose by throwing a real 🎲. 

And the winner is Victor Stoian. Congrats!

Let's talk about the solution now. Fetching each page would work only if the site has few pages. For 1000 pages each loading in 1 second, this would take ~16 minutes of not so interesting work involving clicking the next button in the browser. Fetching the pages could be automated using a script, however the site owner might get unhappy and block the script if this generates a lot of work for the servers behind the site.

Furthermore, if the site has billions of pages, fetching every page becomes intractable. We could question the utility of so many pages, but let's just say that such a site exists, just to make the problem more challenging.

One thing we can immediately take advantage of is the estimation on the first page. We can compute a page based on that estimation and try to fetch it. If it exists and has fewer than N results, we found the last page by just fetching two pages. Lucky!

If it has N results (it's a "full page"), we can take the estimation on that page and repeat.

However, if the page does not exist, we have to try smaller pages until we find one that exists. This can be achieved using a binary search.

I was particularly impressed by the elegant solution, analysis and Python code submitted by Andrei Olariu. Great job! 

Here is my solution, trying to combine binary search with being greedy when a full page is found. As the comments suggest, I am not sure this is the best we can do, but it's the best I could think of so far :)

Definitions

results(i) = number of results on the i-th page; 0 if the page does not exist 

estimation(i) = estimated number of pages based on the estimation available on the i-th page; we assume estimation(i) >= i for any non-empty page

report_answer(a) = reports that the number of total results is a and terminates the program

Pseudo-code

l = 1, r = max(1, estimation(1)), p = r

ans = 0, min_inexistent_page = infinity 

while (l <= r) {

  nr = results(p)

  if (nr == 0) {

    min_inexistent_page = p

    r = p - 1

    p = l + (r - l) / 2

  } else if (nr == N) {

    ans = p*N

    l = p + 1

    e = min(min_inexistent_page - 1, estimation(p)) 

    // Make sure we make at least one more iteration, 

    // since we are not sure yet if l-th page exists or not

    r = max(l, e)

    // We also ask for r-th page and not the middle, which might work better 

    // as the estimations get better. However, this was not analyzed in detail 

    // and there might be cases when it will perform worse.

    p = r

  } else {

    // p must be the last page since it has between [1, N-1] results.

    report_answer(nr + (p-1)*N)

  }

}

// This covers the case when the last page is full.

report_anser(ans)

I hope you liked this quiz! Let me know if you want to see more like this via comments or reactions on social media sites.

[ganceanu]

Why You Should Vote

The Romanian presidential election will take place soon. 

Folks that live abroad, like me, can register for voting on http://votstrainatate.ro. I just did and it was quite simple. The option to vote from home is also offered.

But why should we go through the trouble and vote? 

Here is a TED talk giving reasons why the young people should be active politically.

However, these videos with Stephan the Great and Michael the Brave are shorter and more to the point. They crack me up everytime I watch them :))

[ganceanu]

The Value of Mistakes and Failure

“To try and fail is at least to learn; to fail to try is to suffer the inestimable loss of what might have been.” Chester Barnard 

“You miss 100% of the shots you don't take.” Wayne Gretzky

“A new answer to the same question / How many times will you learn the same lesson?” “Legendary” song by Welshly Arms

Celebrate your success, embrace and learn from your failures.

I'm not going to explain too much about the first part. Everyone knows how important success is. Without it you can't go on with your pursuit, be it your education, business or job. Performance is usually evaluated on your success, if you don't perform you don't promote, you don't raise another round of investment, etc. We all know that. 

Success generates success. That is also touted a lot. The more success you have, the more likely it is that you know how to be successful again in a new endeavour. "Serial entrepreneur" basically implies that you started multiple businesses and you had enough success to be motivated to start another. Given how hard it is to start a business, you would be crazy to continue trying after failing 10 times in a row.

I will not say more about success, because what we don't do enough is talk about our failures. My claim is that we are underestimating by a high margin the value of failure.

This can be partially because failure feels a lot worse, in particular when it can be attributed directly to you. Instinctively, you try to forget as quickly as possible, you try to hide it from others, including parents, managers or investors.

I propose to embrace failure. Let it feel bad for a while. That feeling usually motivates you to figure out the causes of the failure. And if you discover something that you could have done differently to at least increase the chances of success the next time, you learned something very useful since it's from your own unique experience. No amount of reading or coaching could teach you that.

Of course some lessons can be learned without making the mistakes yourself. I can tell you for sure that regular smoking is really bad for you. There is enough evidence to make this not worth exploring yourself at the risk of badly harming your health. There is not much to be learned from starting to smoke other than perhaps how hard it is to give up a harmful daily habit later on in life.

Same goes with certain psychoactive substances like heroin. If you try heroin, the chances are high you would want to try again which very quickly leads to a really strong addiction. Read about opioid addiction and what happens if you go down that path and you know that is not a mistake worth making. The risk cost versus the opportunity to learn something useful simply don't make sense in this case.

But most other mistakes and failures are not that harmful.

You tried some new move while playing soccer with your friends. You fell, you sprained an ankle. It will recover after some time. Through that time you learn that you risked too much and now you can't play soccer because of that. This one is easy. 

You were over ambitious and committed to too many goals, more than you can handle. You fail some of those goals, perhaps you burn out. Now for some time work is really unattractive, perhaps even life doesn't make much sense. But then you discover you have friends and family that care deeply about you and with some suffering, a lot of care and therapy, you get back on your feet. You learn to put priorities in your life. You learn that work, career success or business is really not more important than your health. You might learn that you have friends even at work. You might discover you had interest in a different type of work and you make a pivotal turn in your career.

This one is tricky because some people burn out and don't fully recover. So don't burn out that badly, please. Ideally you never burn out, but instead learn that work is not much more than something to keep your hands and mind fit and oriented towards a goal. You might have the ambition to change the world with your business, career or scientific research. But you will never get to change the world if you burn out and don't recover. Don't let over-ambition stand in the way of the end goal of your pursuit. Most "world changing" goals involve a marathon of work spread over the years, usually involving many more people than yourself. Whatever you do must be sustained over time, bursts don't work in the long run.

If you optimize for learning and well-being you are probably on a very good path. You made a mistake that cost you your job, half of your savings or your startup. As long as that mistake did not hurt your well being or freedom, as long as you learned your lesson out of it, you will be able to move on with your life. You will find a way to stay happy even without what you just lost, at least until you have a new job or a new business idea. This does not apply if you are retired. But then you don't have a job that pays and hopefully your savings don't disappear overnight.

Celebrate your success. I know you will in your presentations, promotion statements, elevator pitches and chats with your friends. However, don't forget the value of mistakes and failures. Don't hide them under the carpet. You are then giving up an excellent opportunity to learn something unique to you, and this is priceless. 

Don't be engulfed for too long with the natural feelings that surround a mistake or failure. Then you get depressed and sacrifice your well being. But don't move away too quickly from these feelings either because they are just as important and human as pride and joy are. 

I would go as far as to say that if you don't make mistakes in your pursuit, you are not progressing as fast as you could. 

But be more careful when your mistakes have the potential to make more people suffer. Those mistakes have a higher weight than the mistakes that only cause suffering on your end. Also be more careful with the mistakes that have potential for bigger material losses. Those large losses could be used for better purposes.

However, you will never develop a sense for the risk of an action without making some mistakes yourself. If you have someone with experience that is helping you to avoid the big mistakes, appreciate that help because it is very valuable. But assert your courage to make some decisions yourself and don't be too afraid of making a mistake in front of that person. They are likely wise enough to know the value of such a mistake.

Here is video of the Kung Fu Panda scene from which the above picture comes from.

You made a mistake. First off, congratulations! How do you learn the most out of this mistake? Here is a list of ideas of what you could do:

First make sure you recovered from the mistake, psychologically, physically and materially.

Assess how big of an impact the mistake had and whether it's worth going the extra mile to avoid making this type of mistake in the future.

Understand the reasons that lead to the mistake. Would the outcome be any different if you made different choices or acted differently? 

Register what you learned in a document living the cloud or your paper notebook. Review the notes with some regularity (e.g., once every 3 months).

Talk to a few people about your mistake and your analysis so far. This might bring new perspectives and new lessons. Also, talking to people means you are on a good path acknowledging and accepting your mistake.

For bigger mistakes, write a postmortem. Find someone to review the postmortem, in particular what action items you will commit to to reduce the likelihood of this mistake happening again. 

There is also the concept of pre-mortem, but that seems to be about avoiding mistakes as a team. This is also very valuable.

After you have done the analysis, collected your learnings, make sure you move on and don't ruminate about the mistake.

I am quite grateful for the many suggestions I received from three special people that reviewed early drafts of this post:

Nelson Mattos -- COO of the Karimu Foundation. I really like the mission of the foundation! 

To the other folks: if you’d like your name to be mentioned here, please let me know :)

[ganceanu]

Algorithms & Data Structures and why studying them is good for interviews

I initially wrote this in Romanian (see this doc) to motivate high-school students to study Algorithms & Data structures in their Computer Science classes. I wrote that doc as a basis for a workshop with a class of students in my former high-school (Gheorghe Roșca Codreanu National College Bârlad -- wikipedia in Romanian). 

I recently realised that this material might be useful to other people, so I decided to translate it into English as well. I will preserve the style of a document meant for a workshop.

Key Messages

The coding interviews at big tech companies are standardized. An interview lasts about 45 minutes and you are asked to write some code for a task solvable by a good candidate in about 30 minutes. In phone screens (prior to onsite interviews), you get to write your solution in a doc or a code-editor. In onsites (usually 4-5 during 1 day in an office of that company), usually you write on a whiteboard (there might be other options).

There are other types of interviews, but for folks coming straight out of a Bachelor’s Degree the expectation is that they do very well on the coding interviews. The programming language is usually not that important for this type of candidates.

To excel in the coding interviews, you need to have a solid basis in Algorithms (e.g., all basic sorting algorithms and when it’s good to use one or the other, graph traversals) and Data Structures (e.g., kinds of lists & vectors, stack/queue, hash sets, how to represent a graph). 

Another important skill is to estimate the complexity of a piece of code: how many steps does it require for a given input, how much memory it consumes & what type of memory, if it writes to disk what are the consequences of that, etc.

To solve a typical algorithmic problem involves at a smaller scale the skills required to design a system or an application:

Exploring the problem space: what are the requirements, how big is the input, special cases, constraints, non-goals.

Breaking down the problem into subtasks that are easier to solve on their own: reading the input, representing the data, solve sub-task #1 & sub-task #2, combine the results, output the final results.

Analyse your solution: typical algorithmic problems have bounds for time & memory allowed to be used. If there are no such bounds, the question becomes “Will it run in 1 second, 1 day or our life time? Will it run on a typical machine or does it need more resources? What are the bottlenecks?”

Test your solution: write a separate program that implements a brute-force version of the solution and cross check the output with your most efficient solution so far.

Sample Quizzes

One of my blog posts (Cute Quiz #1) gives a good example of an algorithmic question coming from the real world of the Internet. See if you can solve it! Warning: it’s quite though :)

You have in front of you a ladder with N steps. You can make jumps of 1 or 2 steps. In how many different ways can you climbe the whole ladder?

Recommended Reads / Videos

Introduction to Algorithms: I read this book in the last years of my high-school and I understood 70% of it. It’s one of the few books about which I can say that they changed my life in a very significant way. Thanks a ton Cristi & Sergiu for recommending & buying the Romanian copy of the book at that point in my life.

https://train.usaco.org/usacogate: Training material that is well written & problems that are easy at the beginning but then they become quite though. I learned a lot from going through it.

Cranking the code inteview videos

Cranking the code interview

Google interview example

Google page on interviews

Hangout on air on Tech Interviewing

[Romanian] Sfaturi pentru interviuri de programare

[ganceanu]

Cute Quiz #1

Here is a cute quiz I thought about recently. It might work well as an interview question, but I have never tried it myself in this setting. Here it goes:

“You are in front of a paginated web site giving you pages of N results and an estimation of the total number of results. The initial total number of results is big, but imprecise. You want to know the exact number of results which you can get on the last page. You cannot modify the web site and you cannot access the services behind it. You can only display pages of the web site using a browser. What do you do?”

Please ask questions in the comments, but I hope you refrain from posting your solution there so that others get to try without spoilers :) 

Please email solutions to the following address (it’s not a fake, I just created it to not share my personal email in a public post):

Hint: You can assume that the web site supports the "page” HTTP GET parameter to fetch a given page. For example, http:// mywebsite.myorg?page=11 fetches the 11th page if it exists.

The solution was posted here.

[ganceanu]

Family Hotels

Our vacations changed dramatically after Sofia came into our lives. Before we were world travellers, trying to tick as many boxes in each vacation: taste and experience local food and culture, visit as many landmarks, relax as little as possible :)

Now we are great fans of the Family Hotel concept. These hotels offers day care and all-inclusive food packages. They usually have a lot to offer on-site: spas, saunas, pools, a lot of places for kids of different ages. There are great for parents and children alike. Nowadays I want to make as little decisions as possible during a vacation and such a hotel is great.

If you are a parent and can afford it, we definitely recommend them. I have compiled a document with the family hotels we’ve been to. Feel free to comment on it and I will try to incorporate your feedback.

[ganceanu]

Don’t be so greedy

Don’t change your car, laptop or phone every 2 years because you need the shiny new one.

If you were to save those hundreds, thousands or even tens of thousands of dollars, imagine how many lives you could influence for the better.

I’ve recently travelled to the place I was born and lived up until I was 17 years old. It is encouraging how many things changed for the better. But a lot of problems are still far from being solved. 

Children living in poverty, household violence, schools that need to be renovated. Streets still kill people. 

How do we solve these problems?

PS: RIP Ion&Constanța Cimpoaie

[ganceanu]

Distributed CEO

My 3 weeks of being CEO will expire on Monday and I will pass the CEO hat to Mircea. It's been a crazy and fun period for us! I had the chance to manage one "intimate" beta launch and one private beta launch. It all ended up with an awesome private beta party this Friday -- 55 beers and 1 bottle of whiskey is what we accomplished together with our Bootup Labs friends.

Since many people are asking us who's the CEO in our team I am going to tell you the story behind our "system". The quick answer is this: at Summify we have a distributed CEO - each of us wears the CEO hat for 3 weeks and we rotate.

When we started working at Balaur.ro we didn't have a CEO: we were managing our operations all together, we were going to meetings together, etc. We've soon realized that this is inefficient.

Luckily we've attended one of Radu Georgescu's talks about entrepreneurship. The talk was awesome: he made a comparison between Poker and Business :) One of the things that he pointed out was the conflict of interests between the different layers in a company: shareholders, board of directors, CEO and employees.

When you're running your own startup you have a hat for each of these layers: you are a shareholder and a director, sometimes you act as the manager but most of the time you're just doing whatever needs to be done to push the company just another inch forward.

At that talk we realized that we have to play a CEO game of some sort. That someone has to assume this role, manage day to day operations and make things happen.

Since we were all interested in being a CEO we came up with a system so that each of us gets to run the company for a fixed period of time. At the end of each week during this period the other two guys in the team magically transform from employees into shareholders and judge the CEO based on results. That's how the conflict of interests gets born and this is pure health for the company: it creates an isolated moment when valuable feedback is brought on the table, the CEO gets his credit or some kicks in the nuts :)

For us it went great so far: we are constantly making progress and each of us is improving his CEO's skills based on the feedback he gets from the shareholders. This trick enabled us to run better our startup and get a lot more things done.

We're constantly looking to improve our ways to run our company so if you have any suggestion or comment I will be happy to hear from you.

[ganceanu]

We have great news to share with you: Summify is now officially in private beta, starting today, 23rd March 2010! Woohoo!

After weeks of hard work we finally have something that we can share with more people! It took us a full week of “intimate” beta to detect and squash all the major bugs...

[ganceanu]

Personal pitch

This is my first blog post and instead of the old "hello world" trick I'll try to pitch myself to you. In this way you'll get to know me a bit better right from the start.

So here it goes:

"Hi, I'm Silviu and I am a co-founder of ReadFu. I'm from Romania and I came all the way down to Vancouver to join Bootup Labs and to build an awesome product.

During high school I participated in programming competitions and I won a gold medal at the international Olympiads in Informatics. In that time I've co-founded infoarena.ro which is now the biggest community of talented computer geeks in Romania.

In my college years I've tried as many things as I could: I've done 2 software engineering internships with Google (one in Mountain View and one in Zurich) and I was a research intern at Ecole Polytechnique Federale de Lausanne.

After I finished my BS Degree in Computer Science I decided to build something of my own and I started balaur.ro which is the best job aggregator in Romania. But my dream was to build an international business and here I am pursuing my dream in the beautiful city of Vancouver."

I intend to use this pitch as my personal story in networking events around Vancouver. If you have any suggestions, leave me a message.