xxks-kkk / shuati

Interview questions central repo

shuati

This is the respository that I put my systematic algorithm learning into practice by solving various interview questions. This is also the place where I practice different programming languages.

Steps to developing a usable algorithm.

• Model the problem.
• Find an algorithm to solve it.
• Fast enough? Fits in memory?
• If not, figure out why not.
• Find a way to address the problem.
• Iterate until satisfied

Usage

The repo contains a mixture of different programming languages. To build and test solutions written in specific language, follow steps below:

C, C++

To build all C, C++ solutions, run

$ mkdir -p build && cd build && cmake .. && make -j4

Java

To build Java solutions, find Makefile inside the directory that program resides, and run make

Rust

To test all Rust solutions, run

$ cd rust
$ cargo test

Go

To test all Go solutions, run

$ cd shuati
$ go test ./...

shuati's Issues

hackerrank scraper

hackerrank has login page before we can access the actual content of the html. So, we need to use alternative approach different from leetcode scraper.

Reference follows:

• hackerrank crawler
• scrapy tutorial
• How to scrape a website that requires login with Python - bitbucket example
• logging in With Requests
• scraping with login python - google search
• How to scrape a website that requires login first with Python

scraper.py stop working

the content with <div id="question-detail-app"></div> seems to be dynamically loaded by javascript and beautifulsoup cannot get the content anymore.

Migrate to github actions

For C++, go, rust, and Java

Sunset testall.py

In PR #181, we enable CTest in CMake. This allows us to add test case directly in CMakeList.txt. This way is better than testall.py method as we now need to run make test to kick off all the tests.

Implement EPI-style next gen test infrastructure

Study EPI judge test infrastructure and use it as the prototype for the next-gen test framework.

Reorg repos

• Move goinclude, cppinclude, cinclude from leetcode directory under a separate directory include, which is at the same level as leetcode directory
• Breakdown CMakelists.txt into different sub CMakelists and write a test script that to be run by travis

Add CI for epi code

CI driver of EPI: https://github.com/adnanaziz/EPIJudge/blob/master/.github/workflows/test_cpp_cmake.yml

The issue is how to properly integrate into existing infrastructure.

Automatically add dependency during the build

Consider how we build LC138 binary in C++

add_executable(138
  leetcode/138-CopyListWithRandomPointer/copyListWithRandomPointer.cc
  include/cppinclude/linkedList_rand.cc
  include/cppinclude/cpputility.h
  include/jsoncpp/jsoncpp.cpp)

Is there a way to include jsoncpp.cpp automatically whenever we include the .cc that has dependency on it (e.g., linkedList_rand.cc has dependency on jsoncpp.cpp. Can we include jsoncpp.cpp whenever we use linkedList_rand.cc automatically?)

Implement test infrastructure for stack problem

See PR #189

Build Misc binary not in numbers

PR #178 offers a way to build all the binary under hackerrank/ without enforcing the binary name be the numeric. We want to do the same for misc/

EPI code integration

EPI has better C++ code implementation and definition than Leetcode's. Using leetcode has negative impact on C++ practice. Try to integrate EPI code along with test infrastructure in the repo and point to the EPI implementation whenever we can find the same leetcode problem in EPI.

See PR #168 Todo section on one example.

Enable Java compilation with CMake

We want to compile Java just like we do with C++ and C. Instead of using Maven or sbt, which have strict requirements on the directory structure, we want to keep everything simple and maintain the current problem-based structure.

Some good reference:

• https://cmake.org/cmake/help/v3.4/module/FindJava.html
• https://stackoverflow.com/questions/18985726/cmake-to-compile-java-code
• https://github.com/ptitpoulpe/cmake-swig-java-example/blob/master/CMakeLists.txt
• https://cmake.org/cmake/help/v3.10/module/UseJava.html
• https://github.com/remram44/java-cpp-example/blob/master/java-jni/CMakeLists.txt
• https://cmake.org/pipermail/cmake/2015-December/062173.html

Add test infrastructure for python code

Add test infrastructure code for python to allow push-button test on all python programs

Add performance test infrastructure

Add performance test infrastructure to test the code runtime finish within the given time budget. For example, in LC5, we have the following input as s:

"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"

And, we get TLE on such input for certain solution, according to run test case, the time budget is smaller than 240ms, and we need to enforce this when perform performance test.

Add Doc written in LaTex about pseudo algorithm for each problem

Write LaTex doc with pseudo algorithm for each problem and list out the optimization point with the performance gain.

It should include:

• Problem description
• Link to the problem description
• Pseudo algorithm
• Link to the actual implementation
• Optimization technique and performance gain from each technique

leetcode-94-Binary Tree Inorder Traversal (Morris traversal)

Understand and implement second solution using morris traversal, which doesn't use stack.

https://leetcode.com/problems/binary-tree-inorder-traversal/#/description

See the solution: https://discuss.leetcode.com/topic/24683/o-n-solution-with-o-1-space-using-morris-traversal

Move all src directories under src/

New test infrastructure for Linked List/ Graph problems in Leetcode

Leetcode now adopts a new way to represent linked list and graph input. For example, in LC138, the input looks like:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Now, we need to have infrastructure support for creating linked list and graph based on the new input format.

This issue is critical as now linked list and graph problem cannot be properly tested locally.

ClimbTheHill DP Solution

Automatically generate C++ template boilerplate

Should automatically generate C++ template boilerplate to remove the overhead of writing specific solution. For example, we should generate main function, necessary macros and test structs, etc.