Useful knowledge for tech interviews

Standard

World population: 7.3B (July 2015)

Number of cell phones in the world: 6.8B (2013)

Number of Internet users in the world: 3.2B (2015)

Number of cars in the world: 1.2B (2014)

Most populous countries in the world (July 2015):
  – 1st China 1.36B
  – 2nd India 1.25B
  – 3rd US 321M

Most Internet users by country (2014):
  – 1st China 642M (46% penetration. Asia has 46% of world Internet users)
  – 2nd US 280M (87% penetration. North America has 10% of world Internet users)
  – 3rd India 243M (19% penetration)

Most cellphones by country (2014):
  – 1st China 1.28B (93% penetration with 47% smartphone penetration)
  – 2nd India 960M (78% penetration with 17% smartphone penetration)
  – 3rd US 327M (103% penetration with 56% smartphone penetration)

Most motor vehicles per capita by country (2011):
  – 1st San Marino 1263
  – 4th US 809
  – n-th China 113
  – m-th India 118
* per capita = per 1000 people

Most populous city in the US (July 2014):
  – 1st NYC 8.5M
  – 2nd LA 3.9M
  – 3rd Chicago 2.7M
  – 10th San Jose 1M
  – 13th SF 852K
  – 20th Seattle 668K
  – 29th Las Vegas 614K

Median household income in the US: $53K (2014)

Most profitable industries (2014):
  – 1st Health $21.8 billion
  – 2nd IT services $19.3B
  – 3rd Business products and services 18B
  – 4th Energy $17.5B
  – 5th Financial services $17.2B
  – 6th Human resources $12.3B
  – 7th Logistics and transportation $11.1B
  – 8th Consumer products and services $10.7B
  – 9th Construction $10.3B
  – 10th Telecommunications $9.4B

World’s largest tech companies by revenue (2014):
  – Apple $183B (55% iPhone, 18% iPad, 13% Mac, 9% iTurnes/Apps)
  – Amazon $89B (37% AWS, 26% merchandise, 4% media)
  – Microsoft $87B (33% Office, 26% server/tools, 24% Windows, 13% Skype/Xbox)
  – Google $66B (62% adWords, 21% adSense, 9% other, 8% Motorola)

Some thoughts about the future of TV

Standard

Concerning TV the appliance – With the demise of plasma TVs*, the line between TVs and computer monitors/tablets are further narrowing. They now both use LED LCDs for display; they both got brains; and they are getting interactive. The Microsoft Surface Hub might well represent the future of TVs/tablets – Sizable, smart, and interactive with a touchscreen. The future household might have a Surface Hub like piece on their living room wall, which performs tasks including greeting the family when they get home, displaying missed calls/voice mails/social media notifications, providing interface for adjusting lighting/curtains/temperature, and serving as a TV/gaming/video conference device when needed.

Regarding TV the service – Millions of people are switching from cable to low-cost streaming services. Inevitably, streaming will disrupt TV the same way the internet disrupted the music and print-media industries – by “unbundling” content and making it cheaper. This will also impact home networks – media streaming will become the No. 1 data consumer, therefore instead of streaming media over the existing cable Internet, we may get fiber Internet for streaming, and we will hookup laptops to the streaming device to access the Internet (Check out Google fiber).

* Both LG and Samsung ended production of plasma TVs in late 2014.

If you are asked to “find the k-th largest element in an unsorted array of length n” at an interview

Standard

First, think twice about this problems. For a general question like this, it can be shaped into different questions which might have different optimal solutions. Therefore, clarify things with the interviewer if needed. Following are some directions you can think:

  • About the elements in the given array

Is this an integer array?

Are there duplicate elements?

Are the elements sparse? (Will be explained below)

  • About what to return

If array contains duplicated numbers, how is the “k-th largest element” defined? Does it imply “finding the k-th distinct largest element” (e.g. the 2nd largest element in {1, 5, 5, 5, 3, 3} is 3 instead of 5)?

Do we need to maintain the order of the array while returning?

  • About k, n, and the relationship between them

Is n very large?

Is k a relatively small number as compared to n?

Is k a function of n?

What if k is larger than n/What if the k-th largest element does not exist (e.g. finding the fourth largest element in {1, 2, 3} or {1, 1, 1})?

  • About the algorithm complexity analysis

What’s the best solutions you can come up with in turns of time or space?

Are there any constraints on time/space?

