GSD Questions
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

372 lines
12 KiB

3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
  1. \documentclass[a4paper,10pt]{article}
  2. \usepackage{a4wide}
  3. \usepackage{german}
  4. \usepackage{graphicx}
  5. \usepackage{versions}
  6. \usepackage{amsmath}
  7. \usepackage{color}
  8. \usepackage{colortbl}
  9. \usepackage{anysize}
  10. \usepackage{enumerate}
  11. \usepackage{verbatim}
  12. \usepackage[utf8]{inputenc}
  13. \usepackage{amssymb}
  14. \usepackage{amsmath}
  15. \usepackage{tikz}
  16. \usepackage{listings}
  17. \pagestyle{empty}
  18. \setlength{\parindent}{0mm}
  19. \begin{document}
  20. \vspace*{-3cm}
  21. \hspace*{-1cm}\begin{tabular}{p{.55\linewidth}p{.55\linewidth}}
  22. \begin{minipage}{\linewidth}
  23. {\bf Global Software Development} \\
  24. Kreiker, Pape, Rieger, Todtenh"ofer\\
  25. Summer Term 2018\\\\
  26. \today\\
  27. \end{minipage}
  28. &
  29. \includegraphics[width=\linewidth]{images/logo}
  30. \end{tabular}
  31. \begin{center}
  32. {\Large\bf GSD Interview Questions}\\
  33. \end{center}
  34. %\def\loesung{}
  35. \section{Programming}
  36. \subsection{Row Vectors}
  37. Consider an $n\times m$ matrix. Calculate the absolute value for each row vector of the matrix in a programming language of your choice. Example:
  38. $$
  39. \left(\begin{array}{cc}
  40. 2 & 2 \\ 4 & 4 \\ 6 & 5
  41. \end{array}\right)
  42. \qquad \Rightarrow \qquad\texttt{calcAbsRowVector}\qquad \Rightarrow \qquad
  43. \left(\begin{array}{c}
  44. 2.82 \\ 5.65 \\ 7.81
  45. \end{array}\right)
  46. $$
  47. \subsection{Merging and Sorting}
  48. Let $A$ and $B$ be two arrays of $n$ (unsorted) integer entries each. Write
  49. a function that merges both arrays into a \emph{sorted} array of $2\dot n$
  50. entries. Example:
  51. $$
  52. \begin{array}{lcl}
  53. A & = & [2, 7, 5, 34]\\
  54. B & = & [3, 48, 4, 72]\\
  55. \hline
  56. C & = & [2, 3, 4, 5, 7, 34, 48, 72]\\
  57. \end{array}
  58. $$
  59. \subsection{Recursion}
  60. Consider a herd of cows. Write a \emph{recursive} function to calculate the
  61. sum of all legs. Use addition only (no multiplication allowed).
  62. \ifdefined\loesung
  63. \subsection{Loesung}
  64. \verbatiminput{todten/GSDSolution.java}
  65. \fi
  66. \section{Algorithms and Data Structures}
  67. \subsection{In-situ List Reversal}
  68. Describe an algorithm to reverse a singly-linked list that \emph{does not}
  69. copy any memory cells.
  70. \ifdefined\loesung
  71. \textcolor{red}{
  72. {\bf Solution}: Maintain three pointers following each other: current, next, and
  73. previous. The first pointer is one element ahead of the second. Reverse each pointer
  74. as you you.}
  75. \fi
  76. \subsection{Preorder Tree Traversal}
  77. Consider the following tree and state the \emph{preorder} and \emph{inorder} traversal.
  78. \begin{verbatim}
  79. 5
  80. / \
  81. 7 4
  82. \ / \
  83. 1 2 9
  84. \end{verbatim}
  85. Which data structure do you need to implement such a traversal?
  86. \ifdefined\loesung
  87. \textcolor{red}{
  88. {\bf Solution}: Preorder: 5, 7, 1, 4, 2, 9; Inorder: 7, 1, 5, 2, 4, 9.
  89. Such traversals are implemented using a stack (explicitly or implicitly using
  90. a recursive traversal)}
  91. \fi
  92. \subsection{Breadth-First-Search}
  93. What is the BFS traversal of the tree above? Which data structure is needed to implement
  94. such a traversal?
  95. \ifdefined\loesung
  96. \textcolor{red}{
  97. {\bf Solution}: BFS: 5, 7, 4, 1, 2, 9. You need a queue to implement BFS.}
  98. \fi
  99. \section{Networking}
  100. \subsection{Protocol Stacks}
  101. Explain the major differences between the network protocols UDP, TCP and IP.
  102. \ifdefined\loesung
  103. \textcolor{red}{
  104. {\bf Solution}: UDP is connectionless, offers no error correction etc., data is sent directly without handshake, typically used for real-time protocols. TCP is connection-oriented, offers error correction, flow control (also congestion control), bidirectional reliable data transfer. IP is on a different layer (Layer 3 / network layer) compared to TCP and UDP (Layer 4 / transport layer), IP is connectionless transports datagrams between endpoints, supports routing etc.}
  105. \fi
  106. \subsection{TCP Characteristics}
  107. Fill the gaps with appropriate values for the corresponding TCP header fields:
  108. \begin{figure}[htb]
  109. \includegraphics[width=0.9\columnwidth]{images/tcp-handshake-and-flowcontrol.png}
  110. \end{figure}
  111. \ifdefined\loesung
  112. \textcolor{red}{
  113. {\bf Solution}: 2: Flags = SYN+ACK, 3: Flags = ACK, 5: ACK = sa+900, Data-Length = 400 (according to ACK in 7), 6: SEQ = sa+900, Data-Length = 100 (due to limit in (Receive) Window Size), 7: sa+1000.}
  114. \fi
  115. \subsection{Network Addresses}
  116. Insert the Layer 2 and Layer 3 addresses used the following transfer from Computer A to Computer B. How many IP addresses can exist in the subnet Computer B is placed in? What is the network address of this subnet?
  117. \begin{figure}[htb]
  118. \includegraphics[width=0.9\columnwidth]{images/mac-address.png}
  119. \end{figure}
  120. \ifdefined\loesung
  121. \textcolor{red}{
  122. {\bf Solution}: Source IP: 1.1.1.10 (not 1.1.1.10/24), Destination IP: 2.2.15.100 (not 2.2.15.100/21), Source MAC: 11:22:33:44:55:66, Destination MAC: aa:bb:cc:dd:ee:ff (not 33:44:55:66:77:88). Number of hosts in /21 IPv4 subnet = 2046 ($2^{32-21}-2$). Network address of the IP subnet of Computer B: 2.2.8.0/21.}
  123. \fi
  124. \section{Regular Expressions and Shells}
  125. \subsection{Regular Expression}
  126. Explain the following regex:
  127. \begin{verbatim}
  128. ^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$
  129. \end{verbatim}
  130. \ifdefined\loesung
  131. \textcolor{red}{
  132. {\bf Solution}: This regex describes well-formatted IPv4 addresses. Number of repetitions
  133. given in braces, Question mark for optional choices, brackets denote ranges.}
  134. \fi
  135. \subsection{Extract Lines}
  136. Write a shell command to extract lines number 101-110 from a file {\tt a.txt} and
  137. output them (numerically sorted) to file {\tt b.txt}.
  138. \ifdefined\loesung\textcolor{red}{
  139. {\bf Solution}: {\tt cat a.txt | head -110 | tail -10 | sort -n > b.txt}}
  140. \fi
  141. \subsection{Large Files}
  142. Write a shell command to find the file with the most number of lines in
  143. the current directory.
  144. \ifdefined\loesung\textcolor{red}{
  145. {\bf Solution}: {\tt wc -l * | sort -nr} is key. One might get rid of the \emph{total} line count
  146. and access the file name only. Optional.}
  147. \fi
  148. \section{Databases}
  149. %------------------------------------------------------------------------------
  150. \subsection{SQL statements}
  151. %------------------------------------------------------------------------------
  152. Write down the results of the following SQL statements on table T.
  153. \begin{quote}
  154. \begin{tabular}[t]{l|l|l|l}
  155. T & A & B & C \\
  156. \hline
  157. & 1 & blue & 10 \\
  158. & 2 & blue & 40 \\
  159. & 3 & pink & 30 \\
  160. & 4 & orange & 10 \\
  161. & 5 & orange & 20 \\
  162. & 6 & orange & 50 \\
  163. & 7 & orange & 50 \\
  164. & 8 & black & 50 \\
  165. & 9 & black & 40 \\
  166. & 10 & violet & 10 \\
  167. & 11 & violet & 20 \\
  168. & 12 & violet & 10 \\
  169. \end{tabular}
  170. \end{quote}
  171. \begin{description}
  172. \item[a.)] {\tt SELECT B, COUNT(*) FROM T GROUP BY B HAVING SUM(C)<=40}
  173. \begin{quote}
  174. \begin{tabular}[t]{|p{2.5cm}|p{2.5cm}|}
  175. \hline
  176. B & COUNT(*) \\
  177. \hline
  178. \hline
  179. \ifdefined\loesung
  180. \textcolor{red}{pink} & \textcolor{red}{1} \\[0.3cm]
  181. \hline
  182. \textcolor{red}{violet} & \textcolor{red}{3} \\[0.3cm]
  183. \hline
  184. \textcolor{red}{} & \textcolor{red}{} \\[0.3cm]
  185. \hline
  186. \textcolor{red}{} & \textcolor{red}{} \\[0.3cm]
  187. \else
  188. & \\[0.3cm]
  189. \hline
  190. & \\[0.3cm]
  191. \hline
  192. & \\[0.3cm]
  193. \hline
  194. & \\[0.3cm]
  195. \fi
  196. \hline
  197. \end{tabular}
  198. \end{quote}
  199. \item[b.)] {\tt SELECT B, COUNT(*) FROM T WHERE C>35 \\GROUP BY B HAVING COUNT(*)>=2}
  200. \begin{quote}
  201. \begin{tabular}[t]{|p{2.5cm}|p{2.5cm}|}
  202. \hline
  203. B & COUNT(*) \\
  204. \hline
  205. \hline
  206. \ifdefined\loesung
  207. \textcolor{red}{orange} & \textcolor{red}{2} \\[0.3cm]
  208. \hline
  209. \textcolor{red}{black} & \textcolor{red}{2} \\[0.3cm]
  210. \hline
  211. \textcolor{red}{} & \textcolor{red}{} \\[0.3cm]
  212. \hline
  213. \textcolor{red}{} & \textcolor{red}{} \\[0.3cm]
  214. \else
  215. & \\[0.3cm]
  216. \hline
  217. & \\[0.3cm]
  218. \hline
  219. & \\[0.3cm]
  220. \hline
  221. & \\[0.3cm]
  222. \fi
  223. \hline
  224. \end{tabular}
  225. \end{quote}
  226. \end{description}
  227. %------------------------------------------------------------------------------
  228. \subsection{Constraints \& Integrity}
  229. %------------------------------------------------------------------------------
  230. The following table definition with integrity constraints are given.
  231. \begin{quote}
  232. {\tt
  233. \begin{tabbing}
  234. CREATE TABLE T1 (\=A INT, B INT, C INT,\\
  235. \>CONSTRAINT T1\_PS PRIMARY KEY (A,B),\\
  236. \>CONSTRAINT T1\_SK UNIQUE (C));\\
  237. \\
  238. CREATE TABLE T2 (A INT, B INT, C INT, D INT, E INT,\\
  239. \>CONSTRAINT T2\_PS PRIMARY KEY (A),\\
  240. \>CONSTRAINT T2\_FS1 FOREIGN KEY (B,C) REFERENCES T1(A,B),\\
  241. \>CONSTRAINT T2\_FS2 FOREIGN KEY (D) REFERENCES T1(C),\\
  242. \>CONSTRAINT T2\_E\_NN CHECK (E IS NOT NULL),\\
  243. \>CONSTRAINT T2\_E\_13 CHECK (E BETWEEN 1 AND 3)); \\
  244. \end{tabbing}}
  245. \end{quote}
  246. The table T1 and T2 contain the following tuples. NULL values are indicated by a hyphen (-).
  247. \begin{quote}
  248. \begin{tabular}[t]{l|l|l|l}
  249. T1 & A & B & C \\
  250. \hline
  251. & 1 & 1 & 5 \\
  252. & 2 & 2 & 10 \\
  253. & 3 & 3 & 15 \\
  254. & 4 & 4 & 20 \\
  255. & 5 & 5 & 25 \\
  256. \end{tabular}
  257. \hspace{2cm}
  258. \begin{tabular}[t]{l|l|l|l|l|l}
  259. T2 & A & B & C & D & E\\
  260. \hline
  261. & 100 & - & - & 15 & 1 \\
  262. & 101 & 2 & 2 & 25 & 2 \\
  263. & 102 & 2 & 2 & - & 3 \\
  264. & 103 & 3 & 3 & 10 & 3 \\
  265. & 104 & 3 & 3 & 10 & 3 \\
  266. \end{tabular}
  267. \end{quote}
  268. Which of the following INSERT-statements are violating/not violating the defined integrity constraints? Only one integrity constraint will be violated for each statement. Enter the name of the violated integrity constraint or ''none'' if all conditions are met.
  269. \begin{tabular}[t]{|l|l|l|}
  270. \hline
  271. Nr. & INSERT-statement & Violated constraint \\[0.3cm]
  272. \hline
  273. 1 & {\tt INSERT INTO T1 VALUES (1, 2, 5)} & \ifdefined\loesung \textcolor{red}{T1\_SK} \fi \\[0.3cm]
  274. \hline
  275. 2 & {\tt INSERT INTO T1 VALUES (1, 2, 30)} & \ifdefined\loesung \textcolor{red}{none} \fi \\[0.3cm]
  276. \hline
  277. 3 & {\tt INSERT INTO T1 VALUES (1, 1, 50)} & \ifdefined\loesung \textcolor{red}{T1\_PS} \fi \\[0.3cm]
  278. \hline
  279. 4 & {\tt INSERT INTO T1 VALUES (1, NULL, NULL)} & \ifdefined\loesung \textcolor{red}{T1\_PS} \fi \\[0.3cm]
  280. \hline
  281. 5 & {\tt INSERT INTO T2 VALUES (117, 2, 2, 5, 5)} & \ifdefined\loesung \textcolor{red}{T2\_E\_13} \fi \\[0.3cm]
  282. \hline
  283. 6 & {\tt INSERT INTO T2 VALUES (109, 3, 1, 10, 3)} & \ifdefined\loesung \textcolor{red}{T2\_FS1} \fi \\[0.3cm]
  284. \hline
  285. 7 & {\tt INSERT INTO T2 VALUES (103, 1, 1, 20, 2)} & \ifdefined\loesung \textcolor{red}{T2\_PS} \fi \\[0.3cm]
  286. \hline
  287. 8 & {\tt INSERT INTO T2 VALUES (110, 4, 4, 35, 1)} & \ifdefined\loesung \textcolor{red}{T2\_FS2} \fi \\[0.3cm]
  288. \hline
  289. \end{tabular}
  290. %------------------------------------------------------------------------------
  291. \subsection{Relations \& DDL-statements}
  292. %------------------------------------------------------------------------------
  293. The following tables and DDL-statements are given. Please note: an exam with a grade other than 5.0 is passed.
  294. \begin{figure}[htb]
  295. \begin{minipage}{0.30\linewidth}
  296. \includegraphics[width=38mm]{images/task3-chen.pdf}
  297. \end{minipage}
  298. %\hfill
  299. \begin{minipage}{0.55\linewidth}
  300. \scriptsize\lstinputlisting[numbers=none]{queries/task3-ddl.sql}
  301. \end{minipage}
  302. \end{figure}
  303. \begin{description}
  304. \item[a.)] What is defined in the table {\tt STUDENT}?
  305. \ifdefined\loesung \textcolor{red}{
  306. \begin{itemize}
  307. \item the student's Id is the primary key
  308. \item a student's Id have to be between 100000 and 999999
  309. \item the GENDER column is restricted to 'm' for male and 'f' for female
  310. \end{itemize}}\else \vfill \fi
  311. \item[b.)] What is defined in the table {\tt EXAM}?
  312. \ifdefined\loesung \textcolor{red}{
  313. \begin{itemize}
  314. \item the primary key is composed of the student's Id, the attempt and the course name
  315. \item an exam can be taken three times
  316. \item the possible grades for an exam are 1.0, 1.3, 1.7, 2.0, 2.3, 2.7, 3.0, 3.3, 3.7, 4.0, 5.0
  317. \item the referenced student Id must exist in the {\tt STUDENT} table ({\tt FOREIGN KEY})
  318. \item the deletion of a student will also delete all associated exams ({\tt ON DELETE CASCADE})
  319. \end{itemize}}\else \vfill \fi
  320. \item[c.)] Define a SQL query to find students (student's Id, firstname, lastname and course) who failed in the third attempt?
  321. \begin{quote}
  322. \ifdefined\loesung \textcolor{red}{\tt SELECT S.STUDENT\_ID, S.LASTNAME, E.COURSE FROM STUDENT S, EXAM E \\ WHERE S.STUDENT\_ID=E.STUDENT\_ID AND ATTEMPT=3 AND GRADE=5}\else \vfill \fi
  323. \end{quote}
  324. \item[d.)] Define a SQL query to report the average attempts for male and female students?
  325. \begin{quote}
  326. \ifdefined\loesung \textcolor{red}{\tt SELECT S.GENDER, AVG(ATTEMPT) FROM STUDENT S, EXAM E \\ WHERE S.STUDENT\_ID=E.STUDENT\_ID AND NOT GRADE=5 GROUP BY S.GENDER}\else \vfill \fi
  327. \end{quote}
  328. \end{description}
  329. %------------------------------------------------------------------------------
  330. \end{document}
  331. %------------------------------------------------------------------------------