Category Archives: interview-amazon

[Leetcode] Reverse Words in a String

Posted on by
Reply

Problem

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Analysis

  • 首先split string by space
  • 然后 append word in reverse order
  • 注意 如果当前非空，在append下一个word之前，需要append空格

Code


Reference

[Code Interview] Count number of ones

Posted on by
Reply

Problem

Counting the number of 1 bits in the binary representation of a given integer.  

Analysis

Method 1: 

  • shift the number right by one bit each time, and check whether the right-most bit is 1
    • If yes, count++

Method 2:

    • if n is not 0, count++
    • assign n = n & (n-1), repeat until n is 0

    Time complexity
    • method 1: theta(n)
    • method 2: O(n)

    Code



    Reference