## Thursday, 21 January 2016

### Dynamic Programming Example

Dynamic programming problem explained and solved using C++.

I like programming in general, but the paradigm which appeals to me most is Dynamic programming. Back in 2013, during my college days, I used to  hone my skills by solving problems on CodeChef. But then I got a job and it does not involve a lot of DP.

Recently I've realized that I have become clumsy, and too used to the "safe life", hence I've decided to solve DP problems on HackerEarth, the purpose of this blog is to keep me motivated :p

Samu and Shopping

```Samu is in super market and in a mood to do a lot of shopping. She needs to buy shirts, pants and shoes for herself and her family. There are N different shops. Each shop contains all these three items but at different prices. Now Samu has a strategy that she won't buy the same item from the current shop if she had already bought that item from the shop adjacent to the current shop.

Now Samu is confused, because although she want to follow her strategy strictly but at the same time she want to minimize the total money she spends on shopping. Being a good programmer, she asks for your help.

You are provided description about all N shops i.e costs of all three items in each shop. You need to help Samu find minimum money that she needs to spend such that she buys exactly one item from every shop.

Input Format:
First line contain number of test cases T. Each test case in its first line contain N denoting the number of shops in Super Market. Then each of next N lines contains three space separated integers denoting cost of shirts, pants and shoes in that particular shop.

Output Format:
For each test case, output the minimum cost of shopping taking the mentioned conditions into account in a separate line.

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 105
Cost of each item (shirt/pant/shoe) does not exceed 104

1
3
1 50 50
50 50 50
1 50 50
52
Explanation
There are two ways, each one gives 52 as minimum cost. One way is buy shirt from first shop, pant from second shop and shirt from third shop or she can buy shirt from first shop, shoe from second shop and shirt from third shop.

Both ways , cost comes up to 1 + 50 + 1 = 52

Time Limit: 2 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded if any testcase passes.
Allowed languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA, JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP, PYTHON, RUBY, R, RUST, SCALA```

Okay, so we have prices of 3 items from n shops. This is best represented as a 2D array/vector with three columns and n rows.

shirt      pant    shoes
 1 50 50 50 50 50 1 50 50
We need to calculate the minimum money required to purchase atleast one item from each shop, so if we buy the cheapest item from each shop we should be fine, BUT we cannot buy the same item from adjacent shops(I wonder why :D). So if we buy shirt from the first shop we have to buy either pant or shoes from the adjacent shop and so on,

Hmm.. looks like a binary tree to me, lets try and represent it as one.

The number(i,j) here denote the indices of the price matrix, where denotes the shop and j  is the item.

We start with -1,-1 as the starting point, because we want the minimum of all the possible selections(Just a way to represent, feel free to change this).

So, if I start with the first item from the first shop, it would be equivalent to choosing the 0th item from the 0th shop in the matrix(think in terms of array indexes), after which I can choose either the Pant(index 1) from the second shop(index 1) OR I could choose shoes(item index 2) from the second shop(index 1), and so on.
These are a lot of combinations, so we will follow a greedy approach. At each node consider that child, which has the least cost. If we follow this approach bottom up,we will arrive at our answer.

If each node(i,j) in the tree represents the cost of buying an item(j) from a shop(i), then it is clear that a lot of things are being recalculated, for ex the nodes(1,0) and (1,2). If we can avoid these recalculation, by remembering the previously calculated values, we can achieve better performance when we have a lot of data, and this is nothing but dynamic programming.

In the code below, we use an array cache[][] to store previously calculated results. We calculate the cost at each node only if it has not been calculated earlier, and store it in the cache for later use.

Here is the code:

## Tuesday, 9 September 2014

### SAP Labs India Interview Experience

This is regarding the selection process of SAP labs for the 2014 batch.

The process was divided into two main parts
1: Online Test
2: Interviews

Online Test

• Quantitative Aptitude
• Basic Programming knowledge ( O.O concepts, Output prediction etc )
• English
• Code ( Candidates had to write code for a problem statement )
Most candidates faced problems in the code section so I advice students to Practice writing code, preferably on Online code editors.

Interviews

Students who cleared the written round were called for Interviews.
There were 4 interviews in total
Two technical one Managerial and one Hr.

The First Interview
The first interviews is to check the basic knowledge of almost all core subjects such as Data Structures,Operating Systems, DBMS etc.

