interview codings

algorithm

给定一个二维数组 L[n][m], 设计一个算法, 使其可以从左上角开始, 按照顺时针顺序由外向内的输出二维数组的每个元素.

比如给定输入:

L = [[0, 1, 2, 3, 4, 5],
     [9, 0, 1, 2, 3, 6],
     [8, 1, 2, 3, 4, 7],
     [7, 0, 5, 4, 5, 8],
     [6, 9, 8, 7, 6, 9],
     [5, 4, 3, 2, 1, 0]]
     
输出:

```
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5
```

<div style="page-break-after: always"></div>

给定一个列表 L, 列表内元素均为 2 个数字元素的定长数组。
已知数字大小范围为 [0, 10000)， 请使用 python 内置的
sorted 函数对 L 进行排序: 要求按照二元数组的第一个值
进行生序排列, 值相同的情况下按照第二个元素进行降序排列;


比如输入:

```
L = [[3, 4],
 [9, 5],
 [2, 9],
 [0, 6],
 [4, 0],
 [5, 3],
 [1, 4],
 [8, 9],
 [10, 7],
 [2, 3],
 [5, 8],
 [1, 1],
 [9, 0],
 [3, 8],
 [4, 8],
 [2, 6],
 [0, 1],
 [5, 5],
 [5, 6],
 [10, 1]]
```

输出:

```
[[0, 6],
 [0, 1],
 [1, 4],
 [1, 1],
 [2, 9],
 [2, 6],
 [2, 3],
 [3, 8],
 [3, 4],
 [4, 8],
 [4, 0],
 [5, 8],
 [5, 6],
 [5, 5],
 [5, 3],
 [8, 9],
 [9, 5],
 [9, 0],
 [10, 7],
 [10, 1]]
```

bad_code_python.md

代码片段1:

import time


def timer(func):
    def wrapper(*args, **kwargs):
        timeout = kwargs.get('timer_timeout', 0)

        start = time.time()
        ret = func(*args, **kwargs)
        end = time.time()

        duration = end - start

        if duration > timeout > 0:
            tips = '(mark as timeout)'
        else:
            tips = ''

        print 'function %s totally use: %.3f %s' % (func.__name__, duration, tips)

        return ret

    return wrapper


@timer
def add(a, b):
    print "%d + %d = %d" % (a, b, a + b)
    

add(3, 4)
add(3, 4, timer_timeout=0.1)

代码片段2:

from threading import Thread
from multiprocessing import Process
from dbmodels import PrsPolicyConfigRiskSyslog

class BaseConsumer(Thread):
    
    def start(self):
        self._start()
        
    def _start(self):
        return NotImplemented


class ApiConsumer(BaseConsumer):

    def _start(self):
        # do some business here
        pass


class SyslogConsumer(BaseConsumer):

    def _start(self):
        # do some business here
        pass


def start_sub_process(send_type):
    send_map = {
        "api": ApiConsumer,
        "syslog": SyslogConsumer
    }
    for data in PrsPolicyConfigRiskSyslog.select().where(PrsPolicyConfigRiskSyslog.risk_type == send_type):
        t = Thread(target=send_map[send_type]().start, args=(data.to_dict(),))
        t.daemon = True
        t.start()


def start_api_consumer():
    p = Process(target=start_sub_process("api"), args=())
    p.start()
    p.join()


def start_syslog_consumer():
    p = Process(target=start_sub_process("syslog"), args=())
    p.start()
    p.join()


class SyslogWorker(object):

    def process(self):
        start_api_consumer()
        start_syslog_consumer()

go_channel_with_test.md

// sample.go
func doBadthing(done chan bool) {
	time.Sleep(time.Second)
	done <- true
}

func timeout(f func(chan bool)) string {
	done := make(chan bool)
	go f(done)
	select {
	case <-done:
		return "function call over and is ok"
	case <-time.After(time.Millisecond):
		return "function call timeout"
	}
}

// sample_test.go
func test(t *testing.T, f func(chan bool)) {
	t.Helper()
	retMap := make(map[string]int, 2)
	for i := 0; i < 1000; i++ {
		retMsg := timeout(f)
		if retV, ok := retMap[retMsg]; ok == true {
			retV++
		} else {
      retMap[retMsg] = 1
    }
	}
	time.Sleep(time.Second * 2)
	t.Log(fmt.Sprintf("测试结束后剩余 goroutine 数量为: %d", runtime.NumGoroutine()))
	for retK, retV := range retMap {
		t.Log(fmt.Sprintf("result msg: %s - count: %d", retK, retV))
	}
}

func TestBadTimeout(t *testing.T) {
	start := time.Now()
	test(t, doBadthing)
	end := time.Now()
	fmt.Printf("totally use: %s\n", end.Sub(start))
}

一般问题

• 1、上述测试用例执行结束总耗时大概需要多久？
• 2、上述测试用例执行完毕之后，剩余 gorouting 数量是多少？是哪些 gorouting？
• 3、上述测试用例执行完毕之后，retMap 里有哪些 key， value 分别是多少？
• 4、golang 测试用例规范是什么？ 测试用例函数有哪几种类型？参数分别是什么类型？用于什么场景？
• 5、将 doBadthing 中的 time.Second 更换为 time.Millisecond，问题 1、2、3 的答案会如何变化？

