Archives for Tháng Ba 2017


Trở thành lập trình viên chuyên nghiệp từ một tay chơi poker – Haseeb Qureshi

Hôm nay mình sẽ kể cho các bạn nghe về câu chuyện về Haseeb Qureshi. Anh từ một tay chơi Poker chuyên nghiệp đến một nhà lập trình viên xuất sắc, nhận được 8 offer của các công ty lớn trong đó có Google, Uber, Airbnb…

yeulaptrinh.pw

Haseeb Qureshi chơi Poker từ năm 16 tuổi, anh nhanh chống trở thành một trong những người chơi Poker đẳng cấp thế giới và kiếm được khá nhiều tiền. Năm 21 tuổi, sau một scandal xảy ra trong nghề nghiệp của mình, anh quyết định từ bỏ việc chơi Poker.

Trở về nhà, anh dành nhiều thời gian suy ngẫm về quá khứ của mình, sau đó hoàn tất việc học Anh Ngữ/Triết Học của mình tại The University of Texas. Tháng 12/2013 Haseed cho ra đời quyển sách “How to Be a Poker Player: The Philosophy of Poker” và nó nhanh chống trở thành một trong những quyển sách viết về Poker bán rất chạy thời đó.

Tuy nhiên Haseeb cảm thấy thật sự không hạnh phúc, ông quyên góp toàn bộ số tiền mình kiếm được cho từ thiện và cho gia đình mình, anh giữ lại 10.000 USD để học những gì mình yêu thích.

Năm 2014 Haseed bắt đầu dấn thân vào ngành công nghiệp công nghệ cao, anh chọn Công Nghệ Thông Tin là bước đi tiếp theo của mình. Anh bắt đầu tự học thêm kiến thức cho mình. Để đi một con đường mới là không hề dễ dàng và Haseed lên kế hoạch và lộ trình học tập cho riêng mình.

Sau đây là từng bước chiến lược học tập của Haseed, mình xin chia sẽ với các bạn:
————-
1. Tham gia khóa học Thuật Toán miễn phí trên Coursera “Princeton Coursera course on algorithms”
Link: https://www.coursera.org/learn/algorithms-part1.

2. Đọc quyển “The Algorithm Design Manual” của Steven S Skiena để bổ sung các kiến thức nền tảng về Cấu Trúc Dữ Liệu và Giải Thuật.

3. Đọc quyển “Cracking the Coding Interview” Gayle Laakmann McDowell để lấy kinh nghiệm và lên chiến lược Interview phù hợp.

4. Nghe thường xuyên các tin tức về Software Engineering trên các trang như:
– Software Engineering Daily: http://softwareengineeringdaily.com/category/podcast/
– The Bike Shed: http://bikeshed.fm/
– Đọc tên tin tức tại Hacker News: https://news.ycombinator.com/

Theo Haseed thì có thể ban đầu việc nghe sẽ rất khó khăn với bạn nhưng bạn chỉ nghe thôi không cần hiểu dần dần bạn sẽ quen. Việc Nghe tin tức về lĩnh vực bạn sẽ giúp bạn nắm bắt nhanh các xu thế CNTT hiện nay, quen dần với các thuật ngữ phổ biến bằng Tiếng Anh trong CNTT và đó cũng là cách để bạn có thể nói chuyện với các Developer khác một cách chuyên nghiệp.

5. Về phần System Design and Architecture, Haseed khuyên bạn nên đọc các kiến thức tại:
– HiredInTech: http://www.hiredintech.com/system-design
– High Scalability: http://highscalability.com/all-time-favorites/
————–

Sau đó Haseed tham dự bootcamp một khóa học ngắn hạn (12 tuần) để Review lại kiến thức của mình tại App Academy. Với Haseed điều quan trọng nhất là bạn phải “study study study” và không được nản chí. Anh là người thường xuyên đến sớm nhất và về trể nhất trong các buổi học.

