{"id":256764,"date":"2026-07-13T15:02:49","date_gmt":"2026-07-13T12:02:49","guid":{"rendered":"https:\/\/1kitap1.com\/en\/conquer-the-coding-interview-efficiently-in-python-cathy-qian\/"},"modified":"2026-07-13T15:02:49","modified_gmt":"2026-07-13T12:02:49","slug":"conquer-the-coding-interview-efficiently-in-python-cathy-qian","status":"publish","type":"post","link":"https:\/\/1kitap1.com\/en\/conquer-the-coding-interview-efficiently-in-python-cathy-qian\/","title":{"rendered":"Conquer The Coding Interview Efficiently In Python – Cathy Qian"},"content":{"rendered":"
\"<\/figure>\n

# solution 1: bfs from collections import defaultdict, deque class AlienOrder: def alienOrder(self, words: List[str]) -> str: # Step 0: create data structures + the in_degree of each unique letter to 0. adj_list = defaultdict(set) # set not list in_degree = {c : 0 for word in words for c in word} # required # Step 1: We need to populate adj_list and in_degree. # For each pair of adjacent words…<\/p>\n

for w1, w2 in zip(words, words[1:]): # use of zip # Check that the second word isn’t a prefix of the first word. if len(w2) < len(w1) and w2 == w1[:len(w2)]: return \"\" for c, d in zip(w1, w2): if c != d: if d not in adj_list[c]: # need to check to avoid duplicated input adj_list[c].add(d) in_degree[d] += 1 break # Step 2: We need to repeatedly pick off nodes with an indegree of 0. output = [] # note the following deque can be permuted to get all possible output permutations d = deque([c for c in in_degree if in_degree[c] == 0]) while d: c = d.popleft() output.append(c) for v in adj_list[c]: in_degree[v] -= 1 if in_degree[v] == 0: Copyright \u00a92023 Cathy Qian.<\/p>\n

All rights reserved. d.append(v) # If not all letters are in output, that means there was a cycle and so no valid ordering. Return “” as per the problem description. if len(output) < len(in_degree): return \"\" # Otherwise, convert the ordering we found into a string and return return \"\".join(output) # string operation # solution 2: dfs def alienOrder(self, words: List[str]) -> str: # Step 0: Put all unique letters into the adj list. self.adj_list = {c : [] for word in words for c in word} # Step 1: Find all edges and put them in adj_list.<\/p>\n

for w1, w2 in zip(words, words[1:]): # Check that the second word isn’t a prefix of the first word. if len(w2) < len(w1) and w2 == w1[:len(w2)]: return \"\" for c, d in zip(w1, w2): if c != d: self.adj_list[c].append(d) break # Step 2: Depth-first search. self.output = [] # note the following deque can be permuted to get all possible output permutations self.color = {c:0 for word in words for c in word} self.has_cycle = False for vertex in range(len(self.color)): if self.color[vertex] == 0: self.dfs(vertex) if self.has_cycle: break if self.has_cycle: return \"\" Copyright \u00a92023 Cathy Qian.<\/p>\n

All rights reserved.<\/p>\n

\n

Cathy Qian is currently a Senior Machine Learning Engineer at Pinterest, with expertise in developing large scale end-to-end machine learning solutions. She has previously worked at Twitter and Expedia, where she helped build and deploy machine learning applications in ads and search ranking systems. She has received a Ph.D. degree from the University of Pennsylvania and published 20+ research papers in high-impact peer-reviewed journals before transitioning to the high-tech industry. She enjoys writing and knowledge sharing in her spare time. Follow her on LinkedIn.<\/p>\n

Copyright \u00a92023 Cathy Qian. All rights reserved. 1 Table of Contents Introduction 4 Basic Python Syntaxes 5 List 5 Set 6 Heap 6 Dictionary 7 Collections 8 Deque 9 String 9 Bitwise Operator 11 Random Number Operation 11 Misc 11 Python Class 14 Time Complexity of Basic Python Data Structures 15 List 16 Deque 17 Dictionary 17 Set 18 Tuples 18 String 19 Core Data Structures 20 Linear Data Structures 20 Array and String 20 Common problems and solutions 20 Code examples 20 Linked List 23 Common problems & solutions 24 Code examples 24 Tree Data Structures 28 Binary Tree & Binary Search Tree 28 Common problems & Solutions 29 Heap 38 Implement a minHeap 38 Common problems & Solutions 41 Trie 43 Implement a Trie 44 Common problems and solutions 45 Graph 46 Implement a Graph 46 Common problems & Solutions 49 Core Algorithms 59 Divide and Conquer 59 Typical problems 59 Master Theorem 59 Related data structures 59 Sample Solutions 59 Binary Search 61 Typical problems 61 Related data structures 61 Sample Solutions 62 Breadth-First Search 68 Typical problems 68 Related data structures 68 Sample Solutions 68 Depth-First Search 74 Typical problems 74 Related data structures 74 Sample Solutions 75 Dynamic Programming 97 Typical problems 97 Related data structures 97 Sample Solutions 97 Union Find 104 Typical problems 104 Related data structure 104 Sample Solutions 104 Core Machine Learning Algorithms From Scratch 108 Linear Regression 108 Logistic Regression 109 K-means clustering 110 K-nearest neighbor 111 Decision tree 112 Reservoir sampling 115 Summary 116 Copyright \u00a92023 Cathy Qian.<\/p>\n

All rights reserved. 3 Introduction Coding interviews are an essential part of standard engineering interviews in the high-tech industry nowadays.<\/p>\n<\/blockquote>\n

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.<\/em><\/p>\n

\n
\n

Table of Contents<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n