DeV_V Blog

backend | crypto | pipeline

0%

Posted on In ,

Problem

Given a slice a. There are 2 sub slices. One’s length is k, the other’s is p.
These 2 sub slices are not overlaid. Find the max sum of the 2 sub slices.

Return -1 if can’t find one.

Example 1:

1
2
Input: [1,3,4,7,5,8,2,9], 3, 2
Output: 35

Example 2:

1
2
Input: [1,3,4,7,5,8], 100, 2
Output: -1

Thought

Move slice K through A, at the left and right side of K place the slice P.
To improve the efficiency, store sums of K and P in hash tables.


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
func maxSum(a []int, k, p int) int {
	if k+p > len(a) {
		return -1
	}
	kt := hashTable(a, k)
	pt := hashTable(a, p)
	ki := 0
	for ki < len(kt) {
		left := maxVal(pt[:max(0, ki-p+1)]...)
		right := maxVal(pt[min(ki+k, len(pt)):]...)

		if left == -1 && right == -1 {
			kt[ki] = -1
		} else {
			kt[ki] = kt[ki] + max(right, left)
		}
		ki++
	}

	return maxVal(kt...)
}

func hashTable(a []int, length int) []int {
  if length > len(a) {
		return []int{}
	}
	tlen := len(a) - length + 1
	t := make([]int, tlen)
	i := 0
	for i < tlen {
		t[i] = sum(a[i : i+length]...)
		i++
	}
	return t
}

func maxVal(nums ...int) int {
	m := -1
	for _, v := range nums {
		if m < v {
			m = v
		}
	}
	return m
}

