Amazon Appstore: How to install on HTC Inspire

I got my HTC Inspire 4G recently and am loving it. The first thing that I wanted to check was the ability to install non-android market apps on it. So, I picked Amazon appstore app to install. here is what I did.

• Entered phone number in a textbox under Getting Started on Amazon Getting Started
• I got an SMS immediately with a link to download appstore. I clicked on that and the download finished in a few seconds.
• When I was about to install, I got an error saying "For security reasons apps from other sources are blocked"

Very disappointing. Android can't be like iPhone in terms of someone dictating me what I can install or not on MY PHONE. Since I bought the phone on Amazon, I went to their website for help. Amazon says, amazon appstore is available on HTC inspire 4G. I contacted them through this link. Immediately a representative calls me and says ATT has an update, that when pushed on to my phone, I'll be able to see "Unknown sources" option under Settings->Applications and be able to install appstore. I must say their customer service is awesome.

Now I call ATT customer care. First they put me in queue for couple of minutes before serving me. Then a robot says something that I'm remotely even interested. After entering a few details to identify myself, someone answers the call. He doesn't even understand the problem I have. He puts me on hold to ask someone if they understand my problem. After several minutes, he comes back and says my software version is the latest and I have to wait for next release to get any update. I told myself, Amazon can't be lying. So I asked to speak with his manager. I'm put on hold for another 5minutes. Finally, manager seem to understand the problem. She at least know that people had this problem in the past. I felt so relived when someone from ATT knew the problem I'm talking about. But she doesn't know how to resolve. She puts me on hold to contact another person who might be able to help me. after waiting for another 5minutes, she puts another person in conference call. He is the one I should have talked to in the first place. He immediately pushes an update in real time and I was able to install appstore while on the phone with him.

It took me 50 minutes of talking and waiting to get a damn update installed on my phone. The wait is worth. I got my amazon appstore installed and several other amazon apps.

It seems like very few people know what this update is. So if you need an update, escalate it and talk to more ATT representatives. I know its painful but sadly thats the way it works.

I don't understand why ATT by default push this update. Has it got anything to do with the rivalry between Google and Amazon appstores?

How did I prepare for Amazon Onsite Interview

Note: This post is not about the interview questions I was asked at Amazon. Its about how I approached the interview preparation. There are many blogs out there talking about their Amazon interview experience and the questions they were asked.

Fortunately, Amazon got interest in my profile and scheduled telephonic interview for SDE position. Couple of days before the interview, I was wondering what could Amazon (or anyone) ask me to code in 30min on phone? After thinking for a while, I came to a conclusion that they can't ask me to code problems that are long. At the same time they can't ask me silly questions like factorial! So I figured problems that have recursive solutions or problems on arrays and strings are a good fit. I was inclined more towards recursion because I like recursion!!! Well, anyone who has done fair bit of functional programming always thinks recursively! Imagine writing code without loops... Many problems on trees are fundamentally recursive an complex problems in trees can be solved recursively easily in short code. Turning them to iterative using stacks is interesting but hard to do over phone. I practised writing code for some tree problems recursively. I was always taking more than 30min which is not a good sign. I was worried about it. I also looked at Java collections and C++ STL data structures. Finally my first telephonic interview went successfully given that my basics in OS, algorithms, networking is good.

At this point I was thinking whether they are going to schedule 2nd phone interview or fly me to their office but not about being rejected! I was contacted in 2 days and scheduled 2nd round. This time I did solve some problems I found on the web. I was expecting some dynamic programming or graph questions but to my luck they asked simple question. But I never thought I could present 4 solutions to this problem. Presented theoretical analysis and covered edge cases well. I step back and say problems with my previous approach and why it occurs, how to correct it. After this round, I was sure they are going to fly me!

As expected, they asked me to visit their office for onsite interview. I have not prepared everything that I wanted. Under any circumstance, I didn't want to lose this opportunity. I wanted this job. So I planned for a week preparation (well 5 days only!). Here is my preparation for 5 days.

All the 5 days I practised solving and writing complete code. learnt that I'm making some mistakes. Writing one or 2 problems a day on the board and timing!.