• O.O Concepts are of particular Importance
• Questions will be asked on the basics of programming language(s) Of candidate's choice,the candidates are also expected to write code on paper for the Interviewer's problems
• Two logical reasoning puzzles are also asked( The trick to solving these is to take your time and keep trying )
• Also general questions such as, what is memory leak, segmentation fault, virtual functions, double pointer, Diamond problem etc can be expected.

The second Interview
This interview is more In depth.

• Initially a detailed problem statement is given and candidates have to write code for it on paper, Emphasis is on the Logic and thought process, not the syntax.
• Puzzles can be expected ( depends on the interviewer )
• Questions about Database Design and Normalization can be expected

The third Interview ( Managerial )
This interview is taken by a senior manager

• What was the toughest question asked till now and why
• What are your passions ( answer these wisely, later in the interview you would be asked to justify them)
• Why should I select you etc

Final Interview ( H.R )
This interview is taken by a Senior H.R member

• list your strengths and weaknesses
• justify them with real life examples
• A situation based puzzle can be asked

# littleBits Goes a Long Way

"The goal -- and challenge -- in this project was to create highly respectful, scientifically accurate projects that replicate NASA's groundbreaking work, while also making them modern, engaging and fun for nonscientists," said littleBits Product Designer Krystal Persaud. "We think this will empower people who were previously uninterested in STEM to get excited and get involved."
Space fans the world over long have dreamed of exploring the universe for themselves, but a new, 12-module kit from NASA and littleBits aims to give enthusiasts a way to bring the thrill of space exploration closer to home.
The new littleBits Space Kit, launched on Thursday, includes an assortment of electronic modules and NASA-designed projects and activities designed to allow anyone to observe and measure the universe, build and remotely control a model Mars Rover, or wirelessly send music to a model of the International Space Station.

"In 2012, NASA approached us with a big challenge that they were facing: 'How can we make space education more interesting and engaging?'" littleBits Product Designer Krystal Persaud told TechNewsWorld. "We then worked very closely with NASA scientists and engineers for 18 months to bring the Space Kit to life."
Now available for US\$189, the Space Kit features 12 modules, five NASA lesson plans, and 10 activities related to STEM -- that is, science, technology, engineering and math.

## 'Scientifically Accurate Projects'

Targeting users 14 and up, the littleBits Space Kit offers activities focusing on the fundamentals of energy, robotics, wireless data transmission, physics and astronomy, among other topics. Users can gain insight for themselves into how scientists communicate with spacecraft billions of kilometers away, how electromagnetic energy is transmitted, and how the AURA satellite senses gases in our atmosphere, for example.
"The goal -- and challenge -- in this project was to create highly respectful, scientifically accurate projects that replicate NASA's groundbreaking work, while also making them modern, engaging and fun for nonscientists," Persaud explained. "We think this will empower people who were previously uninterested in STEM to get excited and get involved."
Recent events such as the discovery of Earth-like planet Kepler-186f, SpaceX's successful docking at the International Space Station, new evidence of the Big Bang, and the introduction of Neil deGrasse Tyson's new Cosmos documentary mean that "space is more than ever at the center of the cultural conversation," noted Ayah Bdeir, littleBits founder and CEO.
Indeed, planetariums have even reported increased traffic just in the wake of the popularity of the recent movie Gravity.
"We aim to bring space closer by putting the building blocks to invent, learn and explore directly into the hands of educators, students, NASA enthusiasts and builders of all ages," Bdeir added.

## An Open Source Library

The Space Kit is part of a larger open source library from littleBits that seeks to break electronics down into simple but powerful modules.
"LittleBits products are a teaching tool: Sharing our designs allows for the possibility of teaching how these circuit designs work down to a circuit level," Persaud explained. "This means that anyone can use littleBits products and then come back to them later on in their education for a deeper understanding of electronics."
Also launching on Thursday were three new littleBits modules -- dubbed "IR LED," "Number" and "Remote Trigger" -- that can be used with any of the modules in the extended LittleBits library to create trillions of circuit combinations.

## 'One of the Most Inspiring Disciplines'

"Progress and creativity are driven by curiosity," Mario Livio, astrophysicist with the Space Telescope Science Institute and author of Brilliant Blunders, told TechNewsWorld.
"As long as people, young and old, are curious, we can be sure that we'll see advances in both the sciences and the arts," Livio added.
"Space science is one of the most inspiring disciplines in this respect, since on one hand it addresses our cosmic origins, and on the other it introduces us to fascinating technologies," he concluded. "All endeavors that can engage the public in these directions are welcome."

