作者: paul

[C# UnitTest]Mock IHttpClientFactory中生成HttpClient的方法

[C# UnitTest]Mock IHttpClientFactory中生成HttpClient的方法

在撰寫服務時,若有跟外部的資源或Api整合,需要用到HttpClient作互動時
我們通常會使用加入IHttpClientFactory來由底層生成HttpClient,以避免過度使用HttpClient

IHttpClientFactory是可以透過Mock的機制去Setup CreateHttpClient
不過我們HttpClient真的要模擬的是PostAsync的行為,但是卻沒有IHttpClient可以作Mock

網路上查到有另外做一個IHttpClientWrapper,隔離掉HttpClient的實作的方式,但事倍功半

以下 的方法,是最快可以直接Mock掉HttpClient的作法。主要就是透過 Mock

HttpMessageHanlder的方式,詳細寫法範例如下 !

var handlerMock = new Mock<HttpMessageHandler>(MockBehavior.Strict);
            handlerMock
                .Protected()
                .Setup<Task<HttpResponseMessage>>(
                    "SendAsync",
                    ItExpr.IsAny<HttpRequestMessage>(),
                    ItExpr.IsAny<CancellationToken>()
                )
                .ReturnsAsync(new HttpResponseMessage(HttpStatusCode.OK)
                {
                    Content = new StringContent(JsonConvert.SerializeObject(new MigrateService.PPAMigrateResponse()
                    {
                        Status = "success",
                        Message = "",
                        Data = new MigrateService.PPAMigrateMemberInfoResponse()
                        {
                            member_id =memberId 
                        }
                    }))
                })
                .Verifiable();
            
            var mockHttpClient = new HttpClient(handlerMock.Object);

            SetupMock<IHttpClientFactory>(a =>
                a.Setup(b => b.CreateClient(It.IsAny<string>())).Returns(mockHttpClient));
[動手做]安裝 GUI Dockers管理器 – Portainer

[動手做]安裝 GUI Dockers管理器 – Portainer

既上一篇

租了3台機器,但是各自沒有使用Docker,接下來會逐漸的將所有核心都開始Docker化

Docker雖然方便,但是經過了不同機器的隔離,要去操作,仍需要ssh的話,也很麻煩

因為GUI Portainer的工具的出現,徹底的簡化了這一層

在此記錄一下相關的配置操作

首先Docker Portainer的安裝 我們安裝在Jenkins的主機上

Jenkins其實本身也可以用Docker安裝,暫時先不討論

Jenkins這台VM我們裝上去Docker

Docker CE的指令就看官網的就好了
https://docs.docker.com/engine/install/ubuntu/

接著建立Portainer的相關容器(只要幾個指令也太無腦了)

docker volume create portainer_data
docker run -d -p 8000:8000 -p 9443:9443 --name portainer --restart=always -v /var/run/docker.sock:/var/run/docker.sock -v portainer_data:/data portainer/portainer-ce:latest

接著是被管理的Docker VM上可以設定Docker Api

sudo nano /lib/systemd/system/docker.service
ExecStart=/usr/bin/dockerd -H fd:// --containerd=/run/containerd/containerd.sock -H=tcp://0.0.0.0:4243

systemctl daemon-reload 
sudo service docker restart
注意,重新啟動docker後,有可能會造成container不見,這邊可以再去用 jenkins重建服務

接著要去portainer設定相關環境了,portainer在初次 連結的時候可能會需要你重啟container(註)
設定了超過12碼的帳密後,就可以登入了。

接著我們將 要被遙控的docker server,透過 gui加入環境中(如下面擷圖)

重新看,可以從portainer看到

Reference

https://ithelp.ithome.com.tw/articles/10265048

https://docs.portainer.io/start/install-ce/server/docker/linux

https://docs.portainer.io/start/install-ce/server/docker/linux

https://hackmd.io/@JYU/B1w9NDGnD

[動手做] 將C# Api佈署上 AWS+Github+Jenkins + Docker 的CICD實踐-Jenkins篇

[動手做] 將C# Api佈署上 AWS+Github+Jenkins + Docker 的CICD實踐-Jenkins篇

寫了微軟程式這麼久,雖然都是寫功能比較多,對於DevOps界久聞Jenkins大名,但從未真的使用過Jenkins做過一段完整的CICD流程。出於好奇心,找了一部網路影片,結合C# dotnet core的主題,希望實際 手把手try出如何在aws上做完一個low level的佈署過程 。總不好說自己會用 Azure Pipelin就是有做過 CICD ,終究Azure Pipeline也封裝 簡化了很多東西,做起來已經相對簡單一點了,不過缺點也是彈性不夠大加上指令或任務也不夠透明化。這一版本sonarQube先ignore(主要是 做的時候發現無法啟動,待之後再來補強這段)

這一次的專案範例如下 ,不接 db不接 外部服務,純程式的模擬

github url: https://github.com/pin0513/CICDExample

Program.cs的內容是一個模擬未來五天的天氣預測的Api

using System;
using System.Linq;
using Microsoft.AspNetCore.Builder;
using Microsoft.Extensions.DependencyInjection;
using Microsoft.Extensions.Hosting;
using Microsoft.FeatureManagement;

var builder = WebApplication.CreateBuilder(args);

builder.Services.AddEndpointsApiExplorer();
builder.Services.AddSwaggerGen();
builder.Services.AddFeatureManagement();

var app = builder.Build();

if (app.Environment.IsDevelopment())
{
app.UseSwagger();
app.UseSwaggerUI();
}

app.UseHttpsRedirection();

var summaries = new[]
{
“Freezing”, “Bracing”, “Chilly”, “Cool”, “Mild”, “Warm”, “Balmy”, “Hot”, “Sweltering”
};

app.MapGet(“/weatherforecast”, () =>
{
var forecast = Enumerable.Range(1, 5).Select(index => new WeatherForecast()
{
DateTime = DateOnly.FromDateTime((DateTime.Now).AddDays(index)),
Temperature = Random.Shared.Next(-20, 55),
Status = summaries[Random.Shared.Next(summaries.Length)]
}).ToArray();
return forecast;
}).WithName(“GetWetherForecast”)
.WithOpenApi();
app.Run();

public class WeatherForecast
{
public DateOnly DateTime { get; set; }
public int Temperature { get; set; }
public string Status { get; set; }
}

實際跑起來如下 :

接著我們把他Commit與Push到Github

AWS端,我們先創建EC2的VM作為 Jenkins Server

選擇免費方案就好了XD

分別建立3個Instance後如下

我們透過 SSH連線過去,會先發現

paul@IpdeMacBook-Pro aws-cert % ssh -i SSH-KEY-Jenkins.pem ubuntu@18.206.225.245 

Permissions 0644 for 'SSH-KEY-Jenkins.pem' are too open.
It is required that your private key files are NOT accessible by others.
This private key will be ignored.
Load key "SSH-KEY-Jenkins.pem": bad permissions
ubuntu@18.206.225.245: Permission denied (publickey).

爆了以上的錯誤,代表你的權限開太大了,執行前必須先將你的金鑰改成無法公開檢視

重新輸入paul@IpdeMacBook-Pro aws-cert % sudo chmod 440 SSH-KEY-Jenkins.pem 以後,就可以ssh過去了

在Jenkins的Vm上依序執行以下指令

sudo apt update
sudo apt install openjdk-11-jre

https://www.jenkins.io/doc/book/installing/linux/

curl -fsSL https://pkg.jenkins.io/debian/jenkins.io-2023.key | sudo tee \
  /usr/share/keyrings/jenkins-keyring.asc > /dev/null
echo deb [signed-by=/usr/share/keyrings/jenkins-keyring.asc] \
  https://pkg.jenkins.io/debian binary/ | sudo tee \
  /etc/apt/sources.list.d/jenkins.list > /dev/null
sudo apt-get update
sudo apt-get install jenkins

安裝後,接著到EC2端設定 安全性

接著啟動jenkinks

systemctl status jenkins

跑起來後,會如下圖,會有token到時拿來登入用的,此擷圖不是我的主機,僅示意,安全性至上!

新的作業 -> enter automated-pipeline-aws

接著到Github專案去設定 Webhook

http://18.206.225.245:8080/github-webhook/ (這邊注意要加/)

接著到jenkins測試一下,點擊馬上建置

看一下工作目錄,就有包含最早我們commit的方案資訊

接著到github測試一下webhook

Reference: https://www.youtube.com/watch?v=361bfIvXMBI

建置觸發成功!實際看jenkins的工作目錄也有新的檔案了!

SonarQube Vm透過SSH一樣 的方式登入後,去SonarQube官網下載Community版本

ubuntu@ip-172-31-89-20:~$ wget ttps://binaries.sonarsource.com/Distribution/sonarqube/sonarqube-10.1.0.73491.zip

sudo apt install unzip
unzip sonarqube-10.1.0.73491.zip
/home/ubuntu/sonarqube-10.1.0.73491/bin/linux-x86-64
ubuntu@ip-172-31-89-20:~/sonarqube-10.1.0.73491/bin/linux-x86-64$ ./sonar.sh console

上面指令跑不成功可能是java環境沒裝,所以抄上面jenkins的安裝java指令執行一次

實測Java要裝到18版

sudo apt install openjdk-19-jdk-headless

實際跑起來目前

2023.08.06 05:12:07 INFO  app[][o.s.a.SchedulerImpl] Waiting for Elasticsearch to be up and running的問題 (會暫時卡住)

我們先跳過去做佈署到Docker-Server

paul@IpdeMacBook-Pro aws-cert % ssh -i SSH-KEY-Jenkins.pem ubuntu@3.86.234.190

ubuntu@ip-172-31-82-131:~$ sudo hostnamectl set-hostname docker
ubuntu@ip-172-31-82-131:~$ /bin/bash
ubuntu@docker:~$ sudo apt update
sudo apt-get install ca-certificates curl gnupg
sudo install -m 0755 -d /etc/apt/keyrings $ curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo gpg –dearmor -o /etc/apt/keyrings/docker.gpg $ sudo chmod a+r /etc/apt/keyrings/docker.gpg

執行
echo \
  "deb [arch="$(dpkg --print-architecture)" signed-by=/etc/apt/keyrings/docker.gpg] https://download.docker.com/linux/ubuntu \
  "$(. /etc/os-release && echo "$VERSION_CODENAME")" stable" | \
  sudo tee /etc/apt/sources.list.d/docker.list > /dev/null

回到jenkins切換 hostname

sudo hostnamectl set-hostname jenkins

ubuntu@jenkins:~$ sudo su jenkins
ubuntu@jenkins:~$ ssh ubuntu@3.86.234.190 (連到Docker Server)

此時會出現
ubuntu@3.86.234.190: Permission denied (publickey).

這時先回到docker的那台 vm,用 sudo su進去root

再編輯nano /etc/ssh/sshd_config 檔案 (注意: 是sshd_config)

把以下幾個設定啟用 ,反註解後存檔

PubkeyAuthentication yes
PasswordAuthentication yes 

重啟sshd : systemctl restart sshd (要在root權限下: sudo su)

同時在 root 權限下 passwd ubuntu這個帳號設定密碼

測試jenkins可否連到docker~

ssh ubuntu@3.86.234.190

若可以連線並驗證密碼通過就會像上圖

回到jenkins的vm透過sudo su jenkins切到jenkins的user透過ssh-keygen產生一個key

接著ssh-copy-id ubuntu@3.86.234.190

經過了上述的行為,我們透過了jenkins這個user去生成了一個ssh的key加到了docker的server

也就是我可以直接在jenkin vm這台透過 jenkins這個user執行ssh不用密碼就可以跟docker互動

接著我們試著透過 jenkins的管理去設定佈署的docker server

管理 Jenkins => 安裝 ssh2easy的plugin(因為影片中用的就是這個)

設定ServerGroupsCenter

組態中我們可以先試著用 remote shell做一個指令看看

馬上儲存來建置看看,實測如下,有確實執行指令

實際上也有帶上來!!

jenkins建置 C#的準備

sudo apt-get install -y dotnet-sdk-7.0
sudo apt-get install -y aspnetcore-runtime-7.0
sudo apt install nuget
sudo apt install zip

我們預計從Jenkins發佈程式後,上傳 zip到docker-server去處理
建立Build Steps

執行 Shell
dotnet publish ${WORKSPACE}\\WeatherWebApplication\\WeatherWebApplication.sln -c Release -o out -r linux-x64 --self-contained

執行 Shell

cd out && zip -qr output.zip .

Remote Shell
touch ${WORKSPACE}\\WeatherWebApplication\\out\\output.zip

最後我們設定一個
建置後動作 Delete workspace when build is done(這個是一個plugin)

上面的建置過程中我曾經發現他會一直出現以下錯誤 
error NETSDK1005: Assets file '/var/lib/jenkins/workspace/automated-pipeline-aws/WeatherWebApplication/WeatherWebApplication/obj/project.assets.json' doesn't have a target for 'net7.0'

後來發現,我雖然裝的是net7的SDK,但是在obj的project.assets.json中有綁到target: net8.0的配置,而且 obj目錄不小心commit了,所以我後續使用上面的delete workspace when is failure做清除後
再重新建置一次,這時改成is Success再清就好了,因為若是失敗的話,就還可以檢查問題
所以jenkins在工作目錄的操作預設是只會做覆蓋。所以錯誤的配置調整後,可能還是會錯誤這點在釐清問題的時候還是要看一下。

####################################
execute command exit status -->0
##########################################################################
[automated-pipeline-aws] $ /bin/sh -xe /tmp/jenkins16435309995668868877.sh
+ cd out
+ date +%F
+ mv output.zip output-2023-08-08.zip
+ date +%F
+ scp /var/lib/jenkins/workspace/automated-pipeline-aws/out/output-2023-08-08.zip ubuntu@3.86.234.190:~/upload
[WS-CLEANUP] Deleting project workspace...
[WS-CLEANUP] Deferred wipeout is used...
[WS-CLEANUP] done
Finished: SUCCESS

終於建置到移轉到docker-server,也看到docker-vm上有我們scp過去的檔案

接著我們嘗試加入一個Remote Shell

這一段主要是希望透過編碼可以做到整理Deploy上去的zip檔案。未來可以做版本備份的概念,但其實期望應該是可以做到日期流水編,這邊先簡單用日期做

在Docker-Server端為了設定權限,加上以下的script

ubuntu@docker:~/upload/app$ sudo usermod -aG docker ubuntu
ubuntu@docker:~/upload/app$ newgrp docker

做到不用sudo 可以執行docker

因為.net core在Docker的相容性已經有目共睹了,所以這邊索性調整Sample Project給的DockerFile

FROM mcr.microsoft.com/dotnet/aspnet:7.0 AS base
WORKDIR /app
EXPOSE 80
EXPOSE 443

FROM base AS final
WORKDIR /app
COPY *.* .
ENTRYPOINT ["dotnet", "WeatherWebApplication.dll"]

註: 測試Jenkins時,建議都先 在linux主機上驗證,通常 可以跑的指令 在jenkins上不太會出錯。

透過Remote Shell定義Docker Command

經過幾次調整後,終於可以運作了

因為是綁8085 port,所以docker server的安全性設定要開放8085 port

大功告成

我們試試看改程式後,整個運作起來看看正不正常

Enumerable 從1-5筆改成1-10筆

Push後,一路觸發了

哈!馬上建置失敗

因為Docker 的name已經重疊了,無法建立,為了簡單驗證,所以調整一下docker run 的shell,先 停止再 重新run,設定如下(–rm實測無法動態移除存在的container,所以我先改成stop再 rm):

cd ~/upload/app
docker build -t docker-app-image .
docker stop weather-app
docker rm weather-app
docker run -d -p 8085:80 --name=weather-app --rm docker-app-image

最後成功了!!

改成50筆也不是問題

讚啦…

首次手把手建立C# .net core程式透過jenkins模擬 CICD的流程 ,雖然還沒自動呼叫單元測試,但也算是解決了自已長久以來好奇的部分細節。

不過實務上每個細節都還有很多改進空間(廢話),例如cd的部分不太可能像我這邊用 stop的方式 中斷 服務,應該是能透過 Docker Swarm或是K8加入node的方式,也要更提早考慮封裝image的問題。以確保不是在prod環境才進行封裝,而是在stage封裝 後在 其他環境pull下來的image已經是穩定的。

這次的案例雖簡化許多,不過能打通一解我心中長久之謎,在很多細節真的是需要一一擊破,僅作為筆記 記錄此行~~

.Net 8的計量新框架 (Metrics)

.Net 8的計量新框架 (Metrics)

想當年,要做到.Net的監控機制,就是要做到這麼多的事情

可能包含要自己設計Log,考慮如何非同步寫入分庫DB,或是另外獨立呼叫外部服務(ex.Sentry)。

當然外部服務是肯定方便又快速的整合方式,但是就是貴森森,而且還有服務綁架問題(就是用一用 ,你就很難轉移到其他平台上)

曾幾何時,我們以前的公司也有架構team,專門搞了一個整合Grafana, Kibana, ElasticSearch的底層平台過。當然當初要架這些東西還沒容器化前,相信也是有相當的維運成本(現在也是有啦)

不過自從容器化後,這些事情都變的好像更容易指令化,就可以打包好一個獨立的自有服務。

當然 今天看到這篇.Net 8支援 Metrics的功能後,其實真的簡化了很多以往要自已造輪子的工。

有興趣可以看 .Net網紅的Demo

而官方文件也給出了手把手的教學!!

https://learn.microsoft.com/zh-tw/dotnet/core/diagnostics/metrics-collection

LeetCode之外,資料結構與演算法解題技巧-Counter, Pointer, Sliding Window

LeetCode之外,資料結構與演算法解題技巧-Counter, Pointer, Sliding Window

有鑑於雖然為本科系(資管),但是實際上在學校時期學習資料結構與演算法時,雖然那個時候都算有印象,但是都畢業這麼久了,除了偶爾看到針對 特定演算法討論,但其實更常使用的其語言函式庫提供的排序/查找,甚至Linq語法讓我們不用看到那些也可以寫出對應的程式。

最近有機會做到一些 LeetCode,汗顏只能第一直覺使用暴力法來解決問題。因此為了隨時能補足觀念問題,包含預備未來可能會遇到Dynamic Programming的演算法大魔王,因此從Udemy大特價時,快速入手了以下課程。課程連結: https://www.udemy.com/course/algorithm-data-structure/ (老師的數學觀念好,好羡慕)

從書本時代過來的我,也開始意識到其實數位課程若在合理價格的情況下,其實可以合適的當作數位書籍看待,甚至可以在anytime,anywhere(包含陪小孩去上游泳課)的時候隨時拿出來找章節來聽 ,著實方便。以下就是我重溫前幾章節 的時候,覺得不錯的技巧,事實上真實案例中 ,都會用到。不過遇到解題的時限跟題目內容理解分析過程。其實很容易 無腦使用暴力法。但下面的技巧其實就是幫助未來就算是使用O(N^2)以上的複雜度。也可以再想看看能否改善為O(N)甚至 O(logN)的方向。也作為一個小筆記吧。順勢把一些重點就重溫過一下。

Counter 技巧

使用hashtable做key/value計算次數

範例題:

Coding Practice:Intersection Problem

若寫成O(n^2)複雜度就會如下 (其關鍵是O(M*N)),有巢狀迴圈

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
	   var result = Intersection(new []{1, 3, 5, 7, 9}, new[]{2, 3, 5, 8, 10});
	   foreach(var item in result)
	   {
	       Console.WriteLine(item);
	   }	
	}
	
	public static int[] Intersection(int[] arr1, int[] arr2)
	{
	   var result = new List<int>();
	   for (int i = 0; i < arr1.Length; i++)
	   {
	      for (int j = 0; j < arr2.Length; j++)
	      {
		if (arr1[i] == arr2[j])
		   result.Add(arr1[i]);
		}
	      }
		
	      return result.ToArray();
	   }
}

