4661
BAN USER- 1of 3 votes
AnswersPower set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If S has n elements in it then P(s) will have 2^n elements
- 4661 in United Statespublic List<List<int>> ComputePowerSet(int[] nums) { List<List<int>> powerSet = new List<List<int>>(); if (nums == null) return powerSet; bool[] bits = new bool[nums.Length]; bool overFlowBit = false; while (!overFlowBit) { List<int> lst = new List<int>(); for (int i = 0; i < nums.Length; i++) { if (bits[i]) lst.Add(nums[i]); } //function PlusOne returns false if the end is reached i.e. 2^n if (!PlusOne(bits)) overFlowBit = true; powerSet.Add(lst); } return powerSet; } public bool PlusOne(bool[] bits) { bool carry = true; //add i i.e. true to the bits int i = bits.Length-1; while (i >= 0 && carry) { bool b = bits[i]; bits[i] = b ^ carry; carry = b & carry; i--; } //if carry is true implies reached the end i.e. 1111 + 1 = 0000, carry = 1 return !carry; }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 1of 1 vote
AnswersFind the deepest node in a binary tree:
- 4661 in United States
Example:
A
/ \
B C
/ \ / \
D E F G
\
H
Return Node ‘H’| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer - 1of 1 vote
AnswersFind the deepest node in a binary tree:
- 4661 in United States
Example:
A
/ \
B C
/ \ / \
D E F G
\
H
Return Node ‘H’| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer
Initially assume first word is the longest common prefix. check if each character in the rest of the words is exactly same, if not return the substring of first word.
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0)
return "";
String lcp = strs[0];
for(int i =0; i < lcp.length(); i++)
{
for(int j =1; j <strs.length; j++)
{
if(i >= strs[j].length() || lcp.charAt(i) != strs[j].charAt(i))
return lcp.substring(0,i);
}
}
return lcp;
}
if there is no restriction on extra space, then have a HashSet and add the values. When ever you encounter a duplicate value, return it.
- 4661 August 03, 2014