Category Archives: Uncategorized

Which data structure is best suited for making a simple phone book program that returns a number given users name and vice versa?

0
Posted on by

Answer by Vishnu Jayvel:

Thanks for the A2A.
It depends … There is a tradeoff between space and time complexity when you use any datastructure, be it trie or ternary search tree or hash table.
Trie
  Trie uses a lot of space but we can search in O(n) where n= maximum string length.
But how much memory could you afford ?
If there is 2000 contacts and each contact at the max requires 64 bytes ( 64 character),
Worst case approximately 2000X64 bytesX(nodesize=64 bytes) = 8000KB of memory is required. If your RAM could accomodate such huge trie then you can go for it.  You will need 2 tries ( one for contact name and other for phone number) on the whole.
Ternary search tree
 Space efficient compared to Trie and it searches in O(logn) time. But you can go for either trie or Ternary search tree only if the memory could satisfy the space complexity.
Database ( Hashing)
Create a table with Phone number and contact as fields and do indexing for both the fields. You will be storing the database in the internal phone storage . Based on the query you can send back the result set from the database.
You can take advantage of pagination !You need not show entire result at the same time .For example, if the result set has 50 records fetch 10 records first and then display it the screen , at the same time keep ready of the next 10 records to be displayed in the next page and later when there is time fetch 10 more records and so on.
Since indexing is done by hashing the key(search term),If there is collision more buckets will be created.So it is important to create a good hash function so that there is little or no collision.
Blend of both trie and Hashing
If the collision is unavoidable and if there is so many buckets, hash table might take more time in fetching the result. The you can create a trie initially which can be used to fetch the correct bucket in the hash table which has the result and later you can do binary search in the set of values in the respective bucket and fetch the result.

I hope this helps. Correct me if iam wrong.

Which data structure is best suited for making a simple phone book program that returns a number given users name and vice versa?

What is it like to intern at Amazon?

0
Posted on by

Answer by Vishnu Jayvel:

I interned at Amazon India – Chennai during summer 2014.

In short:
I had a very good experience. It was fun and challenging.

In detail:
Amazon has always been a dream company for me and I was so excited when I got an offer to intern in Amazon. I was working in Kindle Book Content team.

Smart people everywhere :
Amazon is filled with smart engineers and anytime you roam around the office you could find a group of super talented people brainstorming about some interesting challenges. I was highly motivated by my co-workers everyday.

Interns get challenging projects:
Your work at Amazon totally depends on the team you're on. My manager gave me a project that had good business value for Amazon and was expected to go for production soon. I was very excited by the thought that my project is going to impact millions of Kindle Book readers around the world, so I started to take ownership from the day one.

I wanted to make the best use of my internship period at Amazon. I had periodic brainstorming and feedback sessions with my manager. I adopted Kanban flow (sorted the tasks into ‘todo’,’doing’ and ‘done’), a methodology for task management. This helped me to have reality checks and find my weaker areas.

Bias for action:
At Amazon, everyone is expected to figure out things on their own.
Right from the beginning of my internship, I was encouraged by my manager to make decisions on my own and proceed with my tasks. In fact I was not assigned a mentor and I had to directly report to my manager.

He gave me complete freedom to make changes in the codebase. With great freedom, comes great responsibility. There were scenarios where I was ambiguous in choosing the right path. But as time went on, I got used to this. Thanks to Amazon, I improved my decision making sills.

Nice perks :

  • Pretty good stipend
  • Sodexo meal coupons
  • 24/7 cab facility

Sometimes I went to the office at midnight to collaborate with my manager, who is based in Seattle. I got an Amazon cab anytime I wanted.

Flexible work schedule:
Employees can come in late, work from home, or leave early if they want to. I normally went to office at 11 in the morning. Since nobody monitored me, I had complete freedom. I felt very relaxed and could concentrate on my work without any pressure.

Amazonians are very helpful:
I had two tasks assigned to me during my internship. For my 2nd task, I wanted to know about a feature in Amazon Kindle Direct Publishing. After finding out that the SLO (San Luis Obispo) team was handling the service, I directly contacted the software development managers from SLO and they were so helpful in helping me clear my doubts regarding their service. As an intern, I was suprised to find them friendly and helpful.

Very strict code review:
In Amazon, even if a single line of code is modified it must be reviewed by any of the team members before pushing it to the codebase. My manager reviewed all of my code. If I had made any mistake or if any of my code is unclear he will comment near the line that had issues and send me his review. He sometimes include smilies in code review. Who would do that? 🙂 He was a cool guy. Even though many of co-workers and my seniors told me that code review will be difficult and time confusing to handle, I actually found it interesting.

Each and every line of my code was read. For a system that handles millions of books, it was necessary for the code to be as optimized as possible. Even a single unnecessary instruction has to be carefully pruned from the code before it is pushed to the code base.  

Getting a return offer:
Interns are asked to fill self performance reviews, which is then looked by the mentor/manager, who also give feedback about the intern. This document plays an important role in the hiring decision.

The mentor, manager, bar raiser, and HR are the decision makers.

