Thursday, 10 August 2017

Euclid’s theorem: Proof of Infinitely many primes

Also known as the Euclid’s theorem, the theorem of infinitely many primes is one of the most elegant ones around. I came across it while brushing up on discrete math and had to blog about it.

Let's try to explain a proof of this theorem.

Before we begin, lets revisit the following things:
  1. Any number can be written as a product of prime numbers as stated in the fundamental theorem of arithmetic.
  2. The number sets

Here we go!

To prove: There are infinite prime numbers

Let’s dispute that claim for a second and assume that we know all the prime numbers.
Let’s write these as follows:
P1 P2 P3….Pn

Lets try to form a new number Q the following way:
Q = P1 x P2 x P3 x ….Pn + 1

Now, Q can either be:
  1. Prime
  2. Non prime
Why? Because any natural number > 1 has to be either prime or non prime.

If its:
  1. Prime, our list was incomplete as there is at least one more prime number and more prime numbers can be generated in a similar way. Contradiction!
  2. Non prime, we should still be able to write it in prime factorization form, i.e. Q should be a multiple of primes raised to some powers. But, as we can see, Q is not divisible by any of the primes in our list ( P1 to Pn ) as, upon division, 1 will always be left over.  This in turn means, that all of the prime factors of Q are not in the list, meaning our list is incomplete. Contradiction!

Hence, we can generalize that there are infinite many primes.

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

Sample Input(Plaintext Link)
1 50 50
50 50 50
1 50 50
Sample Output(Plaintext Link)
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.

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
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

 It had the following sections:

  • 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.


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

Question asked were:

  • 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

Questions asked were:

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

Sunday, 27 April 2014

littleBits Goes a Long Way

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 undo send
Gmail screenshot
2. Select Labs from the row of tabs.
gmail sent send undo
Gmail screenshot
3. Scroll all the way to the bottom where you see Undo Send and click Enable.
gmail send sent undo
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 undo sent send
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.

Tuesday, 3 September 2013

Google says next version of Android will be called KitKat

Google says next version of Android will be called KitKat

NEW DELHI: Sundar Pichai, head of Android division at Google, on Tuesday revealed on Twitter that the next version of the company's mobile operating system (OS) will be called Android KitKat.

"We now have over 1 billion Android activations and hope this guy in front of the building keeps that momentum going," Pichai tweeted as well as posted an image of a giant Android mascot built like KitKat chocolate.

Earlier, there were rumours that the next version of the OS would be called Android Key Lime Pie.

Since Android 1.5, Google has named each version of the OS after a sweet. Android 1.5 was Cupcake. Android 1.6 was Donut. Android 2.0 was Eclair. Android 2.2 was Froyo. Android 2.3 was Gingerbread. Android 3.0 was Honeycomb. Android 4.0 was Ice Cream Sandwich. And Android 4.1, 4.2 and 4.3 have been called Jelly Bean.

"Android is the operating system that powers over 1 billion smartphones and tablets. Since these devices make our lives so sweet, each Android version is named after a dessert... As everybody finds it difficult to stay away from chocolate we decided to name the next version of Android after one of our favorite chocolate treats, Kitkat," Google said.

The KitKat will be Android 4.4. So far there is no word on when Google will release this OS but it is likely to debut in the market with the new Nexus phone in the coming months.

Google announced the new version of Android just minutes after Apple sent out invites for an event on September 10 where it is likely to launch the next version of iPhone.

For KitKat name Google has tied up with Nestle, which makes KitKat chocolates.

"We couldn't imagine a better name for our Android K release than the tasty chocolate that's been a favourite among the team since the early days of Android," said Marc Vanlerberghe, director of Android marketing.

Nestle said that to mark the release of Android KitKat, more than 50 million specially branded KitKat bars will be available in 19 countries including Australia, Brazil, Germany, India, Japan, Dubai, Russia, the United Kingdom and the United States.

The packs will lead consumers to the website where they will have the opportunity to win prizes including a limited number of Google Nexus 7 tablets, and credits to spend in Google Play.

A small number of Android robot-shaped KitKat bars will be offered as prizes in selected markets.


Microsoft's Nokia deal: Layoffs look inevitable 

(read original)

BANGALORE: Microsoft and Nokia's India operations are among the biggest outside their home countries, and it looks like a certain number of redundancies and consequent layoffs are inevitable. Microsoft CEO Steve Ballmer's email to Microsoft employees on the Nokia deal said the companies would integrate all global marketing and have a unified brand and advertising strategy. It said that finance, legal, HR, communications, evangelism, customer care and business development would integrate functionally at Microsoft. ICM/IT will also integrate functionally for traditional IT roles, it said.

Such integration in most cases implies redundancies. Nokia has 9,000 employees in India, almost a tenth of its global workforce. Microsoft has 6,000 employees here, out of its global strength of 97,000. It's unlikely that there will be much overlap at the engineering, support and R&D levels, because Nokia is a devices company, and Microsoft largely a software company.

But in all of the divisions that Ballmer's mail mentions as being integrated, layoffs are likely. Anshul Gupta, principal research analyst in Gartner, said there could be redundancies.