Bloomberg

  • For a given number n, output numbers from 1 to n in lexicographical order.
    Example: 
    Given n = 11
Output 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9

几种思路：

  1. 把所有整数变成长度一样然后排序，之后再还原。
  2. 直接用to_string，然后排序
  3. overload排序算法

Solution-1

def orderNumber(n):
    nums = range(1, n+1, 1)
    tmp = 1
    while ( n/tmp >= 1 ): tmp *= 10
    for i in range(n):
        while ( nums[i]*10 < tmp ): nums[i] *= 10
    nums.sort()
    i = 0
    while ( i <= n-1 ):
        if ( nums[i] > n ): nums[i] /= 10
        j = i
        while ( j <= n-1 and nums[i] == nums[j] ): j += 1
        tmp = 1
        k = j-1
        while ( k >= i ): 
            nums[k] /= tmp
            tmp *= 10
            k -= 1
        i = j
  return nums

Solution-2&3
Note the syntax of overloading! (check leetcode 352 solution for references.)

bool compare1(int i1, int i2) {
  return ( to_string(i1) < to_string(i2) );
}
class Solution {
  public:
    struct compare2 {
      bool operator() (int i1, int i2 ) { return to_string(i1) < to_string(i2);}
    }compare3;
    vector<int> newsort(int n) {
      vector<int> res;
      // or here, directly res.push_back(to_string()i+1), then sort
      for (int i = 0; i <= n-1; i++ ) res.push_back(i+1);
      sort(res.begin(), res.end(), compare1);
      sort(res.begin(), res.end(), compare2());
      sort(res.begin(), res.end(), compare3);
      return res;
    }
};

  • Two sum on a BST. Given a binary search tree and a target number, return a pair of nodes whose sum equals to the target.

  • Reverse an integer without using string. 

    def reverseInteger(n):
 res = 0
 while ( n != 0 ):
     res = res*10 + n%10
     n = n/10
 return res

  • Find insection of 5 array.

    • use set
    • use hashmap
    • sort the array first.

  • Two sum

  • Given an array, return number of duplicated numbers.
    For example

    Given [5, 2, 2, 4], return 1
Given [8, 33, 7, 8, 7, 7], return 2
Given [1, 2, 3], return 0
    • sort? hashtable?

  • Given a target number and the root of a binary search tree. Delete the leaf node whose value equals to the target number.

  • Define the path sum as the sum along each root-to-leaf node path. Find the minimum path sum, and output the path.

  • String Compression 

    Given "aabbbc", return "a2b4c".

    Solution: 

    class Solution {
public:
  string compressString(string s) {
    int n = s.size();
    if ( n <= 1 ) return s;
    char c = s[0];
    string res;
    int icount = 1;
    s = s + ' ';
    for ( int i = 1; i <= n; i++ ) {
      if ( s[i] == c ) { icount += 1; continue; }
      res += c;
      if ( icount != 1 ) res += to_string(icount);
      c = s[i];
      icount = 1;
    }
    return res;
  }
};

  • Add Digits (leetcode 258)

    • Constant time solution?
      // Note the relation:
// addDigits(n) == (n-1)%9 + 1

  • Traverse a binary tree in level order.

    • Follow up: 层序输出path sum为奇/偶的节点（不能更改节点的结构）
  • Given a string, output the characters that only appear once.
    • Follow up 1: 按原序输出.
    • Follow up 2: 只需用set，不许用hashmap
  • H-index (two solutions?)
    Solution
    Note the fact that
    1. h-index <= number of papers;
    2. h-index <= maximum citations
  • Sort the citations array in descending order,
    • the h-index at i-th position can not be larger than (i+1).
    • when adding the (i+1)-th paper with a citation number lower than h_index(i), h_index(i+1) = h_index(i). (And h_index cannot be increase again...) 
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size(), i;
        sort(citations.begin(), citations.end());
        for ( i = n-1; i >= 0; i-- ) {
            if ( citations[i] < n-i) return n-i-1;
        }
        return n;
    }
};

Optimized solution:
Use "binary search" to optimize the above solution. Take [3, 0, 6, 1, 5] as an example:
Consider two arrays: 

citations = [0, 1, 3, 5, 6]
helper = [5, 4, 3, 2, 1]