用Counter改寫

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var result = Intersection(new []{1, 3, 5, 7, 9}, new[]{2, 3, 5, 8, 10});
		foreach(var item in result)
		{
			Console.WriteLine(item);
		}
		
	}
	
	public static int[] Intersection(int[] arr1, int[] arr2)
	{
		var result = new List<int>();
		var counter = new Dictionary<int, int>();
		for (int i = 0; i < arr1.Length; i++)
		{
			if (counter.ContainsKey(arr1[i]))
			{
			   counter[arr1[i]]++;
			}
			else
			{
			   counter.Add(arr1[i], 1);
			}
		}
		
		for (int i = 0; i < arr2.Length; i++)
		{
			if (counter.ContainsKey(arr2[i]))
			{
			   counter[arr2[i]]++;
			}
			else
			{
			   counter.Add(arr2[i], 1);
			}
		}
		
		foreach(var kv in counter)
		{
			if (kv.Value > 1)
			{
			   result.Add(kv.Key);
			}
		}
		
		return result.ToArray();
	}
	
}

透過Counter計數器變成分別走訪3個迴圈,其BigO應為O(m+n+m+n) = O(2(m+n)) = O(N)(常數可忽略)

課程中 再舉了一個可以用Counter解決的問題如下 :

Coding Practice:Frequency Problem