Năm 2016 là năm thành công rực rỡ của Haseed anh nhận được 8 lời mời làm việc tại Google, Uber, Yelp, and Airbnb… Sau đó anh quyết định gia nhập Airbnb và hiện nay đang là kỹ sư phần mềm quan trọng của Airbnb.

Haseed là tấm gương điển hình mà chúng ta nên lấy đó là động lực để phấn đấu. Mình hi vọng những chia sẽ này sẽ giúp ích cho các bạn.

Tác giả: thầy Phạm Nguyễn Sơn Tùng – HCMUS

NKNUMFRE – spoj

Đề bài:

Thuật toán:

  • Vét cạn.

Code:

const
  fi='';
  fo='';
var
  a,b,i,j,dem,num : longint;
procedure swap(var x,y : char);
  var tg :char;
  begin
    tg:=x;x:=y;y:=tg;
  end;
function gcd(a,b : longint) : longint;
  var r : longint;
  begin
    while b>0 do
      begin
        r := a mod b;
        a:=b;
        b:=r;
      end;
    exit(a);
  end;
function dao(x : longint) : longint;
  var s : string;
      y : longint;
  begin
    str(x,s);
    i:=1;j:=length(s);
    while i<j do
      begin
        swap(s[i],s[j]);
        inc(i);dec(j);
      end;
    val(s,y);
    exit(y);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(a,b);
  for num := a to b do
    if gcd(dao(num),num)=1 then inc(dem);
  writeln(dem);
  close(input);close(output);
end.

QBHEAP – spoj

Đề bài:

Thuật toán:

  • Với C++ bạn có thể dùng sẵn CTDL Priority Queue (hàng đợi ưu tiên). Còn với Pascal thì bạn phải tự viết CTDL Heap

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 20000;
string s;
priority_queue <int> h;
char key;
int num, a[MAXN];
 
bool cmp(int a, int b) {
    return (a > b);
}
 
int main() {
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    // solve
    getline(cin, s);
    do {
        key = s[0];
        if (key == '+') {
            s.erase(0,1);
            num = atoi(s.c_str());
            if (h.size()<15000) h.push(num);
        } else if (!h.empty())
        {
            num = h.top();
            while (!h.empty() && h.top()==num) h.pop();
        }
        getline(cin, s);
    } while (s != "");
    // pop
    int res = 0;
    while (!h.empty()) {
        res++;
        a[res] = h.top();
        while (!h.empty() && h.top()==a[res]) h.pop();
    }
    // print
    cout << res << endl;
    for (int i = 1; i <= res; i++) cout << a[i] << endl;
    return 0;
}
const   fi='';
        fo='';
        maxn=15000+3;
var     h:array[1..maxn] of longint;
        i,j:longint;
        res:array[0..maxn] of longint;
        nh,n,ans:longint;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,i,j:longint;
begin
            i:=l;j:=r;
            x:=res[(i+j) div 2];
            repeat
                while res[i]>x do inc(i);
                while res[j]<x do dec(J);
                if i<=j then
                        begin
                            swap(res[i],res[j]);
                            inc(i);dec(j);
                        end;
            until i>j;
            if i<r then qs(i,r);
            if j>l then qs(l,j);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:= i + i;
        if j>nh then exit;
        if (j<nh) and (h[j]<h[j+1]) then inc(j);
        if h[j]>h[i] then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if h[i]>h[j] then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
procedure push(x:longint);
begin
        inc(nh);
        h[nh]:=x;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure xuat;
begin
        for i:=1 to n do
                if res[i]<>res[i-1] then writeln(res[i]);