Find the smallest i s.t. citations[i] >= helper[i]. Note the loop condition in binary search when implementing it. 

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if ( n == 0 ) return 0;
        vector<int> helper(n, 0);
        for ( int i = 0; i <= n-1; i++ ) helper[i] = n - i;
        if ( citations[n-1] < helper[n-1]) return 0;
        if ( citations[0] >= helper[0] ) return helper[0];
        int l = 0, r = n-1, mid;
        while ( l < r-1 ) {
            mid = (l+r)/2;
            if ( citations[mid] >= helper[mid] ) r = mid;
            else l = mid;
        }
        return helper[r];
    }
};

  • Merge K sorted linked lists

  • 在一个排序的数组中找一个数出现的次数， 用binary search

  • For a given string, find the number of its unique substrings.
    Solution 

    def countUnique(s):
  n = len(s)
  count = 0
  for i in range(1, n+1, 1):
      record = {}
      tmp = n-i+1
      for j in range(n-i+1):
          sub_s = s[j:j+i]
          if ( sub_s not in record ): 
              record[sub_s] = 1
          else:
              tmp -= 1
      count += tmp
return count

  • Jumping Number
    http://www.geeksforgeeks.org/print-all-jumping-numbers-smaller-than-or-equal-to-a-given-value/

    def jumpingNumber(n):
  if ( n <= 9 ): return range(n+1)
  res1 = range(1, 10, 1)
  res = res1[:]
  while ( len(res1) != 0 ):
    res += res1
    res2 = []
    for i in res1:
      last_digit = i%10
      if ( last_digit != 9 ):
        new_i = i*10 + last_digit + 1
        if ( new_i <= n ):
          res2.append(new_i)
      if ( last_digit != 0 ):
        new_i = i*10 + last_digit - 1
        if ( new_i <= n ):
          res2.append(new_i)
      res1 = res2[:]
    res.append(0)
  return res

  • Jump robot (enforce jump) 

import random
def jump():
  return random.randrange(2)

def enforceJump():
  start, end = 0, 0
  while ( end != start+1 ):
    end += (2*jump())-1
    print end
  return

enforceJump()
  • Hashmap 里放名字和编号，名字是value，编号是key，要求打印出以名字为顺序的内容。
    example:
    map: 1 John 2 John 3 Bob 4 Amy
    output: Amy 4 Bob 3 John 1 John 2
    要求不允许使用第二个map。 
def print_name(dict):
  res = [];
  for i in dict:
    name = dict[i]
    add = False
    for j in range(len(res)):
      if ( name < res[j][0] or ( name == res[j][0] and i < res[j][1]) ):
        res.insert(j, [name, i])
        add = True
        break
      if ( name == res[j][0] and i > res[j][1] ):
        res.insert(j+1, [name, i])
        add = True
        break
    if ( not add ): res.append([name, i])
  print res

dict = {}
dict[1] = 'John'
dict[2] = 'John'
dict[3] = 'Bob'
dict[4] = 'Amy'
print_name(dict)
  • 一个是链表求最后第k个node，要用快慢指针，快的先走k步，然后快慢一起走。
  • LRU cache，好像以前的面经提到过。先是让你实现有股票id，然后取price（用map）。然后加要求，说要取最近的10个（用list存map的value），然后是再这个基础上还要知道最大最小值（map的value变成一个object，包括最大最小值和list），最后是怎么空间有限，怎么办（没直接提LRU，但就是LRU的方法）。

  • 有event大概是有id，desc，和timestamp，要实现getEventById和getEventByRange（startTime， endTime， order（desc | asc））。

  • 一列vector，每个数打印后一个比他大的数，比如 1,3,2,4打印 1->3, 3->4, 2->4 打印顺序不要求. follow up: time complexity

    def nextGreater(nums):
stack = []
res = []
for i in nums:
  while ( len(stack) >= 1 and i > stack[-1] ):
    res.append(str(stack[-1]) + "->" + str(i))
    stack.pop(-1)
  stack.append(i)
return res

  • Integer sqrt: 

    def sqrt_int(n):
  if ( n < 0 ): return
  if ( n == 0 or n == 1 ): return n
  l, r = 0, n
  while ( True ):
    m = (l+r)/2
    if ( m**2 <= n and (m+1)**2 > n ): return m
    if ( m**2 > n ): r = m
    else: l = m

  • float sqrt: 

    def sqrt_float(n, d):
  if ( n < 0 ): return
  if ( n == 0 or n == 1 ): return n
  l, r = 0., max(1, float(n))
  while ( True ):
    m = (l+r)/2.
    if ( m**2 <= n and (m+d)**2 > n ):
      m = int(m/d)*d
      if ( (m+d)**2 > n ): return m
      else: return (m+d)
    if ( m**2 > n ): r = m
    else: l = m

  • 给一个数列，按照数字出现次数从多到少依次打印出数字。同时必须保持数字的原顺序：
    输入：[6,1,2,2,1,3,3,3,9]
    输出：3,1,2,6,9
    Solution
    map + priority_queue 

    class Solution {
public:
  vector<int> frequency(vector<int>& nums) {
    unordered_map<int, int> freq;
    priority_queue<pair<int, int> > maxHeap;
    vector<int> res;
    int n = nums.size();
    if ( n == 0 ) return res;
    for ( int i = 0; i <= n-1; i++ ) {
      if ( freq.find(nums[i]) == freq.end() ) freq[nums[i]] = 1;
      else freq[nums[i]] += 1;
    }
    for ( auto it = freq.begin(); it != freq.end(); it++ ) {
      maxHeap.push(pair<int, int>(it->second, it->first));
    }
    while ( ! maxHeap.empty() ) {
      res.push_back(maxHeap.top().second);
      maxHeap.pop();
    }
    return res;
  }
};

  • 给一个Tree，这个tree的每一个node可以有很多children，每一个node只有一个pointer指向它的parent，和平常熟悉的tree不一样，平常的tree都是parent有pointer指向children.

    • 他先让我把TreeNode的definition写出来，
    • 然后让我做一个function，input是一个数组和一个int，数组里面存的是这个tree的所有的node, int存的是target。要我在这个tree里找到target然后return这个target node的所有的children(including the grand children, I guess...)。 HashTable!-- not tested yet
      class Solution {
struct TreeNode {
int val;
TreeNode* parent;
TreeNode(int x): val(x), parent(NULL){};
};
public:  
vector<TreeNode*> help(unordered_map<TreeNode*, vector<int> >& children, vector<TreeNode*>& nodes, TreeNode* parent) {
vector<TreeNode*> res;
if ( children.find(parent) == children.end() ) return res;
int n = children[parent].size();
for ( int i = 0; i <= n-1; i++ ) {
  int j = children[parent][i];
  res.push_back(nodes[j]);
  auto tmp_res = help(children, nodes, nodes[j]);
  int nres = tmp_res.size();
  for ( int k = 0; k <= nres-1; k++ ) res.push_back(tmp_res[k]);
}
return res;
}
vector<TreeNode*> findChildren(vector<TreeNode*>& nodes, int target ) {
int n = nodes.size(), itarget = -1;
vector<TreeNode*> res;
unordered_map<TreeNode*, vector<int> > children;
if ( n == 0 ) return res;
for ( int i = 0; i <= n-1; i++ ) {
  if ( nodes[i]->val == target ) itarget = target;
  children[nodes[i]->parent].push_back(i);
}
if ( itarget == -1 ) return res;
return help(children, nodes, nodes[itarget]);
}
};
  • Server Attack ?? 只有一个function，用这个function来察觉有没有在攻击服务器。这个function return bool, 每次有一个server request这个function都会被call. 然后告诉我这个function will return true如果在5秒内有10次以上的request。 (这个题我一开始给出的方法是用一个time和count来看，每5秒更新一次time并重设count为0. 但是面试官指出这个方法对于这种情况不行: {0 1 2 3 4 5.5 5.5 5.5 5.5 5.5 5.5}。在这种情况下我的function会给false 但是其实应该是true，因为我的function会在第一个5.5上reset。然后我就纠结了半天，面试官给了一些提示，最后才想出用一个window卡住10个request 然后每一次只看头和尾的时间差，如果是小于5秒就证明有server attack。这个window用queue来做。) 
bool serverAttack(double t){
  static priority_queue<double> time_record;
  int n = time_record.size();
  if ( n <= 8 ) {
    time_record.push(-t);
    return false;
  }
  double earliest = -time_record.top();
  time_record.pop();
  time_record.push(-t);
  double interval = t - earliest;
  return ( interval <= 5);
}
int main(){
  double array[11] = {0, 1, 2, 3, 4, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5};
  for ( int i = 0; i <= 10; i++ ) {
    cout << serverAttack(array[i]) << endl;
  }
  return 0;
}
  • 给我一个tree，每一个node有pointer指向up, right, down。然后说每一个node都比自己上面的值大，比下面的值小，最后右边的值比自己的值大，也比所有自己下面的值要大。他给我画了个example，所以这样比较好懂。他先给了我1到9，让我把这10个数字放进他画的tree里面。然后问我如果写算法要怎么把1到n放入tree里面。我解释完，他让我写一个function来print所有的node， in order。然后我写迅速写了一个recursive的方法，蛮简单的，一遍就过。然后他问我那iterative呢，我说每个node的上面用stack, 下面用queue，他说上面确实要用stack,但是下面真的需要queue么。我想了想，说不需要，用那个stack也能做到，然后再解释了一下，他表示满意。 
    example:
     2
     |
     3    5
     |    |
1 -> 4 -> 6 -> 9
     |    |
     7    10
     |
     8
    pseudo code?
    ``` vector inorder(TreeNode* root) { vector res; if ( root == NULL ) return res; res.push_back(root->val);

} ```

results matching ""

    No results matching ""