سلسة الإعداد لوظيفة مهندس برمجيات – الجزء٣ – خطة المذاكرة – للمستوى المتقدم

دي خطة تفصيلية للناس اللي عندها خبرة مسبقة بالبرمجة و محتاجة تأهل نفسها لمقابلات العمل في أي من الشركات الكبرى

  • هنحتاج نمشي على الخطة دي بالترتيب من الأول للآخر علشان هي حاجات مترتبة بصورة كبيرة على بعض
  • ممكن تطبعها و تعلم على المواضيع اللي خلصتها و بكده هتحس بالإنجاز و تبقى مدرك فاضلك ايه 
  • بالنسبة للناس المبتدأة أو اللي مش حاسة إن الخطة دي مناسبة ليها ممكن أحاول أجهز لهم خطة مناسبة ليهم لو لقيت فعلا في ناس محتاجاها

المقالات السابقة في السلسلة:


Algorithmic complexity / Big-O / Asymptotic analysis


Data Structures

  • Arrays

    • Implement an automatically resizing vector.
    • Description:
    • Implement a vector (mutable array with automatic resizing):
      • Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.
      • new raw data array with allocated memory
        • can allocate int array under the hood, just not use its features
        • start with 16, or if starting number is greater, use the power of 2 – 16, 32, 64, 128
      • size() – number of items
      • capacity() – number of items it can hold
      • is_empty()
      • at(index) – returns item at given index, blows up if index out of bounds
      • push(item)
      • insert(index, item) – inserts item at index, shifts that index’s value and trailing elements to the right
      • prepend(item) – can use insert above at index 0
      • pop() – remove from end, return value
      • delete(index) – delete item at index, shifting all trailing elements left
      • remove(item) – looks for value and removes index holding it (even if in multiple places)
      • find(item) – looks for value and returns first index with that value, -1 if not found
      • resize(new_capacity) // private function
        • when you reach capacity, resize to double the size
        • when popping an item, if size is 1/4 of capacity, resize to half
    • Time
      • O(1) to add/remove at end (amortised for allocations for more space), index, or update
      • O(n) to insert/remove elsewhere
    • Space
      • contiguous in memory, so proximity helps performance
      • space needed = (array capacity, which is >= n) * size of the item, but even if 2n, still O(n)

  • Linked Lists

    • Description:
    • C Code (video)– not the whole video, just portions about Node struct and memory allocation.
    • Linked List vs Arrays:
    • why you should avoid linked lists (video)
    • Gotcha: you need a pointer to pointer knowledge:(for when you pass a pointer to a function that may change the address where that pointer points)This page is just to get a grasp on ptr to ptr. I don’t recommend this list traversal style. Readability and maintainability suffer due to cleverness.
    • implement (I did with tail pointer & without):
      • size() – returns number of data elements in list
      • empty() – bool returns true if empty
      • value_at(index) – returns the value of the nth item (starting at 0 for first)
      • push_front(value) – adds an item to the front of the list
      • pop_front() – remove front item and return its value
      • push_back(value) – adds an item at the end
      • pop_back() – removes end item and returns its value
      • front() – get value of front item
      • back() – get value of end item
      • insert(index, value) – insert a value at index, so current item at that index is pointed to by new item at index
      • erase(index) – removes node at given index
      • value_n_from_end(n) – returns the value of the node at nth position from the end of the list
      • reverse() – reverses the list
      • remove_value(value) – removes the first item in the list with this value
    • Doubly-linked List


  • Queue

    • Using Queues First-In First-Out(video)
    • Queue (video)
    • Circular buffer/FIFO
    • Priority Queues (video)
    • Implement using linked-list, with a tail pointer:
      • enqueue(value) – adds value at position at tail
      • dequeue() – returns value and removes least recently added element (front)
      • empty()
    • Implement using a fixed-sized array:
      • enqueue(value) – adds item at end of available storage
      • dequeue() – returns value and removes least recently added element
      • empty()
      • full()
    • Cost:
      • a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n)because you’d need the next to last element, causing a full traversal each dequeue
      • enqueue: O(1) (amortized, linked list and array [probing])
      • dequeue: O(1) (linked list and array)
      • empty: O(1) (linked list and array)