func sum(nums ...int) int {
	res := 0
	for _, n := range nums {
		res += n
	}
	return res
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

Posted on In ,

Problem

Given a string s, return a cropped which max length is n.
Also, spaces at prefix and postfix need to be removed.

Example 1:

1
2
Input: "Hello World", 8
Output: "Hello"

Example 2:

1
2
Input: "   Hello World   ", 100
Output: "Hello World"

Example 3:

1
2
Input: "Hello World", 3
Output: ""

Thought

Find the start point l and end point r then return result s[l:r]
Left point is easy to find. If s[l] is space, pointer l move right.
On the other hand, r starts from l + N, if s[r] is NOT space, pointer r move left.

The tricky point is that if the given string’s length equals to given n,
and the string ends with character, the last word would be cropped.

Example:

1
2
3
Input: "Learn Golang", 12
Output: "Learn"
Expected: "Learn Golang"

An easy solution is to append a SPACE to the given string at the beginning.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func crop(s string, n int) string {
	s = s + " " // append an extra space

    // keep moving right until reaching the first character
	l := 0
	for l < len(s)-1 {
		if s[l] == ' ' {
			l++
		} else {
			break
		}
	}

    // start from `l+n` or the last char (extra space)
    // keep moving left until reaching the first space
	r := min(l+n, len(s)-1)
	for r > l {
		if s[r] == ' ' {
			break
		} else {
			r--
		}
	}
	return s[l:r]
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

Posted on

Tutorial

Follow this tutorial

New C++ Project in Xcode

Select command line tool

Edit Header Search Paths & Library Search Paths

I could not find where to edit Header Search Paths and Library Search Paths until I found this Toutube tutorial.

Set additional preferences like below

build shorcut in xCode: command + b

Resource

Posted on In ,

There is no output window in Mac’s Maya so I can’t print out text by std::out. The only way I know is to use Global::displayInfo. However, Global::displayInfo only accepts MString. I haven’t digged into what MString is yet but just provide some examples here. Hope you can get the basic idea:)

1
2
3
4
5
6
7
8
Global::displayInfo("hello"); // Works

string str = "hello";
Global::displayInfo(str); // This will fail

char str[10];
sprintf(str, "hello"); // Writes content to `str`
Global::displayInfo(str); // Works

In this way, we can also print out numeric types!

1
2
3
4
5
flaot value = 100.0f;
char str[10];

sprintf(str, "value:%f", value);
Global::displayInfo(str);

Posted on In ,

Concept

  • MObjects
    • class to handle all kinds of data in Maya
    • a handle object pointing to actual data
    • typeless
  • Function Sets
    • work with mobject
  • Wrappers
    • allocated and deallocated by you
  • Proxies
    • used to create custom maya objects (i.e. MPxNode, MPxDeformerNode)

Resources

Posted on Edited on In ,

Write a custom Maya command that print “Hello world!” in Maya console.
There are Python API 1.0 and 2.0. The syntax would be different.
We will integrate with API 2.0 in this example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys
import maya.api.OpenMaya as api

# Must include to use Maya API 2.0
def maya_useNewAPI():
    pass

class HelloWorldCmd(api.MPxCommand):
    kCmdName = 'helloWorld'

    def __init__(self):
        api.MPxCommand.__init__(self)

    @staticmethod
    def creator():
        return HelloWorldCmd()

    def doIt(self, arg_list):
        print('Hello world!')

# initialize and uninitialize functions are
# needed to be loaded by Maya Plug-in Manager 
def initializePlugin(mobject):
    fn_plugin = api.MFnPlugin(mobject)
    try:
        fn_plugin.registerCommand(
            HelloWorldCmd.kCmdName,
            HelloWorldCmd.creator
        )
    except:
        sys.stderr.write("Fail to register plugin: " + HelloWorldCmd.kCmdName)

def uninitializePlugin(mobject):
    fn_plugin = api.MFnPlugin(mobject)
    try:
        fn_plugin.deregisterCommand(
            HelloWorldCmd.kCmdName
        )
    except:
        sys.stderr.write("Fail to deregister plugin: " + HelloWorldCmd.kCmdName)

Open Maya Plug-in Manager, and hit “Browse” to load our command.

Then we can run our command

1
helloworld;

We can also call it in Python:

1
2
from maya import cmds
cmds.helloWorld

Posted on Edited on In ,

Doc:
https://developers.google.com/protocol-buffers/docs/gotutorial

Proto Buffer

Download Proto Buffer:
https://developers.google.com/protocol-buffers/docs/downloads

Check if protoc installed

1
$ protoc --version

Install protoc-gen-go

1
$ go install google.golang.org/protobuf/cmd/protoc-gen-go@latest

Add these text to ~/.bashrc or ~/.zshrc (depends on what shell you use)

1
2
export GOPATH=$HOME/go
export PATH=$PATH:$GOPATH/bin

This step is important to avoid Error "protoc-gen-go: program not found or is not executable"

.proto File

.proto example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
syntax = "proto3";

package proto;

option go_package ="../proto"; // avoid "unable to determine go import path"

message Request {
    int64 a = 1;
    int64 b = 2;
}

message Response {
    int64 result = 1;
}

service AddService {
    rpc Add(Request) returns (Response);
    rpc Multiply(Request) returns (Response);
}

Scaffolding:

1
2
3
4
project/
└── proto/
   └── package.proto

Compile

1
2
$ cd proto
$ protoc --go_out=plugins=grpc:. service.proto

plugins=grpc is needed or the output file will lack some functions

Install grpc

1
$ go get -u google.golang.org/grpc

Reference

Posted on In ,

Study how to use Borsh Serialize. When we write vanila Solana program, we need to serialize and deserialize accounts’ data by ourselves.

1
2
3
4
5
// Cargo.toml
// ...
[dependencies]
borsh = "0.9.3"
borsh-derive = "0.9.1"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// main.rs
use borsh::{BorshDeserialize, BorshSerialize};

#[derive(BorshSerialize, BorshDeserialize, Debug)]
struct Node {
    num: i32,
    str: String
}

fn main() {
    let uint:i32 = 256; // 2^8 -> 1 byte
    let node = Node{
        num: uint.pow(0) + uint.pow(1)*2 + uint.pow(2)*3 + uint.pow(3)*4, // [1, 2, 3, 4]
        str: String::from("好") // first 4 bytes represents how many bytes of this string
    };

    if let Ok(buf) = node.try_to_vec() {
        println!("serialized: {:?}", buf);

        if let Ok(deserz_node) = Node::try_from_slice(&buf) {
            println!("deserialized: {:?}", deserz_node);
        }
    }
}

Run the code:

1
2
3
$ cargo run
serialized: [1, 2, 3, 4, 3, 0, 0, 0, 229, 165, 189]
deserialized: Node { num: 67305985, str: "好" }

Posted on In , 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// rest.js
const row = {
    name: "Amy",
    age: 32,
    email: "amy@gamil.com",
    job: "cook"
};

const { job: a, none: b, ...rest_props } = row;

console.log(a); // maps to property "job"
console.log("---")
console.log(b); // property "none" doesn't exist so b is undefined
console.log("---")
console.log(rest_props); // row but without "job" property

run the code:

1
2
3
4
5
6
$ node rest.js                                                                                           
cook
---
undefined
---
{ name: 'Amy', age: 32, email: 'amy@gamil.com' }

More

Posted on In ,

Problem

Problem: Implement strStr()

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. If needle is empty, return 0.

Thoughts

strategies:

  • two pointers to compare each characters of needle and haystack (2 while loops)
  • iterate through haystack to get slices to compare with needle
  • iterate through haystack to get slices. Hash each slice and compare the hashed with the hashed needle
  • use find method

Code

Two While Loops

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let hay_vec: Vec<char> = haystack.chars().collect();
        let needle_vec: Vec<char> = needle.chars().collect();

        let mut i_hay: usize = 0;
        let mut i_needle: usize = 0;
        while i_hay < hay_vec.len() {
            while i_needle < needle_vec.len() {

                let offset_hay = i_hay + i_needle;
                if offset_hay >= hay_vec.len() {
                    break;
                }

                if hay_vec[offset_hay] != needle_vec[i_needle] {
                    i_needle = 0;
                    break;
                } else if hay_vec[offset_hay] == needle_vec[i_needle] && i_needle == needle_vec.len() - 1 {
                    return i_hay as i32;
                }

                i_needle += 1;
            }

            i_hay += 1;
        }

        return -1;
    }
}