end;
procedure main;
var     tam,s:string;
        x,err:longint;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    while not seekeof(input) do
        begin
            readln(s);
            if s[1]='+' then
            begin
              if nh<15000 then
                begin
                    tam:=copy(s,2,length(s));
                    val(tam,x,err);
                    push(x);
                end
                end
                ELSE
                if nh>0 then
                begin
                        if nh>0 then x:=pop;
                        while (nh>0) and (h[1]=x) do pop;
                end;
        end;
        for i:=1 to nh do
                begin
                        res[i]:=pop;
                        inc(n);
                end;
        qs(1,n);
        res[0]:=-1;
        for i:=1 to n do
                if res[i]<>res[i-1] then inc(ans);
        writeln(ans);
        xuat;
 
    close(input);close(output);
end;
begin
    main;
end.

NDCCARD – spoj

Đề bài:

Thuật toán:

  • Dùng mảng f[i] đánh dấu giá trị lớn nhất <= i trong dãy A.
  • Vậy nên các cặp 3 số là a[i], a[j], f[m-a[i]-a[j]].
  • Chú ý đề bài cho dãy A đôi một khác nhau nhé.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int oo = 500001;
const int MAXN = 10001;
int i, j, n, m, a[MAXN], tmp, res, f[oo];
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    tmp = 0;
    for (int i = a[1]; i <= m; i++) {
        if ((tmp < n) && (i >= a[tmp+1])) tmp++;
        f[i] = a[tmp];
    }
    for (int i = 1; i<= n-2; i++) {
        for (int j = i+1; j <= n-1; j++) {
            tmp = m - a[i] - a[j];
            if (tmp < 1) continue;
            tmp = f[tmp];
            if (tmp <= a[j]) continue;
            res = max(res, a[i] + a[j] + tmp);
        }
    }
    cout << res;
    return 0;
}
CONST fin='';
     fout='';
VAR res, i, j, n, m, x, min: longint;
    a, ok: array[1..1000000] of longint;
    f: text;
BEGIN
  Assign(f,fin);
  Reset(f);
  Readln(f,n,m);
  min:=maxlongint-1;
  For i:=1 to n do
    Begin
      Read(f,a[i]);
      ok[a[i]]:=a[i];
      If a[i]<min then min:=a[i];
    End;
  Close(f);
  For i:=min+1 to  1000000 do
    If ok[i]=0 then ok[i]:=ok[i-1];
  res:=0;
  For i:=1 to n-1 do
    For j:=i+1 to n do
      Begin
        x:=m-a[i]-a[j];
        If x>0 then
          Begin
            If (ok[x]<>a[i]) and (ok[x]<>a[j]) and (ok[i]<>0) then
              If a[i]+a[j]+ok[x]>res then res:=a[i]+a[j]+ok[x];
          End;
      End;
  Assign(f,fout);
  Rewrite(f);
  Writeln(f,res);
  Close(f);
END.

VECTOR – spoj

Đề bài:

Thuật toán:

Code:

const
  fi='';
  fo='';
  maxn=30;
  oo=5000;
var
  d : array[-oo..oo,-oo..oo] of longint;
  x,y : array[1..maxn] of longint ;
  i,j,n,u,v,xx,yy,s1,s2 : longint;
  res : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i:=1 to n do read(x[i],y[i]);
    read(u,v);
    close(input);
  end;
procedure up1;
  begin
    inc(d[xx,yy]);
  end;
procedure try1(i : longint);
  var j: longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin xx:=xx+x[i]; yy:=yy+y[i]; end;
        if i=s1 then up1 else try1(i+1);
        if j=1 then begin xx:=xx-x[i]; yy:=yy-y[i] end;
      end;
  end;
procedure up2;
  var tg1,tg2 : longint;
  begin
    tg1 := u - xx;
    tg2 := v - yy;
    if (tg1<=oo) and(tg1>=-oo) then
    if (tg2<=oo) and (tg2>=-oo) then inc(res,d[tg1,tg2]);
  end;
procedure try2(i : longint);
  var j: longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin xx:=xx+x[i]; yy:=yy+y[i]; end;
        if i=n then up2 else try2(i+1);
        if j=1 then begin xx:=xx-x[i]; yy:=yy-y[i] end;
      end;
  end;