Conversion from intern to full-time employee is purely based on your project and your work. This can fall into 3 cases:

  • Pre-Placement Interview (PPI): If you have completed your project on time and if you have done a decent job, you will be given an oppurtunity to take a pre-placement interview, which will mostly comprise of 1 or 2 technical rounds. Amazon has a very high hiring bar and so the interviews will be mostly challenging.
  • Pre-Placement Offer (PPO):If your manager is impressed with your work you might even get a direct offer without any interviews.
  • Rejection: If your mentor/manager thinks that you are not up to Amazon standard, you will not be given a PPI. As far as I know, this is a very rare case. No one I knew during my internship got a direct reject.

Overall, it was an enriching learning experience. Amazon has groomed me as a good software developer. For me, coding is like casting magic spells and I am always excited to write code that impacts millions of people. I'm looking forward to going back to Amazon, and yes, I got a Pre-Placement Offer. 🙂

To know about my productive work habits during internship refer
Vishnu Jayvel's answer to What are the best ways to excel in a summer internship?

What is it like to intern at Amazon?

Ron Weasley and a magical die

1
Posted on by

Ron Weasley bought a magical die having 10 sides(numbered  1 to 10) from  Zonko’s Joke Shop in hogsmeade.In this die all the even numbered sides are colored blue and all odd numbered sides are colored white. He wants to find the probabilty of getting a blue color and number 9 in a single throw. Can you answer him.(answer rounded to 3 decimal places)

[Answer in comment section]

How does coding improve with time?

0
Posted on by

Answer by Phillip Oldham from Quora:

  • You write code that’s easier to read. Better variable/function/class names, inline comments, better layout, more logical flow.
  • You learn that documentation is a GoodThing™ and, while boring to produce, is something you start to add without being prompted.
  • You find naming things (arguably the hardest part of programming) gets easier.
  • You learn how to structure your code better. Grouping functionality into classes, modules, packages becomes second nature.
  • You stop copy-pasting code around your codebase to duplicate functionality, and start following “Don’t Repeat Yourself” practices.
  • You learn to log properly, and how useful that is for debugging.
  • You stop to think more. When you start out you tend to just keep writing code until something works. As you progress, you start to think more about the problem and stop piling on the code to attempt to fix things.
  • You write less code overall; experience teaches you better approaches to the basics you start with.
  • You learn what Technical Debt is. And you learn to hate it.
  • You learn to refactor. You’d be surprised how often you fix a problem by refactoring and simplifying your code.
  • You learn that premature optimisation is a “sin”, but you also learn to use optimal constructs by default.
  • You learn to manage your code properly. Version control. Code reviews. Versioning. Releases.
  • You stop relying on things. Networks, APIs, protocols, libraries, databases, data, people, even your own code… what can go wrong will go wrong, so you learn to be defensive about everything. While this sounds pessimistic, you realise it’s simply practical.

How does coding improve with time?

What are the best ways to excel in a summer internship?

0
Posted on by

My answer from Quora:

Kellen , Elynn and Erin have already covered all important points for excelling in a internship. Here is my 2 cents 🙂
Take notes :
Right from the day 1 take notes of

  • observation that you make
  • pseudocode of algorithms that you design
  • questions to ask your mentor/manager
  • sample test cases and expected output
  • software architecture
  • errors and its solution
  • important development tool commands

Split your project into several small tasks and maintain seperate note for each   task. Initially you might feel that it is unnecessary and waste of time. Trust me this will help you in a long run.
I would recommend evernote to take notes.
(A sample internship devlog notebook in evernote)

​

Track your progress :
Use progress tracking apps such as trello to classify your task into “todo, doing, done” list.  Divide your task for the day into a set of small tasks and prioritize it .

​
This will give you a reality check everytime you review your progress and you will tend to plan your work accordingly.

Manage time :
During your internship it is very important to meet your deadlines. You will be expected to finish your work on time, So track your time effiiciently!
Use time management app such as Rescuetime to track what you do everyday. With so many distractions and social platforms in your digital life, it’s easy to get distracted. RescueTime helps you understand your daily habits so you can focus and be more productive. Download both chrome browser(if you use chrome) and desktop version of Rescuetime.

​

Listen to coffitivity :
If you want to concentrate on your work and stop hearing the noise around your workstation try using coffitivity. Coffitivity – Increase Your Creativity!
This is what coffitivity team describes about their app:

Research shows it’s pretty hard to be creative in a quiet space.
And a loud workplace can be frustrating and distracting.
But, the mix of calm and commotion in an environment like a coffee house is proven to be just what you need to get those creative juices flowing.

Initially I found this to be crazy and stupid idea. But pretty soon I realized how effective it was and so I used it throughout my internship period.

​

Make yourself home :
Personalize your workstation so that you will feel like home. Stick some posters or add any creative accessories and turn your boring workstation into a fun place to work.

​
My friend drew this for me 🙂 I stuck this in my workstation during my summer internship at Amazon.

Finally ,be passionate about the work you are doing and enjoy doing it.

To read about my internship experience :
Vishnu Jayvel’s answer to What is it like to intern at Amazon?

What are the best ways to excel in a summer internship?

Codeforces Round #285 (Div. 2) C. Misha and Forest