Compare String Slice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let (hay_len, needle_len) = (haystack.len(), needle.len());

        if needle_len == 0 { return 0 }
        else if needle_len > hay_len { return -1 } // avoid hay: "aa", needle: "aaaa"

        for i in 0..=hay_len - needle_len {
            if haystack[i..i + needle_len] == needle {
                return i as i32;
            }
        }

        -1
    }
}

Use Manual Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const MAGIC_NUM: u64 = 31; // can be any number but should not too big

pub fn str_str(haystack: String, needle: String) -> i32 {
    let (hay_len, needle_len) = (haystack.len(), needle.len());

    if needle_len == 0 { return 0 }
    else if needle_len > hay_len { return -1 } // avoid hay: "aa", needle: "aaaa"

    let hash_needle = hash(&needle);
    let mut hash_hay:u64 = 0;
    let highest_pow = MAGIC_NUM.pow(needle_len as u32 - 1);

    for i in 0..=hay_len - needle_len {
        if hash_hay == 0 { 
            hash_hay = hash(&haystack[i..i + needle_len]); 
        } else {
            /* rolling hash */ 
            // abc -> _bc
            let first_c = haystack.chars().nth(i-1).unwrap();
            hash_hay -= first_c as u64 * highest_pow;
            // _bc -> bc_
            hash_hay *= MAGIC_NUM;
            // bc_ -> bcd
            hash_hay += haystack.chars().nth(i + needle_len - 1).unwrap() as u64;
        }

        if hash_hay == hash_needle {
            return i as i32;
        }
    }

    -1
}

fn hash(str: &str) -> u64 {
    let mut buf:u64 = 0;

    for c in str.chars() {
        buf *= MAGIC_NUM;
        buf += c as u64;
    }

    buf
}

Use Find

1
2
3
4
5
6
7
8
9
10
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        if needle.is_empty() { return 0 }

        match &haystack.find(&needle) {
            Some(i) => *i as i32,
            None => -1
        }
    }
}

If An Unicode String Given

1
2
let str = String::from("好");
println!("{}", str.len()); // This will print out 3

Since the len() returns the length of bytes not characters, we need to change our code if unicode strings given.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        // Get length of chars instead of bytes
        let (hay_len, needle_len) = (
            haystack.chars().count(),
            needle.chars().count()
        );

        // Collect string into `Vec<char>`
        let (hay_chars, needle_chars) = (
            haystack.chars().collect::<Vec<char>>(),
            needle.chars().collect::<Vec<char>>()
        );

        // The rest are same
        if needle_len == 0 { return 0 }
        else if needle_len > hay_len { return -1 }

        for i in 0..=hay_len - needle_len {
            if hay_chars[i..i + needle_len] == needle_chars {
                return i as i32;
            }
        }

        -1
    }
}

Conculsion

  • utilize string slice or find looks easier.
  • in some situations, hash may be useful. However, for this case, it may not be the best practise.