Day 1:
+ Revise c++ and java languages.
+ C++
+ I/O, overloading <<, >> etc
+ String manipulation, bit manipulation.
+ Code using STL without reference.
+ Design and code OOP way. (virtual?) inheritance, polymorphism
+ operator overloading, functors, templates, exceptions,
+ exceptions, thread-safe, mutexes, locks, iterators,
+ internationalization wchar_t???, reference?, pointer?
+ friends, smart pointers, auto_ptr?, RAII?, casts?
+ new, delete[] implementation?, nothrow new, placement new?
+ stack unwinding, assert?, assignment op, copy constructor
+ custom memory allocators for containers like list, vector (Well, I didn't study this. just planned)
+ Java
+ I/O, String manipulation
+ Using collections java.util without reference.
+ OOP support. inheritance, static, access modifiers?
+ Threads, abstract classes, synchronization, exceptions
+ equals(), hash(), deep, shallow copy, type system?
+ know thread-safe, and unsafe classes?
+ design patterns used in collections.
+ aggregation, composition, association, has-a, is-a?
+ anonymous inner classes? comparator, comparable?
+ RTTI, JDBC?, garbage collection?, inner classes, generics,
+ reflections? (didn't revise. no time!)
+ c++ vs java.
Note: also coded standard algorithms that require stack, queue, priority_queue, map and hashtable both in c++ and java.

Day 2:
+ Operating Systems, Concurrency, OOP I
+ Processes
+ Threads, posix threads, mutexes, semaphores?, deadlocks?, livelocks?
+ synchronization primitives implementation, multicore?, barriers?
+ scheduling, scheduling algorithms, priority inversion,
+ classic thread synchronization problems, critical section.
+ virtual memory, demand paging, TLB, address translation, segmentation?
+ caching, page replacement algorithms, thrashing?,
+ file system implementation, inodes, buffer cache, inode cache,
+ block allocation schemes? trade-offs?
+ DMA, disk scheduling etc, interrupts, syscalls, traps? signals?

+ Basics of OOP, class design? UML? relationship? design principles?

Day 3:
+ Object Oriented Design II & Design Patterns.
+ Misc:
+ Basics of compilers
+ AI search, BFS, DFS, Iterative Deepening, UCS, A*,
+ graph coloring, inference?, min-max?
+ functional language? haskell? why? what they offer?
+ different types of languges and what they offer and what not?

Day 4:
+ Relational Databases, SQL, joins?, Regular Expressions in perl
+ Networking: different layers, functionality of each one, design choices?
+ TCP/IP???, routing, packet switched vs circuit switched?
+ DNS, DHCP, MAC, IP, ARP, RARP, ping? tracert? longest prefix match?
+ broadcasting, multicasting, unicasting, congestion control?
+ Revise Algorithms & Data Structures - part I

Day 5:
+ Revise Algorithms & Data Structures - part II
+ Divide & Conquer, Backtracking, Greedy, Dynamic programming
+ Graph Algorithms (yes Flow problems too!), Sorting and Searching,
+ Strings, suffix trees, tries, KMP substring, basic number theory, prime numbers.

.... I know that is long.... but I didn't want to miss this opportunity. At the end it was worth it. I was way confidant than before. Solved all arrays, strings problems on careercup at a rate of more than 1 per minute. Well I couldn't solve some in 5-10min also. Noted them down and solved at the end.

I did well in onsite interviews and hoping to hear good news soon. Few lessons I learnt during onsite interview.

• Solving problems on board didn't allowed me to think through the problem. Some programming errors were not obvious because code is all over the board and I couldn't get complete picture of what is written unless I step back a few times. Usually on computer, I can see full code and a bug easily attracts me.
• I write different parts of programs at different times. for example I dont write recursion termination condition first. I write after combining sub problems which are solved recursively. So writing on board was kind of trouble.

Good part is, interviews didn't last long. In 4 hrs I finished 5 interviews including lunch!. It was good experience, churning out code and design continuously without any delay. I must say people at Amazon are really bright and nice.

Note: I know the list that I presented in 5-day preparation is exhausting. Being aware of this stuff before makes life lot better otherwise I would suggest month time. This is how I prepared. I'm not expecting anyone to prepare all of this.

Lessons learnt - part 1

It was my first day (Monday, May 17th 2010) as an Intern at BBN Technologies. The day I remember for meeting most interesting and brilliant people there. One of the really cool people I met there is my reporting manager, Henry Yeh. I must say he has influenced me in ways that you will see soon in this post. He encouraged me (read as strongly recommended!) to attend early morning 7 A.M. "Core Power Strength" and noon "Yoga" classes offered by BBN at free of cost to all employees. I'm well known for not being able to get up early in the morning. Keeping that in mind, I have not given promise to him but at the same time I couldn't resist his recommendation, So I escaped myself by saying "I'll give it a try!".

You probably would have guessed right. Yes, I didn't make it to the first class. I have to get up by 6 A.M. if I want to be in the class by 7 A.M. It used to be a tough task to me. I tried to compensate missing morning class by attending next day noon Yoga class. He was happy seeing me there. I must admit that people out there in the class are doing very well with yoga postures/stretching whatever you name it. I was a bit disappointed at how rigid I was. I consider myself to be Ave (read as Average!.... can't stop using bitsian slang) Fitness guy. Thats when I realized I overestimated myself. I stand in Ave- (read as below Average) category. Henry gave me a pat at the end of class and said I'll do good after some classes, that gave me some motivation to attend. Well another reason being the class at noon time!

After fighting for several days in the early morning with myself convincing to get up, I managed to attend morning class. Guess what?, I was late by 15 minutes! I felt embarrassed to attend class late. Its better than skipping class! I followed the instructions from Eddie (Instructor) and gathered required equipment for the exercises. I got exhausted so much that I had difficulty going home after the class. Henry is much stronger than I imagined for his age. After I convinced myself that I can attend this class regularly, I stopped attending Yoga classes. If I attend every class they offer who will do my work? It was an easy decision to make, because it doesn't help me achieve my short term goal (overcoming underweight status!).

I continued attending morning classes regularly (late by 5-10min!). I used to feel bad for not making to the class on time. When I mentioned about this to Eddie, he said "You are here, thats all I care!". I felt better but it didn't make me come on time :(. This is the time I learned some valuable lesson. I always used to give up in the 1hr class 5-6 times. I feel like my body is not gonna cooperate and I gave my best. But the truth I realized is thats not the case. Intensity of the exercises and the way they make use of muscles from all angles made me temporarily exhausted. I kept on continue with the class members. What a shame when a old lady continues to do and I stop doing! Thats the reason I like classes. It motivates me to continue in the class. If I were alone doing workout I'm sure I would stop way before I do in the class.

There are 2 takeaway lessons (at least thats what I learnt): 1) We always think we are working hard on something and give an excuse to ourselves by saying we are tired and need to stop working. You never know how hard you can work on something! There is always room to improve. Trust me on this. 2) If I had done my workout with low intensity or skipping classes I wouldn't have seen any improvement in me. It applies in general too. If you are doing some work, concentrate fully on it and be persistent. I didn't overcome underweight just over the night. It took time. You better not work on something if you can't give your best. Because you don't see results and its nothing but waste of your time (I would rather sleep!).