Is there a priority in the solution (e.g. fastest performance, least space, etc)?

What next? Start with some simple solution and work on refining them later. This not only saves yourself from stressful thinking, but also helps you think out loud and show the interviewers your analysis capability.

The solutions you can think of probably are in these 2 directions: A) sort the array and then take k th largest element, B) select first k largest element one by one. From easy to hard, following is the list of possible solutions.

  1. A) Sorting based algorithms
  • Sort the array using one of the O(n^2) algorithms (e.g. bubble/insertion/selection sort) then return the k-th largest element.
  • Sort the array using one of the O(nlogn) algorithms (e.g. merge/quicksort/heap sort) then return the k-th largest element.
  • If this is an integer array (or, the number of digits is a constant instead of a function of n), we can sort the array using the radix/counting/bucket algorithm (depending on sparsity/duplication) with time complexity O(n) then return the k-th largest element.
  • If k is relatively small as compared to n, instead of sorting the entire array, we could use a modified selection sort (i.e., perform a selection sort but stop after obtaining the largest k elements) with O(nk).
  1. B) Selection based algorithms
  • Select largest element k times, the maximum value in k-th iteration would be the k-th largest element. Time complexity is then O(kn).

Finally, some test cases:

  • An array of many duplicates, e.g. {1, 1, 1, 5, 5, 5, 3, 3, 3, …}
  • An array with duplicated pivots, e.g. finding the 4th largest element in {1, 2, 3, 4, 4, 4, 5, 6, 7}
  • An array with a single value, e.g. {5, 5, 5, 5, 5, …}
  • A sorted array (ascending and descending)
  • An array with the pivot as the first/last element
  • In real world implementations, test k and n whenever necessary, make the function robust to illegal arguments

Notes

A similar problem is to “find the top k elements in an unsorted integer array of length n”. Solving the first problem essentially solves the second one – one is to find the pivot, and the other is to partition the array based on the pivot. However, if there are duplicates in the array, the first problem may be harder to optimize in some cases. Consider “finding the top 90 elements in an array of length 100″ vs “finding the 90th largest element in an array of length 100″. When there are duplicates in the array, the former can be translated into “finding the bottom 10 elements”, whereas the latter cannot be translated into “finding the 10th smallest element” .

We are assuming that when there are duplicates, “finding the k-th largest element” implies “finding the k-th distinct largest element”, e.g. the 2nd largest element in {1, 3, 3, 5, 5, 5} is 3 instead of 5.

Framing effect and poker

Standard

Framing effect refers to the phenomenon that people react differently to the same piece of information, due to how the information is presented – in terms of loss, or in terms of gain. An example in poker would be: Suppose a player is considering investing 5k into a 5k pot. He could be thinking ‘If I invest, I could earn 5k’ (positive frame), or ‘If I invest, I could lose 5k’ (negative frame). Research has found that people tend to avoid risk when a positive frame is presented (‘I may win 5k, but this is risky, and I don’t want to take the risk’), but seek risks when a negative frame is presented (‘I may lose 5k, although it’s risky, I want to take the risk’).

I can see how this affects decision making for someone who is unclear about his goals. Now my question is: if someone is clear about his goals (e.g., a good poker player), could framing still affect him?

A good poker player is required to prioritize his goals in almost every single minute – Is this a tournament that I want to ‘win big or go home’, or just cash? Is this a stage that I need to accumulate more chips, or just sit and watch the endangered players being eliminated? Is it more important for me to win this pot, or I can’t afford to lose more chips? Once he understands his priorities, he will know which one is more important – gain or loss – and make decisions accordingly.

Better still, if a player is really that good, he can totally use the framing effect to his advantage – if he wants to encourage himself to take more risks, he could think in terms of negative frames; and when he wants to remind himself to avoid risk, he resorts to positive frames. 

It’s not what we say, it’s how we say it.

Standard

Research is suggesting that, ‘it’s not what we say, it’s how we say it’. The sound of our voices – such as pitch and accent – affect how we are perceived by others. In other words, the same statement, if voiced in different ways, could be understood differently. So someone could be totally having great opinion and intentions, but just because he is not good at delivery, his opinion or intentions are discounted, or even misunderstood. This is actually sad. It’s the content, not the form, that matters, isn’t it? Could we ask every time, before we make any judgements or grow any emotions, ‘what is this person really trying to say’, and ‘what is this person’s intention’, instead of ‘what is felt’?