Welcome to Shanshan Blog!

• Replace Words in the Folder Using Python

  2017-02-05

  Python

  Python

  import os
  
  # list files
  
  def listFiles(dirPath):
      fileList = []
  
      for root, dirs, files in os.walk(dirPath):
  
          for fileObj in files:
              fileList.append(os.path.join(root, fileObj))
  
      return fileList
  
  
  def main():
      fileDir = "/Users/fushanshan/Documents/Shanshan-IC.github.io/_posts"
  
      fileList = listFiles(fileDir)
  
      for fileObj in fileList:
  
          f = open(fileObj, 'r+')
  
          all_the_lines = f.readlines()
  
          f.seek(0)
  
          f.truncate()
  
          for line in all_the_lines:
              f.write(line.replace('[hihoCoder]', 'hihoCoder'))
  
          f.close()
  
  
  if __name__ == '__main__':
      main()
  

  Read All

  ---

• Search Algorithm

  2017-02-04

  Algorithms

  Algorithms
  • Linear Search
  • Binary Search
  • Hash Table
  • Interpolation Search

  An algorithm is a step-by-step procedure or method for solving a problem by a computer in a given number of steps. The steps of an algorithm may include repetition depending upon the problem for which the algorithm is being developed. The algorithm is written in human readable and understandable form.

  Linear Search

  A linear search searches an element or value from an array till the desired element or value is not found and it searches in a sequence order. It compares the element with all the other elements given in the list and if the element is matched it returns the value index else it return -1.

  def linear_search(list, val):
      for index, x in enumerate(list):
          if (val == x):
              return index
      return -1
  
  if __name__ == '__main__':
      print linear_search([1, 2, 3, 5, 6, 7, 101010, 1928394, 10299283, 28282829338474], 1928394)
  

  Binary Search

  # -*- coding:utf-8 -*-
  """
  假设列表从小到大排列，查询一个数字，使用二分法的思想
  """
  
  def binary_search(list, val):
      left = 0
      right = len(list)-1
      while (left<=right):
          mid = left+(right-left)/2
          if val == list[mid] :
              return mid
          elif val < list[mid]:
              right = mid-1
          else:
              left = mid+1
      return -1
  

  Hash Table

  Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

  Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.

  Interpolation Search

  Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.

  In binary search, we use mid = (low + high) / 2, in interpolation search, we use mid = low + (key - a[low] / (a[high] - a[low]) * (high - low))

  # -*- coding:utf-8 -*-
  """
  比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5，
  会考虑从数组下标较小的开始查找。
  经过以上分析，折半查找这种查找方式，还是有改进空间的，并不一定是折半的！
  mid = （low+high）/ 2, 即 mid = low + 1/2 * (high - low);
  改进为下面的计算机方案（不知道具体过程）：
  mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low)，
  也就是将上述的比例参数1/2改进了，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，
  这样也就间接地减少了比较次数。
  
  """
  def interpolation_search(list, val):
      len_list = len(list)
      left = 0
      right = len_list-1
      while (left <= right):
          pos = left + (val-list[left])/(list[right]-list[left])*(right-left)
          if (list[pos] == val):
              return pos
          elif (list[pos] > val):
              right = pos - 1
          else:
              left = pos + 1
      return -1;
  

  Read All

  ---

• DiDi Online Test 2017

  2017-02-03

  Interview

  Interview CPP
  • First Question
  • Second Question

  DIDI Interview Questions

  First Question

  • 平面上有N个点，怎么样才能找到斜率最大的两个点。

  Note:

  step 1: 先对N个点的x排序 step 2: 斜率最大的值为最大的point[i+1], point[i]的斜率

  #include <iostream>
  #include <vector>
  
  using namespace std;
  bool compare(pair<int,int> i, pair<int, int>j) {
      return i.first<=j.first;
  }
  int main() {
      vector<pair<int,int>> vs;
      vs.push_back(make_pair<int, int>(1,2));
      vs.push_back(make_pair<int, int>(6,4));
      vs.push_back(make_pair<int, int>(4,6));
      vs.push_back(make_pair<int, int>(2,11));
      vs.push_back(make_pair<int, int>(3,9));
      
      // code part
      double maxs = (vs[1].second-vs[0].second)*1.0/(vs[1].first-vs[0].first);
      sort(vs.begin(), vs.end(), compare);
      for (int i=1; i<vs.size()-1; i++) {
          double temp =(vs[i+1].second-vs[i].second)*1.0/(vs[i+1].first-vs[i].first);
          if (temp>maxs)  maxs=temp;
      }
      cout << "the max one is " << maxs << endl;
  }
  

  Second Question

  • 在矩形中找到一块面积最大的区域。
  Read All

  ---