I'm glad that I interned at BBN Technologies (for several reasons.). Being consistent for 3 months doing workout gave me motivation to continue here at Utah. Henry & Eddie, you sure have made it part of my life. Thanks a bunch!

Microsoft Interview

back to blogging after a long pause. I happened to get a chance to interview with Microsoft at my campus. I thought I did really well but surprisingly I got rejected :( waa, :( waa. I'll describe my experiences. As such I have not signed any confidentiality agreements, so I believe its okay to post here.

Interviewer: what is palindrome?

Chiku: any string which is same as when reversed!

Interviewer: what is stack?

Chiku: LIFO (with an example!)

Interviewer: If i give you $1000 and ask you to buy one electronic gadget, what would you buy?

Chiku: Amazon Kindle

Interviewer: Why?

Chiku: I already have a good configuration laptop and high end mobile, So having kindle helps me read papers, books, novels and it keeps me updated with news. Its flexible and easier to carry and read anytime!

Interviewer: What is the most technically challenging problem you have faced and how did you solve it?

Chiku: (said blah blah about last year company work!)

Interviewer: List down the languages you know in the order of how much comfortable you are with.

Chiku: C,Java, C++, Python and Haskell

Interviewer: have you worked on SQL? databases?

Chiku: yes I did! PostgreSQL

Interviewer: Write down a program in C to find out the first non repeating character in a given string.

Chiku: asked several good questions like, what is the domain of characters that make the string?, is small and capital letter should be treated same or not?, etc)

Chiku: described the algorithm, keep track of frequencies of characters and their first indices as I walk down the string. Finally walk over the frequency table and check which has frrequency 1 and least index. wrote c program.

Interviewer: how would you test this code?

Chiku: test cases like, passing null pointer, non-null terminated string, passing strings that have non-letters, empty string etc...

Russ: any questions?

Chiku: what would I be working on If I would be hired?

Interviewer: you could be working in any department. said blah blah about microsoft...d same story!

Chiku: What is the project you are working on?

Interviewer: he said blah blah on virtualization,

Chiku: (since I know about that stuff, I asked some questions and talked about it).

Chiku: I already have an internship offer from XYZ company

Interviewer: We will keep it in mind and will try to process yours quickly.

I wrote c program which is identical to this one but not complete because of lack of time.

Lets try it again, until I succeed. :-)