进阶问题（面试者应当在回答上述问题后再知晓如下问题）

• 1、如果结束的时候显示 gorouting 数量很多，如何调整代码使 gorouting 数量降到最低？
• 2、如果 retMap 没有正确统计到 timeout 函数返回的不同字符串的次数，该如何进行修改？
• 3、针对问题 2，有没有更简单的修改？（对方答案不是最简的情况下）

go_channel_with_test_and_bad_code.md

// sample.go
func doBadthing(done chan bool) {
	time.Sleep(time.Second)
	done <- true
}

func timeout(f func(chan bool)) {
	done := make(chan bool)
	go f(done)
	select {
	case <-done:
		return "function call over and is ok"
	case <-time.After(time.Millisecond):
		return "function call timeout"
	}
}

// sample_tester.go
func test(t *testing.T, f func(chan bool)) {
	t.Helper()
	retMap := make(map[string]int, 2)
	for i := 0; i < 1000; i++ {
		retMsg := timeout(f)
		if retV, ok := retMap[retMsg]; ok == true {
			retV++
		}
	}
	time.Sleep(time.Second * 2)
	t.Log(fmt.Sprintf("测试结束后剩余 goroutine 数量为: %d", runtime.NumGoroutine()))
	for retK, retV := range retMap {
		t.Log(fmt.Sprintf("result msg: %s - count: %d", retK, retV))
	}
}

func TestBadTimeout(t *testing.T) {
	start := time.Now()
	test(t, doBadthing)
	end := time.Now()
	fmt.Printf("totally use: %s\n", end.Sub(start))
}

一般问题

• 1、请指出上述代码片段中的错误或者缺陷，并说明为何以及如何修改。
• 2、上述测试用例执行结束总耗时大概需要多久？
• 3、上述测试用例执行完毕之后，剩余 gorouting 数量是多少？是哪些 gorouting？
• 4、上述测试用例执行完毕之后，retMap 里有哪些 key， value 分别是多少？
• 5、golang 测试用例规范是什么？ 测试用例函数有哪几种类型？参数分别是什么类型？用于什么场景？
• 6、将 doBadthing 中的 time.Second 更换为 time.Millisecond，问题 2、3、4 的答案会如何变化？

进阶问题（面试者应当在回答上述问题后再知晓如下问题）

• 1、如果结束的时候显示 gorouting 数量很多，如何调整代码使 gorouting 数量降到最低？
• 2、如果 retMap 没有正确统计到 timeout 函数返回的不同字符串的次数，该如何进行修改？

go_point_question_1.md

type Reader interface {
  ReadANumber() int
}

func ReadANumberOrZero(a Reader) int {
  if a == nil {
    return 0
  }

  return a.ReadANumber()
}

• 1、请找出上边程序的设计缺陷（提示：假定调用任一 Reader 实现的 ReadANumber 方法均不会 panic）

type Reader interface {
  ReadANumber() int
}

func ReadANumberOrZero(a Reader) int {
  if a == nil {
    return 0
  }

  return a.ReadANumber()
}

type ImplementA struct{}

func (i \*ImplementA) ReadANumber() int {
  return 1
}

func main() {
  fmt.Println(ReadANumberOrZero(nil))
  fmt.Println(ReadANumberOrZero(ImplementA{}))
  fmt.Println(ReadANumberOrZero((\*ImplementA)(nil)))
}

• 1、请说出上面的程序执行的输出

type Reader interface {
  ReadANumber() int
}

func ReadANumberOrZero(a Reader) int {
  if a == nil {
    return 0
  } 

  return a.ReadANumber()
}

type ImplementA struct{}

func (i ImplementA) ReadANumber() int {
  return 1
}

func main() {
  fmt.Println(ReadANumberOrZero(nil))
  fmt.Println(ReadANumberOrZero(ImplementA{}))
  fmt.Println(ReadANumberOrZero((*ImplementA)(nil)))
}

• 2、请说出上面的程序执行的输出（提示：与问题 1 的区别在于 ImplementA 的 ReadANumber 方法的接收者参数非指针）

type Reader interface {
  ReadANumber() int
}

func ReadANumberOrZero(a Reader) int {
  if a == nil {
    return 0
  }

  return a.ReadANumber()
}

type ImplementA struct{}

func (i *ImplementA) ReadANumber() int {
  return 1
}

type ImplementB struct {
  a int
}

func (i *ImplementB) ReadANumber() int {
  return i.a
}

func main() {
  fmt.Println(ReadANumberOrZero(nil))
  fmt.Println(ReadANumberOrZero(&ImplementA{}))
  fmt.Println(ReadANumberOrZero((*ImplementA)(nil)))
  fmt.Println(ReadANumberOrZero(&ImplementB{2}))
  fmt.Println(ReadANumberOrZero((*ImplementB)(nil)))
}

• 1、请说出上面的程序执行的输出