More Knowledge



Trees

  • Trees – Notes & Background

    • Series: Core Trees (video)
    • Series: Trees (video)
    • basic tree construction
    • traversal
    • manipulation algorithms
    • BFS (breadth-first search)
      • MIT (video)
      • level order (BFS, using queue)time complexity: O(n)space complexity: best: O(1), worst: O(n/2)=O(n)
    • DFS (depth-first search)
      • MIT (video)
      • notes:time complexity: O(n)space complexity:best: O(log n) – Avg. height of a treeworst: O(n)
      • inorder (DFS: left, self, right)
      • postorder (DFS: left, right, self)
      • preorder (DFS: self, left, right)



Sorting

If you need more detail on this subject, see “Sorting” section in Additional Detail on Some Subjects


Graphs

Graphs can be used to represent many problems in computer science, so this section is long like trees and sorting were.

You’ll get more graph practice in Skiena’s book (see Books section below) and the interview books


Even More Knowledge










  • Scheduling

    • in an OS, how it works
    • can be gleaned from Operating System videos
  • Implement system routines

    • understand what lies beneath the programming APIs you use
    • can you implement them?


System Design, Scalability, Data Handling


Final Review

This section will have shorter videos that can you watch pretty quickly to review most of the important concepts.
It's nice if you want a refresher often.

Coding Question Practice

Now that you know all the computer science topics above, it’s time to practice answering coding problems.

Coding question practice is not about memorising answers to programming problems.

Why you need to practice doing programming problems:

  • problem recognition, and where the right data structures and algorithms fit in
  • gathering requirements for the problem
  • talking your way through the problem like you will in the interview
  • coding on a whiteboard or paper, not a computer
  • coming up with time and space complexity for your solutions
  • testing your solutions

There is a great intro for methodical, communicative problem-solving in an interview. You’ll get this from the programming

interview books, too, but I found this outstanding:

Algorithm design canvas

My Process for Coding Interview (Book) Exercises

Supplemental:

Read and Do Programming Problems (in this order):

See Book List above


Coding exercises/challenges

Once you’ve learned your brains out, put those brains to work.

Take coding challenges every day, as many as you can.

Challenge sites:

Maybe:


Once you’re closer to the interview


Your Resume


Be thinking of for when the interview comes

Think of about 20 interview questions you’ll get, along with the lines of the items below. Have 2-3 answers for each.

Have a story, not just data, about something you accomplished.

  • Why do you want this job?
  • What’s a tough problem you’ve solved?
  • Biggest challenges faced?
  • Best/worst designs seen?
  • Ideas for improving an existing Google product.
  • How do you work best, as an individual and as part of a team?
  • Which of your skills or experiences would be assets in the role and why?
  • What did you most enjoy at [job x / project y]?
  • What was the biggest challenge you faced at [job x / project y]?
  • What was the hardest bug you faced at [job x / project y]?
  • What did you learn at [job x / project y]?
  • What would you have done better at [job x / project y]?

Have questions for the interviewer

Some of mine (I already may know answer to but want their opinion or team perspective):
  • How large is your team?
  • What does your dev cycle look like? Do you do waterfall/sprints/agile?
  • Are rushes to deadlines common? Or is there flexibility?
  • How are decisions made in your team?
  • How many meetings do you have per week?
  • Do you feel your work environment helps you concentrate?
  • What are you working on?
  • What do you like about it?
  • What is the work life like?

Additional Books