Thoughts on MAC, IP, ARP and DHCP

A week ago, in the middle of a class a question popped up in my head. Why are there 2 addresses viz. IP address and MAC address? My friend and I were trying into find out the rationale behind such addressing schemes. here is the conversation...

Friend: I guess destination mac address in a packet doesn't change in its journey. Routers stay in promiscuous mode and grabs every packet it can see and forwards based on routing algorithms.

Me: I beg to differ! If the sending node has to keep the destination mac address in the packet, sender has to know destination mac address before it sends a packet. How does it happen to know destination MAC? It kind of seems like DNS name resolution where given a host name its IP address is retrieved. But there is a catch here. ARP protocol works within a subnet not on Internet unlike DNS. So I'm not sure if we can find destination mac address. For time being let's assume that we know destination mac address and embed it in packet. If there are two routers in a subnet (I'm not sure if such a topology exists for real!) then both routers will forward the packet. That means packet gets duplicated unnecessarily. Which doesn't happen in real networks. So I realized that whenever sender wants to send packet to a host which is in a different subnet, it sends it to the router it is connected to. That is, router's mac address is put in packet destination mac field. Now the router doesn't have to listen in promiscuous mode. It now filters packets which are not destined to it.

coming back to the center of this discussion, i would like to mention some reasons for why we need 2 addressing schemes. Before I delve into the details let me list down key differences between MAC and IP addresses.

1. MAC is 6 octets and is burned into NIC ROM by the manufacturer and IEEE ensures that manufacturers give unique MAC addresses to these devices. IP is (4 octets in case of IPv4 or 16 octets in case of IPv6) either statically configured or dynamically obtained using DHCP protocol.
2. MAC operates at Link Layer and it is independent of geographical location. That is, even if the node moves to any geographical location, its mac address DO NOT change. IP operates at network Layer and it changes whenever node moves to a different subnet.
3. MAC address is used by all nodes to make decision about passing packet to higher layers of the node or discard it. Routers use IP address to determine how to pick the destination interface and forwarding.
4. During a packet journey source and destination MAC address in link layer header change for every link in the path. Source and destination IP addresses do not change unless NAT's are involved. When NAT's are involved, IP address changes only near the end points and not in the middle of network.

I'm sure would have missed some of the differences between them. I would appreciate if you can comment any difference that is not mentioned.

We have already seen that IP addresses operate at network layer and are specific to IP protocol. Most people seem to think that only IP protocol operates at network layer. But thats not true. There are other protocols which operate at network layer like Novell's IPX or Digital equipment Corporation's DECnet. Each have its own addressing scheme. How do we interconnect such wide variety addressing nodes. We needed something which is common across all of the above.

Another reason being, filtering based on MAC address reduces the packets that go upward in the protocol stack. If we do not have MAC address then every frame seen on the communication medium has to be sent to higher layers. Which is resource consuming.

At this juncture it is really worth knowing about ARP and DHCP protocols, their role in communication.

ARP : ARP stands for Address Resolution Protocol. It is a lookup service to find MAC address of a node given its IP address. Its worth noting about another protocol RARP which does reverse lookup i.e. given MAC address it finds IP address. One important point I would like to mention is that It works within a subnet not on Internet.

Here is the protocol.

• ARP protocol works at link layer. ARP request packet (Who has IP 192.168.1.100?) is sent to broadcast MAC address FF:FF:FF:FF:FF:FF in a subnet.
• If the node exists with that IP, it replies to the sender its MAC address. Sender then updates its ARP table. Each entry in it has expiry time. So even when a node dies its entry will be deleted from the table, keeping it in clean state.

Security weakness???

Sender blindly trusts the response from any node. There is no authentication. So attacker can possibly send his MAC address when queried for another IP. Sender now have a wrong mapping between IP and MAC address in its table. This is called ARP poisoning.

DHCP : DHCP stands for Dynamic Host Configuration Protocol. It is used to obtain IP address from DHCP server dynamically when a node arrives into the system. Here is how the protocol works.

• DHCP discovery is the first step. Newly arrived node broadcasts a DHCP request packet to port 67 (It is the default port for DHCP server). packet has IP source address as 0.0.0.0 and destination 255.255.255.255 (broadcast address).
• Node receives DHCP offers from DHCP server with assigned IP address, network mast etc.
• Node sends DHCP Confirm message to DHCP server.
• Once node receives DHCP Ack then the protocol ends and both agree on the new IP address.

I hope to come up with an interesting blog on NAT's soon.