|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On November 28 2016 17:05 icystorage wrote:
I had a job interview last week (I already have a job) for a mid level position. During the technical interview Q&A, I only answered around 40% of the total questions, is that normal?
Really depends on the company. Some places will fail you out if you mess up more than a question or two. Some places just ask a ton of random ass questions and use it more to figure out placement than pass/fail, so you're expected to not do well in all areas. Hard to say without knowing that specific company's hiring methods.
This is an in person spoken interview, or like a written multiple choice type deal?
|
Skype call, but yeah thanks, there were a lot of questions.
|
Is binary serialisation the fastest in theory? I came across protobuf (protocol buffers) yesterday and they say it is faster. However, it is probably concrete implementation, so I'm not sure what to make of it. 
|
On November 30 2016 08:20 Shield wrote:Is binary serialisation the fastest in theory? I came across protobuf (protocol buffers) yesterday and they say it is faster. However, it is probably concrete implementation, so I'm not sure what to make of it.
This is a difficult question to answer because there are different serialisation methods and formats. But,
1. Binary serialisation will be faster to read and write than text, due to smaller file sizes and faster comparison operations;
2. Protobuf looks really interesting
|
I am soooo tired. But... exam tomorrow. I'll do a little study tonight and wake up early for some more study.
Some exam review questions... are these answers accurate?
graph questions, define these
cycle: a path that goes back to the starting node without repeating a node
simple path: a path that doesn't repeat vertices
acyclic graph: a graph without any cycles
connecting graph: a graph where any two nodes can be connected by a path
Which kind of graph traversal is likely to use recursion: depth first
How can a graph be implemented using an adjacency list:
+ Show Spoiler +
Define a vertex object or edge object. Fill a list with those objects. Each object itself contains a list of nodes it connects to.
What kind of graphs do it work for? Weighted/directed/undirected?
+ Show Spoiler +
Well.. Is it still an "adjacency list" if it's using maps? I am guessing not. So the answer is that it works for directed or undirected graphs but not weighted graphs...? I dunno actually
A couple quick sorting algorithm questions
What kind of data works well with bucket sort: When you are sorting mostly unique elements(so they are spread out)?
What kind of data works well with counting sort: When you are working with a limited key range (counting sort will work with strings, right?)
What kind of data works with radix sort: Inputs that are limited in size and uniqueness of keys? I guess, relative to the total number of inputs ?
some threading questions
What is the difference between a thread and a process? A process handles an entire application, and a thread handles a specific part of an application. A process can be made of multiple threads, but a thread cannot be.
Describe the memory diagrom for multi-threaded java program: My answer here is probably terrible but i believe that each thread uses it's own stack, but they all share the one heap. Been a while since I've done this stuff but the stack is a stack (last in first out) and has the temporary memory stuff in it(references to the heap and primitives?). The heap has the stuff that is more permanent, and a special section for static stuff.
Examples where you might want a multi-threaded program: When you want your program to be able to handle new input while simultaneously executing code(is this answer terrible?). Example: a gui
What is a data race: when 2 threads access the same memory and at least one of them is a write.
what is a lock: ergggh. It's when you say "hey, only one thread at a time can use this block of code".
how do threads behave when encountering a synchronized block: "all other threads stop until the synchronized thread is done executing?"
what is a thread safe class: a class that can be used with multiple threads and work as expected
what is a deadlock: when 2 threads try to access the code that is currently locked to access from only the other threads (they both lock each other out).
Please critique! Thanks
|
Q) How can a graph be implemented using an adjacency list?
A) An adjacency list is a map. The key is the vertex, the value is a list of vertices.
Q) What kind of graphs does(sic) it work for? Weighted/directed/undirected?
A) Works for all.
Related Graph Questions that will deepen your understanding:
1. When do you use an adjacency list vs an adjacency matrix?
a. How much space do they use?
b. What is their running speed?
2. What is a undirected Graph?
a. How do you store this in an adjacency list?
b. What is a degree?
3. What is a directed Graph?
a. How do you store this in an adjacency list?
b. What is an indegree?
c. What is an outdegree?
4. What is a weighted Graph?
a. When would you use a weighted graph?
b. When you use a weighted directed Graph, and your run breadth first search, do you expect to find the shortest path? If not, why?
5. When do you want to use depth first search?
a. Can you name of use cases for dfs?
b. What is the running speed for dfs when using an adjacency list?
c. What is the running speed for dfs when using an adjacency matrix?
6. When do you want to use breath first search?
a. Can you name of use cases for bfs?
b. What is the running speed for bfs when using an adjacency list?
c. What is the running speed for bfs when using an adjacency matrix?
Are the questions that you came up with something you came up with or something your teacher provided? Just curious as I find definitions are not really important as knowing how and when to use these data structures.
|
graph questions, define these
cycle: a path that goes back to the starting node without repeating a node
simple path: a path that doesn't repeat vertices
acyclic graph: a graph without any cycles
connecting graph: a graph where any two nodes can be connected by a path
Choose either node or vertex. Don't mix the two words.
Your terminology is too loose.
A cycle is a path that starts and ends at the same node.
A connected graph is a graph where there is a path between any two nodes.
What is the difference between a thread and a process? A process handles an entire application, and a thread handles a specific part of an application. A process can be made of multiple threads, but a thread cannot be.
Handles doesn't make sense. A process is a group of threads associated with a program. A thread is a group of instructions run by a scheduler.
Describe the memory diagrom for multi-threaded java program: My answer here is probably terrible but i believe that each thread uses it's own stack, but they all share the one heap. Been a while since I've done this stuff but the stack is a stack (last in first out) and has the temporary memory stuff in it(references to the heap and primitives?). The heap has the stuff that is more permanent, and a special section for static stuff.
You will probably be asked this, and asked to draw it out.
Examples where you might want a multi-threaded program: When you want your program to be able to handle new input while simultaneously executing code(is this answer terrible?). Example: a gui
The idea is fine but the wording is incorrect. You'd want something closer to, "When you want your program to remain responsive while concurrently executing code". You should know what's the difference between concurrency and parallelism.
how do threads behave when encountering a synchronized block: "all other threads stop until the synchronized thread is done executing?"
Same thing here, right idea but wording. The threads will block themselves until the synchronized block thread finishes executing the synchronized block, at which point the threads will unblock according to the scheduler."
what is a lock: ergggh. It's when you say "hey, only one thread at a time can use this block of code".
More of an example than a definition. A lock is a synchronization mechanism to manage resource access in a multi-threaded environment.
|
Whenever you talk about sorting, you need to be able to answer these questions:
1. Briefly describe the sorting algorithm
2. Is it stable? If not, why?
3. What the running time?
a. O, Omega and Theta notation of running times. (Upper limit, lower limit, and between upper and lower Limit respectively)
4. How much space does it use?
5. How do you implement it in your language?
You should be able to answer the above questions for counting sorts and comparison sorts.
|
maybe it's because it's 5 in the morning and i didn't get much sleep but I feel so much love when I wake up and see you guys helping me. thanks blisse, I wrote down your definitions I'll study those on the bus to school. gonna go through some of neshs questions and then practice pseudocode / threading implementations
On November 30 2016 13:54 Neshapotamus wrote:
Q) How can a graph be implemented using an adjacency list?
A) An adjacency list is a map. The key is the vertex, the value is a list of vertices.
that makes sense I don't know why it wasn't taught to us like that
Related Graph Questions that will deepen your understanding:
1. When do you use an adjacency list vs an adjacency matrix?
a. How much space do they use?
b. What is their running speed?
adjacency matrix is a 2d array right? so this uses more memory n*n
Adjacency list uses less memory but looking up the actual edges would be a lot lower
adjacency matrix... 2 arrays... lookup should be constant time right? if you know the index
adjacency list I am not sure how quick lookup is.. I guess O(n) minimum?
2. What is a undirected Graph?
a. How do you store this in an adjacency list?
b. What is a degree?
3. What is a directed Graph?
a. How do you store this in an adjacency list?
b. What is an indegree?
c. What is an outdegree?
4. What is a weighted Graph?
a. When would you use a weighted graph?
b. When you use a weighted directed Graph, and your run breadth first search, do you expect to find the shortest path? If not, why?
5. When do you want to use depth first search?
a. Can you name of use cases for dfs?
b. What is the running speed for dfs when using an adjacency list?
c. What is the running speed for dfs when using an adjacency matrix?
6. When do you want to use breath first search?
a. Can you name of use cases for bfs?
b. What is the running speed for bfs when using an adjacency list?
c. What is the running speed for bfs when using an adjacency matrix?
Are the questions that you came up with something you came up with or something your teacher provided? Just curious as I find definitions are not really important as knowing how and when to use these data structures.
2.) It means that if there is an edge between 2 vertices you can go either direction between them. In an adjacency list, does this mean that if you map A to B, you also have to map B to A? Or is there another way this is typically handled (perhaps by addressing it in all your methods?)
I quickly looked up degree, I hadn't heard of it. But I am skipping it because i know this won't be on the test (though it looks interesting so I wish it was.
4.) weighted graph is when the edges are assigned values so that they can be compared
a.) when you need to do some meaningful comparison of paths
b.) yes, you do.
5.)You want to use a depth first search when... geeze I don't know why you would use a depth first search. I guess a criteria is that you don't care if you find the shortest path. I guess it may also technically be quicker for visiting all the vertices?
gonna stop and study pseudocode now. thank you!
|
On November 30 2016 19:56 travis wrote:maybe it's because it's 5 in the morning and i didn't get much sleep but I feel so much love when I wake up and see you guys helping me. thanks blisse, I wrote down your definitions I'll study those on the bus to school. gonna go through some of neshs questions and then practice pseudocode / threading implementations Show nested quote +On November 30 2016 13:54 Neshapotamus wrote:
Q) How can a graph be implemented using an adjacency list?
A) An adjacency list is a map. The key is the vertex, the value is a list of vertices.
that makes sense I don't know why it wasn't taught to us like that Show nested quote +
Related Graph Questions that will deepen your understanding:
1. When do you use an adjacency list vs an adjacency matrix?
a. How much space do they use?
b. What is their running speed?
adjacency matrix is a 2d array right? so this uses more memory n*n Adjacency list uses less memory but looking up the actual edges would be a lot lower adjacency matrix... 2 arrays... lookup should be constant time right? if you know the index adjacency list I am not sure how quick lookup is.. I guess O(n) minimum?
O(n) is correct, although generally speaking checking the presence of an edge is not usually a very interesting operation,
Show nested quote +
2. What is a undirected Graph?
a. How do you store this in an adjacency list?
b. What is a degree?
3. What is a directed Graph?
a. How do you store this in an adjacency list?
b. What is an indegree?
c. What is an outdegree?
4. What is a weighted Graph?
a. When would you use a weighted graph?
b. When you use a weighted directed Graph, and your run breadth first search, do you expect to find the shortest path? If not, why?
5. When do you want to use depth first search?
a. Can you name of use cases for dfs?
b. What is the running speed for dfs when using an adjacency list?
c. What is the running speed for dfs when using an adjacency matrix?
6. When do you want to use breath first search?
a. Can you name of use cases for bfs?
b. What is the running speed for bfs when using an adjacency list?
c. What is the running speed for bfs when using an adjacency matrix?
Are the questions that you came up with something you came up with or something your teacher provided? Just curious as I find definitions are not really important as knowing how and when to use these data structures.
2.) It means that if there is an edge between 2 vertices you can go either direction between them. In an adjacency list, does this mean that if you map A to B, you also have to map B to A? Or is there another way this is typically handled (perhaps by addressing it in all your methods?) I quickly looked up degree, I hadn't heard of it. But I am skipping it because i know this won't be on the test (though it looks interesting so I wish it was. 4.) weighted graph is when the edges are assigned values so that they can be compared a.) when you need to do some meaningful comparison of paths b.) yes, you do. 5.)You want to use a depth first search when... geeze I don't know why you would use a depth first search. I guess a criteria is that you don't care if you find the shortest path. I guess it may also technically be quicker for visiting all the vertices? gonna stop and study pseudocode now. thank you!
Re 4:
No. BFS will not give you the shortest path in a weighted graph. Imagine the following graph:
Nodes: (start, a, dest)
Edges:
(start, dest; 10)
(start, a; 1)
(a, dest; 1)
BFS will stop when it finds dest. In the graph above, this will give the path (start -> dest) with cost 10. It will not continue to find (start -> a -> dest) with cost 2, and thus the actual shortest path. That's why you need Dijkstra.
Re 5:
DFS is great if you have to traverse the entire tree anyway. It has a lot less overhead than BFS (especially for wide trees). Other uses are very specifically for the type of problem: if you have many good solutions, but they are hidden deep in a (wide) tree, you want to use DFS.
|
Acrofales: regaridng "shortest path", I was thinking unweighted. So like, it will find a path that contains the shortest amount of edges.
edit: Oh, my bad, I see. He was asking about weighted graphs.
|
|
|
Hyrule18968 Posts
|
|
|
On November 30 2016 23:06 Nesserev wrote:I end up watching this one every couple of months... still love it, especially the last one
Same. I start off thinking "oh, this looks funny", then realize I already watched it, and cry my eyes out laughing anyway.
|
On November 30 2016 13:54 Neshapotamus wrote:
Q) How can a graph be implemented using an adjacency list?
A) An adjacency list is a map. The key is the vertex, the value is a list of vertices.
Q) What kind of graphs does(sic) it work for? Weighted/directed/undirected?
A) Works for all.
Maybe I'm stupid, but how would you implement a weighted graph using the above definition of an adjacency list?
|
I think I did pretty well on the exam. Most of the questions were knowledge questions.
The three knowledge questions I was unsure about was the big O complexity of "average case" bubble sort, "worst case" bucket sort, but with it being specified beforehand that the range was at least as big as n and with uniform distribution, and the "worst case" of counting sort where the range was not bigger than n.
I put that average case of bubble sort was n^2 but I found it to be an odd question, because isn't it like completely up to chance?
I put that the worst case of bucket sort under those conditions was O(n)
I put that the worst case of counting sort under those conditions was O(n)
There were 3 code implementation questions.
The first was to implement bubble sort when passed (Comparable[] a)
For this I did a for loop of i = 0 incrementing to a.length -1;
And inside that I did a for loop of j = 0 going to a.length - i;
and inside that I did an if((index i compareto index i+1) > 0) { swap them }
I see now just looking at it that my inner loop should have started at j = 1. Hopefully that's only 1 point off.
The 2nd implementation was to implement heap sort when passed Comparable[] a and Heap h. It specified that our heap had add and removeSmallest methods
For this I just did a for loop through a[], and added every element to the heap. Then I did a for loop and did remove smallest for every index and put them back into the array. seems like the most straightforward thing ever.
you know what, shit. i don't think I returned the arrays in either of these.. lol. I always do stupid shit when writing the code.
anyways the last implementation had a class with an empty main method in it. I was told to "spawn 500 threads that each print 'hi'"
I made an inner class that implements runnable. inside that I put a run() { System.out.println("hi") }
Then I put in my main method I put a for loop that ran 500 times. inside it said
Thread newThread = new Thread(inner class name);
newThread.start
I don't know if this was actually how I do it, though
|
any android devs here?
when making a skype-like application, do I need a background service implemented myself that always runs and listens for incoming calls, or is there a service provided by Google that I can use to nudge my app to start when a call comes?
for example, for a step counter app, it always needs to run in background to be able to count steps even when app is not in the front, but a skype app does not need that, it just needs to be nudged when a call comes, so it shouldn't need a continuously running background service.
|
Germany2686 Posts
On December 02 2016 00:18 mantequilla wrote:any android devs here? when making a skype-like application, do I need a background service implemented myself that always runs and listens for incoming calls, or is there a service provided by Google that I can use to nudge my app to start when a call comes?for example, for a step counter app, it always needs to run in background to be able to count steps even when app is not in the front, but a skype app does not need that, it just needs to be nudged when a call comes, so it shouldn't need a continuously running background service.
Without knowing too much, you could maybe solve that by using notifications. When a user wants to call another one, the service connects to your backend and the backend pushes a notification. This may be possible with https://cloud.google.com/functions or something simliar.
But I'm not sure if this is the right way to go.
|
On December 02 2016 01:09 shz wrote:Show nested quote +On December 02 2016 00:18 mantequilla wrote:any android devs here? when making a skype-like application, do I need a background service implemented myself that always runs and listens for incoming calls, or is there a service provided by Google that I can use to nudge my app to start when a call comes?for example, for a step counter app, it always needs to run in background to be able to count steps even when app is not in the front, but a skype app does not need that, it just needs to be nudged when a call comes, so it shouldn't need a continuously running background service. Without knowing too much, you could maybe solve that by using notifications. When a user wants to call another one, the service connects to your backend and the backend pushes a notification. This may be possible with https://cloud.google.com/functions or something simliar. But I'm not sure if this is the right way to go.
You can make your app react to phone call intents.
http://stackoverflow.com/questions/15563921/how-to-detect-incoming-calls-in-an-android-device
Now this is for actual phonecalls. Not quite sure what to do for your own voip app, but my bet is you're going to rely on this:
https://developer.android.com/guide/topics/connectivity/sip.html
That's the Android SDK library for it. If that doesn't do what you need, it'll at least give you ideas of how to implement your own version.
|
|
|
|
|
|
EPT