## Thursday, 16 January 2014

### Gmail - Undo Send

You clicked send. Oh crap.

When you send a no-take-backs email — maybe an official email, or accidental reply-all — there's an instant pang of regret. It feels like there's no going back.
Meet Gmail's Undo Send feature, a lifesaving little hack buried in the Gmail Labs settings. It gives you a 30-second window to "undo" sending an outgoing email.
You just have to enable it first.

### Here's how it works:

1. Click the gear icon in the top-right corner of your Gmail window and select Settings from the dropdown menu.

Gmail screenshot
2. Select Labs from the row of tabs.

Gmail screenshot
3. Scroll all the way to the bottom where you see Undo Send and click Enable.

Gmail screenshot
4. Hit Save Changes at the bottom.
5. Breathe easy.
Now when you send an email, the yellow dialogue that displays "Your message has been sent" will also give you the option to Undo. Click it, and the email will reopen, un-sent, in the composition window.

Gmail screenshot
It defaults so that you have 10 seconds to click before the Undo button disappears, but you can adjust that window of opportunity. Go to Settings > General > Undo Send, and select a cancellation period up to 30 seconds.

Note, features in Gmail Labs are experimental and may change, break, or disappear at any time.
You've been warned.

# Why Russian Tech Entrepreneurs Are Willing to Risk Backing Navalny

A group of Russian Internet entrepreneurs has taken the unusual and potentially risky step of speaking out publicly in support of Kremlin critic Alexei Navalny.
In an open letter distributed on Aug. 7 to local media outlets, 37 leaders of Russian Web startups said they were backing Navalny’s campaign for mayor of Moscow, as a protest against corruption and other official abuses. They said they were speaking as individuals, rather than as representatives of their businesses.
“The situation in Russia is deteriorating beyond reasonable limits,” Kamil Kurmakayev, a Web entrepreneur who organized the effort, tells Bloomberg Businessweek in an interview. He says the government’s treatment of Navalny, who is running for mayor while appealing a recent conviction on theft charges, mirrors the experience of business people who see that “in Russia, the government can do anything. There is nobody who is protected against anything.” The government has not yet responded to the letter. The letter in Russian, is availablehere.
Kurmakayev, 33, a Stanford Business School graduate who co-founded an online marketplace, Wikimart, says that companies like his are finding it “harder and harder to attract foreign investment,” as potential investors worry about the lack of protection for property rights. And, he says, “our employees are thinking more and more about moving to other places, like Silicon Valley.”
It’s rare for Russian business people to criticize the government openly, and some who have done so—such as former oil company chief Mikhail Khodorkovsky—have landed in jail. More recently, the founder of social-media site VKontakte, who had clashed with the Kremlin, dropped out of sight after being charged with a traffic violation under murky circumstances.
Kurmakayev, though, says that entrepreneurs are becoming more willing to speak out. “It’s not normal that in private conversations people say one thing, and in public say another.” Representatives of Russia’s biggest Internet companies, such as VKontakte and search engine Yandex, aren’t among the signers of the letter. “These are big companies, they have to be more careful,” Kurmakayev says, “although we know from private conversations that the general sentiment is positive.”
The entrepreneurs’ letter underscores a sharp deterioration in relations between the Kremlin and the country’s high-technology industry since Vladimir Putin replaced Dmitry Medvedev as president last year. The Skolkovo technology hub, promoted by Medvedev as Russia’s Silicon Valley, has run afoul of government authorities.
Russia’s parliament has recently passed laws to tighten controls on the Internet. And after VKontakte founder Pavel Durov resisted government efforts to shut down opposition groups’ pages on the site, an investment fund with close ties to Putin took a 48 percent stake in the company, in what was widely seen as a government-sanctioned raid.
In yet another setback for entrepreneurs, Sergei Guriev, a former Medvedev economic adviser who was an advocate for business, recently fled the country to avoid possible prosecution. “People like [Guriev] command huge respect,” Kurmakayev says. “In our company we have employees who studied with him” at the New Economic School in Moscow, where Guriev was rector.
Signers of the open letter included founders of websites ranging from e-commerce to sports news and an online taxi-reservation service. “We are aware of thousands of entrepreneurs whom the courts have put in jail on fabricated charges,” they wrote. “The rule of law, an independent judiciary, and free elections—for us, these are not abstract ideas. Without them we cannot run a modern, sustainable business.”
Matlack is a Paris correspondent for Bloomberg Businessweek.