本人面試的是 資料倉庫進階工程師–推薦系統,從官網投的校招,2020年底最後一天發的履歷,元旦假三天,四号早上來了通知
以下是面試題,希望有幫助
1.自我介紹
挑重點,與面試職位無關的經曆不要說,除非特别牛逼那最多一兩句(托福雅思三外比賽創業國際代表),年級學校專業目标,大學做過什麼科研立項什麼項目,在實驗室學習什麼方向,自我介紹完了會讓你詳細說某一個做過的項目,然後細問。
2.spark與mapreduce
Spark 是一種與 Hadoop 相似的開源叢集計算環境,但是兩者之間還存在一些不同之處,這些有用的不同之處使 Spark 在某些工作負載方面表現得更加優越,換句話說,Spark 啟用了記憶體分布資料集,除了能夠提供互動式查詢外,它還可以優化疊代工作負載。Spark 在 Scala 語言中實作,它将 Scala 用作其應用程式架構。與 Hadoop 不同,Spark 和 Scala 能夠緊密內建,其中的 Scala 可以像操作本地集合對象一樣輕松地操作分布式資料集。盡管建立 Spark 是為了支援分布式資料集上的疊代作業,但是實際上它是對 Hadoop 的補充,可以在 Hadoop 檔案系統中并行運作。通過名為 Mesos 的第三方叢集架構可以支援此行為。Spark 由加州大學伯克利分校 AMP 實驗室 (Algorithms, Machines, and People Lab) 開發,可用來建構大型的、低延遲的資料分析應用程式。
MapReduce是一種程式設計模型,用于大規模資料集(大于1TB)的并行運算。概念"Map(映射)“和"Reduce(歸約)”,是它們的主要思想,都是從函數式程式設計語言裡借來的,還有從矢量程式設計語言裡借來的特性。它極大地友善了程式設計人員在不會分布式并行程式設計的情況下,将自己的程式運作在分布式系統上。 目前的軟體實作是指定一個Map(映射)函數,用來把一組鍵值對映射成一組新的鍵值對,指定并發的Reduce(歸約)函數,用來保證所有映射的鍵值對中的每一個共享相同的鍵組。
3.jvm
JVM是Java Virtual Machine(Java虛拟機)的縮寫,JVM是一種用于計算裝置的規範,它是一個虛構出來的計算機,是通過在實際的計算機上仿真模拟各種計算機功能來實作的。引入Java語言虛拟機後,Java語言在不同平台上運作時不需要重新編譯。Java語言使用Java虛拟機屏蔽了與具體平台相關的資訊,使得Java語言編譯程式隻需生成在Java虛拟機上運作的目标代碼(位元組碼),就可以在多種平台上不加修改地運作。
4.hashmap
基于哈希表的 Map 接口的實作。此實作提供所有可選的映射操作,并允許使用 null 值和 null 鍵。(除了非同步和允許使用 null 之外,HashMap 類與 Hashtable 大緻相同。)此類不保證映射的順序,特别是它不保證該順序恒久不變。 此實作假定哈希函數将元素适當地分布在各桶之間,可為基本操作(get 和 put)提供穩定的性能。疊代 collection 視圖所需的時間與 HashMap 執行個體的“容量”(桶的數量)及其大小(鍵-值映射關系數)成比例。是以,如果疊代性能很重要,則不要将初始容量設定得太高(或将加載因子設定得太低)。
hashmap的重寫方法
import java.util.*;
public class Exp2 {
public static void main(String[] args) {
HashMap h2 = new HashMap();
for (int i = 0; i < 10; i++) {
h2.put(new Element(i), new Figureout());
System.out.println("h2:");
System.out.println("Get the result for Element:");
}
Element test = new Element(3);
if (h2.containsKey(test)) {System.out.println((Figureout) h2.get(test));}
else {
System.out.println("Not found");
}
}
static class Element {
int number;
public Element(int n) {
number = n;
}
}
static class Figureout {
Random r = new Random();
boolean possible = r.nextDouble() > 0.5;
public String toString() {
if (possible) {
return "OK!";
} else {
return "Impossible!";
}
}
}
}
5.線程與程序的關系(這題應該不是原本要問的畢竟太簡單)
6.代碼題:單連結清單去重(問設計思路、複雜度,以及要寫出來運作,語言可以選)這題之前會問你熟悉的語言是什麼
輸入1 2 2 3 3 3 4
輸出1 4
#include <stdio.h>
#include <stdlib.h>
/******************************************************************
*[email protected] *
*[email protected] *
*[email protected] linked list deduplication *
*******************************************************************/
/**自定義資料類型**/
typedef char Datatype;
/**聲明結構體**/
struct Node
{
Datatype data;
struct Node *next;
};
/**結構體定義**/
typedef struct Node SNode; //結點
typedef struct Node* SLinkNode; //指針
/**單連結清單初始化**/
void InitSList(SLinkNode *head)
{
if((*head=(SLinkNode)malloc(sizeof(SNode)))==NULL)
{
exit(-1);
}
(*head)->next=NULL;
}
/**單連結清單插入元素**/
int InsertSList(SLinkNode head,int i,int elem)
{
SNode *pnew,*p;
p=head;
int j=0;
while(p->next!=NULL && j<i-1)
{
p=p->next;
j++;
}
if(j!=i-1)
{
printf("插入位置錯誤!");
return 0;
}
pnew=(SNode*)malloc(sizeof(SNode));
pnew->data=elem;
pnew->next=p->next;
p->next=pnew;
return 1;
}
/**核心--單連結清單元素去重**/
void DistinctElem(SLinkNode head)
{
SNode *p,*mark,*q;
for(mark=head->next;mark!=NULL;mark=mark->next)
{
q=mark;
p=mark->next;
while(p)
{
if(mark->data==p->data)
{
q->next=p->next;
free(p);
p=q->next;
}else
{
q=p;
p=p->next;
}
}
}
}
int main()
{
char arr[]={'A','B','A','E','B','E','A'};
SLinkNode list1;
//初始化帶有頭節點list1單連結清單
InitSList(&list1);
//插入元素
int i=1;
for(i;i<=sizeof(arr)/sizeof(char);i++)
{
if(InsertSList(list1,i,arr[i-1])==0)
{
printf("插入失敗!");
return;
}
}
//輸出單連結清單
SNode *p=list1;
while(p->next != NULL)
{
p=p->next;
printf("%c ",p->data);
}
printf("\n");
//單連結清單去重
DistinctElem(list1);
//輸出單連結清單
SNode *p1=list1;
while(p1->next != NULL)
{
p1=p1->next;
printf("%c ",p1->data);
}
printf("\n");
return 0;
}
Node* List::deleteDuplication()
{
int n[100];
int i=0;
int times=0;
Node *temp=m_pList; //頭節點
if(!m_pList) return NULL;
while(temp->next!=NULL) //第一次周遊存資料
{
n[i++]= temp->data;
// if(temp->next!=NULL)
temp=temp->next;
}
n[i++]= temp->data; //注意尾節點資料不要丢失
// for(int j=0;j<i;j++) //這三行調試用
// cout <<n[j];
// cout<<endl;
temp=m_pList; //再次指向頭節點
while(temp->next!=NULL) //再周遊去重
{
times++; //記錄位置
Node * tempbefore = temp;
temp=temp->next; //循環向後
for(int k=0;k<times;k++) //這段代碼是連結清單去重
{
if(temp->data == n[k])
{
Node * newtemp = temp->next;
tempbefore->next=newtemp;
newtemp=NULL;
m_iLength--;
temp=tempbefore; //删掉後不要往後指會遺漏
break;
}
}
}
return m_pList;
}
Node* List::deleteDuplication() //重複的都删掉
{
int n[100],m[100];
int i=0;
int times=0;
Node *temp=m_pList;
if(!m_pList) return NULL;
while(temp->next!=NULL)
{
n[i++]= temp->data;
temp=temp->next;
}
n[i++]= temp->data;
i=0;
temp=m_pList;
while(temp->next!=NULL)
{
times++;
Node * tempbefore = temp;
temp=temp->next;
for(int k=0;k<times;k++)
{
if(temp->data == n[k])
{
m[i++]=temp->data;
Node * newtemp = temp->next;
tempbefore->next=newtemp;
newtemp=NULL;
m_iLength--;
temp=tempbefore;
break;
}
}
}
for(int j=0;j<i;j++)
{
temp=m_pList; //再來一輪,把重複出現都删掉
while(temp->next !=NULL)
{
Node * tempbefore = temp;
temp=temp->next;
if(temp->data == m[j])
{
Node * newtemp = temp->next;
tempbefore->next=newtemp;
newtemp=NULL;
m_iLength--;
temp=tempbefore;
}
}
}
for(int j=0;j<i;j++)
{
if(m_pList->data == m[j])
{
Node *newhead=m_pList->next;
return newhead;
}
}
return m_pList;
}
驗證
#include<iostream>
#include"List.h"
using namespace std;
int main(void)
{
Node node1;
node1.data=1;
Node node2;
node2.data=1;
Node node3;
node3.data=2;
Node node4;
node4.data=2;
Node node5;
node5.data=3;
List *pList = new List();
cout<<"從頭部插入:"<<endl;
pList->ListInsertTail(&node1);
pList->ListInsertTail(&node3);
pList->ListInsertTail(&node2);
pList->ListInsertTail(&node4);
pList->ListInsertTail(&node5);
pList->ListInsertTail(&node4);
pList->ListTraverse();
pList->deleteDuplication();
pList->ListTraverse();
delete pList;
pList = NULL;
return 0;
}
接下來要問複雜度,我當時寫的是n方,問我有沒有更快的,提示我檢驗後一個元素與前一個元素相同就删除(這樣複雜度就是n)因為給的題中數字都是連續的
以下代碼輸入122334,輸出1234
LinkedList DeleteDuplicates_1(LinkedList L)
122 {
123 if (L == NULL || L->next == NULL||L->next->next==NULL)
124 return L;
125 //if (L == NULL || L->next == NULL)//如果不存在哨兵結點
126 // return L;
127 Node *pre;
128 Node *p;
129 Node *pnext;
130 pre = L->next;//因為第一個結點L是哨兵結點,是以指向L的下一個結點
131 p = L->next->next;
132 //pre = L;//如果不存在哨兵結點
133 //p = L->next;
134 while (p != NULL)
135 {
136 pnext = p->next;
137 if (pre->data == p->data)
138 {
139 pre->next = pnext;
140 free(p);
141 }
142 else
143 pre = p;
144 p = pnext;
145 }
146 return L;
147 }
以下代碼輸入122334,輸出14
LinkedList DeleteDuplicates_2(LinkedList L)//如果存在哨兵結點
153 {
154 if (L == NULL || L->next == NULL || L->next->next == NULL)
155 return L;
156 Node *prere;
157 Node *pre;
158 Node *p;
159 Node *pnext;
160 int flag = 0;
161 prere = L;
162 pre = L->next;//因為第一個結點是哨兵結點
163 p = L->next->next;
164 //pre = L;//如果不存在哨兵結點
165 //p = L->next;
166 while (p != NULL)
167 {
168 pnext = p->next;
169 if (pre->data == p->data)
170 {
171 pre->next = pnext;
172 free(p);
173 flag = 1;
174 }
175 else
176 {
177 if (flag == 1)
178 {
179 prere->next = p;
180 free(pre);
181 pre = p;
182 flag = 0;
183 }
184 else
185 {
186 prere = pre;
187 pre = p;
188 }
189 }
190 p = pnext;
191 }
192 return L;
193 }
194
195 LinkedList DeleteDuplicates_3(LinkedList L)//如果不存在哨兵結點
196 {
197 if (L == NULL || L->next == NULL)
198 return L;
199 Node *prere;
200 Node *pre;
201 Node *p;
202 Node *pnext;
203 int flag = 0;
204 pre = L;//如果不存在哨兵結點
205 prere = L;
206 prere--;
207 p = L->next;
208 while (p != NULL)
209 {
210 pnext = p->next;
211 if (pre->data == p->data)
212 {
213 pre->next = pnext;
214 free(p);
215 flag = 1;
216 }
217 else
218 {
219 if (flag == 1)
220 {
221 if (pre == L)
222 {
223 L = p;
224 free(pre);
225 pre = p;
226 prere = p;
227 prere--;
228 }
229 else
230 {
231 prere->next = p;
232 free(pre);
233 pre = p;
234 }
235 flag = 0;
236 }
237 else
238 {
239 prere = pre;
240 pre = p;
241 }
242 }
243 p = pnext;
244 }
245 if (flag == 1)
246 {
247 if (pre == L)
248 {
249 L = p;
250 free(pre);
251 pre = p;
252 prere = p;
253 prere--;
254 }
255 else
256 {
257 prere->next = p;
258 free(pre);
259 pre = p;
260 }
261 flag = 0;
262 }
263 return L;
264 }
265
266 int main()
267 {
268 LinkedList list, start;
整體難度不算高(但是我無了,編譯出來一運作5個bug)
面試界面是這個樣子,如果去别的網頁的話面試官那邊有提示
(完)