sameFrequency(“abbc”, “aabc”) false;
sameFrequency(“abba”, “abab”) true;
sameFrequency(“aasdebasdf”, “adfeebed”) false;

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		Console.WriteLine(sameFrequency("abbc", "aabc")); // false;
		Console.WriteLine(sameFrequency("abba", "abab")); //true;
		Console.WriteLine(sameFrequency("aasdebasdf", "adfeebed"));// false;
	}
	
	public static bool sameFrequency(string string1, string string2)
	{
		var arr1 = string1.ToCharArray();
		var arr2 = string2.ToCharArray();
	
		if (arr1.Length != arr2.Length)
			return false;
		
		
		var counter1 = new Dictionary<char, int>();
		var counter2 = new Dictionary<char, int>();
		
		for(int i = 0; i < arr1.Length;i++)
		{
			if (counter1.ContainsKey(arr1[i]))
			{
				counter1[arr1[i]]++;
			}
			else
			{
				counter1.Add(arr1[i], 1);
			}	
		}
		
		for(int i = 0; i < arr2.Length;i++)
		{
			if (counter2.ContainsKey(arr2[i]))
			{
				counter2[arr2[i]]++;
			}
			else
			{
				counter2.Add(arr2[i], 1);
			}	
		}
		
		foreach(var kv in counter1)
		{
			if (!counter2.ContainsKey(kv.Key))
			{
				return false;
			}
			
			if (counter2[kv.Key] != kv.Value)
			{
				return false;
			}
		}
		
		return true;
	}
	
}
在上述的程式中,可以看到篇幅不小,而且3個獨立迴圈。但在演算法時間複雜度的概念中
O(N+M+k)永遠優於O(N*M*K),當然你可以說某一個值很小,但我們通常是假設平均的概念,所以很小情境反而應該視為特例。