procedure process;
  begin
    s1 := n div 2; s2 := s1+1;
    xx := 0; yy:=0;
    try1(1);
    xx := 0; yy:=0;
    try2(s2);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

LUCKYNUM – spoj

Đề bài:

Thuật toán:

  • Duyệt BFS.
  • F[i,j] là phần dư của 88..866..6 (i số 8, j số 6) cho X.

Code:

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
const int MAXN = 203;
const int MAXQ = MAXN * MAXN;
int i, j, t, X, f[MAXN][MAXN];
queue< pair<int,int> > q;
 
int mu (int n) {
    int tmp = 1;
    for (int i = 1; i <= n; i++) tmp = (tmp * 10) % X;
    return tmp;
}
 
void print(int x, int y) {
    for (int i = 1; i <= x; i++) cout << 8;
    for (int i = 1; i <= y; i++) cout << 6;
    cout << endl;
}
 
void bfs() {
    while (!q.empty()) q.pop();
    q.push( make_pair(0,0) );
    pair<int,int> x;
    while (q.size()) {
        x = q.front();
        q.pop();
        if (x.fi+x.se >= MAXN) {cout << -1 << endl; return;}
        if (f[x.fi][x.se+1] == 0) q.push(mp(x.fi,x.se+1));
        if (f[x.fi+1][x.se] == 0) q.push(mp(x.fi+1,x.se));
        f[x.fi+1][x.se] = (f[x.fi][x.se] + mu(x.fi+x.se) * 8) % X;
        f[x.fi][x.se+1] = (f[x.fi][x.se] * 10 + 6) % X;
        if (f[x.fi][x.se+1] == 0) {print(x.fi,x.se+1); return;}
        if (f[x.fi+1][x.se] == 0) {print(x.fi+1,x.se); return;}
    }
}
 
void process() {
    cin >> X;
    memset(f,0,sizeof(f));
    bfs();
}
 
int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        process();
    }
    return 0;
}
const   fi='';
        fo='';
        maxn=201;
type    point=record
                x,y:integer;
                end;
var     q:array[1..maxn*maxn+1] of point;
        f:array[0..maxn,0..maxn] of longint;
        t,n:integer;
        d,c:longint;
procedure xuat(x,y:integer);
var     i:integer;
begin
    for i:=1 to x do write('8');
    for i:=1 to y do write('6');
    writeln;
end;
procedure push(x,y:integer);
begin
    inc(c);
    q[c].x:= x;
    q[c].y := y;
end;
function mu(a:integer):longint;
var     i:integer;
        tam:longint;
begin
    tam:=1;
    for i:=1 to a do tam:=(tam*10) mod n;
    exit(tam);
end;
procedure xuly;
var
        x,y:integer;
begin
 
    d:=1;c:=1;
    q[1].x:=0;q[1].y:=0;
 
    while d<=c do
        begin
            x:=q[d].x; y:=q[d].y;
            inc(d);
            if (x+y>0) and (f[x,y]=0) then begin xuat(x,y); exit; end;
 
            if (y+1+x<=200) and (f[x,y+1]=-1) then
                begin
                    f[x,y+1]:= (f[x,y]*10 +6) mod n ;
                    push(x,y+1);
                end;
 
            if (x+1+y<=200) and (f[x+1,y]=-1)  then
                begin
                    f[x+1,y]:=(8*mu(x+y) mod n + f[x,y] ) mod n ;
                    push(x+1,y);
                end;
 
            if x+y>200 then begin writeln(-1); exit; end;
        end;
        writeln(-1);
end;
procedure init;
var     i,j:integer;
begin
    for i:=0 to 200 do
        for j:=0 to 200 do f[i,j]:=-1;
 
        f[0,0]:=0;
end;
procedure main;
var     i:integer;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    readln(t);
    for i:=1 to t do
        begin
 
            readln(n);
            init;
            xuly;
 
        end;
 
    close(input);close(output);
end;
begin
    main;
end.