Malluce
BAN USERCan we just traverse the list from head and each time check if the node is visited? We can have something like this in the Node class
public void setVisited() {
visited = true;
}
public boolean getVisited() {
return visited;
}
then we can have a method that traverse the list that returns the first node that's visited twice
public Node traverse(LinkedList<Integer> list) {
for (Iterator<Integer> it = list.iterator(); list.hasNext();) {
if (it.next().getVisited()) {
return it.next();
} else {
it.next().setVisited();
}
}
return null;
}
I don't quite understand this question...but I'm thinking maybe we can traverse the list...when it see's a one it just remove from the list and add to tail...so eventually all the 1's will be at the end of the list. I'm not sure if we are allow to do this so please correct me if I'm wrong.
- Malluce August 14, 2012I think this should work...and the runtime is O(n). Explanations are next to the code. Any feedback will be appreciated. :)
import java.util.Vector;
public class MaxArray {
public static Vector<Integer> calcMax(int[] array) {
Vector<Integer> temp = new Vector<Integer>();
int max = 0;
int sum = 0;
for (int i = 0; i < array.length; i++) { // if value > 0 -> add to
// result
if (array[i] >= 0) {
sum += array[i];
max = sum;
temp.add(array[i]);
} else { // if value < 0 -> check conditions
if (i + 1 == array.length) { // if is last index, return without
// last index
return temp;
}
if (sum + array[i] > 0) { // if previous sum + current negative
// value > 0 -> add it
sum += array[i];
max = sum;
temp.add(array[i]);
} else { // else don't add and reset
max = 0;
sum = 0;
temp.clear();
}
}
}
return temp;
}
public static void main(String args[]) {
int[] arr = { -4, 1, 200, -10, 300, 300, 1, -1 };
System.out.println(calcMax(arr));
}
}
I'm not sure if I'm missing anything or misunderstood the question. If you just do a Binary Search, this will only find the "target", i.e., the value it's looking for, but it is not guarantee the first occurance. As someone mentioned up there that we still have to do a backward scan to make sure that is the first occurance, why can't we just do a forward scan at the first place and return the first one it sees. This way we don't have to do a Binary Search and the run time will be O(n), which is equals to O(logn)+O(n).
Please let me know if I'm wrong, maybe I misread this problem.
Can you explain your code? Also, I'm wondering how to handle the case where you can repeat the operators. The way I think about this question is that given an array of ints. I will have length - 1 place to put operators (e.g., 6_6_4_4). With total of 5 operators (Because you cannot have a bracket alone) we can find a permutation solution. So far that's all I got...I can't think of any efficient way to do this.
- Malluce August 06, 20121. Match the value with index. Create another array (let's say, Boolean indexArr) that has size of the max value of the given array. Using the given example, the size should be 8 + 1. Run through the given array (let's say, valArr), mark TRUE the indexArr[valArr[i]]. At the end you will get a array looking like this {F, T, F, F, T, T, T, T, T}.
2. Create an empty vector (let's say, resultVec).
3. Loop through valArr, if (indexArr[valArr[j]] == true) then result.add(valArr[j]), else (meaning it's not consecutive) result.clear() to start over again.
Hmm...looks like the previous answers went a little details in terms of the data structures to use. I'm not sure if I should answer this in a high level scope or low level, but here's my answer.
1. Simple UI. Smart phones are small, you cannot have a UI that requires a lot of micro control such as pressing a tiny buttons or icons. This will make people press the wrong things and can be frustrating easily.
2. (A question for the interviewer, is it a casual social network like Facebook or a professional one like LinkedIn). If it is a casual one then it needs a "wow" factor that a compete with other competitors such as Facebook. The one I could think of is a feature that shows who's around you. Of course it needs to have the users permission first. (Sorta like Google Latitude)
3. Link local contacts to the app. Add those people that are stored locally to the network. This can save a lot of time and prevent users from searching/ adding them one by one.
4. Ability to instantly upload picture or videos. It is a must for social network applications.
5. Security. This one is also important. It needs to have a secure way to delete/ prevent people from hacking the account since people can lose their phone easily or letting others borrow their phones.
Windows 8 (As the preview version, so they might change it already)
1. The Start button. Windows 8 got rid of the Start button which has been one of the MS signature for years. Although they are targeting young people that are familiar with tablets or smart phones. This made it really difficult and confusing for elderly users.
2. Ways to shut down computer. It is way too complicated to just turn off your PC. You have to tap the right side of the screen (or go to start, then tap the right), choose "settings" -> "power" -> "shut down". I know they are trying to develop a better UI for tablets (i.e., no mouse required), but if they want to release a product that will be installed on both tablets and PCs, this is something they should consider redesign it.
3. Start menu. Again, they try to have the new MS grid looking thingy. However, they have to think from a PC user's perspective. This is the most inconvenient UI I've never seen. (Who want's to scroll across your monitor to just open a program?)
4. Log in screen. Now there's a screen before the password enter screen when you start your machine. The way to get rid of that screen is to either click your keyboard or "drag that screen up with your mouse". It is really obvious to see this feature is copying the "slide to unlock" feature on a smart phone. However, is that necessary for a desktop?
5. Log in with your email account. It is nice they try to link everything together so you only need one account/ password. However, not everyone like this. Although there are ways to not use this options. It is just not intuitive enough that might get on users' nerves.
The bottom line is I feel that Windows 8 is a platform designed for tablet not PCs. They should either design a separate UI for desktop or at least having the options to customize the UI.
Is this consider "efficient"? This should be O(n)...
import java.util.ArrayList;
public class SubString {
public static String subString(String s, ArrayList<Character> deli) {
String result = "";
char[] temp = s.toCharArray();
for (int i = 0; i < temp.length; i++) {
if (!deli.contains(temp[i])) {
result += temp[i];
} else {
result += ", ";
}
}
return result;
}
public static void main(String args[]) {
ArrayList<Character> arr = new ArrayList<Character>();
arr.add('c');
arr.add('g');
System.out.println(subString("abbcdeffghujsb", arr));
}
}
well, since it doesn't say we cannot have an extra array. I will just create an extra array with the same size and initialize to 0.
Then I will scan through the given array, if it's less than 0, then put it at the front (say, a counter that starts at 0). If it's greater than 0, then put it at the end (have a counter that starts at n-1).
It should be done after the first pass since it's initialized to 0's already, so the middle ones are all 0's.
The result is
- Malluce August 21, 2012