is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
using System;
- nguyenvanhiencdt49 December 21, 2016using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/* <Program description>
*
* Mr. Kim has to deliver samples to N costumer.
* Find the shortest way to deliver it and return his home
*
* Mr.Kim<Office>--> Costumer1-->....CustomerN--> His Home.
*
*
*
*/
/* <Idea --> Solution>
*
* find all possible path:
* There is N!-1 possible path
*
* for : earch path from 1----> N!-1
* (i)--> Corresponding sequence --> {Permuation}
* --> determine Shortest distance and print "the path sequence"
*
*/
/* <Result >
*
* Case #1: 200: path -> Office->[2-1-4-0-3]-->Home
* Case #2: 304: path-> Office->[1-3-5-0-4-2]-->Home
* Case #3: 366: path-> Office->[6-3-9-4-8-0-5-1-7-2]-->Home
*/
namespace ShortestPathDelivery
{
class Program
{
static void Main(string[] args)
{
// Test case:
// Case 1:
/*
const int N = 5;
int[,] xyLocation = {{ 70, 40 }, { 30, 10 }, { 10, 5 }, { 90, 70 }, { 50, 20 }};
int[,] xyOffice = { {0,0}};
int[,] xyHome = { { 100, 100 } };
*
*/
//case 2:
/*
const int N = 6;
int[,] xyLocation = { { 19, 22 }, { 31, 15 }, { 27, 29 }, { 30, 10 }, { 20, 26 },{5,14} };
int[,] xyOffice = { { 81, 88} };
int[,] xyHome = { { 85, 80 } };
*/
const int N = 10;
int[,] xyLocation = { {35,93 }, { 62,64 }, { 96,39}, { 36,36 }, { 5,59 },
{59,96},{61,7},{64,43},{43,58},{1,36} };
int[,] xyOffice = { {39,9}};
int[,] xyHome = { { 97, 61 } };
int[] pathseq = new int[N];
int[] finalPath = new int[N];
int[] shortestPath = new int[N];
double dis_Min = 10000 ;
// pathseq = GetPathsequence(2982, N);
//List allpath
for (int i = 0; i < GetNmul(N); i++)
{
pathseq = GetPathsequence(i, N);
// PrintPath(pathseq);
finalPath = Convertsequence(pathseq);
// PrintPath(finalPath);
// Calculate corresponding distance
double tempDis = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
// System.Console.Write(" --Dis: {0} ", CalDistance(finalPath, xyLocation, xyHome, xyOffice));
if (i == 0)
{
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
else
{
if (dis_Min > CalDistance(finalPath, xyLocation, xyHome, xyOffice))
{
shortestPath = finalPath;
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
}
}
PrintPath(shortestPath);
System.Console.WriteLine(" Shortest Dis: {0} ", dis_Min);
System.Console.ReadKey();
}
// This function return the sequence from n--> factorized sequence.
public static int[] GetPathsequence(int n, int Ncustom)
{
int[] aSequence = new int[Ncustom];
int divide = 0;
int remainder = 0;
for (int i = Ncustom-1; i >=0;i-- )
{
if(i==Ncustom-1)
{
divide = (int)n / GetNmul(Ncustom-1);
remainder = (int)n % GetNmul(Ncustom-1);
aSequence[Ncustom-1-i] = divide;
}
else
{
divide = remainder / GetNmul(i);
remainder = remainder % GetNmul(i);
aSequence[Ncustom-1-i] = divide;
}
}
return aSequence;
}
public static int GetNmul(int n)
{
if (n == 0)
return 1;
else
return n * GetNmul(n - 1);
}
public static void PrintPath(int [] aPath)
{
for (int i =0; i <aPath.Length; i++)
{
System.Console.Write("{0} :", aPath[i]);
}
System.Console.WriteLine("");
}
public static int[] Convertsequence(int [] inArray)
{
int[] decodeArray = new int[(int)inArray.Length];
List<int> naturalList = new List<int>();
for (int i = 0; i < inArray.Length;i++)
{
naturalList.Add(i);
}
// Decoding
for (int i = 0; i < inArray.Length; i++)
{
decodeArray[i] = naturalList[inArray[i]];
naturalList.Remove(decodeArray[i]);
}
return decodeArray;
}
public static double CalDistance(int[] iPath, int[,] XYLocation, int[,] xyHome, int[,] xyOffice)
{
double dis =0, dis_0,dis_N;
for (int i = 0; i < iPath.Length-1 ; i++)
{
dis = dis + Math.Abs(XYLocation[iPath[i], 0] - XYLocation[iPath[i+1], 0])
+ Math.Abs(XYLocation[iPath[i], 1] - XYLocation[iPath[i+1], 1]);
}
dis_0 = Math.Abs(xyOffice[0,0] - XYLocation[iPath[0], 0])
+ Math.Abs(xyOffice[0,1] - XYLocation[iPath[0], 1]);
dis_N = Math.Abs(XYLocation[iPath[iPath.Length - 1], 0] - xyHome[0,0])
+ Math.Abs(XYLocation[iPath[iPath.Length - 1], 1] - xyHome[0, 1]);
dis = dis + dis_0 + dis_N;
return dis;
}
}
}