Pointer技巧(TwoPointer)

透過多重指針走訪所有節點

Coding Practice: Average Pair
given sorted array , find 2 integer that average is given avg value
averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);

一樣若用暴力法,做O(n^2)的解法如下:

using System;
using System.Collections;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var resultArray = averagePair(new int[]{-11, 0, 1, 2, 3, 9, 14, 17, 21}, 1.5);
		foreach(var itemArray in resultArray)
		{
			Console.WriteLine("--------------");
			foreach(var item in itemArray)
			{
				Console.WriteLine(item);
			}
		}
	}
	
	public static List<int[]> averagePair(int[] array, double avg)
	{
		var result = new List<int[]>();
		var count = 0;
		for (int i = 0; i < array.Length - 1; i++)
		{
			for (int j = i+1; j < array.Length; j++)
			{
				if ((double)(array[i] + array[j]) / 2 == avg)
				{
					result.Add(new[]{array[i], array[j]});
				}
				count++;
			}
		}
		
		Console.WriteLine("total check step:" + count);
		return result;
	}	
}

結果: total check step:36 (C9取2 = 9*8/2 = 36)
————–
-11
14
————–
0
3
————–
1
2

若改用Pointer的技巧可以指定一個left pointer跟right pointer(也常稱two pointer)

using System;
using System.Collections;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var resultArray = averagePair(new int[]{-11, 0, 1, 2, 3, 9, 14, 17, 21}, 1.5);
		foreach(var itemArray in resultArray)
		{
			Console.WriteLine("--------------");
			foreach(var item in itemArray)
			{
				Console.WriteLine(item);
			}
		}
	}
	
	public static List<int[]> averagePair(int[] array, double avg)
	{
		var result = new List<int[]>();
		var count = 0;
		
		var left = 0;
		var right = array.Length-1;
		
		
		while(left < right)
		{
			var temp = (double)(array[left] + array[right]) / 2;
			
			if (temp > avg)
			{
				right--;
			}
			if (temp < avg)
			{
				left++;
			}
			if (temp == avg)
			{
				result.Add(new[]{array[left], array[right]});	
				right--;
				left++;
			}
			count++;
		}
		
		Console.WriteLine("total check step:" + count);
		return result;
	}	
}