• Stack Implementation in Python

  2017-02-02

  Algorithms

  Algorithms

  #include <iostream>
  using namespace std;
  
  class Stack {
  private:
      int size;
      int top;
      int *data;
  public:
      Stack(int _s){
          top = 0;
          size = _s;
          data = new int[_s];
      }
      bool isempty(){
          return size==0;
      }
      
      bool isFull() {
          return top==size;
      }
      
      void push(int x) {
          if (isFull())
              return;
          data[top] = x;
          top++;
      }
      
      void pop() {
          if (isempty())  return;
          top--;
      }
  };
  
  int main() {
      Stack *s = new Stack(19);
      cout << s->isempty() << endl;
      s->push(2);
      cout << s->isempty() << endl;
      s->pop();
      cout << s->isempty() << endl;
      return 0;
  }
  
  

  Two queue Implement stack

  #include <queue>
  using namespace std;
  
  class stack {
  private:
      queue<int> q;
  public:
      bool empty() {
          return q.empty();
      }
      void push(int x) {
          q.push(x);
          for (int i=0; i<q.size()-1; i++) {
              q.push(q.front());
              q.pop();
          }
      }
      int top() {
          return q.front();
      }
      void pop() {
          q.pop();
      }
  };
  

  Read All

  ---

• Queue Implementation in Python

  2017-02-02

  Algorithms

  Algorithms

  #include <iostream>
  using namespace std;
  
  template <typename T>
  
  struct node {
      T data;
      node *next;
      node(T &d){
          data = d;
          next = NULL;
      }
  };
  
  template <typename T>
  class Queuei {
  private:
      int size;
      node<T> *front;
      node<T> *rear;
  public:
      Queuei(T &n) {
          node <T> *p = new node<T>(n);
          size = 0;
          front = p;
          rear = p;
      }
      
      int getQueueSize() {
          return size;
      }
      
      bool isEmpty() {
          return size==0;
      }
      
      void push(T n) {
          node<T> *p = new node<T>(n);
          rear->next = p;
          rear = p;
          size++;
      }
      
      void pop() {
          if (size==0)    return;
          node<T> *p = front->next;
          front->next = p->next;
          delete p;
          size--;
      }
     
  };
  
  int main() {
      int head = 0;
      Queuei<int> * q = new Queuei<int>(head);
      q->push(2);
      q->push(3);
      cout << q->getQueueSize() << endl;
      q->pop();
      return 0;
  }
  

  Using two stack to implement one queue

  #include <stack>
  
  using namespace std;
  
  class Queuei {
  private:
      stack <int> s1;
      stack <int> s2;
      
  public:
      bool isEmpty() {
          return s1.empty() && s2.empty();
      }
      
      void push(int x) {
          s1.push(x);
      }
      
      int pop() {
          if (s2.empty()) {
              while (!s1.empty()) {
                  s2.push(s1.top());
                  s1.pop();
              }
          }
          return s2.top();
      }
  };
  
  

  Read All

  ---

• Heap Sort and Implementation in Python

  2017-02-01

  Algorithms

  Algorithms
  • Heap Sort
  • Example
  • Complexity
  • Pseudocode
  • Implementation in Python

  Heap Sort

  The heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap. This repeats until the range of considered values is one value in length.

  The steps are:

  a. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in O(n) operations.

  b. Swap the first element of the list with the final element. Decrease the considered range of the list by one.

  c. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.

  d. Go to step b unless the considered range of the list is one element.

  Example

  Given a list [6 2 4 1 5 9]

  a. pick the first number 6, and compare other numbers with 6, the bigger one is put in the right, otherwise in the lef, so it become: [2 4 1 5 6 9]

  b. then quick sort the left part [2 4 1 5] and the right part [9], continue step a, it will become: [1 2 4 5], so the result is [1 2 4 5 6 9]

  Complexity

  

  Pseudocode

  procedure heapsort(a, count) is
      input: an unordered array a of length count
   
      (Build the heap in array a so that largest value is at the root)
      heapify(a, count)
  
      (The following loop maintains the invariants that a[0:end] is a heap and every element
       beyond end is greater than everything before it (so a[end:count] is in sorted order))
      end ← count - 1
      while end > 0 do
          (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
          swap(a[end], a[0])
          (the heap size is reduced by one)
          end ← end - 1
          (the swap ruined the heap property, so restore it)
          siftDown(a, 0, end)
  

  Implementation in Python

  def heapify(l, n, i):
      maxs = i
      left = 2*i+1
      right = 2*i+2
      if (left<n and l[left]>l[maxs]):
          maxs = left
      if (right<n and l[right]>l[maxs]):
          maxs = right
      if (maxs!=i):
          l[i], l[maxs] = l[maxs], l[i]
          heapify(l, n, maxs)
  
  def heap_sort(l):
      size = len(l)
      for i in range(size/2-1, -1, -1):
          heapify(l, size, i)
      for j in range(size-1, -1, -1):
          l[0], l[j] = l[j], l[0]
          heapify(l, j, 0)
      return l
  
  def main():
      l = [2, 3, 4, 1, 7, 3, 8, 1100, 282828, 1, 20, 0]
      li = heap_sort(l)
      print li
  
  main()
  
  

  Read All

  ---