0
Posted on by

Problem link – http://codeforces.com/contest/501/problem/C

This is an interesting graph problem 🙂

Since the graph is acyclic, there will be leave(s) (with degree = 1). Identify those leaves. Consider a leaf i.Its xor value (let it be j) will directly give you its neighbour(since xor of a number is the number itself).Add (i,j) as an edge to the ans vector. Now decrement the degree of the node j and also apply xor to j’s xor sum value to remove i. After removing leaf i from the forest, the forest will still remain a forest . So similarly find the leaves in the current forest (and also the edges which is why we are doing this) and carefully prune the leaves until the forest becomes empty.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
typedef long long int ll;
int main(){
int n,v,s;
vector<pair<int,int> > arr,ans;
scanf("%d",&n);
vector<int>leaves;
REP(i,n){
scanf("%d%d",&v,&s);
arr.pb(mp(v,s));
if(v==1)
leaves.pb(i);
}
int l=0;
while(l<leaves.size()){
if(arr[leaves[l]].first==1){
ans.pb(mp(leaves[l],arr[leaves[l]].second));
arr[arr[leaves[l]].second].first--;
if(arr[arr[leaves[l]].second].first==1)
leaves.pb(arr[leaves[l]].second);
arr[arr[leaves[l]].second].second^=leaves[l];
arr[leaves[l]].first--;
}
l++;
}
printf("%d\n",ans.size());
REP(i,ans.size()){
printf("%d %d\n",ans[i].first,ans[i].second);
}
}
view raw Misha and Forest.cpp hosted with ❤ by GitHub

Spoj(CAM5) Prayatna PR

0
Posted on by

A simple DFS will do good.A 2D vector is used to represent the graph via adjacency list.

All you have to do is have a visited array to mark nodes in the graph that is already visited. Have a count variable to count the number of groups available.

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
bool visited[100005];
vector<vector<int> > adj(100005);
int n;
void dfs(int i){
if(visited[i])
return;
visited[i]=1;
for(vector<int>::iterator it=adj[i].begin();it!=adj[i].end();it++){
if(!visited[*it])
dfs(*it);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int e,ans=0,x,y;
scanf("%d %d",&n,&e);
memset(visited,0,sizeof visited);
for(int i=0;i<n;i++)
adj[i].clear();
for(int i=0;i<e;i++){
scanf("%d %d",&x,&y);
adj[x].push_back(y);
adj[y].push_back(x);
}
for(int i=0;i<n;i++){
if(!visited[i]){
ans++;
dfs(i);
}
}
printf("\n%d",ans);
}
}
view raw CAM5.cpp hosted with ❤ by GitHub

Codeforces Round #285 (Div. 2) Problem B – Misha and Changing Handles

0
Posted on by

Problem link – http://codeforces.com/contest/501/problem/B
consider that each word(handle) goes via chain transition. initialhandle->changeinhandle->againchangeinhandle->….->finalhandle
usedmap will keep track of all currenthandle and its immediate parenthandle.
wordmap will keep track of initial and final handle of a contestant.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
typedef long long int ll;
int main(){
int q;
string newStr,oldStr;
map<string,string>wordmap,usedmap;
//consider that each word(handle) goes via chain transition. initialhandle->changeinhandle->againchangeinhandle->....->finalhandle
//usedmap will keep track of all currenthandle and its immediate parenthandle
//wordmap will keep track of initial and final handle of a contestant
scanf("%d",&q);
while(q--){
cin>>oldStr>>newStr;
if(usedmap.find(oldStr)==usedmap.end()){
usedmap[oldStr]=oldStr;
usedmap[newStr]=oldStr;
wordmap[oldStr]=newStr;
}
else{
usedmap[newStr]=usedmap[oldStr];
wordmap[usedmap[oldStr]]=newStr;
}
}
cout<<wordmap.size()<<endl;
for(map<string,string>::iterator it=wordmap.begin();it!=wordmap.end();it++){
cout<<it->first<<" "<<it->second<<endl;
}
}
view raw Misha and Changing Handles.cpp hosted with ❤ by GitHub

Codeforces(#177 div 2 problem B) Books

0
Posted on by

Link: http://codeforces.com/contest/279/problem/B

This is a good problem to use 2 pointer approach.

Refer the comments to understand the solution for the problem

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
typedef long long int ll;
int main(){
int n,t;
int arr[100005];
scanf("%d%d",&n,&t);
REP(i,n){
scanf("%d",&arr[i]);
}
int left=0;
int ans=0;
int sum=0;
int current=0;
//2 pointers/sliding window algorithm
REP(i,n){
sum+=arr[i];//add item to current Sum
current++;
//The following while loop is to adjust the boundary of the current window of
//books. if a new book is added in the right and if the sum exceed given t
//we have to window by removing element(s) from the left
while(sum>t){//if current Sum is greater that available time
current--;
sum-=arr[left];//remove the leftmost element
left++;//increment left pointer
}
ans=max(ans,current);//at each iteration update ans with maximum book window length till now
}
printf("%d",ans);
}
view raw Books.cpp hosted with ❤ by GitHub