Result:

total check step:6
————–
-11
14
————–
0
3
————–
1
2

同樣的結果,可以在9步內(6步)找到一樣結果

複雜度也從巢狀迴圈走訪改成了每個節點最多走訪一次甚至因為two pointer,可以少了3次比對。

因為結果有3個符合,所以一次性left跟right同時會往內縮小範圍。

Sliding Window技巧

透過window size走訪所有的節點。每一次以給定的size橫向 移前一格索引。

Coding Practice:maxSum/minSum

given integer array , find consecutive number of given n value ‘s max and min value

maxSum([2,7,3, 0,6,1,-5,-12,-11], 3)

//minSum([2,7,3, 0,6,1,-5,-12,-11], 3)

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var result = maxSum(new int[]{2,7,3, 0,6,1,-5,-12,-11}, 3);
		Console.WriteLine(result);	
	}
	
	public static int? maxSum(int[] array, int size)
	{
		if (array.Length < size)
			return null;
		
		var count = 0;
		var max = int.MinValue;
		for (int i = 0 ; i < array.Length - size; i++)
		{
			var temp = 0;
			for (int j = i; j < i + size; j++) //
			{
				temp += array[j];
				count++;
			}
			
			if (temp > max)
				max = temp;
		}
		Console.WriteLine(count);
		return max;
	}
}

上面程式的走法是 O(N*M)複雜度。(加總的迴圈的操作也是要算複雜度,也端看size的大小)

Count: 18
maxSum: 12

改善Sliding Window的寫法:

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var result = maxSum(new int[]{2,7,3, 0,6,1,-5,-12,-11}, 3);
		Console.WriteLine(result);	
	}
	
	public static int? maxSum(int[] array, int size)
	{
		if (array.Length < size)
			return null;
		
		var count = 0;
		var max = 0;
		
		//first window
		for (int i = 0 ; i < size; i++)
		{
			max += array[i];
			count++;
		}
				
		for (int j = size ; j < array.Length; j++)
		{
			var temp = max + array[j] - array[j-size];
			if (temp > max)
				max = temp;
			
			count++;
		}
		
		Console.WriteLine(count);
		
		return max;
	}	
}

Count: 9
maxSum: 12
同樣的例子變成了9次,整整省了1/2的複雜度,且變成了O(N)的複雜度(稱為線性時間),當然那個迴圈加總還是一個關鍵。因為size不可知,所以用 迴圈動態處理,但是用sliding window的話,就每次滑動一格,所以是在可預期的步數下去做操作。最多2步。因此這也是一個滿有名的演算法,可以幫助我們在一個循序集合中,找到滿足特定條件的目標值或目標集合。

以上3個 小技巧重點重溫~下集待續~~

HackerRank – New Year Chaos by C#

HackerRank – New Year Chaos by C#

https://www.hackerrank.com/challenges/one-week-preparation-kit-new-year-chaos/problem?h_l=interview&isFullScreen=true&playlist_slugs%5B%5D%5B%5D=preparation-kits&playlist_slugs%5B%5D%5B%5D=one-week-preparation-kit&playlist_slugs%5B%5D%5B%5D=one-week-day-four

測試案例

    public static void minimumBribes(List<int> q)
    {
        var total =0;
        for(int i = q.Count-1; i > 0; i--)
        {
            if (q[i-1] == i+1)
            {
                q[i-1] = q[i];
                total++;
            }
            else if (i>=2 && q[i-2] == i+1)
            {
                q[i-2] = q[i-1];
                q[i-1] = q[i];
                total+=2;
            }
            else if (q[i] != i+1){
                Console.WriteLine("Too chaotic");
                return ;
            }
        }   
        Console.WriteLine(total);
    }

這題老實說,很難看的懂...就算是看答案也一樣

基本上就是帶入程式研究一輪變化吧

首先 傳入的參數 2 1 5 3 4
一開始返向逐一抓值出來,因為假設是由排在後面的人往前做賄絡
順序就是4, 3, 2, 1, 0(index) 
按index就是 
index: 4, 3, 2, 1, 0
value: 4, 3, 5, 1, 2 這個順序來看 

首先index=4時
先
判斷 q[3]若前一個等於5(i+1),代表可以經過換過了一次達成
但這個時候,並不是,這時的q[3]是3,判斷不符
value: 4, 3, 5, 1, 2 

否則 再判斷q[2](i-2,表示前2個)是不是5,
結果符合:
value: 4, 3, 5, 1, 2 
代表可以經由換2次做到5變成index=3的位置
所以試著做
第3個位置換回第4個位置 
index: 4, 3, 2, 1, 0
value: 4, 5, 3, 1, 2  
而第4個位置=第5個位置。
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
然後步驟+2;

再來index=3時
一樣做上述判斷
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
先看前一個q[2]等於4,結果不是
然後看q[1]前2個是否等於4,結果也不是
最後看,第3個是不是等於4,也不是。
這一輪結束

再來index=2時 
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
若前一個q[1]是否等於3,結果不是
然後看 q[0]是否等於3,結果也不是
最後看,第2個是不是等於3,也不是
這一輪結束

再來index = 1時
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
若前一個q[0]是否等於2,結果符合
這時將 q[i-1] = q[i]
最後組合為
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 2, 1 
然後步驟++,此時步驟=3

結束>0的迴圈
印出 total=3;


這個迴圈裡的條件判斷就是假設從最後面一排往前看
若是可以透過假設一步換掉的話,就把他還原
假如可以透過 二步換掉的話,就也把他還原。
否則的話,若比較的值沒有出現在前1、2個位置也沒出現在原位的話,代表 最高可能要超過2步才能達成。所以就印出too chaotic

概念走訪如上...實際寫的話..可能要多記憶一下這個脈絡...XD



Reference :
https://www.youtube.com/watch?v=eFIYc7E4cmQ




LeetCode – ReverseInteger

LeetCode – ReverseInteger

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

看起來很單純的題目
我第一階段的暴力解 是取餘數* 10的(長度-1)次方,每次長度都--;
結果在 大數處理的時候溢位問題很多

寫法最終如下
namespace TestProject1.Reverse_Integer;

public class ReverseInteger
{
    public int Reverse(int x)
    {
        var s = 0;
        while (x != 0)
        {
            var r = x % 10;

            var temp = s * 10 + r;

            if ((temp - r) / 10 != s) //避免溢位問題
                return 0;

            s = temp;
            x /= 10;
        }

        return s;
    }
}

using FluentAssertions;
using NUnit.Framework;
using TestProject1.Reverse_Integer;

public class ReverseIntegerTest
{
    [SetUp]
    public void Setup()
    {
    }

    [Test]
    public void Test001()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(123);
        result.Should().Be(321);
    }
    
    [Test]
    public void Test002()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(-123);
        result.Should().Be(-321);
    }
    
    [Test]
    public void Test003()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(120);
        result.Should().Be(21);
    }  
    
    [Test]
    public void Test004()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(1534236469);
        result.Should().Be(0);
    }
    
    [Test]
    public void Test005()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(32768);
        result.Should().Be(86723);
    }    
    
}
LeetCode-ThreeSum

LeetCode-ThreeSum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != ji != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105
using System;
using System.Collections.Generic;

public class ThreeSumSolution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        if (nums.Length < 3) return new List<IList<int>>();
        Array.Sort(nums);

        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < nums.Length - 2; i++)
        {
            var j = i + 1; //left
            var k = nums.Length - 1; //right
            //排序後,每次 第一位取出來的時候,若後面的值跟前面一樣,代表 前面就循環過了,就不再比較一次 ,直接跳下一個
            //ex [1, 1, 2, 3, 4]
            // 若i=1,值是1,但i=0已經比較過 值是1的,所以SKIP
            if (i > 0 && nums[i] == nums[i - 1]) continue; 
            
            //雙指針
            while (j < k)
            {
                //ex [1, 1, 2, 3, 4]
                // i = 0, 這時j是1,k是3,兩兩 與第i項加總
                
                var sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) //若剛好=0,是我們要的組合
                {
                    result.Add(new List<int>() {nums[i], nums[j], nums[k]});
                    while (j < k && nums[j] == nums[j + 1]) j++; //因為排過序,判斷 往右 是 不是一樣的數字,若是一樣的數字就 再++往右跳過
                    while (j < k && nums[k] == nums[k - 1]) k--; //因為排過序,判斷 往左 是 不是一樣的數字,若是一樣的數字就 再--往左跳過

                    //上面的小while只是累加到重覆的那一個位置 下面還是要再各別往內逼近
                    j++;
                    k--;
                }
                else if (sum < 0)
                {
                    //因為排序過,因此若和小於0,代表 需要從中間數往右找更大的數字看看,所以左指針++
                    j++;
                }
                else
                {
                    //因為排序過,因此若和大於0,代表 需要從最右的大數往左找更小的數字看看,所以右指針--
                    k--;
                }
            }
        }

        return result;
    }
}

using FluentAssertions;
using NUnit.Framework;

public class ThreeSumTests
{
    [SetUp]
    public void Setup()
    {
    }

    [Test]
    public void Test001()
    {
        ThreeSumSolution ts = new ThreeSumSolution();
        var result = ts.ThreeSum(new[] {-1, 0, 1, 2, -1, -4});
        result.Count.Should().Be(2);
    }
}
LeetCode -Task Scheduler

LeetCode -Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

  • 1 <= task.length <= 104
  • tasks[i] is upper-case English letter.
  • The integer n is in the range [0, 100].
using System;
using System.Collections.Generic;
using System.Linq;

public class TaskScheduler
{
    public class task
    {
        public char name { get; set; }
        public int count { get; set; }
    }

    public int LeastInterval(char[] tasks, int n)
    {
        if (0 == n) return tasks.Length;

        Dictionary<char, int> counter = new Dictionary<char, int>();
        foreach (var task in tasks)
        {
            if (counter.ContainsKey(task))
            {
                counter[task]++;
            }
            else
            {
                counter.Add(task, 1);
            }
        }

        int chCount = 0, maxCount = 0, step = 0;
        foreach (var item in counter.Values)
        {
            if (item > maxCount)
            {
                chCount = 1;
                maxCount = item;
            }
            else if (item == maxCount)
            {
                chCount++;
            }
        }
       
        if (step >= tasks.Length) return step;
        return tasks.Length;
    }
}

using FluentAssertions;
using NUnit.Framework;

namespace TestProject1.TaskScheduler;

public class SolutionTests
{
    [SetUp]
    public void Setup()
    {
    }

    global::TaskScheduler _scheduler = new global::TaskScheduler();

    [Test]
    public void Test001()
    {
        var result = _scheduler.LeastInterval(new char[] {'A', 'A', 'A', 'B', 'B', 'B'}, 2);
        result.Should().Be(8);
    }    
    
    [Test]
    public void Test002()
    {
        var result = _scheduler.LeastInterval(new char[] {'A','A','A','B','B','B'}, 0);
        result.Should().Be(6);
    }
    
    [Test]
    public void Test003()
    {
        var result = _scheduler.LeastInterval(new char[] {'A','A','A','A','A','A','B','C','D','E','F','G'}, 2);
        result.Should().Be(16);
    }
}

step = (maxCount – 1) * (n + 1) + chCount;
公式這邊真的看無 ,看起來是找到最大重覆的task的次數後
實際推論上就是

例如new char[] {‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’}, 2
那麼就是 A有3,B有3,n=2 那maxCount = 3, chCount = 2 (因為 > 0的時候 chcount就 =1,若有重覆次數的就再 +=1 )
所以step = (3-1)*(2+1) + 2 = 8

再假如new char[] {‘A’,’A’,’A’,’A’,’A’,’A’,’B’,’C’,’D’,’E’,’F’,’G’}, 2

那麼A有6,B~G各有1
那麼maxCount = 6
公式變成( 6-1) * (2+1)+1=16

照公式的概念就是,最多次數的task,肯定要被n次的限制卡住。若每一次的循環都要跑一次 A+?+?,代表 中間不論是塞次數少的的Task,若分配完了也是要塞 Idle Task。
那麼就代表至少要跑 6個就有5個區間,每個區間都至少要含自已是3個步驟。所以就是15次
那為啥chCount = 1。因為5個區間會少算最後一個出頭的Task。因為B~G總共也在 5次 ,剛好分配到5個區間中的間隔中,代表 塞完間隔後,因為次數不足,還要塞idle,才能再讓 次數最多的跑。


LeetCode – TwoSum

LeetCode – TwoSum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

public class Solution {
	public int[] TwoSum(int[] nums, int target) {
        Hashtable hash = new Hashtable();
        for (int i = 0; i < nums.Length; i++)
        {
            var complement = target - nums[i];
            if (hash.ContainsKey(complement))
            {
                return new int[]{(int)hash[complement], i};
            }
            else
            {
                if (hash.ContainsKey(nums[i]) == false)
                    hash.Add(nums[i], i);
            }
        }
        
        return null;
    }
}

多年前練習過的題目,暴力解是兩個迴圈去倆倆比對(O(N2),此題更優的解法是利用HashTable去建立快取

每比對到跟目標的差,都先記到hashtable中,直到遍歷了每一個元素一次就好,若剛好match到,就代表找到結果了!這樣的話就至少是O(N)的複雜度了。