Additional Learning







  • Unix command line tools

    • suggested by Yegge, from an old Amazon recruiting post. I filled in the list below from good tools.
    • bash
    • cat
    • grep
    • sed
    • awk
    • curl or wget
    • sort
    • tr
    • uniq
    • strace
    • tcpdump














  • Locality-Sensitive Hashing

    • used to determine the similarity of documents
    • the opposite of MD5 or SHA which are used to determine if 2 documents/strings are exactly the same.
    • Simhashing (hopefully) made simple




  • Balanced search trees

    • Know least one type of balanced binary tree (and know how it’s implemented):
    • “Among balanced search trees, AVL and 2/3 trees are now passé, and red-black trees seem to be more popular.A particularly interesting self-organizing data structure is the splay tree, which uses rotationsto move any accessed key to the root.” – Skiena
    • Of these, I chose to implement a splay tree. From what I’ve read, you won’t implement abalanced search tree in your interview. But I wanted exposure to coding one upand let’s face it, splay trees are the bee’s knees. I did read a lot of red-black tree code.
      • splay tree: insert, search, delete functionsIf you end up implementing red/black tree try just these:
      • search and insertion functions, skipping delete
    • I want to learn more about B-Tree since it’s used so widely with very large data sets.
    • Self-balancing binary search tree
    • AVL trees
      • In practice:From what I can tell, these aren’t used much in practice, but I could see where they would be:The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidlybalanced than red–black trees, leading to slower insertion and removal but faster retrieval. This makes itattractive for data structures that may be built once and loaded without reconstruction, such as languagedictionaries (or program dictionaries, such as the opcodes of an assembler or interpreter).
      • MIT AVL Trees / AVL Sort (video)
      • AVL Trees (video)
      • AVL Tree Implementation (video)
      • Split And Merge
    • Splay trees
      • In practice:Splay trees are typically used in the implementation of caches, memory allocators, routers, garbage collectors,data compression, ropes (replacement of string used for long text strings), in Windows NT (in the virtual memory,networking and file system code) etc.
      • CS 61B: Splay Trees (video)
      • MIT Lecture: Splay Trees:
        • Gets very mathy, but watch the last 10 minutes for sure.
        • Video
    • Red/black trees
      • these are a translation of a 2-3 tree (see below)
      • In practice:Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time.Not only does this make them valuable in time-sensitive applications such as real-time applications,but it makes them valuable building blocks in other data structures which provide worst-case guarantees;for example, many data structures used in computational geometry can be based on red–black trees, andthe Completely Fair Scheduler used in current Linux kernels uses red–black trees. In the version 8 of Java,the Collection HashMap has been modified such that instead of using a LinkedList to store identical elements with poorhashcodes, a Red-Black tree is used.
      • Aduni – Algorithms – Lecture 4 (link jumps to starting point) (video)
      • Aduni – Algorithms – Lecture 5 (video)
      • Black Tree
      • An Introduction To Binary Search And Red Black Tree
    • 2-3 search trees
    • 2-3-4 Trees (aka 2-4 trees)
      • In practice:For every 2-4 tree, there are corresponding red–black trees with data elements in the same order. The insertion and deletionoperations on 2-4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2-4 trees animportant tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce2-4 trees just before red–black trees, even though 2-4 trees are not often used in practice.
      • CS 61B Lecture 26: Balanced Search Trees (video)
      • Bottom Up 234-Trees (video)
      • Top Down 234-Trees (video)
    • N-ary (K-ary, M-ary) trees
      • note: the N or K is the branching factor (max branches)
      • binary trees are a 2-ary tree, with branching factor = 2
      • 2-3 trees are 3-ary
      • K-Ary Tree
    • B-Trees
      • fun fact: it’s a mystery, but the B could stand for Boeing, Balanced, or Bayer (co-inventor)
      • In Practice:B-Trees are widely used in databases. Most modern filesystems use B-trees (or Variants). In addition toits use in databases, the B-tree is also used in filesystems to allow quick random access to an arbitraryblock in a particular file. The basic problem is turning the file block i address into a disk block(or perhaps to a cylinder-head-sector) address.
      • B-Tree
      • Introduction to B-Trees (video)
      • B-Tree Definition and Insertion (video)
      • B-Tree Deletion (video)
      • MIT 6.851 – Memory Hierarchy Models (video)– covers cache-oblivious B-Trees, very interesting data structures- the first 37 minutes are very technical, may be skipped (B is block size, cache line size)











Additional Detail on Some Subjects

I added these to reinforce some ideas already presented above, but didn't want to include them
above because it's just too much. It's easy to overdo it on a subject.
You want to get hired in this century, right?

Video Series

Sit back and enjoy. “Netflix and skill” 😛


Computer Science Courses

أضف تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *